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

    image

    Сложно найти человека, не знакомого с игрой "Жизнь", придуманной английским математиком Джоном Конвеем еще в 1970 году, и до сих пор не теряющей своей популярности. Многие программисты писали свою реализацию этой игры, и еще одна вряд ли кого-то удивит. Однако эта игра является отличным примером, показывающим, насколько полезной может оказаться оптимизация вычислений, даже не меняющая асимтотическую сложность алгоритма. Мы начнем с простейшей реализации на c# и будем последовательно применять различные оптимизации, ускоряя работу программы.

    Мы также улучшим алгоритм на JavaScript, ускорив его в 10 раз по сравнению с неоптимизированной версией.

    В конце статьи дана ссылка на код, а также на online-реализацию игры с оптимизированным алгоритмом на JavaScript, выполняющим до двухсот итераций в секунду на поле размера 1920x1080 (Full HD), где вы можете убить время поиграть в эту замечательную игру.

    Правила игры


    Игра «Жизнь» идет на плоскости, состоящей из клеток, каждая клетка имеет 8 соседей. Клетки могут быть «живые» или «мертвые». В каждой итерации (еще называемой «поколением») состояние поля меняется в зависимости от количества живых соседей: если рядом с живой клеткой два или три живых соседа, клетка выживает в следующем поколении. Если рядом с мертвой клеткой ровно три живых соседа, то в следующем поколении клетка «рождается».

    Например:

    — клетка A имеет одного живого соседа, поэтому она умирает;
    — клетка B имеет трех живых соседей, поэтому она остается жить;
    — клетка C имеет трех живых соседей, поэтому она рождается;
    — клетка D имеет пять живых соседей, поэтому она остается мертвой.

    Код на c# требует .NET Core 3.1. За исключением одного класса (использующего System.Runtime.Intrinsics.X86), остальной код должен работать .NET Framework и на более ранних версиях .NET Core. Разработка велась в Visual Studio Community Edition 2019.

    Реализация на JavaScript не требует никаких зависимостей, хотя игру желательно запускать в браузере Chrome, поскольку в Microsoft Edge он работает крайне медленно. Разработка велась в Visual Studio Code.

    Как устроен код на c#


    Размер игрового поля зафиксирован как 1920x1080 (Full HD), причем крайние клетки всегда мертвые. Это не влияет на производительность, но упрощает алгоритмы, избавляя от проверок на граничные условия. Все алгоритмы наследуются от абстрактного класса LifeJourney, что позволяет унифицировать их тестирование:

    LifeJourney.cs
    public abstract class LifeJourney 
    {
        public const int WIDTH = 1920;
        public const int HEIGHT = 1080;
        public string Name => GetType().Name;
        public abstract void Set(int i, int j, bool value);
        public abstract bool Get(int i, int j);
        public abstract void Step(); // makes one iteration. Performance-critical!
        public void Clear() 
        {
            for (int i = 1; i < WIDTH - 1; i++)
                for (int j = 1; j < HEIGHT - 1; j++)
                    Set(i, j, false);
        }
        public void GenerateRandomField(int seedForRandom, double threshold) { ... }
        ... // other methods
    }
    


    Юнит-тесты запускают один и тот же набор тестов для каждого алгоритма:

    LifeTesting.cs
    public class LifeTesting 
    {
           public static void PerformAllTests(LifeJourney life) 
           {
                TestGetSet(life);
                TestSetSimpleFigure(life);
                TestSimpleFigureAtStart(life);
                TestSimpleFigureAtSecondPos(life);
                TestSimpleFigure(life);
                TestGenerate(life);
                TestRandomField(life);
            }
            ...
            private static void TestRandomField(LifeJourney life) 
            {
                life.GenerateRandomField(12345, 0.5);
                life.Step();
                Assert.AreEqual(565797, life.GetLiveCellsCount());
                Assert.AreEqual(-717568334, life.GetFingerprint());
            }
        }
    
       [TestClass]
        public class TestDifferentLives 
        {
            [TestMethod]
            public void Test_1_SimpleLife() => 
                LifeTesting.PerformAllTests(new SimpleLife());
            ...
        }
    


    Тестирование производительности создает поле случайной заливкой с использованием генератора случайных чисел с фиксированным seed-ом (так что каждый раз поле получается одним и тем же). После этого запускается цикл из тысячи итераций, и в конце замеряется время (в секундах), а также проверяется конечное состояние поля (количество выживших клеток и хеш-код) для дополнительной проверки корректности работы алгоритма:

    RunPerformanceTest
    public abstract class LifeJourney 
    {
        public void GenerateRandomField(int seed, double threshold)
        {
            Random rand = new Random(seed);
            for (int i = 1; i < WIDTH - 1; i++)
                for (int j = 1; j < HEIGHT - 1; j++)
                {
                    Set(i, j, rand.NextDouble() < threshold);
                }
        }
    
        public void RunPerformanceTest(int steps) 
        {
            GenerateRandomField(12345, 0.5);
            Stopwatch timer = new Stopwatch();
            timer.Start();
            Run(steps);
            double elapsedSeconds = timer.Elapsed.TotalSeconds;
            Console.WriteLine($"{Name} Performance: {(steps / elapsedSeconds):0.000} steps/sec");
        }
        ... // other methods
    }
    
    class Program
    {
        static void Main(string[] args)
        {
            int steps = 1000;
            new SimpleLife().RunPerformanceTest(steps);
            ...
        }
    }
    


    1. Наивная реализация


    Начнем с самой простой реализации: поле представлено массивом boolean, хранящим информацию о живых клетках; каждая итерация выполняется в два прохода:

    1. для каждой клетки считаем количество ее соседей и записываем будущее состоянее клетки в отдельный массив temp;
    2. копируем массив temp в исходный массив.

    Два прохода нужны потому, что состояние клетки на следующем шаге зависит от состояния ее соседей на текущем шаге, поэтому мы не можем менять состояние клеток, пока мы не вычислили весь следующий шаг.

    SimpleLife
    public class SimpleLife : LifeJourney
    {
        bool[,] field = new bool[WIDTH, HEIGHT];
        bool[,] temp = new bool[WIDTH, HEIGHT];
    
        public override bool Get(int i, int j) => field[i, j];
    
        public override void Set(int i, int j, bool value) => field[i, j] = value;
    
        public override void Step()
        {
            for (int i = 1; i < WIDTH - 1; i++)
            {
                for (int j = 1; j < HEIGHT - 1; j++)
                {  // первый проход: вычисляем будущее состоянее
                    bool isAlive = field[i, j];
                    int numNeigbours = 0;
                    if (field[i - 1, j - 1]) numNeigbours++;
                    if (field[i - 1, j]) numNeigbours++;
                    if (field[i - 1, j + 1]) numNeigbours++;
                    if (field[i, j - 1]) numNeigbours++;
                    if (field[i, j + 1]) numNeigbours++;
                    if (field[i + 1, j - 1]) numNeigbours++;
                    if (field[i + 1, j]) numNeigbours++;
                    if (field[i + 1, j + 1]) numNeigbours++;
                    bool keepAlive = isAlive && (numNeigbours == 2 || numNeigbours == 3);
                    bool makeNewLive = !isAlive && numNeigbours == 3;
                    temp[i, j] = keepAlive | makeNewLive;
                }
            }
    
            for (int i = 1; i < WIDTH - 1; i++)
                for (int j = 1; j < HEIGHT - 1; j++)
                    // второй проход: копируем вычисленное состояние в текущее
                    field[i, j] = temp[i, j];
                }
            }
        }
    }
    


    Результат работы:

    Алгоритм: SimpleLife
    Время работы: 40 секунд
    Скорость работы: 25 шагов в секунду
    

    Исходный код: SimpleLife.cs

    2. Добавляем байты


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

    — Вместо двумерного массива boolean создадим одномерный массив байт, в котором живая клетка представлена значением 1, а мертвая — 0.

    — Вместо восьми проверок будем суммировать байты соседей текущей клетки, тогда их сумма и будет равна числу живых соседей.

    — Во временный массив будем писать сумму клеток, отложив проверку на второй проход:

    LifeBytes
    public class LifeBytes : LifeJourney
    {
        byte[] field = new byte[WIDTH * HEIGHT];
        byte[] temp = new byte[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) => field[j * WIDTH + i] = (byte)(value ? 1 : 0);
    
        public override void Step()
        {
            for (int i = 1; i < WIDTH - 1; i++)
                for (int j = 1; j < HEIGHT - 1; j++)
                {  // считаем число соседей для текущей клетки и кладем в temp[pos]
                    int pos = j * WIDTH + i;
                    temp[pos] = (byte)(
                        field[pos - WIDTH - 1] + field[pos - WIDTH] + field[pos - WIDTH + 1] +
                        field[pos - 1] + field[pos + 1] +
                        field[pos + WIDTH - 1] + field[pos + WIDTH] + field[pos + WIDTH + 1]);
                }
    
            for (int i = 1; i < WIDTH; i++)
                for (int j = 1; j < HEIGHT; j++)
                {  // обновляем текущее состояние
                    // по числу соседей и прошлому состоянию клетки
                    int pos = j * WIDTH + i;
                    bool keepAlive = field[pos] == 1 && (temp[pos] == 2 || temp[pos] == 3);
                    bool makeNewLife = field[pos] == 0 && temp[pos] == 3;
                    field[pos] = (byte)(makeNewLife | keepAlive ? 1 : 0);
                }
        }
    }
    


    Проверяем:

    Алгоритм: LifeBytes
    Время работы: 25 секунд
    Скорость работы: 40 шагов в секунду
    Ускорение от предыдущей версии: 1.6
    Ускорение от первой версии: 1.6
    

    Исходный код: LifeBytes.cs

    3. Добавляем восьмибайтные слова


    Заметим, что при первом проходе для всех байт выполняются одни и те же восемь сложений, что
    наводит на мысль вместо обработки одного байта сразу обрабатывать 8 байтов, так как для многих инструкций, работающих с байтом, на современных процессорах есть аналогичные инструкции, работающие с двух-, четырех- и восьмибайтными словами. В нашем случае сложение восьмибайитных слов будет давать такой же результат, что и восемь сложений соседних байт подряд:

    image

    Заметим, что это не всегда верно, так как если при арифметических операциях с байтами происходит переполнение, то аналогичные операции с длинными словами будут давать неправильный результат. Однако нам повезло, и максимальное значение, которое мы можем получить при сложении в байте, равно восьми, и переполнение у нас случиться не может.
    Чтобы заменить операции над байтами операциями над восьмибайтными словами, нам надо воспользоваться доступной в c# арифметикой указателей:

    — пометить класс как unsafe;
    — получить указатели на оба массива;
    — преобразовывать указатель на байт в указатель на ulong

    вот так
    fixed (byte* fieldPtr = field, tempPtr = temp)
    {
        for (int i = WIDTH + 1; i < WIDTH * HEIGHT - WIDTH - 1; i += 8)
        {
            ulong* ptr = (ulong*)(tempPtr + i);
            *ptr += *(ulong*)(fieldPtr + i - WIDTH - 1);
            *ptr += *(ulong*)(fieldPtr + i - WIDTH);
            *ptr += *(ulong*)(fieldPtr + i - WIDTH + 1);
            *ptr += *(ulong*)(fieldPtr + i - 1);
            *ptr += *(ulong*)(fieldPtr + i + 1);
            *ptr += *(ulong*)(fieldPtr + i + WIDTH - 1);
            *ptr += *(ulong*)(fieldPtr + i + WIDTH);
            *ptr += *(ulong*)(fieldPtr + i + WIDTH + 1);
        }
        ...
    }
    


    Меряем производительность, и…

    Алгоритм: LongLife
    Время работы: 10 секунд
    Скорость работы: 100 шагов в секунду
    Ускорение от предыдущей версии: 2.5
    Ускорение от первой версии: 4
    

    Исходный код: LongLife.cs

    4. Добавляем поиск в таблице


    Мы неплохо оптимизировали первый проход, однако во втором проходе на каждый байт выполняются несколько проверок, от чего мы хотим избавиться. Стандартная оптимизация в таких случаях — lookup table, когда результат для всех комбинаций входных данных вычисляется заранее и кладется в таблицу. Наши входные данные — текущее состояние клетки (один байт в оригинальном массиве) и количество соседей (один байт во временном массиве). Мы могли бы вычислить таблицу для всех комбинаций этих байт, что нам даст размер таблицы 16 килобайт, однако мы можем сократить размер таблицы, заодно упростив код. Идея состоит в том, что количество соседей от 0 до 8 не занимает целый байт, а умещается в младшие три бита (на самом деле, в четыре, но 8 соседей и 0 соседей дают одинаковый эффект, поэтому мы игнорируем четвертый бит в количестве соседей). Поэтому мы закодируем состояние текущей клетки в четвертом бите этого же байта, и наша таблица будет длиной 16 байт, из которых только три значения равны единице. Значения, равные единице, соответствуют индексам, кодирующим мертвую клетку с тремя соседами или живую клетку с двумя или тремя соседями:

    image

    Сам код получается не сильно сложнее
    public unsafe class LifeIsLookingUp : LifeJourney
    {
        static byte[] alivePerNeighbours = new byte[256];
        byte[] field = new byte[WIDTH * HEIGHT];
        byte[] temp = new byte[WIDTH * HEIGHT];
    
        public LifeIsLookingUp()
        {
            alivePerNeighbours[3] = 1;
            alivePerNeighbours[8 + 2] = 1;
            alivePerNeighbours[8 + 3] = 1;
        }
        ...
        public override void Step()
        {
            fixed (byte* fieldPtr = field, tempPtr = temp)
            {
                ...
    
                // второй прогон использует таблицу!
                for (int i = WIDTH; i < WIDTH * HEIGHT - WIDTH; i++)
                {
                    byte neighbours = (byte)((tempPtr[i] & 7) | (fieldPtr[i] << 3));
                    fieldPtr[i] = alivePerNeighbours[neighbours];
                }
                ...
        }
    }
    


    В итоге получаем ускорение почти в два раза:

    Алгоритм: LifeIsLookingUp
    Время работы: 5.5 секунд
    Скорость работы: 180 шагов в секунду
    Ускорение от предыдущей версии: 1.8
    Ускорение от первой версии: 7.2
    

    Исходный код: LifeIsLookingUp.cs

    5. Добавляем битовую магию


    На этот раз забудем предыдущую оптимизацию и заново оптимизируем второй шаг, чтобы не только избавиться от условных выражений, но, как и в первом шаге, вычислять по восемь клеток за раз. Нам надо, фактически, придумать битовую функцию, которая будет получать те же самые результаты, что и lookup table из предыдущего шага. Те, кто изучал булевую алгебру, знают, что для любой таблицы истинности (а наша lookup table именно ей и является) можно написать соответствующую булеву функцию, хотя она и может получиться сложной. Однако существует метод диаграммы Карно, позволяющий из таблицы истинности получить сильно оптимизированную булеву функцию простым и наглядным способом. Этот метод отлично применим и к нашей таблице; однако, учитывая, что в ней всего 16 входных значений, при некотором везении опыте можно подобрать нужную функцию перебором.
    Опустим промежуточные выкладки и приведем:

    получившийся код
    for (int i = WIDTH; i < WIDTH * HEIGHT - WIDTH; i ++)
    {
        byte neighbours = tempPtr[i];
        byte alive = fieldPtr[i];
        neighbours &= (byte)0b00000111;
        byte aliveAndNeighbours = ((neighbours & ~(byte)0b00000001) >> 1) | (alive << 2);
        aliveAndNeighbours ^= (byte)~0b00000101;
        aliveAndNeighbours &= (aliveAndNeighbours >> 2);
        aliveAndNeighbours &= (aliveAndNeighbours >> 1);
        aliveAndNeighbours &= (byte)0b00000001;
    
        ulong makeNewLife = neighbours | (alive << 3);
        makeNewLife ^= (byte)~0b00000011;
        makeNewLife &= (makeNewLife >> 2);
        makeNewLife &= (makeNewLife >> 1);
        makeNewLife &= (byte)0b00000001;
         
        fieldPtr[i] = aliveAndNeighbours | makeNewLife;
    }
    


    В данном виде этот код не особо лучше поиска по таблице, поскольку делает слишком много операций на байт. Однако он позволяет перейти от побайтовых вычислений к обработке 8 байтов за раз:

    Аналогичный код для ulong вместо байт
    for (int i = WIDTH; i < WIDTH * HEIGHT - WIDTH; i += 8)
    {
        ulong neighbours = *(ulong*)(tempPtr + i);
        ulong alive = *(ulong*)(fieldPtr + i);
        neighbours &= 0b00000111_00000111_00000111_00000111_00000111_00000111_00000111_00000111ul;
    
        ulong aliveAndNeighbours = ((neighbours & ~0b00000001_00000001_00000001_00000001_00000001_00000001_00000001_00000001ul) >> 1) | (alive << 2);
        aliveAndNeighbours ^= ~0b00000101_00000101_00000101_00000101_00000101_00000101_00000101_00000101ul;
        aliveAndNeighbours &= (aliveAndNeighbours >> 2);
        aliveAndNeighbours &= (aliveAndNeighbours >> 1);
        aliveAndNeighbours &= 0b00000001_00000001_00000001_00000001_00000001_00000001_00000001_00000001ul;
    
        ulong makeNewLife = neighbours | (alive << 3);
        makeNewLife ^= ~0b00000011_00000011_00000011_00000011_00000011_00000011_00000011_00000011ul;
        makeNewLife &= (makeNewLife >> 2);
        makeNewLife &= (makeNewLife >> 1);
        makeNewLife &= 0b00000001_00000001_00000001_00000001_00000001_00000001_00000001_00000001ul;
    
        *(ulong*)(fieldPtr + i) = aliveAndNeighbours | makeNewLife;
    }
    


    Код стал совершенно непонятным, однако работает почти в два раза быстрее предыдущей версии:

    Алгоритм: LifeInBits
    Время работы: 3.3 секунды
    Скорость работы: 300 шагов в секунду
    Ускорение от предыдущей версии: 1.7
    Ускорение от первой версии: 12
    

    Исходный код: LifeInBits.cs

    6. Храним по две клетки на байт


    Последняя оптимизация такого типа логично вытекает из предыдущих: до сих пор мы хранили по одной клетке на байт, обрабатывая по восемь байтов за один раз, но во всех вычислениях мы на самом деле оперировали только четырьмя младшими битами в байте, так как старшие четыре бита всегда были нули. Теперь мы будем хранить по две клетки на один байт: одну в младших четырех битах, другую — в старших. Временный массив, хранящий число соседей, также будет хранить количество соседей независимо в младших и в старших четырех битах. Выгода в том, что мы все равно будем обрабатывать по восемь байт за раз, но в этот раз в них будет не восемь, а уже шестнадцать клеток! Потенциально это может привести к более чем двукратному ускорению, так как, кроме уменьшения в два раза количества операций, мы также уменьшаем в два раза размер используемой памяти, что позволит лучше утилизировать кеш процессора.
    В самом алгоритме при втором прогоне меняются только константы и границы итерирования, но при первом прогоне из-за упаковки по две клетки в байт приходится приходится применять логические сдвиги на 4 и 60 бит влево и вправо, что делает код более запутанным:

    Две клетки в байте
    public override void Step()
    {  
        fixed (byte* fieldPtr = field, tempPtr = temp)
        {  // прежде всего обнуляем временный массив
            for (int i = 0; i < temp.Length; i += 8)  *(ulong*)(tempPtr + i) = 0;
            // теперь вместо сдвига указателей применяются арифметические сдвиги
            for (int i = WIDTH; i < WIDTH * HEIGHT / 2; i += 8)
            {
                ulong* ptr = (ulong*)(tempPtr + i);
    
                ulong src1 = *(ulong*)(fieldPtr + i - WIDTH / 2);
                ulong src2 = *(ulong*)(fieldPtr + i);
                ulong src3 = *(ulong*)(fieldPtr + i + WIDTH / 2);
    
                ulong src4 = *(ulong*)(fieldPtr + i - WIDTH / 2 - 8);
                ulong src5 = *(ulong*)(fieldPtr + i - 8);
                ulong src6 = *(ulong*)(fieldPtr + i + WIDTH / 2 - 8);
    
                ulong src7 = *(ulong*)(fieldPtr + i - WIDTH / 2 + 8);
                ulong src8 = *(ulong*)(fieldPtr + i + 8);
                ulong src9 = *(ulong*)(fieldPtr + i + WIDTH / 2 + 8);
    
                *ptr += (src1 << 4) + src1 + (src1 >> 4);
                *ptr += (src2 << 4) + (src2 >> 4);
                *ptr += (src3 << 4) + src3 + (src3 >> 4);
    
                *ptr += (src4 >> 60) + (src5 >> 60) + (src6 >> 60);
                *ptr += (src7 << 60) + (src8 << 60) + (src9 << 60);
            }
            // здесь поменялись только константы
            for (int i = WIDTH; i < WIDTH * HEIGHT / 2; i += 8)
            {
                ulong neighbours = *(ulong*)(tempPtr + i);
                ulong alive = *(ulong*)(fieldPtr + i);
                neighbours &= 0b0111_0111_0111_0111_0111_0111_0111_0111_0111_0111_0111_0111_0111_0111_0111_0111ul;
    
                ulong keepAlive = ((neighbours & ~0b0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001ul) >> 1) | (alive << 2);
                keepAlive ^= ~0b0101_0101_0101_0101_0101_0101_0101_0101_0101_0101_0101_0101_0101_0101_0101_0101ul;
                keepAlive &= (keepAlive >> 2);
                keepAlive &= (keepAlive >> 1);
                keepAlive &= 0b0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001ul;
    
                ulong makeNewLife = neighbours | (alive << 3);
                makeNewLife ^= ~0b0011_0011_0011_0011_0011_0011_0011_0011_0011_0011_0011_0011_0011_0011_0011_0011ul;
                makeNewLife &= (makeNewLife >> 2);
                makeNewLife &= (makeNewLife >> 1);
                makeNewLife &= 0b0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001_0001ul;
    
                *(ulong*)(fieldPtr + i) = keepAlive | makeNewLife;
            }
    
        }
        // В конце "убиваем" клетки на левой и правой границе, так как
        // предыдущие манипуляции могли их поменять
        for (int j = 0; j < HEIGHT; j++)
        {
            Set(0, j, false);
            Set(WIDTH - 1, j, false);
        }
    
    }
    


    А вот реализация методов get и set усложняется. К счастью, эти методы практически не влияют на производительность, так что можно не слишком беспокоиться по этому поводу. Также обратите внимание на технический трюк: для корректной работы алгоритма пришлось добавить по одной пустой строчке в начало и в конец массива, чтобы избежать проверок на выход за границы массива.

    get и set
    public unsafe class LifeIsABitMagic : LifeJourney
    {
        byte[] field = new byte[WIDTH + WIDTH * HEIGHT / 2];
        byte[] temp = new byte[WIDTH + WIDTH * HEIGHT / 2];
    
        public override bool Get(int i, int j)
        {
            int pos = WIDTH / 2 + j * (WIDTH / 2) + (i / 2);
            if (i % 2 == 1) return (field[pos] & 0x10) == 0x10;
            else return (field[pos] & 1) == 1;
        }
    
        public override void Set(int i, int j, bool val)
        {
            int pos = WIDTH / 2 + j * (WIDTH / 2) + (i / 2);
            if (i % 2 == 1)
            {
                if (val) field[pos] |= 0x10;
                else field[pos] &= (0xFF & ~0x10);
            }
            else
            {
                if (val) field[pos] |= 0x1;
                else field[pos] &= (0xFF & ~0x1);
            }
        }
        ...
    }
    


    Вот результат:

    Алгоритм: LifeIsABitMagic
    Время работы: 1.3 секунды
    Скорость работы: 770 шагов в секунду
    Ускорение от предыдущей версии: 2.6
    Ускорение от первой версии: 31
    

    Исходный код: LifeIsABitMagic.cs

    7. Используем SIMD-инструкции процессора


    Каждая последующая оптимизация дается нам все большим трудом, так что в этот раз мы пойдем другим путем и используем, пожалуй, самый мощный из доступных на сегодняшний момент способов оптимизации: SIMD-инструкции, а точнее, набор инструкций AVX2, доступный на большинстве современных процессоров Intel и AMD, и позволяющий производить операции над 32 байтами за раз! Этот способ не всегда применим, однако наш случай (работа с байтами и отсутствие ветвлений) идеально ложится на идеологию SIMD, поэтому мы можем ожидать значительного улучшения производительности. Еще несколько лет назад это было доступно только в языках низкого уровня. Нас бы это не остановило: ради оптимизации мы бы скомпилировали библиотеку на C++ и использовали из C# через механизм P/Invoke. Однако буквально год назад в .NET Core появилась встроенная поддержка этого набора инструкций, об этом была даже статья на Хабре. Так что теперь мы можем использовать эту «тяжелую артиллерию» напрямую в C#! За основу возьмем предпоследнюю версию алгоритма LifeInBits, хранящую одну клетку на байт (по причинам, выходящим за рамки этой статьи), и заменим ручную манипуляцию байтами, битами и восьмибайтными словами на соответствующие AVX2-инструкции. При этом, как ни странно, код даже стал проще и понятней!

    простой и понятный код
    public AdvancedLifeExtensions()
    {  // проверим, что мы не на Pentium III
        if (!Avx2.IsSupported) throw new NotImplementedException("Not in this life!!!");
    }
    
    public override void Step()
    {
        fixed (byte* fieldPtr = field, tempPtr = temp)
        {
            Vector256<byte> zero = Vector256<byte>.Zero; // тут 32 нуля
            for (int i = 0; i < WIDTH * HEIGHT; i += 32)
            {
                Avx.Store(tempPtr + i, zero);
            }
    
            for (int i = WIDTH; i < WIDTH * HEIGHT - WIDTH; i += 32)
            {
                Vector256<byte> src1 = Avx.LoadVector256(fieldPtr + i - WIDTH - 1);
                Vector256<byte> src2 = Avx.LoadVector256(fieldPtr + i - WIDTH);
                Vector256<byte> sum1 = Avx2.Add(src1, src2);
                Vector256<byte> src3 = Avx.LoadVector256(fieldPtr + i - WIDTH + 1);
                Vector256<byte> src4 = Avx.LoadVector256(fieldPtr + i - 1);
                Vector256<byte> sum2 = Avx2.Add(src3, src4);
                Vector256<byte> src5 = Avx.LoadVector256(fieldPtr + i + 1);
                Vector256<byte> src6 = Avx.LoadVector256(fieldPtr + i + WIDTH - 1);
                Vector256<byte> sum3 = Avx2.Add(src5, src6);
                Vector256<byte> src7 = Avx.LoadVector256(fieldPtr + i + WIDTH);
                Vector256<byte> src8 = Avx.LoadVector256(fieldPtr + i + WIDTH + 1);
                Vector256<byte> sum4 = Avx2.Add(src7, src8);
    
                Vector256<byte> sum5 = Avx2.Add(sum1, sum2);
                Vector256<byte> sum6 = Avx2.Add(sum3, sum4);
                Vector256<byte> sum = Avx2.Add(sum5, sum6);
    
                Avx.Store(tempPtr + i, sum);
            }
    
            for (int i = WIDTH; i < WIDTH * HEIGHT - WIDTH; i += 32)
            {
                Vector256<byte> neighbours = Avx.LoadVector256(tempPtr + i);
                Vector256<byte> alive = Avx.LoadVector256(fieldPtr + i);
    
                // в v_1 тридцать два байта единичек
                Vector256<byte> isAlive = Avx2.CompareEqual(alive, v_1);
                // в v_2 тридцать два байта двоек
                Vector256<byte> isTwoNeighbours = Avx2.CompareEqual(neighbours, v_2);
                // в v_3 тридцать два байта троек
                Vector256<byte> isThreeNeighbours = Avx2.CompareEqual(neighbours, v_3);
    
                Vector256<byte> isTwoOrThreeNeighbours = Avx2.Or(isTwoNeighbours, isThreeNeighbours);
                Vector256<byte> aliveAndNeighbours = Avx2.And(isAlive, isTwoOrThreeNeighbours);
    
                Vector256<byte> shouldBeAlive = Avx2.Or(aliveAndNeighbours, isThreeNeighbours);
                shouldBeAlive = Avx2.And(shouldBeAlive, v_1);
    
                Avx2.Store(fieldPtr + i, shouldBeAlive);
            }
    
        }
    
        for (int j = 1; j < HEIGHT - 1; j++)
        {
            field[j * WIDTH] = 0;
            field[j * WIDTH + WIDTH - 1] = 0;
        }
    
    }
    


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

    Алгоритм: AdvancedLifeExtensions
    Время работы: 0.4 секунды
    Скорость работы: 2500 шагов в секунду
    Ускорение от предыдущей версии: 3.2
    Ускорение от первой версии: 100
    

    Исходный код: AdvancedLifeExtensions.cs

    Это все?


    Для полноты картины надо упомянуть еще две оптимизации, которых мы не коснулись:

    1. Перенос вычислений на видеокарту — поскольку алгоритм хорошо ложится на логику SIMD, можно ожидать ускорения еще на порядок. Именно на нем исследователи игры «Жизнь» (да, есть и такие!) ищут новые интересные фигуры методом перебора. К сожалению, код для обработки данных на видеокарте пока еще невозможно написать на .NET.
    2. Сложность всех рассмотренных алгоритмов линейна по времени и площади поля. Существует алгоритм Hashlife, в некоторых ситуациях имеющий логарифмическую сложность по времени и площади! Именно этот алгоритм используется для симуляции огромных систем на миллионы и миллиарды итераций. Тем не менее, существуют плохие начальные условия, при которых этот алгоритм будет значительно медленнее классических, как минимум, на начальном этапе.

    JavaScript


    Наконец-то мы дошли до самого интересного: можно ли эти оптимизации перенести в JavaScript?

    К сожалению, SIMD-версию использовать невозможно, поскольку AVX2 туда еще не завезли. Однако, как ни удивительно, предпоследнюю версию с битовой магией и упаковкой по две клетки в один байт вполне можно использовать, правда не восьмибайтный вариант, а только четырехбайтный.

    Трюк здесь в том, что в JavaScript есть специальные классы, позволяющие работать с массивом байт одновременно и как с байтами, и как с числами: UInt8Array и UInt32Array. При этом можно перенести код практически дословно (с поправкой на обработку четырех байт вместо восьми) и надеяться, что JIT-компилятор яваскриптового движка сможет обработать нашу битовую арифметику без конвертации в числа с плавающей точкой.

    Код на JavaScript
    class LifeField {
        constructor() {
            this.field = new ArrayBuffer(LifeField.WIDTH + LifeField.WIDTH * LifeField.HEIGHT / 2);
            this.temp = new ArrayBuffer(LifeField.WIDTH + LifeField.WIDTH * LifeField.HEIGHT / 2);
            this.fieldBytes = new Uint8Array(this.field);
            this.tempBytes = new Uint8Array(this.temp);
            this.fieldInts = new Uint32Array(this.field);
            this.tempInts = new Uint32Array(this.temp);
        }
    
        get(x, y) { 
            const pos = LifeField.WIDTH / 2 + y * (LifeField.WIDTH / 2) + (x >> 1);
            if ((x & 1) == 1) return (this.fieldBytes[pos] & 0x10) == 0x10;
            else return (this.fieldBytes[pos] & 1) == 1;
        }
    
        set(x, y, val) { ... } //аналогично
        
        step() {
            for(var i = 0; i < this.tempInts.length; i++) this.tempInts[i] = 0;
    
            for (var j = LifeField.WIDTH; j < LifeField.WIDTH * LifeField.HEIGHT / 2; j += 4)
            {
                const i = j / 4;
    
                const src1 = this.fieldInts[i - LifeField.WIDTH / 8];
                const src2 = this.fieldInts[i];
                const src3 = this.fieldInts[i + LifeField.WIDTH / 8];
    
                const src4 = this.fieldInts[i - LifeField.WIDTH / 8 - 1];
                const src5 = this.fieldInts[i - 1];
                const src6 = this.fieldInts[i + LifeField.WIDTH / 8 - 1];
    
                const src7 = this.fieldInts[i - LifeField.WIDTH / 8 + 1];
                const src8 = this.fieldInts[i + 1];
                const src9 = this.fieldInts[i + LifeField.WIDTH / 8 + 1];
    
                this.tempInts[i] += (src1 << 4) + src1 + (src1 >> 4);
                this.tempInts[i] += (src2 << 4) + (src2 >> 4);
                this.tempInts[i] += (src3 << 4) + src3 + (src3 >> 4);
    
                this.tempInts[i] += (src4 >> 28) + (src5 >> 28) + (src6 >> 28);
                this.tempInts[i] += (src7 << 28) + (src8 << 28) + (src9 << 28);
            }
    
            for (var j = LifeField.WIDTH; j < LifeField.WIDTH * LifeField.HEIGHT / 2; j += 4) {
                const i = j / 4;
                const neighbours = this.tempInts[i] & 0x77777777;
                const alive = this.fieldInts[i];
    
                var keepAlive = ((neighbours & ~0x11111111) >> 1) | (alive << 2);
                keepAlive ^= ~0x55555555;
                keepAlive &= (keepAlive >> 2);
                keepAlive &= (keepAlive >> 1);
                keepAlive &= 0x11111111;
    
                var makeNewLife = neighbours | (alive << 3);
                makeNewLife ^= ~0x33333333;
                makeNewLife &= (makeNewLife >> 2);
                makeNewLife &= (makeNewLife >> 1);
                makeNewLife &= 0x11111111;
    
                this.fieldInts[i] = keepAlive | makeNewLife;
            }
    
            for(var y = 1; y < LifeField.WIDTH - 1; y++) {
                this.set(0, y, false);
                this.set(LifeField.WIDTH - 1, y, false);
            }
        }
        ...
    }
    LifeField.WIDTH = 1920;
    LifeField.HEIGHT = 1080;
    


    Вот результат:

    Алгоритм: LifeIsABitMagic (JavaScript 32 bit), вне конкурса
    Время работы: 5 секунд
    Скорость работы: 200 шагов в секунду
    Ускорение от предыдущей версии: -
    Ускорение от первой версии: 8
    

    Полный код в файле lifefield.js

    В заключение сводная таблица со всеми алгоритмами:

    image

    Онлайн-игра


    Напоследок самое интересное: на основе этого алгоритма была написана онлайн-игра, стабильно быстро работающая на поле размера 1920x1080 (Full HD) при любой начальной конфигурации:

    играть в симуляцию игры «Жизнь» image

    Исходные коды опубликованы на гитхабе.

    Средняя зарплата в IT

    113 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 5 444 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 121

      +4

      Интересно, что будет если обрабатывать только клетки с изменившимся состоянием и их соседей? Исходя из правил в большинстве случаем большую часть времени большая часть клеток находится в неизменном состоянии — так что можно их эффективно обсчитывать за 0 тактов.

        +2
        Можно даже дальше пойти: разбить плоскость на квадраты и кешировать результат итераций для каждого квадрата. Собственно, эта идея лежит в основе того самого Hashlife.
          0

          В моей реализации почти так и происходит. Правда обрабатываются просто окрестности всех живых клеток.
          Координаты каждой живой клетки упаковываются в int и засовываются в Set. Размер инта позволяет таким образом иметь тороидальное поле 64к*64к.


          lightln2 может объединимся?


          Кому интересно поковырять через консоль, это можно сделать так:


          state = new Set
          for( let x = -100; x < 100; ++x ) {
              for( let y = -100; y < 100; ++y ) {
                  if( Math.random() > .5 ) state.add( $mol_coord_pack( x , y ) )
              }
          }
          $hyoo_life.Root(0).Map().state( state )
            +3
            $mol — я чуть кофе на себя не пролил
            +1
            Я провел такой эксперимент, ускорение получилось в 3.5 раза для рандомной начальной конфигурации (но, конечно, для маленьких и статичных конфигураций ускорение может быть в сотни и тысячи раз)
            Обсуждение и код в этой ветке. Может быть, кто-то сможет еще больше ускорить.
            Я прошу прощения, нам с самого начала надо было вести обсуждение под Вашим комментарием (теперь, наверно, не перенести).
            +4
            Вот отличный алгоритм на случай если надо будет ускорить сильнее.
              0
              да, это тот самый Hashlife, я его упомянул в статье. Интересно было бы попробовать применить вышеописанные оптимизации к нему (исключительно для саморазвития: эту игру люди исследуют уже 50 лет, и все, что можно было оптимизировать, думаю, уже давно соптимизировали)
                0

                Как это всё заоптимизировали? Ещё квантовый процессор не поменяли, наверно :)

              +1
              Была похожая статья
              habr.com/en/post/455958

              Вообще, интересно было бы прикрутить GPU, через WebGL.
                +2
                  +2

                  И SIMD через wasm

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

                      В FF 78 nightly можно уже без флагов пробовать, правда если процессор x64 с поддержкой SSE 4.1+. В остальных если есть, то пока еще под флагами.

                  0

                  Зачем поле делать 1920х1080, если оно даже в полноэкранном режиме не влезет в такой же монитор из-за верхней панели? Оптимизируйте размер поля так чтоб только на видимой части экрана было

                    0
                    А как лучше эту проблему решить? Просто уменьшить размер поля на высоту панели? или скриптом проверять размер экрана и скейлить канвас? или можно как-то подобрать значение meta name=«viewport», чтобы браузер сам все за нас сделал? Я имеюю в виду даже не технический аспект, а юзабилити — какой способ даст наиболее логичное с точки зрения пользователя поведение?
                      +1
                      Картинка должна остаться пиксель в пиксель, чтоб не получить проблемы растяжения/сжатия. С точки зрения пользователя поле должно идеально вписываться в экран) Но есть проблемы:
                      1) редкий пользователь знает о полноэкранном режиме.
                      2) устройство можно повернуть, размер экрана изменится
                      3) браузер можно ресайзить
                      4) размеры под поле заранее тоже не угадаете — у всех разные панели сверху/снизу и в разных браузерах даже верхняя панель может быть разной (у меня на ней только 2 кнопки из 4 нормально отображаются)

                      Я бы сделал стандартное поле каким-то невыпирающим фиксированным, типа 800х600 и разрешил указывать свои размеры или по кнопке подгонять под текущий экран. Но это так себе решение.

                      По нажатию на «random pattern» я хочу видеть реально random, а не поле для ввода числа руками. И незачем это прятать в отдельное окно, если места на экране пустого уйма — покажите мне сид сразу. А переключение скорости мне вообще непонятно. 2х-50х примерно на одинаковой скорости работают, только на 50 заметно больше кадров пропускает. На не самом слабом компе эти переключатели не имеют смысла из-за размеров поля. Дайте посмотреть на это на поле поменьше/побольше, на мой вкус. Мне интересно было бы глянуть на реальный х50, пусть и на поле 600х600.
                        0
                        Спасибо за фидбек, у меня нет опыта в UI, и для меня такие вещи не очевидны.
                        2х-50х примерно на одинаковой скорости работают

                        А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
                          0
                          Firefox/Ubuntu, выше 120 не поднимается (это соответствует 25% нагрузке на процессор т.е. одному ядру из моих 4). Процессор FX-4170
                            +1
                            Я на ноутбуке (Windows 10, Intel Core i7-6700HQ) скачал Firefox и проверил количество итераций в секунду на всех скоростях на всех трех браузерах:
                            image
                            Я так понимаю, у них разные движки, но все равно такая разница удивительна.
                            0
                            Firefox 56/Win7 на 50х максимально 88 итераций в секунду. 25% нагрузки на процессор — 1 ядро из 4 Intel Q8300
                          +1
                          С точки зрения пользователя хочется ещё иметь возможность масштабировать поле.
                          Средствами браузера не очень удобно, так как пропадает доступность панели управления.
                          У меня например случайно создалась довольно крупная стабильная структура, хотелось рассмотреть вблизи и пошагово, оказалось не очень удобно. Спас пробел, который работает как шаг, за это спасибо.

                          Кстати интересно, а есть каталог стабильных структур?
                            +1
                            Вот, например: List_of_common_still_lifes
                              0

                              А в машиночитаемом виде есть такой?

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

                      Можно еще избавиться от операции копирования из temp-буфера, сделав 2 буфера, и переключаться между ними поочередно

                        0
                        Согласен, это тоже классическая оптимизация, которую было бы неплохо применить. Я, честно говоря, поленился: суммарно оба массива не превышают одного мегабайта, и должны помещаться в кеш третьего уровня, так что копирование должно быть быстрым по сравнению с довольно большим количеством логических операций. Но так как эта оптимизация не усложняет код, то кажется логичным ее применить, даже если она даст только 10% выигрыша.
                          +1
                          Копирование одного мегабайта даже в рамках кеша, это много)
                          0
                          Можете, пожалуйста, чуть подробнее объяснить?
                            0

                            Пусть есть 2 одинаковых массива A и B.
                            Будем считать, что ссылка x означает предыдущую итерацию, а y — следующую.
                            Пусть вначале x указывает на A, а y на B.
                            На каждом шаге выполняем следующие действия:


                            1. Зачитываем данные из x, пишем в y.
                            2. Рендерим на экран содержимое y.
                            3. Выполняем операцию swap(x, y)
                              0
                              Получается подход будет работать, только если за проход мы проставляем вообще все клетки, даже те, что по идее не изменились. Потому что информация в массиве, в который ведется запись, отстает на шаг.
                                0

                                в смысле? одна итерация алгоритма все равно требует сканирования всего поля

                          +1
                          Сейчас проверил, переключение буфера вместо копирования дает ускорение примерно в 1.15 раз (на 13%)
                          0
                          Интересно, насколько известная Golly golly.sourceforge.net (C++) с алгоритмом QuickLife и другими обгоняет эту C# программу (даже без учёта очень быстрого алгоритма HashLife, реализованного в Golly и дающего большое преимущество в случае регулярных паттернов на поле).
                            0
                            Я, когда готовил статью и искал интересные шаблоны, работал с Golly, но в основном на Hashlife. Я сейчас мельком посмотрел на код qlifealgo.cpp, и там тоже огромное количество оптимизаций, при чем они все равно используют quadtree, так что его скорость тоже растет с улучшением регулярности. Хотя SIMD они не используют. Я сейчас запустил его на рандомно заполненном поле размера 1920x1080 с коэффициентом 0.5 (то есть, примерно половина клеток — живые, половина — мертвые), и за первую секунду он обработал 1000 итераций, за вторую — уже 10000, и на статической картинке скорость стабилизировалась где-то на 50000 в секунду. На картинке из КПДВ он работает стабильно примерно со скоростью 5000 в секунду.
                            +7
                            В 1995 году во время олимпиады по математике-информатике я познакомился с парнем из Черноголовки, который предложил свою оптимизацию проходов поля игры Жизнь. У них в школе это было типа внутреннего соревнования, в котором он победил.
                            Короче, подробности я конечно не вспомню, но поле 640х480 на 386 проце делалось около 50 итераций в секунду. Это я запомнил, т.к. на экране «светофоры» замирали в одном положении, либо горизонтальном, либо вертикальном, т.к. за время прохождения строчной развертки ЭЛТ монитора программа успевала пройти (как минимум) две итерации.
                            Забавно то, что уже тогда основной эффект был достигнут переносом вычислений в видеопамять.
                            Я тут прикинул на коленке, поле было меньше в 6.75 раз, процессор медленнее в 100 раз (4ГГц сегодняшних процессоров против 40 МГц на 386 в режиме турбо).
                            AdvancedLifeExtensions на таком поле выдал бы 2500х6.75=16875 итераций в секунду, но в переводе на MIPSы 1995 года — в 100 раз меньше, 169 итераций в секунду.
                            Алгоритм 1995 года выдавал 50 итераций в секунду.
                            За 25 лет улучшение в 3.375 раз (смайлик).
                            Прошу, не воспринимайте этот пост слишком уж серьезно. Это больше про башковитых парней из подмосковного наукограда. Их же там много было раз существовало внутреннее соревнование.
                              +4
                              Где-то в то же время (может на 2-3 года позже) довелось мне столкнуться с разочарованием.
                              Мы с другом были фанатами программирования, что было несколько необычно для нашей почти сельской местности. Благо повезло — учились в экспериментальной гимназии и компьютеры у нас в гимназии были. Не 386-е, конечно (о них мы только в журналах читали), а Поиск-2, но на то время и они казались нам неверояными. Где-то в 1997-м завезли нам один 286-й, но за него никого кроме учителей не пускали.
                              Мы постоянно зависали после уроков в компьютерном классе и что-то писали. Расходились по домам со списком задач, которые необходимо решить и возвращались с листочками, исписанными программами, которые печатали и решали чей вариант решения лучше.
                              В общем участвовали в районной олимпиаде по программированию, где участников было ещё несколько человек помимо нас двоих. Была надежда попасть на областную олимпиаду.
                              В области наши работы завернули под предлогом, что нам помогали учителя. Видимо слишком выбивались работы из обычного районного уровня.
                              Обидно было.
                                +1

                                Ну так а сейчас-то как? Пошли по пути программиста профессионально или нет?

                                  +8
                                  Отучился не по профилю (далековато до области было, а поблизости — разве что пединститут на учителя информатики), на экономиста. В кабинете информатики и там был завсегдатаем, на кафедре ИКТ был как родной. Деньги зарабатывал на расчётках по информатике и курсовых по разным предметам.
                                  Для диплома написал программу для вычисления кредитоспособности предприятия исходя из годовых отчётов.
                                  По специальности не работал. Сразу компы год собирал, потом фотографом пару лет отработал. На обоих местах писал софт для автоматизации рабочих мест. Недавно был в фотосалоне — до сих пор ребята на старой винде сидят и древним фотошопом пользуются, потому что за 14 лет уже не представляют себе как без моего софта работать, а у меня исходники не сохранились, чтобы прикрутить к чему посвежее (там глубокая интеграция с фотошопом).
                                  После фотосалона выстрелило моё резюме на программиста, перебрался в столицу, ну и 14 лет уже как программирую.
                                  Друг, к сожалению, пошёл в другую сторону и сейчас обычным электриком на родине трудится, хотя программировал гениально и компьютерами фанател. Алгоритмы его, как правило, получались получше моих. Пару лет назад виделись, пытался ему на пальцах объяснить что такое ООП, но, то ли способностей учителя у меня нет, то ли он навыки растерял…
                                  Но для меня программирование — это жизнь, постоянно что-то писал (и пишу), ежедневно, а у друга были невероятные способности ко всему, как говорят «не гумманитарному». Математика, информатика, физика, химия — всё подряд. А вот с гумманитарными предметами — наоборот. Из гимназии был отчислен за неуспеваемость по иностранному языку. И с дальнейшим обучением были проблемы того же рода.
                                  Его способностями восхищались все преподаватели естественных дисциплин. Уверен — при должной мотивации он мог бы сказать своё слово в науке, но наше образование всегда всех под одну гребёнку гребло и гребёт. Не вписываешься в стандарты — гуляй, даже если человек — гений в чём-то отдельном. Разве что спортсменов и шоуменов-КВНщиков готовы вытаскивать по всем предметам ради престижа учебного заведения. А физмат мало кому интересен, если гениальность в отрыве от гумманитарных предметов.
                                0
                                Довольно странно. Видеопамять в таких компах была очень медленной, и видеокарты ничего вычислять не умели.
                                +1
                                К сожалению, код для обработки данных на видеокарте пока еще невозможно написать на .NET.

                                Хорошая попытка, Microsoft, но нет.

                                –2
                                image
                                Параллельно удалось показать, что JavaScript (в контексте скорости вычислений) в 12,5 раз медленнее нативной реализации. Т.е. каждое приложение на электроне жрет в 12.5 раз больше ресурсов чем нативная реализация.
                                  +1

                                  При всей нелюбви к электрону, так считать нельзя. Во-первых, далеко не каждое нативное приложение использует SIMD-инструкции. Во-вторых, далеко не каждое приложение является подобной "битодробилкой", а в других областях соотношение производительности может оказаться другим.

                                    +1

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

                                    +5

                                    Джону Хортону Конвею, жизнь которого в возрасте 82 лет прервал короновирус в апреле 2020-го года, посвящается...

                                    • НЛО прилетело и опубликовало эту надпись здесь
                                        +1
                                        Я точно не знаю, но возможно, что так как она была придумана в 1970 году, когда персональных компьютеров не было, требовался игрок, который должен был вручню гонять симуляцию на листке в клеточку.
                                          0
                                          А кто тогда задаёт начальные условия? Игрок
                                            0
                                            Песочница же. Как минимум начальное состояние можно задавать, а в некоторых реализациях можно вводить паттерны прямо в процессе. В детстве написал себе игрушку, в которой было два вида клеток, и одному виду можно было вручную помогать вытеснить второй.
                                            +1

                                            Многопоточность никак тут не заюзать?

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

                                                        Вы же предлагаете проверять всех соседей каждой живой клетки — а их аж 9. А поскольку чтобы проверить не проверили ли мы уже клетку, надо тоже потратить время — выигрыш по времени выходит только когда живых клеток менее где-то 1/9.

                                                        • НЛО прилетело и опубликовало эту надпись здесь
                                                            0
                                                            эта игра жизнь ВСЕГДА вырождается к сильно разреженной матрице живых клеток

                                                            Доказано, что плотность может превышать 50%
                                                            • НЛО прилетело и опубликовало эту надпись здесь
                                                                +1
                                                                Из осциллятора, который получил QDeathNick, можно составить нестатическую фигуру, если я не ошибся в подсчетах, 32% плотности:
                                                                image
                                                                  0
                                                                  А как технически сделаны статические буквы на заглавной картинке статьи?
                                                                    0
                                                                    Фотошопом
                                                                      0
                                                                      Если Вы имеете в виду наложение кода на картинку, то не фотошопом: я использовал paint.net, сгенерировал пять картинок, и воспользовался одним из онлайн-генераторов анимированных gif.
                                                                      +1
                                                                      в программе Golly, взял статическую картинку из четырех точек и копипейстом размножил по форме букв: image
                                                                0
                                                                Проверил на коленке Вашу идею:
                                                                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
                                                                
                                                                0
                                                                Соседей — 8.
                                                                  0

                                                                  От самой клетки тоже зависит её следующее состояние, так что проверять нужно 9 клеток, а не 8.

                                                                    –1
                                                                    Не вижу противоречия со своим комментарием.
                                                          –1
                                                          bump
                                                            +1
                                                            А если использовать функциональный подход и взять функциональный язык, то тогда возможна игра не бесконечном поле. Для этого вместо того чтобы хранить массив клеток, надо хранить только множество живых фигур. Тогда будет обсчитываться только та часть поля, где есть фигуры, а та часть поля, где фигур больше нет — не будет обсчитываться. Это ещё и решает проблему того, что планер улетает в бесконечность. Нет никаких проблем чтобы просчитать одинокий планер улетевший в бесконечность, поскольку мы не храним многомиллионный массив. И функция Step будет не обходить массив в цикле на каждом шаге, а будет преобразовывать фигуру прошлого поколения, в фигуру нового поколения. Так как такие функция будут чистыми, то это позволяет очень просто распараллеливать вычисления на любое количество потоков, включая также GPU. При этом можно использовать такие же битовые оптимизации. Также это будет обобщённым решением, и позволит играть хоть на 3D поле, а не только 2D.

                                                            P.S. Для меня это стало большой неожиданностью, что создатель этой игры и великий математик Джон Конвей умер в этом году.
                                                              0
                                                              Так как такие функция будут чистыми, то это позволяет очень просто распараллеливать вычисления на любое количество потоков, включая также GPU

                                                              Интересно, как? У вас есть функция, которая принимает на вход все живые клетки и выдаёт новые живые клетки. Функция внутри особо не паралелится, а снаружи для запуска следующей итерации нужно закончить вычисление предыдущей.

                                                                0
                                                                Параллелизм тут только на уровне одного шага, следующий шаг зависит от предыдущего. Функция принимает фигуру, мы не храним полное состояние поля. Если две фигуры расположены в разных углах, они независимы и не могут повлиять друг на друга. И поэтому мы их можем посчитать независимо. То есть новое поколение фигуры зависит только от самой фигуры, а не от глобального состояния. Из-за этого эта функция чистая и их можно легко распараллеливать. И потому что нет изменяемого состояния (например, как с копированием массива temp в тексте), мы можем, образно говоря, посчитать каждую из фигур в вакууме.
                                                                  0
                                                                  Вот, например, неплохое объснение Hashlife, там очень похоже на то, как Вы описываете.
                                                                    0

                                                                    А что такое "фигура"? Если между двумя фигурами есть промежуток в 1 пиксель — они считаются одной фигурой? Что если две фигуры влияют на один пиксель (растут)?


                                                                    Сомнительный выигрыш, короче.


                                                                    И потому что нет изменяемого состояния (например, как с копированием массива temp в тексте)

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

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

                                                                    Извиняюсь, возможно я что-то упустил, но разве граничные клетки не сшиваются с противоположными краями, замыкая всю игровую поверхность?

                                                                      +4

                                                                      В оригинале игра идёт на бесконечном поле. Но, так как память компьютера ограничена — то поле тоже ограничивается. А какую ему при этом дать топологию, прямоугольника или тора — это уже деталь реализации. В обоих случаях в симуляции возможны эффекты, которые на бесконечном поле невозможны.

                                                                        0

                                                                        Спасибо. Не берусь утверждать, но чисто интуитивно мне кажется, что ход игры на прямоугольнике и на «торе» будет кардинально различаться. Проверю при возможности.

                                                                      –4
                                                                      копируем массив temp в исходный массив.

                                                                      И вот здесь я перестал читать и просто проскролил до конца.

                                                                        0
                                                                        Вы поступили не умно. Очень интересная статья.
                                                                          –4

                                                                          Ну, я вообще-то не очень умный. И соответственно часто поступаю не умно. Например, пишу все на ассемблере. И не копирую массив temp в исходный массив никогда. И кстати, поискал и оказывается, у меня в исходниках (500kloc) нет ни одной переменной, массив или просто этикетку с имени "temp". Мне стыдно, но что поделать… (но есть "template" — это считается?)

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

                                                                              Ну-у-у, если и там копировали temp, то вполне нормально… Вообще, компилируемый язык и хороший компилятор не делают автоматически код быстрым. И писать действительно быстрый код на C++, совершенно нетривиальный процесс. (кстати, написать то же самое в плане оптимизации на ассемблере намного легче) Посмотрите как выглядит какая нибудь хорошо оптимизированная библиотека на C++.

                                                                                0
                                                                                Последовал Вашему совету и полез в мой любимый 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
                                                                                
                                                                                ...
                                                                                
                                                                                
                                                                                  –3

                                                                                  А в C есть фабричная гарантия от багов, что ли???


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


                                                                                  Но что баги — их тестят и исправляют.


                                                                                  П.С. Кстати, я имел ввиду смотреть на оптимизированный код C/C++, а не на то что написано на ассемблере.

                                                                              0
                                                                              не копирую массив temp в исходный массив никогда

                                                                              просто этикетку с имени «temp»

                                                                              Если кому интересно, простой поиск по коду Linux находит дофига и переменных temp, и копирования в и из них

                                                                              drivers/misc/mic/scif/scif_dma.c
                                                                              	if (!window_virt)
                                                                              		return;
                                                                              	if (to_temp)
                                                                              		memcpy(temp, window_virt, loop_len);
                                                                              	else
                                                                              		memcpy(window_virt, temp, loop_len);
                                                                              		window_virt = _get_local_va(offset, window, loop_len);
                                                                              		if (!window_virt)
                                                                              			return;
                                                                              		if (to_temp)
                                                                              			memcpy(temp, window_virt, loop_len);
                                                                                –1

                                                                                Так вы считаете, что код Linux это такой эталон что-ли? Раз в Linux так делают, то и нам можно. :D

                                                                          0
                                                                          Сложно найти человека, не знакомого с игрой «Жизнь»

                                                                          ИМХО, таких людей очень много.
                                                                            0

                                                                            Если вдруг решите оптимизировать по-настоящему, то посмотрите на эту статью — https://habr.com/ru/post/180135/

                                                                              0
                                                                              я видел ее. Мне кажется, или его результат только примерно совпадает с классическими правилами?
                                                                              +4
                                                                                      for (int i = 1; i < WIDTH - 1; i++)
                                                                                          for (int j = 1; j < HEIGHT - 1; j++)

                                                                              При обходе двумерного массива, внутренний цикл всегда должен быть по строке, а не столбцу. Так намного быстрее, особенно когда данные не влезают в кеш-память.
                                                                                +1
                                                                                Ваш комментарий верен в общем случае, но при обходе двумерного массива внутренний цикл должен быть по второму индексу, так что в данном случае этот порядок правильный, можете поменять местами и проверить. Тут скорее проблема в том, что массив определялся как new bool[WIDTH, HEIGHT], хотя надо было бы длину и ширину поменять местами.
                                                                                +1
                                                                                «Жизнь» можно даже
                                                                                SQL-запросом:
                                                                                with
                                                                                -- параметры - количество поколений, ширина, высота и количество элементов
                                                                                parms as (select last_gen, width, height, width * height total_cells
                                                                                    from (select 8 last_gen, 10 width, 7 height from dual)
                                                                                ),
                                                                                -- Исходное поле
                                                                                src_field as (
                                                                                  select rpad(lpad(rpad('0010', width, '0') || rpad('0001', width, '0') ||
                                                                                                    rpad('0111', width, '0'),
                                                                                                    width * 4,
                                                                                                    '0'),
                                                                                               total_cells,
                                                                                               '0') field
                                                                                    from parms
                                                                                ),
                                                                                -- Жизнь, как она есть
                                                                                life(gen, i, field, next_field) as (
                                                                                  select 0 gen, 0 i, field, '' next_field
                                                                                    from src_field
                                                                                  union all
                                                                                  select case
                                                                                           when i = total_cells then
                                                                                            gen + 1
                                                                                           else
                                                                                            gen
                                                                                         end gen,
                                                                                         mod(i + 1, total_cells + 1) i,
                                                                                         case
                                                                                           when i = total_cells then
                                                                                            translate(next_field, '0123456789ABCDEFGH', '000100000001100000')
                                                                                           else
                                                                                            field
                                                                                         end field,
                                                                                         case
                                                                                           when i = total_cells then
                                                                                            ''
                                                                                           else
                                                                                            next_field ||
                                                                                            substr('0123456789ABCDEFGH',
                                                                                                   substr(field, i + 1, 1) * 9 +
                                                                                                   substr(field,
                                                                                                          mod(i + total_cells - width - 1, total_cells) + 1,
                                                                                                          1) + substr(field,
                                                                                                                      mod(i + total_cells - width, total_cells) + 1,
                                                                                                                      1) +
                                                                                                   substr(field,
                                                                                                          mod(i + total_cells - width + 1, total_cells) + 1,
                                                                                                          1) +
                                                                                                   substr(field, mod(i + total_cells - 1, total_cells) + 1, 1) +
                                                                                                   substr(field, mod(i + 1, total_cells) + 1, 1) +
                                                                                                   substr(field, mod(i + width - 1, total_cells) + 1, 1) +
                                                                                                   substr(field, mod(i + width, total_cells) + 1, 1) +
                                                                                                   substr(field, mod(i + width + 1, total_cells) + 1, 1) + 1,
                                                                                                   1)
                                                                                         end next_field
                                                                                    from life, parms
                                                                                   where gen < last_gen
                                                                                     and i <= total_cells
                                                                                )
                                                                                -- select --------------------------------------
                                                                                select case
                                                                                         when y = -1 then
                                                                                          'Generation ' || gen
                                                                                         else
                                                                                          translate(substr(field, y * width + 1, width), '01', '.X')
                                                                                       end v
                                                                                  from life
                                                                                 cross join (select level - 2 y, width
                                                                                               from parms
                                                                                             connect by level <= height + 1) ys
                                                                                 where i = 0
                                                                                 order by gen, y;
                                                                                


                                                                                Generation 0
                                                                                ..........
                                                                                ..X.......
                                                                                ...X......
                                                                                .XXX......
                                                                                ..........
                                                                                ..........
                                                                                ..........

                                                                                ...
                                                                                Generation 1
                                                                                ..........
                                                                                ..........
                                                                                .X.X......
                                                                                ..XX......
                                                                                ..X.......
                                                                                ..........
                                                                                ..........
                                                                                Generation 2
                                                                                ..........
                                                                                ..........
                                                                                ...X......
                                                                                .X.X......
                                                                                ..XX......
                                                                                ..........
                                                                                ..........
                                                                                Generation 3
                                                                                ..........
                                                                                ..........
                                                                                ..X.......
                                                                                ...XX.....
                                                                                ..XX......
                                                                                ..........
                                                                                ..........
                                                                                Generation 4
                                                                                ..........
                                                                                ..........
                                                                                ...X......
                                                                                ....X.....
                                                                                ..XXX.....
                                                                                ..........
                                                                                ..........
                                                                                Generation 5
                                                                                ..........
                                                                                ..........
                                                                                ..........
                                                                                ..X.X.....
                                                                                ...XX.....
                                                                                ...X......
                                                                                ..........
                                                                                Generation 6
                                                                                ..........
                                                                                ..........
                                                                                ..........
                                                                                ....X.....
                                                                                ..X.X.....
                                                                                ...XX.....
                                                                                ..........
                                                                                Generation 7
                                                                                ..........
                                                                                ..........
                                                                                ..........
                                                                                ...X......
                                                                                ....XX....
                                                                                ...XX.....
                                                                                ..........

                                                                                Generation 8
                                                                                ..........
                                                                                ..........
                                                                                ..........
                                                                                ....X.....
                                                                                .....X....
                                                                                ...XXX....
                                                                                ..........
                                                                                  +1

                                                                                  Не могу не отметить, что объяснять правила на примере, где белые клетки — живые, а черные — мертвые… Нужно быть сильно рисковым человеком в 2020 году. ))

                                                                                    0

                                                                                    Да и бинарное деление на 2 цвета не отвечает современным потребностям нецисгендеров )

                                                                                    +1
                                                                                    «Жизнь» лучше всего работает на FPGA. Прикрутить RAM на ~50GB\s и можно наслаждаться 14КFPS в FullHD и не на самом топовом камне. :D
                                                                                    И это мы делаем «в лоб»! Добавить оптимизаций и можно получить «плавающий фпс» хоть до +100KFPS в FullHD!(шучу немного)
                                                                                    Кнш… 50GB\s вы получить наврядли сможете, а вот 10GB\s вполне можно развести «недорого».

                                                                                    ЗЫ — Даже на SDRAM с дёшевеньких плат, на каких-нить циклонах4 с 22KLE, можно без оптимизаций ~40фпс выжать в FullHD.
                                                                                      0
                                                                                      Круто! Получается, скорость будет ограничена только пропускной способностью канала памяти? После Вашего комментария полез искать, пользуются ли FPGA для ресёрча, и нашел, что пользуются, но, похоже, это единичные случаи.
                                                                                      Два вопроса по этому поводу (чисто теоретических):
                                                                                      1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
                                                                                      2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?
                                                                                        +1
                                                                                        В такой задаче у нас будет матрица из 1024 вычислителей (32х32), и посути их работа тормозится лишь памятью. Если не заморачиваться с конвейером и широкими шинами с кэшем, то загруженность матрицы для плат с SDRAM меньше 1% при fmax в районе 50МГц(можно и больше, но опять же, конвейер нужно делать).
                                                                                        Я не сильный спец по FPGA, это моё излюбленное хобби. Воссоздаю старые железки, пишу свои. Вот так вот))
                                                                                        1 — Скорее всего можно, ибо самих данных о ячейках «жизнь» меньше чем шина между ними. Разве что придумать чуть хитрый подход как этот массив считывать, чтоб место на чипе сэкономить, и только. Такую матрицу не получится настроить кнш, но чисто фиксировано считать HD может хотя бы на те же 50МГц, те ~50МFPS
                                                                                        А если прям обмозговать, думаю там найдётся способ используя внутреннюю SRAM расширить хотя бы до FullHD или уж больше. Но тут ещё раз проблема как это считывать и хотяб просто по ethernet отправить чтоб камень не разрося раз в 5.
                                                                                        2 — (*После написания осознал что видимо не так вас понял, ASIC, те специализированную схему, можно сделать любой, я вас умоляю. Но нафига? Это очень дорого выйдет, а аппаратно считать «жизнь» в 4К с 500MFPS??? А то и 1GFPS если вы сможете достаточно хорошо оптимизировать это всё, почему нет? xDDDD. Дальше можно не читать, меня просто понесло сильно, но я решил оставить хз зачем*)

                                                                                        С SRAM камнем ты просто получишь меньше задержек при считывании, но не большие МБ\с. (многие поддерживают конвейерный подход что нам на руку)
                                                                                        Замечу что хорошие и быстрые SRAM камушки стоят почти столько же сколько дешёвый фпга типа тех же 4 циклонов c 22КLE.
                                                                                        В принципе добиться одной итерации за такт можно, ибо это FPGA. У тебя может быть просто 1024 ячеек + регистры с данными о них, а потом по сигналу «ena» посчитать их за один такт. Толи дело что fmax страдать будет.
                                                                                        Про суматор я не сильно понял, прошу прощения ))

                                                                                        А лучший способ ускорить матрицу, это ввести нормальный конвейер с кэшированием. Тк задача без ветвлений, то конвейер даже простаивать не будет + SRAM тоже конвейерный. Также можем просто считать строки 32х32, и дальние(что не используются в вычислениях а нужны лишь их крайние ячейки) сохранять в кэш, что уже разгрузит память неплохо ибо нужно лишь 1 раз по данным пройтись.

                                                                                        Дальше улучшать… Остаётся лишь добавить аппаратное сжатие к памяти, либо усложнять сами алгоритмы загрузки.
                                                                                        К примеру…
                                                                                        Тк мы не ограничены лютыми задержками ибо SRAM+кэш, можем добавить лишний байт к каждой группе ячеек, и просто не грузить их если они пустые и наоборот, иначе грузить всю группу. Что даст не хилый такой буст во многих случаях, но оно даст плавающий FPS, а не стабильный как раньше.
                                                                                        Чисто прикинем, если раньше мы всегда читали полностью 32х32 то теперь мы читаем группы по 4х4. Тоесть при пустых ячейках у нас тратится 64такта на чтение 32х32, при полу пустых 576, а при полных 1088. Что вроде как больше чем старые 1024, но как я знаю, у нас редко когда все ячейки полностью забиты. Потому думаю в среднем FPS будет выше.
                                                                                        Думаю при всём этом на DE0-Nano можно будет выжать ~100фпс FullHD в среднем
                                                                                        (У меня сейчас под рукой подобного типа китайская плата просто)

                                                                                        Ну и последняя улучшалка, вроде видел 2х порт SRAM камни, что может офигеть как разгрузить шину, и не надо будет пропускную способность на 2 делить. Либо поставить их несколько и писать\читать по цепочке.

                                                                                        Ой чота меня понесло, не буду удалять во общем.
                                                                                        Тут я просто «на глаз» оценивал, в реале цифры могут отличаться
                                                                                        И да, по факту у нас всё упрётся в память, ибо только на топовые FPGA можно прикрутить достаточно быструю память, чтоб она смогла покрыть чистую «производительность» матрицы, либо уже на их внутренних SRAM ячейках всё держать.

                                                                                        Крч по приколу, надо сделать это. В ближайшее время и простенькую статью написать… Мб аккаунт до «полноценного» улчшу xDDD
                                                                                          0
                                                                                          Спасибо! Было бы интересно, чего можно достичь на не-топовых FPGA.
                                                                                          Вообще интересно, чего можно достичь на разных технологиях за разные деньги. Я по сумме всех комментариев понял примерно так (плюс-минус порядок):
                                                                                          — процессор ($1'000) — 50'000 итераций в секунду
                                                                                          — видеокарта ($1'500) — 500'000 итераций в секунду
                                                                                          — FPGA ($15'000) — 50 миллионов итераций в секунду
                                                                                          — ASIC ($1'500'000) — 1 миллиард итераций в секунду
                                                                                            +1
                                                                                            Было бы интересно, чего можно достичь на не-топовых FPGA.

                                                                                            Ну много чего можно, проблема лишь в том, что выгодней делать именно специальные схемы для конкретных задач и только те что на видяхе считаются меньше ~200М«итераций»(я взял в среднем из сложных что видел). То есть, те же хэши считать, вроде на EP4CE115 можно уместить 4 «считалки» хэшей, которые могут тянуть 4*200Мхэш\с, но если примерно такой же цены видеокарта справляется так же, профита будет не особо много. Разве что Ватт меньше жрать будет. (В разы меньше xD)
                                                                                            Так со многими задачами где надо считать что-то или фильтровать + зависит от того кто делает это всё. Ибо можно оптимизировать архитектуру под конкретную FPGA, а можно просто логику описать, думаю понятно что результаты будут разные и порой в разы. (Самое простое, это что мультиплексоры для конкретного камня надо делать «определённой разрядности», те подгонять условия правильно, иначе это может генерить очень много лишней логики)

                                                                                            Кстааате, на FPGA очень офигенно синтезируются старые процессоры(примерно до ~10Мгц, уже дальше фана меньше). Допустим описав логику можно получить «аппаратную» эмуляцию с частотами даже в 10 раз больше оригинальной и кучей плюшек. Толку? Можно много всяких свистелок придумать, вон популярная статья на хабре была, где NES делали. (Вроде как малинка тоже так умеет, но радостей от «аппаратного клона» было больше xD) Ещё можно спокойно тренить ИИ на таком камушке. Помнится всплывала подобная статья на хабре, где взяли «не сильно» жирный камень и уместили ~10старых приставок, разогнали их в несколько раз и тренили ИИ, приводилось что на Xeon'ах оно работало изрядно плохо, потому искали другие пути.(точных чисел не помню, ну буст там был дичайший xD)

                                                                                            И ещё знаю пару людей, коих интересуют всякие «новаторские» подходы в параллельном программировании. То есть, различные конфигурации по типу… Тех же NUMA, или уж совсем экзотические.(Давно не общался, не помню точно всё + я с этим плохо знаком) Как бы выглядели чисто «аппаратные» свистелки которые прижились в программировании параллельных «программок». И просто всякие эксперименты «а оно вообще работать будет?»… Кнш двигалось это черепашьим темпом, но просто как забавный факт, есть

                                                                                            На этом применимость FPGA для меня «всё». Можно ещё так «по изучать» как железо работает, что бы вот прям быть «знающим страшные тайны, что не подвласны абстракциям!!!» xD
                                                                                            +1
                                                                                            Было бы очень интересно прочесть такую статью
                                                                                          0
                                                                                          Давайте тогда на ASIC сразу замахнемся :)
                                                                                            0
                                                                                            Может, сразу делать дисплеи с интегрированной логикой клеток? Каждый пиксель смотрит на 8 своих соседей. Обсчёт всего поля — 1-2 такта. Можно достичь скорости 4e9 FPS.
                                                                                              0
                                                                                              Дисплей с ФПС 4е9? Такие бывают?
                                                                                                0
                                                                                                Для человека это ничем не будет отличаться от дисплея на 1000FPS, поэтому быстродействием переключения можно пренебречь.

                                                                                                Практическая польза — в оценке на больших дистанциях: вымерла популяция, вошла в короткий цикл, или ещё развивается.
                                                                                                0
                                                                                                А это чисто физически можно сделать на двумерной схеме? Ведь у каждой клетки будет свой сумматор, и надо будет к нему тянуть линию от всех восьми ее соседей.
                                                                                                  +1
                                                                                                  Ну а как сделаны любые интегральные схемы, например, процессоры? Их коммутация гораздо запутаннее. Конечно, слоями.
                                                                                            +1
                                                                                            Возможно уже писали такой комментарий. Я не нашел.
                                                                                            Если последний шаг с AVX накатить на последнюю версию, где по 2 клетки на байт, разве не будет ускорения еще в 2 раза?
                                                                                              0
                                                                                              Спасибо за комментарий, это действительно отличная идея, я ее проверил уже после написания статьи.
                                                                                              Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
                                                                                              Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
                                                                                              Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.
                                                                                                0
                                                                                                Точно! Вы правы. Я что-то не подумал об усложнениях, которые появляются.
                                                                                                Ваша дополнительная идея очень хорошая. Ее можно слегка оптимизировать. Не уверен, что это сильно поможет. Когда Вы хотите произвести вычисления для некоторого элемента в середине поля, Вам необходимо знать предущую линию (под нее выделить память), в текущей линии предыдущий элемент, текущий и следующий (под них можно выделить 3 локальных переменных) и следующая линия (которая и так есть в исходном массиве, так как Вы еще не успели начать ее «портить»).
                                                                                                Тогда кешируется куски не 4 массивов, а лишь 3.
                                                                                                Но это, скорее оптимизация по памяти, чем по времени.
                                                                                                  0
                                                                                                  Не особо во всём этом разбираюсь, но разве не хватит кеша под 2 линии + 4 элемента? Ведь пройденная часть кеша верхней линии уже не будет использоваться при расчётах, и в неё можно заполнять кеш текущей линии, а потом переключать их. Не знаю понятно ли объяснил, закодить за 5 минут вряд ли смогу.
                                                                                                    0
                                                                                                    Тут дело не сколько в размерах кеша, сколько в количествах обращений к оперативной памяти.
                                                                                                      0
                                                                                                      А разве при сокращении размеров кеша не повышается вероятность того, что он будет в кеше (извиняюсь за тавтологию) процессора? Впрочем оказалось что эта тема уже поднималась, но это было целый месяц назад.
                                                                                                      0
                                                                                                      Вроде бы чисто теоретически должно сработать, но затрудняюсь сказать, насколько это усложнит код. Кроме того, размер поля 1 мегабайт, а размер линии — 1 килобайт (по 4бита на клетку), так что экономия на одной линии не особо должна повлиять на производительность. Вот действительно где можно было бы сильно сэкономить, — это хранить клетки не в 4 битах, а в одном бите, и распаковывать только для подсчетов, примерно как это делается в этой статье. К сожалению, чтобы биты расширить в байты более-менее эффективно, нужен десяток AVX-инструкций; я пытался делать, но производительность только ухудшилась. В AVX512 будет специальная инструкция для этого, тогда можно будет попробовать, но пока процессоры не особо его поддерживают.
                                                                                                0
                                                                                                промахнулся

                                                                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                                Самое читаемое