0

假设我有一个以unsigned int;为键的关联数组 值可以是任何固定大小的类型。有一些预定义的最大数量。的实例。

API 使用示例：MyStruct * valuePtr = get(1234);和put(6789, &myStructInstance);...基本。

当我从这个数组中快速随机读取条目时，我想尽量减少缓存未命中，所以我预先malloc(sizeof(MyType) * MAX_ENTRIES)尽可能确保引用的局部性。

泛型对于 values 数组很重要。我看过C pseudo-generics，但void *为了简单起见更喜欢；但是，不确定这是否与性能目标不一致。最终，我想知道什么最适合性能。

我应该如何实现关联数组以提高性能？到目前为止的想法...

  • 我是否将关联数组传递void *给 ed values 数组的单个指针malloc并允许它在内部使用它（为此我们需要保证匹配的键数组大小）？我可以一般地这样做吗，因为需要知道类型（？）才能索引到值数组？
  • 我是否void * valuePtrs[]在关联数组中有一个单独的，然后让这些指针指向malloced values 数组中的每个元素？这似乎可以避免需要了解具体类型？
  • 我是否使用C 伪泛型并因此允许get()返回特定的值类型？当然，在这种情况下，唯一的好处是不必显式转换，例如MyStruct* value = (MyStruct*) get(...)......数组元素仍然必须被取消引用，因此具有相同的开销？

而且，一般来说，上述最小化 cahce 未命中的方法似乎有意义吗？

4

2 回答 2

1

在这两种情况下，性能基本相同。在第一个（void* 实现）中，您需要查找值 + 取消引用指针。所以这是两条指令。
在另一个实现中，您需要将索引与值的大小相乘。所以这个实现也需要两条指令。然而，第一个实现将更容易和更干净地实现。此外，阵列是完全透明的；用户不需要知道数组中有哪些类型的结构。

于 2015-02-10T16:01:21.820 回答
1

请参阅下面分类的解决方案，根据优缺点（感谢 Ruben 帮助我思考）......我已经为我的用例实现了选项 2 和 5，这有点笼统；如果您需要一个非常具体的一次性数据结构，我推荐选项 4。选项 3 是最灵活的，但对代码来说是微不足道的，也是最慢的。选项 4 是最快的。选项 5 有点慢，但在阵列大小和一般使用方面具有灵活性。

关联数组结构指向类型化指针数组：

优点不需要失败值，不需要显式转换，不需要数组的编译时大小

成本高昂的双重 deref，需要通用库代码

关联数组结构包含void *指针数组：

优点不需要失败值，没有通用库代码

缺点昂贵的双重 deref，显式强制转换get()，如果不使用 VLA，则需要数组的编译时大小

关联数组结构指向void *值数组：

优点没有通用库代码，不需要数组的编译时大小

代价高昂的三重 deref，显式强制转换，get()需要偏移量计算，这需要显式传入的 sizeof 值

关联数组结构包含类型值数组：

优点便宜的单一 deref，不需要显式转换，键和条目连续分配

cons需要通用库代码，必须提供失败值，如果不使用 VLA，则需要数组的编译时大小

关联数组结构指向类型值数组：

不需要显式强制转换，灵活的数组大小

缺点昂贵的双重 deref，需要通用库代码，必须提供失败值，如果不使用 VLA，则需要数组的编译时大小

于 2015-02-10T18:32:35.710 回答