今天,又重新看了一下GLIBC中快速排序的源码~ 又多了一些不同的理解,为什么这篇文章迟迟没有

发布,也是因为对于源码没有深刻的理解,感觉很多点都不明白.今天就找了些资料,仔细揣摩了一遍源

码,索性就写出来,有不到之处,请批评指正~

 

之前一直都是以为GLIBC中的源码应该会花费大量的代码做通用处理,但是今天重新浏览之后,发现自己

错了,哎~  不过还是蛮高兴的,毕竟还年轻嘛~

 

其实,GLIBC中快速排序的源码重点在榨取CPU的性能,提高快排的执行效率.为什么说是榨取呢? 因为

源码真的将利用效率做到了极致.

1   /* For large object sizes use indirect sorting.  */2   if (s > 32)3     size = 2 * n * sizeof (void *) + s; // 这里为什么要计算2N+1的空间?

 

 看到前面的英文注释了吧,源码中对于快速排序也做了不同的分类,采用不同的方式.意思就是:如果单个元素

长度大于32BYTE,那么就视为大对象,采用间接排序.至于间接排序是什么意思?下面再说.

 

不知道有没有同学会不理解为什么会需要sizeof(void *).这个问题嘛,只能说脑袋总是有闹别扭的时候.

浪费一点时间回头看看qsort_r函数声明.

1 void2 qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)

 

 可以很清楚的看到,将目标数组参数的类型声明为void *,所以这里是需要计算需要的存储空间大小.然后联系

源码中采用的两种排序方式,间接快速排序和直接快速排序,如果只是单凭元素大小来选择排序方式,那是不可靠

的,为什么? 因为即使元素占用空间很大,但是数量很少还是不能采用间接排序,所以判断需要排序的目标数组的

长度才是最可靠地依据.(修正,其实这里指的是指针的长度,看没看出错误呢?广大同学们. -,-)

1   if (size < 1024)2     /* The temporary array is small, so put it on the stack.  */3     p.t = __alloca (size);

所以呢,上面的代码就可以说明一切了.

 

__alloca是什么？我们看看哈~ 它是一个宏:

1 #ifdef    __GNUC__2 # define __alloca(size)    __builtin_alloca (size)3 #endif /* GCC.  */

 这是GCC特有的一个函数实现,查阅了很多的资料.手册中说_builtin_alloca是一个私有的实现版本.

其他的并没有多作说明. 其他的资料暂时也没有找到,知道的可以告诉我哈~

 

这几段代码告诉我们,若目标数组长度小于1024BYTE,那么就使用直接快速排序,否则就是用间接快速排序.

1       if (size / pagesize > (size_t) phys_pages)2     {3       _quicksort (b, n, s, cmp, arg);4       return;5     }

 

先跳过前面的几段代码,直接看看上面的这段代码,这里调用了直接快速排序,我们先不关心直接排序的实现,

先看看为什么会调用直接排序.注意一下条件. 需要弄懂这个条件,就需要看前面一段忽略的代码.

