首次尝试更好的
下一次尝试:
我正在用。raw文件中的RGB数据排序1000多万个uint64_t，我的C程序时间的79%花在qsort上。我正在寻找一个更快的排序为这个特定的数据类型。
作为RAW图形数据，数字是非常随机的，大约80%是唯一的。不能期望部分排序或运行已排序的数据。uint64_t内的4个uint16_t s分别为R、G、B和0(可能有少量的计数<= ~20)。
我有最简单的比较函数，我能想到使用unsigned long long s(你不能只是减去它们):
qsort(hpidx, num_pix, sizeof(uint64_t), comp_uint64);
...
int comp_uint64(const void *a, const void *b) {
if(*((uint64_t *)a) > *((uint64_t *)b)) return(+1);
if(*((uint64_t *)a) < *((uint64_t *)b)) return(-1);
return(0);
} // End Comp_uint64().
有一个非常有趣的"编程谜题"代码Golf"在StackExchange上，但他们使用float s。然后是QSort, RecQuick, heap, stooge, tree, radix…
swenson/sort看起来很有趣，但对我的数据类型uint64_t没有(明显的)支持。还有"快速排序"时间是最好的。一些消息来源说qsort系统可以是任何东西，不一定是"快速排序"。
c++的排序绕过了void指针的泛型转换，实现了比C的性能的巨大改进。必须有一种优化的方法来通过64位处理器以warp速度猛冲u8。
系统/编译器信息:
我目前正在使用GCC与草莓Perl
gcc version 4.9.2 (x86_64-posix-sjlj, built by strawberryperl.com
Intel 2700K Sandy Bridge CPU, 32GB DDR3
windows 7/64 pro
gcc -D__USE_MINGW_ANSI_STDIO -O4 -ffast-math -m64 -Ofast -march=corei7-avx -mtune=corei7 -Ic:/bin/xxHash-master -Lc:/bin/xxHash-master c:/bin/stddev.c -o c:/bin/stddev.g6.exe
首次尝试更好的qsort, QSORT() !
尝试使用Michael Tokarev的inline qsort .
"READY-TO-USE" ?来自qsort.h文档
-----------------------------
* Several ready-to-use examples:
*
* Sorting array of integers:
* void int_qsort(int *arr, unsigned n) {
* #define int_lt(a,b) ((*a)<(*b))
* QSORT(int, arr, n, int_lt);
--------------------------------
Change from type "int" to "uint64_t"
compile error on TYPE???
c:/bin/bpbfct.c:586:8: error: expected expression before 'uint64_t'
QSORT(uint64_t, hpidx, num_pix, islt);
我找不到一个真实的，编译的，工作的示例程序，只是用"一般概念"的注释
#define QSORT_TYPE uint64_t
#define islt(a,b) ((*a)<(*b))
uint64_t *QSORT_BASE;
int QSORT_NELT;
hpidx=(uint64_t *) calloc(num_pix+2, sizeof(uint64_t)); // Hash . PIDX
QSORT_BASE = hpidx;
QSORT_NELT = num_pix; // QSORT_LT is function QSORT_LT()
QSORT(uint64_t, hpidx, num_pix, islt);
//QSORT(uint64_t *, hpidx, num_pix, QSORT_LT); // QSORT_LT mal-defined?
//qsort(hpidx, num_pix, sizeof(uint64_t), comp_uint64); // << WORKS
"ready-to-use"示例使用int, char *和struct elt类型。uint64_t不是一种类型吗??试试long long
QSORT(long long, hpidx, num_pix, islt);
c:/bin/bpbfct.c:586:8: error: expected expression before 'long'
QSORT(long long, hpidx, num_pix, islt);
下一次尝试:RADIXSORT:
结果:RADIX_SORT是RADICAL!
I:br3pf.249465>grep "Event" bb12.log | grep -i Sort
<< 1.40 sec average
4) Time=1.411 sec = 49.61%, Event RADIX_SORT , hits=1
4) Time=1.396 sec = 49.13%, Event RADIX_SORT , hits=1
4) Time=1.392 sec = 49.15%, Event RADIX_SORT , hits=1
16) Time=1.414 sec = 49.12%, Event RADIX_SORT , hits=1
I:br3pf.249465>grep "Event" bb11.log | grep -i Sort
<< 5.525 sec average = 3.95 time slower
4) Time=5.538 sec = 86.34%, Event QSort , hits=1
4) Time=5.519 sec = 79.41%, Event QSort , hits=1
4) Time=5.519 sec = 79.02%, Event QSort , hits=1
4) Time=5.563 sec = 79.49%, Event QSort , hits=1
4) Time=5.684 sec = 79.83%, Event QSort , hits=1
4) Time=5.509 sec = 79.30%, Event QSort , hits=1
比qsort开箱即用的排序快3.94倍!
而且，更重要的是，有实际的，工作的代码，而不是一些大师给出的你需要的80%的代码，他们认为你知道他们所知道的一切，可以填写其他的20%。
神奇的解决方案!谢谢路易·利玛窦!
我将使用基数排序与8位基数。对于64位值，优化好的基数排序必须迭代列表9次(1次用于预先计算计数和偏移量，8次用于64位/8位)。9*N的时间和2*N的空间(使用阴影数组)。
优化后的基数排序是这样的
typedef union {
struct {
uint32_t c8[256];
uint32_t c7[256];
uint32_t c6[256];
uint32_t c5[256];
uint32_t c4[256];
uint32_t c3[256];
uint32_t c2[256];
uint32_t c1[256];
};
uint32_t counts[256 * 8];
} rscounts_t;
uint64_t * radixSort(uint64_t * array, uint32_t size) {
rscounts_t counts;
memset(&counts, 0, 256 * 8 * sizeof(uint32_t));
uint64_t * cpy = (uint64_t *)malloc(size * sizeof(uint64_t));
uint32_t o8=0, o7=0, o6=0, o5=0, o4=0, o3=0, o2=0, o1=0;
uint32_t t8, t7, t6, t5, t4, t3, t2, t1;
uint32_t x;
// calculate counts
for(x = 0; x < size; x++) {
t8 = array[x] & 0xff;
t7 = (array[x] >> 8) & 0xff;
t6 = (array[x] >> 16) & 0xff;
t5 = (array[x] >> 24) & 0xff;
t4 = (array[x] >> 32) & 0xff;
t3 = (array[x] >> 40) & 0xff;
t2 = (array[x] >> 48) & 0xff;
t1 = (array[x] >> 56) & 0xff;
counts.c8[t8]++;
counts.c7[t7]++;
counts.c6[t6]++;
counts.c5[t5]++;
counts.c4[t4]++;
counts.c3[t3]++;
counts.c2[t2]++;
counts.c1[t1]++;
}
// convert counts to offsets
for(x = 0; x < 256; x++) {
t8 = o8 + counts.c8[x];
t7 = o7 + counts.c7[x];
t6 = o6 + counts.c6[x];
t5 = o5 + counts.c5[x];
t4 = o4 + counts.c4[x];
t3 = o3 + counts.c3[x];
t2 = o2 + counts.c2[x];
t1 = o1 + counts.c1[x];
counts.c8[x] = o8;
counts.c7[x] = o7;
counts.c6[x] = o6;
counts.c5[x] = o5;
counts.c4[x] = o4;
counts.c3[x] = o3;
counts.c2[x] = o2;
counts.c1[x] = o1;
o8 = t8;
o7 = t7;
o6 = t6;
o5 = t5;
o4 = t4;
o3 = t3;
o2 = t2;
o1 = t1;
}
// radix
for(x = 0; x < size; x++) {
t8 = array[x] & 0xff;
cpy[counts.c8[t8]] = array[x];
counts.c8[t8]++;
}
for(x = 0; x < size; x++) {
t7 = (cpy[x] >> 8) & 0xff;
array[counts.c7[t7]] = cpy[x];
counts.c7[t7]++;
}
for(x = 0; x < size; x++) {
t6 = (array[x] >> 16) & 0xff;
cpy[counts.c6[t6]] = array[x];
counts.c6[t6]++;
}
for(x = 0; x < size; x++) {
t5 = (cpy[x] >> 24) & 0xff;
array[counts.c5[t5]] = cpy[x];
counts.c5[t5]++;
}
for(x = 0; x < size; x++) {
t4 = (array[x] >> 32) & 0xff;
cpy[counts.c4[t4]] = array[x];
counts.c4[t4]++;
}
for(x = 0; x < size; x++) {
t3 = (cpy[x] >> 40) & 0xff;
array[counts.c3[t3]] = cpy[x];
counts.c3[t3]++;
}
for(x = 0; x < size; x++) {
t2 = (array[x] >> 48) & 0xff;
cpy[counts.c2[t2]] = array[x];
counts.c2[t2]++;
}
for(x = 0; x < size; x++) {
t1 = (cpy[x] >> 56) & 0xff;
array[counts.c1[t1]] = cpy[x];
counts.c1[t1]++;
}
free(cpy);
return array;
}
EDIT这个实现是基于JavaScript版本最快的方式来排序JavaScript中的32位有符号整数数组?
这是用于C基数排序的IDEONE http://ideone.com/JHI0d9
我看到了一些选项，大致按最简单到最难的顺序排列。
- 使用
-flto开关使能链路时间优化。这个可以让编译器内联比较函数。不去尝试太容易了。 - 如果LTO没有效果，你可以使用内联qsort实现，比如Michael Tokarev的内联qsort。这一页建议了2倍的改进，同样仅仅是因为编译器内联比较函数的能力。
- 使用c++
std::sort。我知道您的代码是用C编写的，但是您可以编写一个只排序并提供C接口的小模块。你已经在使用一个支持c++的工具链了。 试试swenson/sort的库。它实现了许多算法，因此您可以使用最适合您的数据的算法。它似乎是可内联的，他们声称比 - 找到另一个排序库。可以做路易斯基数排序的东西是一个好建议。
qsort快。注意，您也可以对单个分支而不是两个分支进行比较。只要找出哪个更大，然后相减。
对于某些编译器/平台，下面的代码是无分支的，速度更快，尽管与OP的原始代码没有太大的不同。
int comp_uint64_b(const void *a, const void *b) {
return
(*((uint64_t *)a) > *((uint64_t *)b)) -
(*((uint64_t *)a) < *((uint64_t *)b));
}
也许有些?:而不是if会让事情更快一些。