如何提取公共字段节省内存并保留Item数组的顺序？

这是个非常典型的「重复数据压缩+顺序保留」的内存优化问题，既要砍掉重复void* a的冗余内存，又不能破坏Item的顺序灵活性，咱们可以根据你的实际场景从这几个方向入手：

1. 位字段合并：零额外开销的极致压缩 #

如果你的size_t b字段实际取值不需要用到全部64位（比如b表示内存大小，48位已经能覆盖256TB，完全够用），这绝对是最优方案：

把a的索引塞进b的高位，同时保留原数组的连续性，结构定义如下：

// 假设最多256种不同的a值，用高8位存索引；如果需要更多，可调整为16位
struct PackedItem {
    union {
        struct {
            size_t b : 56;       // 低56位存原始b值
            uint8_t a_idx : 8;   // 高8位存a的全局索引
        };
        size_t raw;              // 方便直接操作整个64位值
    };
};

// 全局存储所有不同的a值，因为a的取值极少，这个数组非常小
void* a_table[256];

优势： #

• 内存直接砍半：原Item是void* + size_t（16字节），现在每个PackedItem仅8字节，完美达到50%的节省目标。
• 内存 locality 拉满：数组还是连续的，访问效率和原数组完全一致，没有拆分或对齐问题。
• 顺序操作无额外开销：交换、插入、删除Item的逻辑和原数组完全相同，只是多了一步通过a_idx从a_table取a的操作，几乎可以忽略。

如果b确实需要用到全部64位，也可以把a_idx和b打包成一个12字节的结构体，然后通过编译器对齐优化（比如__attribute__((aligned(8)))）来保证访问效率，虽然比8字节多一点，但还是比原16字节省不少。

2. 连续相同a的批量打包 #

如果你的Item数组中存在大量连续的相同a值（比如按a分组的连续段），可以把这些连续段打包成批次：

struct ItemBatch {
    void* a;               // 该批次共享的a值
    size_t count;          // 批次内Item的数量
    size_t* b_values;      // 连续存储的所有b值
};

// 用数组或链表存储所有批次，保留整体顺序
struct ItemBatch* batches;
size_t batch_count;

优势： #

• 内存节省显著：原百万个Item占16MB，假设平均每个批次有1000个相同a，总内存仅为batch_count*(24字节) + 1000000*8字节，约8MB+极小的批次开销，接近50%的节省。
• 批量操作高效：针对相同a的Item做批量处理时，效率远高于原数组。

注意： #

如果顺序变化频繁（比如随机插入不同a的Item），需要拆分/合并批次，但因为a的取值极少，这类操作的频率和开销都在可控范围内。

3. 分层索引+连续b数组 #

如果a的分布比较零散，但取值数量依然极少，可以用分层索引的方式分离a和b：

// 记录每个a对应的连续b段
struct Segment {
    void* a;
    size_t start_idx;  // 在b_array中的起始位置
    size_t count;      // 该段的Item数量
};

// 连续存储所有b值，保证locality
size_t* b_array;
// 存储所有a对应的段，数量极少
struct Segment* segments;
size_t segment_count;

访问方式： #

要获取第n个Item的a和b，先通过二分查找找到包含n的Segment，然后从segments[i].a得到a，从b_array[n]得到b。

优势： #

• 内存开销极低：b数组占8MB，segments数组因为a的取值极少，仅占几KB到几十KB，总内存接近原数组的50%。
• b数组的locality极佳，segments因为体积小，缓存命中率几乎100%。

注意： #

如果需要频繁随机插入/删除Item，b数组的连续存储会带来一定开销，此时可以考虑用链表存储b值，但会牺牲部分locality——不过因为a的取值极少，链表的节点数量也不会带来太大问题。

内容的提问来源于stack exchange，提问作者user541686