优化康威的生活游戏

我已经编写了Conway的《人生游戏》的实现的代码，并且其中存在性能瓶颈，我希望对其进行优化。主要逻辑在Universe类中。我已省略所有不适用于酿造性的代码：

public class Universe {

    private static final int FLIP_INDEX = 0;
    private static final int FLOP_INDEX = 1;
    private final boolean[][][] universeDoubleBuffer;
    private final int height;
    private final int width;
    private int flipFlopIndex = FLIP_INDEX;

    public Universe(boolean[][] universeState) {
        height = universeState.length;
        width = universeState[0].length;
        universeDoubleBuffer = new boolean[2][height][width];
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                universeDoubleBuffer[FLIP_INDEX][y][x] = universeState[y][x];
            }
        }
    }   

    public boolean[][] recalculateUniverseState() {
    int newFlipFlopIndex = (flipFlopIndex == FLIP_INDEX ? FLOP_INDEX : FLIP_INDEX);
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            int liveNeighbors = countLiveNeighbors(x, y);
            boolean isLiving = universeDoubleBuffer[flipFlopIndex][y][x];
            if (!isLiving && liveNeighbors == 3) {
                universeDoubleBuffer[newFlipFlopIndex][y][x] = true;
            } else if (isLiving && (liveNeighbors == 2 || liveNeighbors == 3)) {
                universeDoubleBuffer[newFlipFlopIndex][y][x] = true;
            } else {
                universeDoubleBuffer[newFlipFlopIndex][y][x] = false;
            }
        }
    }
    stampPatterns();
    logger.info("Old:" + Arrays.deepToString(universeDoubleBuffer[flipFlopIndex]));
    logger.info("New:" + Arrays.deepToString(universeDoubleBuffer[newFlipFlopIndex]));
    flipFlopIndex = newFlipFlopIndex;
    return universeDoubleBuffer[flipFlopIndex];
}

    private int countLiveNeighbors(int x, int y) {
        int result = 0;
        for (CellNeighbor neighbor : CellNeighbor.values()) {
            try {
                boolean isLiving = universeDoubleBuffer[flipFlopIndex][y + neighbor.getYOffset()][x + neighbor.getXOffset()];
                if (isLiving) {
                    result++;
                }
            } catch (IndexOutOfBoundsException e) {
                logger.info("Cell's neighbor was off the grid.", e);
            }
        }
        return result;
    }    
}

这里是CellNeighbor的代码：

public enum CellNeighbor {

    TOP_LEFT(-1, 1), TOP(0, 1), TOP_RIGHT(1, 1), RIGHT(1, 0), BOTTOM_RIGHT(1, -1), BOTTOM(0, -1), BOTTOM_LEFT(-1, -1), LEFT(-1, 0);

    private int xOffset;
    private int yOffset;

    private CellNeighbor(int xOffset, int yOffset) {
        this.xOffset = xOffset;
        this.yOffset = yOffset;
    }

    public int getXOffset() {
        return xOffset;
    }

    public int getYOffset() {
        return yOffset;
    }
}

我的问题是，如果我创建一个足够大的世界（例如，我使用5000 * 5000进行了测试），生活确实会放慢速度，并且花费在recalculateUniverseState()上的时间将近一秒钟（使用5000 * 5000宇宙时，平均时间为766ms）。 />
我尝试了没有双缓冲区（交换新的boolean[][]阵列）并且没有try / catch块，但是它并没有带来显着的性能改进。

我的问题是如何优化上面的代码会更快？

旧标题有什么问题？

规避数组范围异常并帮助提高性能的一个小技巧是使数组在“世界”周围具有边界。然后，您可以“在世界的边缘”安全地访问单元格值。您不更新边缘单元，而是在countLiveNeightbours调用中访问它们。另外，在Conway的一生中，您可以使用圆环。即包装索引值以保持在范围内。

同样，可以通过查找表来完成级联条件，该条件取决于活动邻居的数量以及当前状态到新状态的映射。

