Почему «angina» — это не «ангина», а «resin» — не «резина», или Ложные друзья переводчика

Мой любимый пример такого рода — электронная виза в Мексику. Вот оригинал:


А вот — русский вариант:

Насколько я понимаю, ministro de culto — это религиозный деятель, а министр культуры будет ministro de cultura. Этому переводу, кстати, уже лет 10, удивительно, что его так и не исправили, можете по ссылке сходить, посмотреть.

Как ускорить игру «Жизнь» в сто раз

Если Вы имеете в виду наложение кода на картинку, то не фотошопом: я использовал paint.net, сгенерировал пять картинок, и воспользовался одним из онлайн-генераторов анимированных gif.

Как ускорить игру «Жизнь» в сто раз

Я провел такой эксперимент, ускорение получилось в 3.5 раза для рандомной начальной конфигурации (но, конечно, для маленьких и статичных конфигураций ускорение может быть в сотни и тысячи раз)
Обсуждение и код в этой ветке. Может быть, кто-то сможет еще больше ускорить.
Я прошу прощения, нам с самого начала надо было вести обсуждение под Вашим комментарием (теперь, наверно, не перенести).

Как ускорить игру «Жизнь» в сто раз

в программе Golly, взял статическую картинку из четырех точек и копипейстом размножил по форме букв:

Как ускорить игру «Жизнь» в сто раз

Последовал Вашему совету и полез в мой любимый zlib. Поймите меня правильно, я люблю ассемблер, и сам на нем когда-то писал, но не могу удержаться:

