sonic
sonic copied to clipboard
bytedance
optimize: use C implement quick sort
We want use C implement quick sort for higer performance.
The origin go implement is https://github.com/bytedance/sonic/blob/main/encoder/sort.go#L21
Hey would you assign me this task? I'm just beginning to open source and I'd like to contribute.
Currently, Sonic has implemented a fast string sorting algorithm in Golang, which can be ported to C language for further optimization of sorting time. The specific sorting algorithm can refer to the existing Golang implementation in Sonic, which has implemented the 3-way Radix Quicksort. The code can be found at https://github.com/bytedance/sonic/blob/main/encoder/sort.go#L21.
You can implement quick-sort as follows:
typedef struct MapPair{
GoString key;
void* value;
} MapPair;
// The following interface is used to swap MapPair.
void swap(MapPair* lhs, MapPair* rhs) {
MapPair temp;
temp = *lhs;
*lhs = *rhs;
*rhs = temp;
}
// Sort the MapPair array kvs by the string key, n is the length of MapPiar array.
// Implement the quick-sort algorithm in a non-recursive way.
// A Stack data structure needs to be implemented for non-recursive implementation. The max stack depth may be 4096.
// If the stack space is exceeded, return an error -1, otherwise return 0.
long quick_sort(MapPair* kvs, size_t n, Stack* stk) {
}