最后的想法-如果您有一个大小如此的网格，一个简单的算法将要求每帧更新25M。因此在Java中766毫秒实际上还不错。您可以从一些线程中获得一些好处-Java非常有用。但是，通过不更新较大的“空白”区域，即通过四叉树等划分为区域，可以实现较大的加速。此功能的有效性取决于当前状态/初始条件。

关于标题编辑：标题应概述代码的上下文（代码所涉及的内容），而不是您认为的问题所在。这样可以更轻松地搜索问题，使相关问题列表更准确，等等。原始标题也是一个非常狭窄的请求，但是代码检查涉及代码的所有方面，并特别注意您所请求的区域重点。

#1 楼

首先，这应该很明显，但是当您在涉及紧密内部循环的代码中遇到性能问题时，您希望尽可能简化该循环。如果您可以通过在其他地方花费一打或一百个循环来节省一个循环，请执行此操作，因为循环中的每个循环都将乘以5000²。

此外，您真正要最小化的是内部循环中的是内存访问。访问局部变量很快，因为它们通常被缓存，并且JVM知道除非方法中的代码本身对其进行更改，否则它们的值无法更改。相比之下，从大型数组中提取随机元素相对较慢，因为它需要完全的RAM访问权限，通常，通常是访问成员变量或调用未缓存的方法。

我已经完成了以前是这样的，*因此，与其列出我可能对您的代码所做的每一个改进，不如让我开始概述如何重写您的核心更新循环：
>关于此代码的几点注意事项：

没有countLiveNeightbors()方法；实际上，该代码根本没有明确地计算活动邻居。取而代之的是，在（x，y）处包含并围绕着这9个单元格的9个单元格的模式将保留在变量environment中，该变量用作对512元素查找表的索引。，如果当前单元格的周围环境看起来像这样（# =活细胞，_ =死细胞）：

// assume these arrays are (height + 2) by (width + 2)
boolean[][] oldBuffer = universeDoubleBuffer[flipFlopIndex],
            newBuffer = universeDoubleBuffer[newFlipFlopIndex];

for (int y = 1; y <= height; y++) {
    int environment
        = (oldBuffer[y-1][0] ? 32 : 0) + (oldBuffer[y-1][1] ?  4 : 0)
        + (oldBuffer[y  ][0] ? 16 : 0) + (oldBuffer[y  ][1] ?  2 : 0)
        + (oldBuffer[y+1][0] ?  8 : 0) + (oldBuffer[y+1][1] ?  1 : 0);

    for (int x = 1; x <= width; x++) {
        environment = ((environment % 64) * 8)
            + (oldBuffer[y-1][x+1] ? 4 : 0)
            + (oldBuffer[y  ][x+1] ? 2 : 0)
            + (oldBuffer[y+1][x+1] ? 1 : 0);

        newBuffer[y][x] = lookupTable[ environment ];
    }
}

当然，您必须先使用此查找表进行设置，但这是您可以在核心循环外进行的操作（例如，在构造函数中）），因此它对性能并不重要。

（实际上，尽管我尚未对此进行基准测试，但我至少会考虑将environment设为局部变量，并在每次调用update方法时对其进行重建，因为重建表的额外成本可能会通过额外的优化机会来抵消如果编译器/ JVM知道没有其他代码可以修改该表，则可以使用它。您可能要同时进行测试，以查看哪种方法更快。）

这种查找表的另一个优点基于实现的方法是，通过更改查找表，它可以使用Moore邻域模拟任何两个状态的细胞自动机，而不仅仅是Conway的生命游戏。

通过重用环境模式的各个部分，由于在相邻单元之间共享，因此代码仅需要每个单元从lookupTable阵列读取3次，而在您的版本中则需要9次。未缓存的阵列访问非常昂贵，因此这可能会大大提高速度。（另外，就像您的代码一样，我的代码还确保访问缓冲区的顺序尽可能接近顺序，首先按行然后按列进行迭代。这对于CPU缓存局部性也很重要。）上面的代码不会更新数组边缘的单元格，这意味着它不必担心（字面）边缘情况，例如数组索引超出范围。（希望编译器/ JVM也可能注意到这一点，并且可能会省略一些内部数组边界检查。）

