[D语言] qsort的尴尬

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要低一些。

评论

2 楼 qiezi 2007-05-13  

thunk比较麻烦，最好能实现一个通用的Thunk类，主要用于一些只接受C回调函数的地方，一个简单的Thunk就可以让它接受委托了。

使用场合一，Windows窗口回调函数：

class Window {
private:
	alias Thunk!(CallType.Windows, LRESULT, HWND, UINT, WPARAM, LPARAM) ThunkType;
	ThunkType thunk;

public:
	this() {
		thunk = ThunkType(&WndProc);
	}

	void Create(){
		WNDCLASS wc;
		// ...
		wc.lpfnWndProc = thunk.proc;
		// ..
	}

	LRESULT WndProc(HWND, UINT, WPARAM, LPARAM) {
		// now we can use *this* pointer;
		return 0;
	}
}

使用场合二，qsort：

import std.c.stdlib;

void main() {
	int cmp(void*, void*){
		// ...
		return 1;
	}

	alias Thunk!(CallType.Cdecl, int, void*, void*) ThunkType;
	ThunkType thunk = ThunkType(&cmp);

	char[][] arr = ["a", "b", "c"];
	qsort(arr.ptr, arr.length, (char[]).sizeof, thunk.proc);
}

实现它是比较困难的，它是CPU架构相关的，还依赖于调用约定，依赖于OS(D调用约定在windows和linux上有所不同)。

1 楼 qiezi 2007-05-11  

这好像是一个普遍的问题，从普通的C回调函数到委托的转换，最好的办法应该是使用thunk，不知道能不能把它做成通用的。。