代码之家 › 专栏 › 技术社区 › Engineer

最便宜的延期结构?

memory-layout collections data-structures performance c

Engineer · 技术社区 · 11 年前

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

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

当我从这个数组中快速随机地读取条目时,我希望最小化缓存未命中,所以我预先- malloc(sizeof(MyType) * MAX_ENTRIES) 以尽可能确保参考位置。

慷慨对价值观阵列很重要。我看过 C pseudo-generics ,但更喜欢 void * 为简单起见;然而,不确定这是否与绩效目标不符。最后,我想知道什么对性能最好。

如何实现关联阵列以提高性能?到目前为止的想法。。。

是否向关联数组传递单个 无效* 指向 malloc ed值数组,并允许它在内部使用(为此,我们需要保证匹配的键数组大小)?由于类型需要知道(?)才能索引到值数组中,所以我可以一般地这样做吗?
我有单独的吗 void * valuePtrs[] 在关联数组中,然后让这些指针指向 锦葵属植物 ed值数组?这似乎可以避免需要了解混凝土类型?
我是否使用 C伪泛型从而允许 get() 返回特定的值类型?当然,在这种情况下,唯一的好处是不必显式转换,例如。 MyStruct* value = (MyStruct*) get(...) …数组元素仍然需要解引用,因此开销相同?

而且,总的来说,上述减少意外事故的方法是否合理?

2 回复 | 直到 9 年前

Ruben Van Dijck 11 年前

在这两种情况下,性能基本相同。在第一个(void*实现)中,您需要查找值+取消引用指针。这是两个指令。
在另一个实现中,需要将索引与值的大小相乘。因此,这个实现还需要两个指令。然而,第一次实施将更容易、更干净。此外,阵列是完全透明的;用户将不需要知道阵列中的结构类型。

Engineer 11 年前

查看以下按利弊分类的解决方案(感谢鲁本帮助我思考)。。。我已经为我的用例实现了选项2和5,这有点笼统;如果您需要非常具体的一次性数据结构,我建议您选择选项4。选项3是最灵活的,但对代码来说微不足道,也是最慢的。选项4是最快的。选项5有点慢,但在阵列大小上具有灵活性,易于通用。

关联数组结构指向类型指针数组:

赞成的意见 不需要失败值,不需要显式强制转换,不需要数组的编译时大小

欺骗代价高昂的双重deref,需要通用库代码

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

赞成的意见 不需要失败值,不需要通用库代码

欺骗代价高昂的双重deref,显式强制转换 get() ,如果未使用VLA,则需要数组的编译时大小

关联数组结构指向的数组 无效* 值:

赞成的意见 没有泛型库代码,不需要数组的编译时大小

欺骗代价高昂的三重deref,显式强制转换 获取() ,需要偏移量calc,这需要显式传入sizeof值

关联数组结构保存类型化值的数组:

赞成的意见 廉价的单个deref,不需要显式强制转换,键和条目连续分配

欺骗需要泛型库代码,必须提供失败值,如果未使用VLA,则需要数组的编译时大小

关联数组结构指向类型化值的数组:

赞成的意见 不需要显式转换,灵活的数组大小

欺骗代价高昂的双解引用,需要通用库代码,必须提供失败值,如果不使用VLA,则需要数组的编译时大小