如果您希望网格被死单元包围，则可以在开始时将它们标记出来边框已死，并在您的更新方法中保持不变。另外，例如，如果您希望网格环绕，则可以在单独的循环中更新边缘单元（这可能效率较低，因为它只在所有单元中的一小部分运行）。

实际上，有几种方法可以进一步优化我上面建议的代码。例如，一个明显的优化是摆脱内部循环中的二维数组访问，因为它们每次都需要两次数组查找。

（至少）有两种方法可以执行此操作：

a）在外部循环中，将oldBuffer的前一行，当前行和下一行保存在局部变量中，如下所示：

b）使缓冲区本身成为一维数组，并调整索引，以便使用oldBuffer代替buffer[y][x]。您可以在外部循环中预先计算偏移量buffer[ y * (width+2) + x ]，还可以预先计算偏移量y * (width+2)，以节省一些算术，或者您可以依靠编译器/ JVM来完成。再一次，您可以尝试两种方法，看看是否有区别。

对于像生命游戏这样的细胞自动机，每个时间步长中通常只有一小部分细胞发生变化，甚至比上面描述的通用表查找方法还快得多的算法。

第一步，ChrisW关于缓存实时邻居计数的建议可能每当每个环境都更快时

通过存储活动单元的列表（即在先前的更新步骤中已更改或具有至少一个邻居的状态更改的单元），可以获得更大的加速。在下一次更新中遍历这些单元。（由于活动单元格的总数在上面受网格大小的限制，因此您可以使用简单的数组作为循环缓冲区来有效地存储此列表。）

有效地将活动单元格列表与双精度组合缓冲可能有些棘手。另一种解决方案是使用单个缓冲区，但将更新方法分为两个阶段：

在第一阶段，您将遍历列表，计算每个活动单元的新状态，然后将其存储在列表中。
在第二阶段，您将再次遍历该列表并更新网格缓冲区以匹配在第一阶段计算出新状态。

（也就是说，同时使用活动列表和双重缓冲确实有一个优势：它允许您处理周期为2的振荡细胞，这很常见在生命游戏中处于非活动状态。这确实需要为每个缓冲区维护单独的活动单元格列表。）

最后，如果您想要一种非常快速的算法来模拟Conway的生命游戏，请查找哈希生活。实际上，它比任何“幼稚”的仿真算法都要快几个数量级，特别是对于稀疏和高度重复的模式（例如许多构造的模式）。

*）请不要以该代码为例来说明良好的编码风格。不过，它非常快。

附录：这是活动列表方法的基本实现，使用单个缓冲区，并使用硬编码的Conway生命游戏规则。

它使用字节填充的单元格状态缓冲区，其中字节的最低位指示该单元格当前是否在活动列表中，第二位存储单元格的实际状态，随后的（四）位存储周围的活细胞数（以避免在每次检查细胞时都要重新计算）：

# # _
_ # #
# _ _

在第一次通过之前，应将所有细胞初始化为具有正确的邻居计数，设置活动位并添加到活动单元队列中。我已经省略了这部分代码，因为它对性能不重要。

请注意，此方法沿状态数组的边缘不使用任何填充单元。或者，我们可以添加填充并为这些单元永久设置活动位，但不将它们包括在队列中，从而可以简化最小/最大坐标的计算。我怀疑这不会有太大的区别，但是没有尝试就无法确定。

\ $ \ begingroup \ $
感谢您的详尽解释！由于某种原因，没有想到使用bitvector（like）结构。
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
14年2月26日在19:48

\ $ \ begingroup \ $
您能解释一下环境变量的计算吗？我不了解x，不知道如何计算其初始值。（（环境％64）* 8）部分也不清楚。
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
2014-2-26在20:20

