最便宜的引用结构？

Question

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

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

我希望在从该数组中快速随机读取条目时最大限度地减少缓存未命中，因此我预先malloc(sizeof(MyType) * MAX_ENTRIES) 以尽可能确保引用的局部性。

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

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

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

而且，总的来说，上述最小化缓存未命中的方法是否有意义？

Answer 1

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