[D语言] qsort的尴尬

qiezi

phobos里面在stc.c.stdlib里提供了qsort，这是个传统的qsort：
void qsort(void *base, size_t nelems, size_t elemsize,int (*compare)(void *elem1, void *elem2));
它接受的比较函数是个函数指针，如果我们想使用委托就比较麻烦了，委托是对象指针和函数指针的绑定。

phobos/internal/qsort2.d里实现了一个数组排序方法：
extern (C) long _adSort(Array a, TypeInfo ti){    synchronized    {tiglobal = ti;std.c.stdlib.qsort(a.ptr, a.length, cast(size_t)ti.tsize(), &cmp);    }    return *cast(long*)(&a);}
当调用array.sort时就会使用它。它使用了一个全局变量，在比较函数里调用这个全局变量，所以能够知道是哪个ClassInfo对象，间接完成了委托功能。由于使用了全局变量，为了防止多个线程同时修改使用tiglobal，它增加了synchronized区块，代价是多个线程对多个数组排序将是顺序执行的。

当然可以避免使用这种临界区，或者是避免长时间锁住，有两种方法。

方法1是在_adSort里锁住临界区，赋值然后调用qsort，在qsort里复制全局的tiglobal以函数执行栈上，然后释放临界区，可以提高效率，也就是避免长时间锁住。带来的问题是qsort变成一个“不干净”的版本，它脏了，而且效率也比较低，临界区的开销不小。如果这样还不如给qsort和它的排序函数加一个参数呢：
void qsort(void *base, size_t nelems, size_t elemsize,int (*compare)(void *elem1, void *elem2, void* arg), void* arg);
稍干净点，一样难看。

方法2是使用线程专有存储(TSS)，我在phobos里面没有看到它使用，所以也比较麻烦，因为需要初始化和释放，修改Thread类？感觉不好。

搜索到一个帖子：
http://www.digitalmars.com/d/archives/137.html

看上去很美，不过没有实现亚，真是麻烦。。自己写线程类吧。。就为了这个接受委托的qsort。。。好像还是重写个qsort更简单一些。

phobos/internal/qsort.d提供了数组排序的不加锁版本，不过是专用的。

以上是打算调用std.c.stdlib.qsort来编写使用委托参数的qsort时遇到的麻烦。感觉还是写一个比较简单：
void qsort(T)(T* arr, size_t n, int delegate(T,T) dg) {if (!n) return;int i=0, k=n-1;T t = arr[k>>1];do {while(dg(arr[i], t) < 0)i++;while(dg(t, arr[k]) < 0)k--;if (i>k)break;if (i!= k) {T tmp = arr[i];arr[i] = arr[k];arr[k] = tmp;}k--;i++;}while(i<=k);if (i<n)qsort!(T)(arr+i, n-i, dg);if (k)qsort!(T)(arr, k+1, dg);}import std.stdio;import std.perf;void main() {int cmp(int a, int b) {return a - b;}PerformanceCounter counter = new PerformanceCounter;counter.start();for(int i=0; i<1000000; ++i) {int[] arr = [5,2,4,1,3,8,5,9,7];qsort(arr.ptr, arr.length, &cmp);}counter.stop();writefln(counter.periodCount());counter.start();for(int i=0; i<1000000; ++i) {int[] arr = [5,2,4,1,3,8,5,9,7];arr.sort;}counter.stop();writefln(counter.periodCount());}
由于没有优化，所以效率比array.sort要低一些。