\ $ \ begingroup \ $
（（environment％64）* 8）除去环境模式的除最低的六位以外的所有位，然后将剩余的位左移三位。您同样可以使用（（environment＆0b111111）<< 3）位运算符来编写它。初始值实际上是x = 0的环境，由y-1，y和y + 1行以及0和1列中六个单元格的状态组成。它不包括（不存在）列-1，因为无论如何，用于编码这些单元状态的位都会从内部循环中移出环境。
\ $ \ endgroup \ $
–伊尔马里·卡洛宁（Ilmari Karonen）
2014-2-26在20:25

\ $ \ begingroup \ $
我可以通过简单地将数字从0转换为511并将其应用到二进制数组中并使用生命游戏规则来创建查找。
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
2014年2月26日21:00

\ $ \ begingroup \ $
您肯定需要更多支持。初步实施使速度提高了10倍！
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
14年2月26日在21:03

#2 楼

与性能无关，只是一些快速的通用说明：

try {
    boolean isLiving = universeDoubleBuffer[flipFlopIndex][y + neighbor.getYOffset()][x
            + neighbor.getXOffset()];
    if (isLiving) {
        result++;
    }
} catch (final IndexOutOfBoundsException e) {
    logger.info("Cell's neighbor was off the grid.", e);
}

对于正常情况，您不应使用异常。（请参见有效Java，第二版，条款57：仅在特殊情况下使用例外）。

isLiving的解释变量在这里很好。比触发器更易读。
inputBuffer代替outputBuffer而不是常量，它们是幻数。

我不明白为什么下面的注释在这里，因为没有任何注释该类被多个线程使用的迹象：

flipFlopIndex = newFlipFlopIndex; // assignment is atomic, no
                                  // synchronization needed

无论如何，分配可能是原子的，但您可能需要适当的同步。

<除非同步读取和写入操作，否则同步才有效。

来自有效Java，第二版，项目66：同步访问共享的可变数据。

锁定不仅涉及互斥，
为了确保所有线程都能看到共享的可变
变量的最新值，读写线程必须在一个公共锁上进行同步。

来自Java Concurrency in Practice，3.1.3。锁定和可见性。

\ $ \ begingroup \ $
事实是，我不能将它们命名为inputBuffer，outputBuffer，因为它们的角色与每一代都互换了。其他人提到了try块的逻辑故障，因此我将其删除。这里有一个评论，但是感谢您指出。这种生活游戏将在Web应用程序中的多个线程中使用，但recalculateUniverseState（）仅从一个线程中调用。在代码中有一个选项未显示，用于将生活模式的游戏标记到宇宙上，但我通过并发队列解决了该问题。（省略代码）。
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
2014年2月25日在10:22

#3 楼

countLiveNeighbors函数看起来很昂贵；您确定for (CellNeighbor neighbor : CellNeighbor.values())在后台没有进行大量的new CellNeighbor调用（和垃圾回收）吗？

更重要的是：所有异常处理都很昂贵！

使用异常处理获得异常的控制流。

通常情况下不要使用它。

我建议如下重写那部分代码，然后进行分析以查看瓶颈是否消失。 br />但是，写的内容提醒我：您是否尝试过分析代码？（随机的Google链接。注释中的某人可能对如何配置Java代码有更好的建议。）

private int countLiveNeighbors(int x, int y) {
    int result = 0;
    for (int dx = -1; dx <= 1; ++dx) {
        int x2 = x + dx;
        if (x2 < 0 || width <= x) continue;
        for (int dy = -1; dy <= 1; ++dy) {
            int y2 = y + dy;
            if (y2 < 0 || height <= y) continue;
            boolean isLiving = universeDoubleBuffer[flipFlopIndex][y2][x2];
            if (isLiving) {
                result++;
            }
        }
    }
    return result;
}

\ $ \ begingroup \ $
嗯，您最近很活跃。您应该在某个时候加入我们的聊天室:)
\ $ \ endgroup \ $
–syb0rg
2014年2月25日在1:59

\ $ \ begingroup \ $
我在没有try块的情况下测试了运行时间，但是并没有带来明显的改善。我将检查CellNeighbor，谢谢。
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
2014年2月25日在10:17

