C - 对结构指针数组进行排序比直接对结构进行排序 (qsort)

Question

我正在使用标准 c 库的 qsort 函数对组织在数组中的数百万个结构进行排序。我试图通过创建具有相同长度的结构指针数组来优化性能。与我的预期相反，第二个变体的执行时间较慢:

qsort 结构数组:199sqsort 结构指针数组:204

我预计在内存中交换指针 block 的时间会比移动结构(大小 576)快。我可能有任何性能泄漏或这是已知行为吗？

Answer 1

这里还有其他问题。

通过创建指针数组，您正在对内存进行分段。标准库中的算法旨在优化连续数组的排序，因此与只有一个更大的数组相比，这样做可能会更频繁地丢失缓存。

Quicksort 特别适用于引用的局部性，因为您将样本大小减半，因此最终您将原始数组的子集按完全适合您的缓存的 block 进行排序。

作为一般规则，缓存未命中比命中慢一个数量级。因此，这个时间延迟可能足够大，足以弥补您通过不复制所有字节而获得的速度。