2的幂次方大小的数据有哪些性能优势?

23

如果我有一个具有3D世界的游戏,而这个世界很大,因此需要将其分成块,那么使用128字节块与150字节块相比,是否存在重大的性能优势?显然,块中的对象仍然是整数个字节。

也就是说,chunks[128][128][128] 是否比 chunks[150][150][150]chunks[112][112][112] 更快?是否存在过多的RAM浪费等其他副作用?还有其他需要考虑的因素吗?

我只是发现把所有变量和数组存储为2的幂次方大小是一种惯例,但我不确定是否有任何优点,以及是否可以更好地使用更人性化的数字,例如100或150。


我认为这取决于数组的类型。非字节类型可能需要内存对齐。 - vulkanino
2
想象一下,你需要运输1000人,而你有容纳50人的巴士。你认为哪种方式更好?将人们分成50人一组,还是将他们分成72人(或38人或其他数字)的小组,并在填满巴士之前再次分组? - pmg
1
想象一下人们戴着不同颜色的帽子。如果你按照与公交车容量不同的数字分组,每辆公交车上都会有戴着不同颜色帽子的人。使用二的幂次方作为数组“维度”,可以提高每个数组组(从indexindex+1之前)占用的内存部分可以作为一个整体访问的机会。 - pmg
如果您的内存是以您所描述的方式分散的(即不完全连续),从内存请求数据将导致缓存中拉取下一个X量的内存数据,如果您的内存中存在无用数据的间隙,则必须再次获取内存数据以获取程序正在寻找的下一位。 - Stowelly
3
作为警告:使用2的幂次方可能会导致超级对齐冲突。请参考此和此链接。由于超级对齐(基于2的幂次方步长)可能会导致缓存未命中和虚假别名停顿,因此性能可能会下降3倍或更多。因此,通过将乘法转换为移位所获得的优势很容易被缓存未命中和虚假别名停顿所抵消(甚至更多)。 - Mysticial
显示剩余2条评论
5个回答

24

其他回答确实正确,使用移位比乘法可以使2的幂大小的数据受益。

然而,2的幂大小的数据有一个暗面。它可能会在你最不希望的时候袭击你。

看看这两个问题/答案:

当你的数据集是2的幂次方时,它们更可能在内存中超级对齐(意思是它们的地址很可能在大的2的幂次方上具有相同的模数)。

虽然这似乎是可取的,但可能会导致:

如果您阅读以上链接的两个问题,您会发现对齐可能会导致超过3倍的减速 - 这很可能远远超过使用移位而不是乘法获得的任何好处。

对于所有性能问题,您需要进行测量,测量和测量...并准备好期望任何事情发生。

您提到您正在表示3D空间-这正是可能导致减速的2的幂步长内存访问的情况。


1
+1,缓存未命中比你在寻址时花费的几个周期更糟糕! - Nils Pipenbrinck
是的,我很惊讶没有人提到对齐作为一个缺点。无论是在答案还是评论中都没有 - 特别是考虑到循环问题所受到的关注度。我本来会早些回答的,但当时在我的时区已经是深夜了。所以我直到现在才看到它。 - Mysticial
感谢您提到缓存问题!非2的幂大小也可以通过移位和加法来实现。移位和加减法可以给您提供块大小,例如129或255。先移位再加/减。不过,值得检查一下您的目标硬件是否能够像移位和加/减法一样快速执行乘法。 - Benjohn

3

它不是“更快”,而是更好地利用可用内存,因为硬件和操作系统以最可能是2的幂的大小单位管理内存。分配小于2的幂的内容通常会导致浪费内存,因为需要对齐。

如果您深入研究分配程序和操作系统内存管理器,您将发现它们以2的幂大小来管理所有内容。操作系统通常按页面来管理进程的内存,而页面大小现在通常为4096个字节。因此,如果您想要分配一个4000字节的块,则操作系统仍然会分配4096字节,剩余的96字节将被浪费。


分配150^3 * 16字节(6,750,000字节)需要多少RAM?这是一个显著的数量吗? - Greg
“而剩下的96个字节将被浪费。” 这只是一个非常简化的观点。内存管理通常在几个层面上进行,根据管理器的不同,这96个字节可能会被用于其他变量。 - adelphus
@adelphus:确实,这只是简化了,我只是想描述一个典型的概念案例。 - Blagovest Buyukliev

2
如果您通过以下方式访问数据:
chunks[150][150][150]
chucks[x][y][z] = 123;

处理器必须进行乘法运算(例如:z + 150 * (y + 150 * x) ...)以获得地址。

如果使用2的幂次方常数,则编译器可以进行一些优化,并使用移位而不是乘法。新CPU使乘法变得非常快,因此效果微不足道。

使用大表可能会导致大量的缓存未命中。因此,较小的表可能比较大的表更快,即使较大的表具有2的幂次方大小的维度,而较小的表没有。


1

在软件编程中,二的幂次方经常被使用,因为计算机使用的是二进制。

例如,操作系统将内存分配给2的幂次方块大小,处理器缓存大小也是2的幂次方,地址大小也是2的幂次方等等。

使用二的幂次方值进行操作也可以进行优化 - 乘法或除法变成了简单的位移。

基本上确保所有东西都使用二的幂次方可能会提高软件性能,但通常编译器和/或操作系统会确保您使用任意大小时数据被有效利用。


0

它可能更快,也可能更慢,也可能是相同的速度。仅仅通过查看代码很难给出正确的答案。所以答案是:测量它,改变代码,再次测量它。如果您的代码必须在不同的计算机上运行,请在每台计算机上进行测量。

我倾向于认为二的幂对齐通常会带来严重的问题,并且使用比所需更多的内存不会有助于性能。使用适合某些缓存的小部分内存进行大量操作,然后切换到下一个内存部分,通常会有所帮助。访问连续的内存地址通常会有所帮助。四舍五入以便可以使用矢量操作通常会有所帮助。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接