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

Question

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

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

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

Answer 1

这里还有其他问题。

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

Quicksort 特别适用于参考位置，因为您将样本大小减半，因此最终您将原始数组的子集按完全适合缓存的块进行排序。

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

Answer 2

快速排序的工作方式是通过将相邻元素靠得更近来逐渐重新组织数组。这允许数据缓存在算法越接近最终结果时更有效地工作。

如果您转换为指针数组，那么数据访问可能会变慢，因为结构保持其 "unsorted" 顺序，而它们的指针正在排序。但是，比较这些结构需要遵循指向其 "unsorted" 实例的指针，这可能会导致数据缓存未命中。

要实现您想要的效果，您可以为数据创建索引结构。索引结构将保存排序键（或其副本）。

struct index_type {
    key_type key;
    data_type *data;
};

现在，您将对 index_type 数组而不是指向 data_type 的指针数组进行排序。由于密钥存储在数组本身中，因此可以避免跟随指向 "unsorted" 结构的指针的问题。

Answer 3

我使用这个结构进行了快速完整性检查（当 int 是 32 位时它的大小为 576）

struct test
{
    int value;
    char data[572];
};

我用这段代码初始化了一个包含 100 万个结构的动态分配数组

for ( int i = 0; i < count; i++ )
{
    array[i].value = rand();
    for ( int j = 0; j < 572; j++ )
        array[i].data[j] = rand();
}

我用这段代码对数组进行了排序

int compare( const void *ptr1, const void *ptr2 )
{
    struct test *tptr1 = (struct test *)ptr1;
    struct test *tptr2 = (struct test *)ptr2;
    return tptr1->value - tptr2->value;
}

int main( void )
{
    int count = 1000000;
    ...
    qsort( array, count, sizeof(struct test), compare );
    ...
}

数组初始化用时4.3秒，数组排序用时0.9秒。

然后我修改了代码以创建指向结构的指针数组，并对指针数组进行排序。初始化时间还是4.3秒（大部分初始化时间是因为调用了rand()5亿次）。对指针数组进行排序需要 0.4 秒。对指针数组进行排序比直接对结构体数组排序快两倍多。

所以我的结论是您的代码存在一些与 qsort.

无关的巨大低效问题

Answer 4

一般来说，哪个更快取决于结构的大小。对于与指针大小相同的结构，那么很明显，对结构进行排序比对结构指针进行排序要快。随着结构大小的增加，将达到相反的情况（想象一下对 1 MB 结构的数组进行排序：您将大部分时间花在 memcopy() 上）。该点的确切位置取决于代码控制之外的事物（缓存结构、缓存大小等）。如果这对您很重要，那么您最好进行实验和衡量。

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

C - Is sorting an array of pointers of structs slower than sorting the structs directly (qsort)

c

arrays

struct

pointers

qsort