1

从内存中,数据只能以体系结构的自然字长读取。例如,在 32 位系统上,数据以 4 字节块的形式从内存中读取。如果将 2 字节或 1 字节的值添加到内存中,它们的读取仍需要访问 4 字节的字。(对于 2 字节值,如果值存储在字边界上,则可能需要两次 4 字节访问。)

因此,当需要访问单个单词时,访问单个值是最快的,并且需要最少的额外工作(例如掩码)。如果我是正确的,这就是虚拟机(例如JVMAndroid 的 DalvikObject )在实例中以 4 字节边界布置成员变量的原因。

另一个概念是缓存友好性,即局部性(例如L1、L2)。如果许多值必须在彼此之后直接遍历/处理,则将它们彼此靠近存储(理想情况下,在连续块中)是有益的。这是空间局部性。如果这是不可能的,那么至少对相同值的操作应该在相同的时间段内完成(时间局部性——即在对其执行操作时,该值很有可能保留在缓存中)。

据我所知,上述两个概念在某些情况下可能是“矛盾的”,它们之间的选择取决于它们的使用场景。例如,较少量的连续数据比大量(微不足道的)数据对缓存更友好,但如果某些数据通常需要随机访问,则字对齐(但更大)结构可能是有益的——除非整个结构适合缓存。因此,我认为,是否应该首选局部性(~arrays)或对齐优势取决于如何操纵这些值

有一个场景对我来说很有趣:让我们假设一个寻路算法将输入图(其他辅助结构)作为数组接收。(它的大部分输入数组存储的值都是 <= 32767。)

寻路算法对数组执行非常多的随机访问(在几个循环中)。从这个意义上说,int[]输入数据(在 Android/ARM 上)可能需要一个,因为访问时这些值将位于字边界上。(另一方面,如果需要顺序遍历,则建议使用较小的数据类型——尤其是对于大型数组——因为缓存友好的可能性更高。)

但是,如果(随机访问的)输入数据在指定为 a 时适合 L1/L2 short[],但如果指定为 则不适合int[]怎么办?在这种情况下,int[]随机访问的 4 字节对齐的优势是否会被 的缓存友好性所抵消short[]

当然,在具体应用中,我会进行测量以进行比较。然而,这不一定能回答上述问题。

4

1 回答 1

0

如果您可以确保移动到短会导致显着更好的位置(也就是所有内容都在缓存中),那么这会超过对齐惩罚。

访问缓存在低纳秒<10ns,访问内存是60-80ns

于 2012-12-27T20:47:25.430 回答