/* inffast.c -- fast decoding
 * Copyright (C) 1995-2017 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

#include "zutil.h"
#include "inftrees.h"
#include "inflate.h"
#include "inffast.h"

#ifdef ASMINF
#  pragma message("Assembler code may have bugs -- use at your own risk")
#else

...

Как ускорить игру «Жизнь» в сто раз

Проверил на коленке Вашу идею:

LifeInList: 1000 steps in 17.252 seconds, 57.965 steps/sec
LifeIsChange: 1000 steps in 11.783 seconds, 84.868 steps/sec

Лучше, чем LifeBytes, но хуже, чем LongLife. Код:

проверяем только живые и их соседей

/// <summary>
    /// only processes live cells and their neighbours
    /// </summary>
    public class LifeInList : LifeJourney
    {
        List<int> liveCells = new List<int>();
        byte[] field = new byte[WIDTH * HEIGHT];
        List<int> nextLiveCells = new List<int>();
        List<int> processedCells = new List<int>();
        bool[] processed = new bool[WIDTH * HEIGHT];

        public override bool Get(int i, int j) => field[j * WIDTH + i] == 1;

        public override void Set(int i, int j, bool value)
        {
            if (value && (i == 0 || i == WIDTH - 1)) throw new ArgumentException("i");
            if (value && (j == 0 || j == HEIGHT - 1)) throw new ArgumentException("j");
            if (Get(i, j) == value) return;
            field[j * WIDTH + i] = (byte) (value? 1 : 0);
            if (value) liveCells.Add(j * WIDTH + i);
            else liveCells.Remove(j * WIDTH + i); // very slow but not used on hot-path
        }

        private void ProcessLiveCell(int cell)
        {
            if (processed[cell]) return;
            processedCells.Add(cell);
            processed[cell] = true;

            int x = cell % WIDTH;
            int y = cell / WIDTH;
            if (x == 0 || x == WIDTH - 1) return;
            if (y == 0 || y == HEIGHT - 1) return;

            int neighbours =
                field[cell - WIDTH - 1] + field[cell - WIDTH] + field[cell - WIDTH + 1] +
                field[cell - 1] + field[cell + 1] +
                field[cell + WIDTH - 1] + field[cell + WIDTH] + field[cell + WIDTH + 1];
            if(neighbours == 2 || neighbours == 3)
            {
                nextLiveCells.Add(cell);
            }
        }

        private void ProcessDeadCell(int cell)
        {
            if (field[cell] == 1) return; // cell is alive, will be processed in the main loop

            if (processed[cell]) return; // already processed
            processedCells.Add(cell);
            processed[cell] = true;

            int x = cell % WIDTH;
            int y = cell / WIDTH;
            if (x == 0 || x == WIDTH - 1) return;
            if (y == 0 || y == HEIGHT - 1) return;

            int neighbours =
                field[cell - WIDTH - 1] + field[cell - WIDTH] + field[cell - WIDTH + 1] +
                field[cell - 1] + field[cell + 1] +
                field[cell + WIDTH - 1] + field[cell + WIDTH] + field[cell + WIDTH + 1];
            if (neighbours == 3)
            {
                nextLiveCells.Add(cell);
            }
        }

        public override void Step()
        {
            foreach(int cell in liveCells)
            {
                ProcessLiveCell(cell);

                ProcessDeadCell(cell - WIDTH - 1);
                ProcessDeadCell(cell - WIDTH);
                ProcessDeadCell(cell - WIDTH + 1);
                ProcessDeadCell(cell - 1);
                ProcessDeadCell(cell + 1);
                ProcessDeadCell(cell + WIDTH - 1);
                ProcessDeadCell(cell + WIDTH);
                ProcessDeadCell(cell + WIDTH + 1);
            }

            foreach (int cell in liveCells) field[cell] = 0;

            foreach (int cell in processedCells) processed[cell] = false;
            processedCells.Clear();

            foreach (int cell in nextLiveCells) field[cell] = 1;

            List<int> temp = liveCells;
            liveCells = nextLiveCells;
            nextLiveCells = temp;
            nextLiveCells.Clear();
        }
    }

проверяем только изменившиеся и их соседей

    /// <summary>
    /// only processes changed cells and their neighbours
    /// </summary>
    public class LifeIsChange : LifeJourney
    {
        byte[] currentField = new byte[WIDTH * HEIGHT];
        byte[] nextField = new byte[WIDTH * HEIGHT];
        List<int> currentChangedCells = new List<int>(WIDTH * HEIGHT);
        List<int> nextChangedCells = new List<int>(WIDTH * HEIGHT);
        List<int> processedCellsList = new List<int>(WIDTH * HEIGHT);
        bool[] processedCellsMap = new bool[WIDTH * HEIGHT];

        public override bool Get(int i, int j) => currentField[j * WIDTH + i] == 1;

        public override void Set(int i, int j, bool value)
        {
            if (value && (i == 0 || i == WIDTH - 1)) throw new ArgumentException("i");
            if (value && (j == 0 || j == HEIGHT - 1)) throw new ArgumentException("j");
            int cell = j * WIDTH + i;
            currentField[cell] = (byte) (value ? 1 : 0);
            currentChangedCells.Add(cell);
        }

        private void ProcessCell(int cell)
        {
            if (processedCellsMap[cell]) return;

            int x = cell % WIDTH;
            int y = cell / WIDTH;
            if (x == 0 || x == WIDTH - 1) return;
            if (y == 0 || y == HEIGHT - 1) return;

            processedCellsMap[cell] = true;
            processedCellsList.Add(cell);

            bool alive = currentField[cell] == 1;

            int neighbours =
                currentField[cell - WIDTH - 1] + currentField[cell - WIDTH] + currentField[cell - WIDTH + 1] +
                currentField[cell - 1] + currentField[cell + 1] +
                currentField[cell + WIDTH - 1] + currentField[cell + WIDTH] + currentField[cell + WIDTH + 1];
            bool nextAlive = (alive & (neighbours == 2 || neighbours == 3)) || (!alive && neighbours == 3);
         
            nextField[cell] = (byte)(nextAlive ? 1 : 0);

            if(nextField[cell] != currentField[cell]) nextChangedCells.Add(cell);
        }

        public override void Step()
        {
            foreach(int cell in currentChangedCells)
            {
                ProcessCell(cell - WIDTH - 1);
                ProcessCell(cell - WIDTH);
                ProcessCell(cell - WIDTH + 1);
                ProcessCell(cell - 1);
                ProcessCell(cell);
                ProcessCell(cell + 1);
                ProcessCell(cell + WIDTH - 1);
                ProcessCell(cell + WIDTH);
                ProcessCell(cell + WIDTH + 1);
            }

            foreach (int cell in processedCellsList) processedCellsMap[cell] = false;
            //Console.WriteLine($"Processed {processedCellsList.Count} cells because of {currentChangedCells.Count} changed cells");
            processedCellsList.Clear();

            List<int> tempCells = currentChangedCells;
            currentChangedCells = nextChangedCells;
            nextChangedCells = tempCells;

            byte[] tempField = currentField;
            currentField = nextField;
            nextField = tempField;

            nextChangedCells.Clear();
        }
    }

По поводу последнего: в такой большой рандомной картинке даже на тысяной итерации изменяется около сорока тысяч клеток:

...
Processed 191416 cells because of 45367 changed cells
Processed 190530 cells because of 45175 changed cells

Как ускорить игру «Жизнь» в сто раз

Кстати, насчет ассемблера: у меня изначально была реализация на C++ через интринсики, но она работала с абсолютно такой же скоростью, что и версия на C#. Я не ожидал, что JIT сможет скомпилировать такой же хороший код, что и C++

Как ускорить игру «Жизнь» в сто раз

я видел ее. Мне кажется, или его результат только примерно совпадает с классическими правилами?

Как ускорить игру «Жизнь» в сто раз

Из осциллятора, который получил QDeathNick, можно составить нестатическую фигуру, если я не ошибся в подсчетах, 32% плотности:

Как ускорить игру «Жизнь» в сто раз

Сейчас проверил, переключение буфера вместо копирования дает ускорение примерно в 1.15 раз (на 13%)

Как ускорить игру «Жизнь» в сто раз

наверняка есть, так как есть глобальная база, в которую все исследователи кладут «интересные» шаблоны (найденные брутфорсом на GPU).
Или можно еще скачать программу Golly, в ней есть пара сотен шаблонов (в простом текстовом формате)

Как ускорить игру «Жизнь» в сто раз

эта игра жизнь ВСЕГДА вырождается к сильно разреженной матрице живых клеток

Доказано, что плотность может превышать 50%

Как ускорить игру «Жизнь» в сто раз

Вот, например, неплохое объснение Hashlife, там очень похоже на то, как Вы описываете.

Как ускорить игру «Жизнь» в сто раз

Вот, например: List_of_common_still_lifes

Как ускорить игру «Жизнь» в сто раз

fuggy
Примерно так и работает алгоритм Hashlife, который может работать в тысячи и миллионы раз быстрее, его придумал американский програмист Bill Gosper в 1983 году. Мне не удалось достать его оригинальную статью, так что не ручаюсь за достоверность, но я слышал, что его оригинальная версия была написана на лиспе.

Как ускорить игру «Жизнь» в сто раз

Это другой тип оптимизации, который может сильно ускорить «хорошие» сценарии, но сильно замедлить «плохие».
Если живых клеток на поле мало, то этот подход даст огромный эффект — можно получить ускорение и в 100 и в 1000 раз. Но если живых клеток много, то время, потраченное на проход их соседей, да еще и не в cache-friendly порядке, может замедлить алгоритм в десятки раз.
Например, на поле 1920x1080 примерно два миллиона клеток, и алгоритм, сканирующий все поле, делает два миллиона итераций.
Для какого-нибудь глайдера, в котором не больше 10 точек, алгоритм со списком будет обрабабывать за итерацию 10 + 8*10 < 100 точек, то есть, будет быстрее в 20000 раз!
Но если в начальной конфигурации поля половина клеток живая, то алгоритм со списком будет делать 9 миллионов итераций, то есть, в 4.5 раза медленнее (на самом деле, еще медленней из-за cache misses). И это только в сравнении с неоптимизированным алгоритмом.

Как ускорить игру «Жизнь» в сто раз

Да, конечно, думаю, тут можно (и даже нужно!) использовать многопоточность, если мы хотим добиться максимальной производительности.
Это не отменяет пользу от однопоточной оптимизации, но согласен, про многопоточность, наверно, следовало упомянуть.

Как ускорить игру «Жизнь» в сто раз

Я точно не знаю, но возможно, что так как она была придумана в 1970 году, когда персональных компьютеров не было, требовался игрок, который должен был вручню гонять симуляцию на листке в клеточку.

Как ускорить игру «Жизнь» в сто раз

Я бы из них тогда попробовал ILGPU — она OpenSource и, вроде как, не требует сложной настройки.

Как ускорить игру «Жизнь» в сто раз

Вроде пока еще на стадии proposal