Комментарии / Профиль lightln2 / Хабр

Все потоки

Oleg T@lightln2

программист

ПрофильСтатьи5ПостыНовостиКомментарии139

База данных простых чисел до ста миллиардов на коленке

lightln2 13 июл 2020 в 17:10

Да, действительно, факторизация по трем первым простым числам мне тоже показалась «оптимальной» именно из-за восьми бит на период.
Хочу только отметить, что если взять достаточно большое количество простых чисел, можно добиться произвольно большого сжатия. Я когда-то подсчитал, что для факторизации по первым четырем миллиардам простых чисел потребуется примерно 0.0225 бит на натуральное число. Однако на практике, конечно, этот алгоритм неприменим, потому что выгода начнется только для простых чисел, состоящих из триллионов (десятичных) знаков. Кроме того, размер таблицы INDEX_TO_BIT будет больше количества атомов во вселенной.

0

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

lightln2 6 июл 2020 в 22:09

Вроде бы чисто теоретически должно сработать, но затрудняюсь сказать, насколько это усложнит код. Кроме того, размер поля 1 мегабайт, а размер линии — 1 килобайт (по 4бита на клетку), так что экономия на одной линии не особо должна повлиять на производительность. Вот действительно где можно было бы сильно сэкономить, — это хранить клетки не в 4 битах, а в одном бите, и распаковывать только для подсчетов, примерно как это делается в этой статье. К сожалению, чтобы биты расширить в байты более-менее эффективно, нужен десяток AVX-инструкций; я пытался делать, но производительность только ухудшилась. В AVX512 будет специальная инструкция для этого, тогда можно будет попробовать, но пока процессоры не особо его поддерживают.

0

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

lightln2 6 июл 2020 в 14:42

Спасибо за комментарий, это действительно отличная идея, я ее проверил уже после написания статьи.
Тут есть техническая проблема: в AVX невозможно сдвинуть на 4 бита весь регистр как одно 256-разрядное число, минимум нужно делать два сдвига и одно сложение, так что ускорение будет немного меньше, чем в два раза, и код сильно усложняется, но выигрыш в скорости все равно получается существенный.
Вкупе с еще одной идеей: избавиться от временного буффера вообще, и хранить дополнительно только три линии поля (текущую, выше, и ниже) получается суммарно ускорение в 330 раз от начальной версии, от 25 до 7400 шагов в секунду!
Можно код посмотреть на гитхабе: AdvancedLifeExtensionsInLineCompressed.cs.

0

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

lightln2 6 июл 2020 в 14:41

промахнулся

0

Game of Life с битовой магией, многопоточностью и на GPU

lightln2 3 июл 2020 в 23:36

Спасибо за статью!
По поводу превосходства GPU: я когда-то пытался делать неоптимизированную реализацию на CUDA, и она оказалась сильно медленнее, чем я ожидал (медленнее вашей версии). Потом я наткнулся на эту статью, в которой утверждается, что ключ к оптимизации — расположение данных в GPU-памяти правильного типа (в идеале, в регистровой памяти).
Их производительность — 0.16 секунд на 1024 итераций на поле 16K на 16K на видеокарте GeForce GTX TITAN X. Эта разница из-за того, что видеокарты несопоставимы по производительности, или Вашу версию еще можно ускорить, если применить аналогичные трюки?

+3

Тетрис на битбордах: старые песни на новый лад

lightln2 19 июн 2020 в 22:58

а, да. я сделал фигурку, четыре варианта которой (меняются вращением) — Ъ, Ы, Ю, Ж, с более простыми буквами слишком легко было

+1

Тетрис на битбордах: старые песни на новый лад

lightln2 19 июн 2020 в 16:24

Вы имеете в виду, фигура, как на КПДВ? Вообще-то это твердый знак (ну, по крайней мере задумывался).
Нету смысла искать оптимальную стратегию в обычном тетрисе — известно, что он проходится до момента, пока не встретится какое-то количество z- и s- фигурок в определенной последовательности. Вот я и добавил фигурку, которая все «портит», чтобы вручную его тоже было сложно пройти — я, например, дальше компьютера не смог.

0

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

lightln2 11 июн 2020 в 10:21

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

0

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

lightln2 11 июн 2020 в 10:08

А это чисто физически можно сделать на двумерной схеме? Ведь у каждой клетки будет свой сумматор, и надо будет к нему тянуть линию от всех восьми ее соседей.

0

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

lightln2 10 июн 2020 в 20:37

Круто! Получается, скорость будет ограничена только пропускной способностью канала памяти? После Вашего комментария полез искать, пользуются ли FPGA для ресёрча, и нашел, что пользуются, но, похоже, это единичные случаи.
Два вопроса по этому поводу (чисто теоретических):
1) Нашел в гугле, что есть FPGA Virtex-7 2000T с двумя миллионами ячеек; в нем можно сделать симуляцию игры не в памяти, а напрямую в этих ячейках? Или топология не позволяет?
2) Может быть, можно сделать специализированную микросхему с двумя мегабайтами SRAM, и к каждой ячейке прикрутить трехбитный сумматор? Тогда теоретически можно добиться по одной итерации на такт?

0

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

lightln2 10 июн 2020 в 00:01

Ваш комментарий верен в общем случае, но при обходе двумерного массива внутренний цикл должен быть по второму индексу, так что в данном случае этот порядок правильный, можете поменять местами и проверить. Тут скорее проблема в том, что массив определялся как new bool[WIDTH, HEIGHT], хотя надо было бы длину и ширину поменять местами.

+1

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

lightln2 9 июн 2020 в 23:32

не копирую массив 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);

0

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

lightln2 9 июн 2020 в 18:25

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

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

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

+3

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

lightln2 9 июн 2020 в 12:18

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

0

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

lightln2 9 июн 2020 в 10:29

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

+1

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

lightln2 9 июн 2020 в 05:37

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

+1

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

lightln2 8 июн 2020 в 20:14

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

...

0

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

lightln2 8 июн 2020 в 20:09

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

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

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

lightln2 8 июн 2020 в 18:00

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

0

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

lightln2 8 июн 2020 в 17:41

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

0

5