我正在尝试优化大型 2D(好吧,将 1D 视为 2D)字节数组的索引,以最大限度地从 64 字节大小的同一高速缓存行中连续查找的数量。每个查找都与前一个查找相差一个,在水平和垂直移动之间交替。运动是积极的还是消极的都可以被视为随机的(实际上它遵循兰顿的蚂蚁规则字符串 RLR,但我不认为该信息是严格相关的),这意味着路径混乱地蜿蜒曲折,倾向于在同一大区域停留一段时间相当长的时间。
在一次正常索引一行的情况下,水平移动可能在同一缓存行内,但垂直移动永远不会。我的解决方案是在 8x8 块中索引数组,这是一个示例,就好像缓存行大小为 9 和 6x6 数组一样:
24 25 26 33 34 35
21 22 23 30 31 32
18 19 20 27 28 39
6 7 8 15 16 17
3 4 5 12 13 14
0 1 2 9 10 11
它在 3x3 块中表现不佳,但它应该允许缓存行被更多地重用:
.
.
.
56 57 58 59 60 61 62 63
48 49 50 51 52 53 54 55
40 41 42 43 44 45 46 47
32 33 34 35 36 37 38 39
24 25 26 27 28 29 30 31
16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15
0 1 2 3 4 5 6 7 ...
我用普通索引和这个索引进行了基准测试,这个索引比较慢。这可能是因为它必须做更多的工作才能计算出所需的索引(它处于一个紧密的循环中,请参阅此处了解正常的索引版本:如何优化这个 Langton's ant sim?)。我不能完全排除这种索引更有效的可能性(制定新索引可能是可优化的,考虑缓存对我来说是新的,我可能做的很糟糕)。
1)健全性检查:我正在尝试做的事情是否明智,它可能会奏效吗?它会在不同的条件下工作吗?
2) Longshot:是否有一个神奇的 gcc 编译器标志可以为您重新排序索引,以尝试优化 2D 数组而不是 1D?
3) 我可以(或者我需要)做些什么来尝试在 CPU 中保留某些高速缓存行吗?目前我假设最新的数据被保留直到被覆盖。
4)如果您有更好的解决方案,请描述它。
64 位 Linux、gcc、i5-2500k
编辑:事实证明:1)这种思维方式是不明智的,2)不适用,3)见接受的答案,4)见接受的答案