\ $ \ begingroup \ $
由于CellNeighbor是一个枚举，所以我很确定它不会执行任何新的CellNeighbor。仅对int进行迭代可能会有所帮助，但我怀疑它是否有意义。
\ $ \ endgroup \ $
–西蒙·福斯伯格
2014-2-25在11:36

\ $ \ begingroup \ $
每次在枚举上调用值都会创建一个新数组。因此最好将其保存在本地一次。
\ $ \ endgroup \ $
– Radioodef
2014年2月25日在18:02

#4 楼

一种提高性能的方法是使用不同的数据结构。例如，您可以使用8位（每个邻居一个位）对一个单元的邻居的状态进行编码。邻居位的组合：这是单个表查找。

如果单元状态发生变化（这种情况很少发生），则更新其邻居的邻居位中的相应位。

您的宇宙是这样的：

boolean state;
byte neighbours;

您的recalculateUniverseState方法是这样的：

foreach (cell in universe)
{
    boolean newState = (state) ? liveState[neighbours] : deadState[neighbours];
    if (newState != state)
        changedCells.add(cell);
}
foreach (cell in changedCells)
{
    // change the state of this cell
    // update the bits in this cell's neighbours
}

>这只是记忆中的一个例子；有一种更有效的方法：Abrash的Zen代码优化描述了一种结构，该结构以8位编码单元状态及其邻居的状态（这取决于至少一个位是冗余的，因为它是在隔壁邻居中编码的）。

Wikipedia上和网站上也建议使用算法加速：例如，记住董事会的哪些单元格或区域没有变化并且不要重新计算。

\ $ \ begingroup \ $
我制作了这个“社区Wiki”，因为它是适用于任何有关改善生活游戏问题的通用答案，而它实际上并不是代码审查。
\ $ \ endgroup \ $
– ChristW
2014年2月25日在9:03

#5 楼

[有点话题，因为它并没有真正帮助纠正“上面的代码” ...而是要解决问题的根源：快速的人生几代人游戏”

我很惊讶没有-有人提到比尔·戈斯珀（Bill Gosper life）（如果您在Google上搜索“比尔·戈斯珀生活”，您将看到他就此主题召开的一些会议）。这是您可能会发现有趣的链接：

http://en.wikipedia.org/wiki/Hashlife（Bill Gosper的Hashlife算法）

优化循环是好的，但是首先应该优化解决问题的方法以及解决问题的方法。

哈希生活可能是Conway生命游戏的一个很好的起点：

维基百科上有关哈希生活的页面上的示例谈到“使用Golly中的hashlife在Intel Core Duo 2GHz CPU上用不到30秒的时间计算出的非常复杂的“人生游戏”模式。通过检测模式中的重复周期并向前跳至任何所需的代，可以进行计算。”

#6 楼

代替universeDoubleBuffer[someIndex]使用2个单独的字段和2个单独的局部变量，在循环的每一步交换局部变量的值。因此，排除了一项昂贵的数组访问操作。
应避免有条件的分支和无条件的分支以便快速执行。
在countLiveNeighbors中，显式读取4个相邻单元而不是循环。
要表示活动性，请使用byte 0或1而不是布尔值。代替if (isLiving && liveNeighbors ...，根据先前的状态，使用预定义的表表示下一个状态的值，而仅从表中读取新状态，而不使用条件语句。

\ $ \ begingroup \ $
您认为byte [] []会比boolean [] []快吗？
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
2014年2月26日在21:14

\ $ \ begingroup \ $
我的意思是，在countLiveNeighbors中，如果（isLiving）{result ++;}可以替换为result + = isLiving，则速度更快。
\ $ \ endgroup \ $
– Alexei Kaigorodov
2014年2月27日，下午2:22

\ $ \ begingroup \ $
我已经实现了@Ilmari Karonen的建议，可以解决此问题。
\ $ \ endgroup \ $
–亚当·阿罗德（Adam Arold）
2014年2月27日在10:25

编程黑洞网