3

我需要一个 2 位数组，我根本不关心节省内存，但我关心的是尽量减少缓存未命中和最大限度地提高缓存效率。使用 bool 数组将使用 4 倍的内存，这意味着对于缓存中每个可用的数据块，将有 3 个未使用。所以从技术上讲，如果我使用位域，我可以获得 3 倍更好的缓存一致性。

计划是将其实现为一个字节数组，分为 4 个相等的位域，并使用 div 函数能够获得整数商和余数，可能在单个时钟内，并使用它们访问正确的索引和右位域。

我需要的数组大约有 10000 个元素长，因此它将产生更密集的打包数据，使用 2 个实际位将允许整个数组适合 L1 缓存，而使用字节数组这是不可能的。

所以我的问题是，是否有人可以告诉我这在面向性能的任务中是否是一个好主意，所以我知道是否值得继续实施 2 位数组？当然，最好的了解方法是分析，但提前提供的任何信息都可能有用，我们将不胜感激。

4

2 回答 2

5

在现代处理器上具有 10000 个元素，它应该以字节（10KB）的形式很好地适应内存，所以我不会太担心它，除非你希望它在一些非常小的微处理器上运行，并且缓存要小得多比现代 CPU 具有的典型 16-32KB L1 缓存。

当然，如果您认为从性能角度来看这是代码的重要部分，您可能很想用不同的解决方案测试性能[根据您在开始优化之前已经完成的分析来衡量，对吗？] .

于 2013-01-20T18:28:28.497 回答
2

我不清楚这是否会带来性能提升。访问每个字段需要几条指令(data[i / 4] >> 2 * (i % 4)) & 0x03（执行时间的额外成本是大于还是小于缓存的差异很难说；你必须配置文件才能确切知道。

如果您可以组织您的算法一次处理一个字节（甚至一个字），那么访问成本可能会低得多。遍历整个数组，例如：

for ( int i = 0; i < 10000; i += 4 ) {
    unsigned char w1 = data[ i / 4 ];
    for ( int j = 0; j < 4; ++ j ) {
        unsigned char w2 = w1 & 0x03;
        //  w2 is entry i + j...
        w1 >>= 2;
    }
}

可能会产生重大影响。大多数编译器将能够将w1和保存w2在寄存器中，这意味着您将只有 1/4 的内存访问。使用unsigned int` 打包可能会更快。

于 2013-01-20T18:41:39.487 回答