如何最小化struct-type的内存使用?

对于Connect Four游戏的转置表(通常是哈希表),我想有效地使用内存(以存储尽可能多的元素)。 一个表元素必须存储以下信息:

  • 锁:无符号64位
  • 移动:[0..6] – >无符号3位
  • 得分:[ – 2000..2000] – >签名12位
  • flag:VALID,UBOUND,LBOUND: – > unsigned 2 bit
  • 高度:[ – 1..42]: – >签名7位

首先我尝试了以下数据结构,需要24个字节:

struct TableEntry1 { unsigned __int64 lock; unsigned char move; short score; enum { VALID, UBOUND, LBOUND } flag; char height; }; 

重新排列元素后,它需要16个字节(我找到了这种行为的答案 ):

 struct TableEntry2 { unsigned __int64 lock; enum { VALID, UBOUND, LBOUND } flag; short score; char height; unsigned char move; }; 

我的最后一次尝试是:

 struct TableEntry3 { unsigned __int64 lock; unsigned int move:3; int score:12; enum { VALID, UBOUND, LBOUND } flag:2; int height:7; }; 

其中还需要16个字节。 是否可以更改结构,使其仅使用12字节(在32位架构上)? 为什么编译器不能使我的最后一次尝试12个字节长?

谢谢!

编辑属性lock是检测哈希冲突的唯一元素ID。

根据您实现锁定的方式,可以减小锁定字段的大小(我假设这是典型的SMP锁定SMP机器)

一种选择是减少锁的数量。 也就是说,有一个单独的更小的锁数组,并在这里锁定从您的数组元素派生的元素。 也就是说,如果您正在访问转置表元素t ,请使用lock t % locktablesize 。 锁表不必几乎与转置表一样大。

使用这种方法和您的TableEntry2字段顺序,并假设您的锁表大小是转置表的一半(可能比必要的大),您可以减少到12个字节而不会因为位移操作而失去性能 – 这种性能损失可能是非常重要,所以能够避免它总是有帮助的。

是的,因为您只有88位信息,所以可以将其打包成96位(12字节); 但是,你真的需要吗? 在极端情况下,请记住这样的打包会降低运行时性能。

如果你将这些文件存储到磁盘中,考虑到之前的微小效率会更有意义,但这是这样的情况吗? 你有没有看到内存使用方面的问题? 您需要多少内存,目前有16个字节的对象,以及它与您的计划限制有多接近? 尝试在不回答最后两个问题的情况下优化运行时内存使用还为时过早 。

除此之外,我怀疑你的编译器在结构的末尾填充,所以__int64总是在8字节边界上对齐。 考虑长度为2的这些数组:大小为12字节,__int64子对象中的至多一个可以是8字节对齐的。

您可以使用非标准构造(如Visual Studio #pragma pack)来达到12个字节:

 #pragma pack(1) struct TableEntry3 { unsigned __int64 lock; unsigned int move:3; int score:12; enum { VALID, UBOUND, LBOUND } flag:2; int height:7; }; 

在这里, sizeof(TableEntry3)为我产生12。