c++ - "factor out"公共(public)字段有什么办法可以节省空间？

Question

我有一个大数组(> 数百万)Item，其中每个 Item 都具有以下形式:

struct Item { void *a; size_t b; };

有一些不同的 a 字段——这意味着有 许多 项具有相同的 a 字段。

我想“分解”这些信息以节省大约 50% 的内存使用量。

但是，问题在于这些 Item 具有重要的顺序，并且可能会随着时间的推移而改变。因此，我不能继续为每个不同的 a 创建一个单独的 Item[]，因为那样会丢失项目之间的相对顺序。

另一方面，如果我存储 size_t index; 字段中所有项目的顺序，那么我将失去因删除 void *a; 字段。

那么有没有办法让我在这里真正节省内存，或者没有？

(注意:我已经可以想到例如使用 unsigned char 为 a 索引一个小数组，但我想知道是否有更好的方法。那将要求我要么使用未对齐的内存，要么将每个 Item[] 分成两部分，这对内存局部性来说不是很好，所以我更喜欢其他东西。)

Answer 1

(Note: I can already think of e.g. using an unsigned char for a to index into a small array, but I'm wondering if there's a better way.)

这种想法是正确的，但并不是那么简单，因为您会遇到一些讨厌的对齐/填充问题，这些问题会抵消您的内存增益。

此时，当您开始尝试抓取像这样的结构的最后几个字节时，您可能会想要使用位域。

#define A_INDEX_BITS 3
struct Item { 
  size_t a_index : A_INDEX_BITS; 
  size_t b       : (sizeof(size_t) * CHAR_BIT) - A_INDEX_BITS; 
};

请注意，这将限制可用于 b 的位数，但在现代平台上，sizeof(size_t) 为 8，从中剥离 3-4 位很少成为问题。