1       /* We should avoid allocating too much memory since this might 2      have to be backed up by swap space.  */ 3       static long int phys_pages; 4       static int pagesize; 5  6       if (pagesize == 0) 7     { 8       phys_pages = __sysconf (_SC_PHYS_PAGES); 9 10       if (phys_pages == -1)11         /* Error while determining the memory size.  So let's12            assume there is enough memory.  Otherwise the13            implementer should provide a complete implementation of14            the `sysconf' function.  */15         phys_pages = (long int) (~0ul >> 1);16 17       /* The following determines that we will never use more than18          a quarter of the physical memory.  */19       phys_pages /= 4;20 21       /* Make sure phys_pages is written to memory.  */22       atomic_write_barrier ();23 24       pagesize = __sysconf (_SC_PAGESIZE)

 

 这段代码涉及到的函数比较的复杂,在本文中将不做详细解释,简单解释一下.这段代码是获取系统的

 物理可用内存参数. 最主要的是避免使用交换空间,因为那样做会降低排序的效率.

 

简单解释了一下这段代码,前面的条件也就清晰明了了,如果系统的可用内存够支配,那么就从堆分配

内存采用间接快速排序.如果不够用了,那么就只好直接快速排序了.也就是直接调用_quicksort函数.

1       int save = errno; 2       tmp = malloc (size); 3       __set_errno (save); 4       if (tmp == NULL) 5     { 6       /* Couldn't get space, so use the slower algorithm 7          that doesn't need a temporary array.  */ 8       _quicksort (b, n, s, cmp, arg); 9       return;10     }11       p.t = tmp;

使用malloc函数从堆分配所需内存空间,如果无法分配(无法分配的原因很多),那么依然采用间接快速排序.

如果分配了内存,那么将空间地址指针放入一个结构体中.看看这个结构体:

1 struct msort_param2 {3   size_t s;4   size_t var;5   __compar_d_fn_t cmp;6   void *arg;7   char *t;8 };

1   p.s = s;2   p.var = 4;3   p.cmp = cmp;4   p.arg = arg;

 

下面这段初始化的源码,初始化p中的成员. 对照着前面的结构体声明,各个参数的类型.

1 if (s > 32)  // 如果单个元素长度>32 2     { 3       /* Indirect sorting.  */ 4       char *ip = (char *) b; // 获取目标数组的地址. 5       void **tp = (void **) (p.t + n * sizeof (void *)); // 获取排序空间第N+1位置指针. 6       void **t = tp; 7       void *tmp_storage = (void *) (tp + n); // 排序空间的最后一个位置,申请的空间大小是2N+1.

8  // 注意这里为什么要使用void *,因为间接排序是对指针进行排序,而不是针对元素. 9       while ((void *) t < tmp_storage)10     {11       *t++ = ip; // 拷贝指针.12       ip += s;   // 移动到下一个指针. 因为类型是字节,所以要按照元素长度进行移位.13     }14       p.s = sizeof (void *);15       p.var = 3;16       msort_with_tmp (&p, p.t + n * sizeof (void *), n);17 18       /* tp[0] .. tp[n - 1] is now sorted, copy around entries of19      the original array.  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */20       char *kp;21       size_t i;22       for (i = 0, ip = (char *) b; i < n; i++, ip += s)23     if ((kp = tp[i]) != ip)24       {25         size_t j = i;26         char *jp = ip;27         memcpy (tmp_storage, ip, s);28 29         do30           {31         size_t k = (kp - (char *) b) / s;32         tp[j] = jp;33         memcpy (jp, kp, s);34         j = k;35         jp = kp;36         kp = tp[k];37           }38         while (kp != ip);39 40         tp[j] = jp;41         memcpy (jp, tmp_storage, s);42       }43     }44   else45     {
               // 下面的源码就没什么了,主要是依照条件初始化p.var46       if ((s & (sizeof (uint32_t) - 1)) == 047       && ((char *) b - (char *) 0) % __alignof__ (uint32_t) == 0)48     {49       if (s == sizeof (uint32_t))50         p.var = 0;  51       else if (s == sizeof (uint64_t)52            && ((char *) b - (char *) 0) % __alignof__ (uint64_t) == 0)53         p.var = 1;54       else if ((s & (sizeof (unsigned long) - 1)) == 055            && ((char *) b - (char *) 0)56               % __alignof__ (unsigned long) == 0)57         p.var = 2;58     }59       msort_with_tmp (&p, b, n);60     }61   free (tmp);

上面的注释中说明了,很大一段代码都是依照条件去初始化p中var的值,在源码中,可以看到,

p.var有四个值,分别是0,1,2,3. 分别代表什么意思呢? 要到msort_with_tmp函数的源码中

去看看才知道.同样,想要搞明白,间接快速排序时如何做的,也要进去看看.

 

下面的分析,留在下一篇文章中再续吧,有事处理一下~