如何推理性能影响（为48位整数更改为更紧凑的表示）？

Question

与此问题类似，x86上成功的未对齐访问的实际效果如何？

我们有一个应用程序，它搜索关键是48位整数的大量结构数组。我们一直使用64位类型来表示48位整数，前提是空间便宜并且对齐可以提高性能。

数组使用的空间很大。所以我很好奇切换到紧凑表示会有什么效果。

这是一个性能问题，所以关键的答案是度量。同时也要承认，为您的使用模式选择最佳算法对性能的影响最大。

问题是，在测量之前，我们可以假设什么？

有效改变：

struct Entry
{
   uint64_t key;
   int32_t value1;
   int32_t value2;   
};
std::vector<Entry> foobar;

要说：

struct uint48
{
   uint16_t v[3];
}

struct Entry
{
   uint48 key;
   int32_t value1;
   int32_t value2;   
} __attribute__((packed));
std::vector<Entry> snafu;

在实践中进行此更改将节省大量内存。我很好奇，我能期望它在实践中对表现有什么影响。

确定的唯一方法当然是测量，但这需要付出不小的努力。

对于预期的效果，我可以做出什么解释？

这是我的出发点：

• 搜索结构由许多基于48位密钥操作的操作组成（主要是汉明距离而不是相等）。
• 该结构始终保持只读。
• 有启发式方法意味着连续搜索应该使用本地数据，并希望利用CPU缓存。
• 假设一个基于x86_64的架构至少具有标准附加组件，如SSE
• 在Linux上使用g

一方面我们有：

>

当前，条目的宽度为128位=16字节。

如果存在这样的情况，将其减少到14将消除任何16字节对齐的好处。

提取48位整数会变得更昂贵。

uint64_tfoo=ntry.key

另一方面：

>

减小每个条目的大小会增加所需数据在缓存中的可能性。

整个数据集太大，无法完全放入任何缓存。

减少内存使用的成本很可能会降低性能，但有没有一种方法可以估计它，从而证明进行实际实验是合理的？

例如，如果我们预计性能会损失50%，那么可能根本不值得尝试。另一方面，如果它可能更接近5%，那么这可能是值得做的。

无论如何，我希望在未来进行实验，但由于其他promise，这可能是一个相当遥远的未来。

我认为这是一个有趣的问题，就你应该如何看待这些问题而言。

优化是一个从算法到手工组装的兔子洞。你可以做很多事情，路上也有很多陷阱。我从算法方面对它很熟悉，但当涉及到如何理解a更改对CPU上运行的影响时，我就不那么熟悉了。

通常，我们通过添加内核和RAM以及具有更多内核的节点来扩展，因为这比为不同商品硬件优化/重新编译的程序员时间和支持成本都要便宜。但这项练习很有教育意义，而且可能会从低垂的果实中获得许多好处。

这个问题最初使用了（此处）为uint48建议的另一个定义[https://stackoverflow.com/a/26198075/1569204]:

struct uint48
{
  unsigned long long v:48;
} __attribute__((packed));

有人指出，这实际上可能不会给出6字节的布局。这被保留在这里，否则引用它的答案就没有意义了。

到目前为止，答案建议从AoS布局切换到SoA布局。这确实是一个很好的观点。这可能是一个比我单独讨论的更好的改变。从这个意义上说，他们回答了性能问题。这也鼓励了更多的思考和问自己一些更好的问题。

到目前为止还没有包括的是关于48位类型的最佳布局和对齐的实际效果的讨论。

考虑：

uint64_t key:48;

int64_t x = key;

vs.

struct uint48
{
   int32_t msb;
   int16_t lsb;
};
uint48 key;
int64_t x = (int64_t)key.msb + (int64_t)key.lsb;

vs.

struct uint48
{
   int8_t v[6];
};
uint48 key;

等。

与其他考虑因素相比，对齐有多重要？

Answer 1

我希望有一个值得考虑的选择

struct Keys {
    uint32_t keys_msb_bits[N];
    uint16_t keys_lsb_bits[N];
};
struct Values {
    int32_t value1[N];
    int32_t value2[N];
};

如果N==8，则每个结构不会严重对齐。值可以分别与缓存线边界对齐，而键可以对齐16个字节（适用于ARM Neon、Intel直至SSE4.1）。

这当然取决于这些数据的内存访问模式，现在的地址计算有点复杂，但它也有机会使用SIMD进行搜索/替换。

Answer 2

struct uint48
{
  unsigned long long v:48;
} __attribute__((packed));

不要这样做。它告诉编译器对象可能只是字节对齐的，所以它通常必须使用未对齐的加载来访问它。你可能最好有三个uint16_t，编译器至少可以假设它们是两个字节对齐的。或者告诉编译器它是两个字节对齐的，而不是打包的。（在某些情况下，根据缓存模式和其他因素，保留一个uint32_t数组和另一个uint16_t数组甚至可能是有益的，然后编译器可以用适合该类型的一条指令加载每个数组。）

假设采用基于x86\u 64的体系结构。

这不足以衡量绩效。该体系结构中有许多不同的处理器型号，它们可以在不同的系统中进行不同的配置，不同的操作系统对它们应用不同的设置。

如果存在这样的情况，将其减少到14将消除任何16字节对齐的好处。

某些x86-64处理器上肯定有16字节对齐的好处。从你问题中的信息来看，你是否在使用其中的任何一种都是未知的。如果在16字节结构中有不同的字段，我怀疑这会有多大好处。（统一字段可能会受益于各种SIMD功能，如SSE2、AVX等。）

减小每个条目的大小会增加所需数据在缓存中的机会。

通过仔细考虑使用模式和数据布局以及基于这些考虑的后续算法重新设计，缓存行为通常可以得到更好的改善，而不是通过稍微减少使用的数据大小。

减少内存使用的成本很可能会降低性能，但有没有一种方法可以估计它，从而证明进行实际实验是合理的？

是的，如果您有足够的关于算法的数据访问模式、正在使用的硬件等的信息。张贴的问题中没有此类信息。

Answer 3

您对C和C“位域”功能的理解非常缺乏

您的结构uint48说“给我分配一个无符号long long。现在使用48位留下16位填充将v放入其中。”。

一组位域成员总是被填充到其基本类型的大小。（sizeof（uint48））

只有在同一结构中有多个具有相同基本类型的非静态位字段，它们被声明为彼此相邻，并且多个相邻字段符合位字段的基本类型时，才能节省内存。

您的更改对内存消耗没有影响。

要提高搜索性能，请使用更好的搜索算法

您提到您正在搜索基于汉明距离的不精确匹配。您需要对结构进行排序，并实现利用该排序执行修剪的查找。

如果您正在寻找汉明距为4或更少的匹配项，并且前16位中有6位不同，您应该跳过整个块，因为无论接下来的32位中出现什么值，您都永远不会得到4的总距离。所以您可以修剪整个子空间而不是搜索它。

基数树可能是一种合适的结构（可能不是最优的，但与现有结构相比有很大的改进），因为前缀距离为树的分支中更深的距离提供了一个下限，允许您跳过（修剪）树的大部分。

这种数据结构包含了@krlmlr关于将关联值从键列表中移开的出色观点，因为在基数树中，键实际上隐含在树结构中，并且您永远不会到达存储叶值的最后一级（将它们带入缓存），直到您已经处理了键并验证您的条件是否满足。

如果您不知道不匹配的允许权重，那么仍然应该使用一些分支和绑定技术。