时间戳

首页 > 解决方案 > 如何提高使用 void** 实现的动态数组的性能？

c - 如何提高使用 void** 实现的动态数组的性能？

问题描述

我需要实现一个可以使用任何类型的简单动态数组。

现在我的void**实现比int*直接使用慢约 50%：

#define N 1000000000

// Takes ~6 seconds
void** a = malloc(sizeof(void*) * N);
for (int i =0; i < N; i++) {
        *(int*)(&a[i]) = i;

}
printf("%d\n", *(int*)&a[N-1]);

// Takes ~3 seconds
int* b = malloc(sizeof(int) * N) ;
for (int i =0; i < N; i++) {
        b[i] = i;
}
printf("%d\n", b[N-1]);

我不是 C 专家。有一个更好的方法吗？

谢谢

编辑

看起来使用void**是个坏主意。有没有办法实现这个void*？

以下是它在 Go 中的实现方式：

type slice struct {
        array unsafe.Pointer
        len   int
        cap   int
}

我想做类似的事情。

编辑2

我设法用void*.

解决方案非常简单：

 void* a = malloc(sizeof(int) * N);
 for (int i = 0; i < N; i++) {
    ((int*)a)[i] = i;
 }
 printf("%d\n", ((int*)a)[N-1]);

现在的表现是一样的。

标签： cdynamic-arraysvoid-pointers

解决方案

您的两个替代方案并不相似。在第二个有效的情况下，您分配的空间足以容纳N整数，然后将值分配给int该空间的 -size 成员。然而，在第一个中，您分配了足够大的空间以容纳N指向 void 的指针，然后，在不初始化这些指针的情况下，您尝试将值分配给它们指向的对象。即使这些指针已被初始化为指向int对象，也存在额外的间接级别。

从某种意义上说，您的第一个代码可以更正，如下所示：

void** a = malloc(sizeof(void*) * N);
for (int i =0; i < N; i++) {
        a[i] = (void *) i;

}
printf("%d\n", (int) a[N-1]);

这依赖于 C 允许指针和整数类型之间的转换（尽管不一定没有数据丢失）这一事实，并注意只有一个间接级别（数组索引），而不是两个。

由于您实现第一个替代方案的行为未定义，我们只能推测它在实践中运行速度较慢的原因。但是，如果我们假设一个简单的实现，那么您观察到的这种性能损失可能是由于所有数组写入的缓存局部性不佳造成的。

推荐阅读