C - 排序结构的指针数组比直接排序结构更慢(qsort)

Question

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

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

我期望在内存中交换指针块的时间比移动结构更快(大小为576).我可能有任何性能泄漏或这是一个已知的行为？

Answer 1

这里还有其他问题.

通过创建指针数组,您可以分割内存.标准库中的算法旨在优化连续数组的排序,因此,通过这样做,您可能比使用更大的数组更频繁地丢失缓存.

Quicksort特别适用于引用的局部性,因为您将样本大小减半,因此最终您将以块的形式对原始数组的子集进行排序,这些块可以完全适合您的缓存.

作为一般规则,缓存未命中比命中慢一个数量级.因此,这个时间延迟可能非常重要,可以通过不复制所有字节来弥补您获得的速度.