В этом материале про Пирог обрабатывалась карта из плиток:
В процессе обработки требовалось для каждой плитки получить значения её соседей сверху, снизу, справа и слева, а также опционально по диагонали.
Сама по себе такая деятельность называется конволюцией, или свёрткой (используется в различных фильтрах и нейросетях). Только в Пироге она применяется не в истинном математическом смысле, но тем не менее, никакой принципиальной разницы.
Давайте создадим на Питоне матрицу размером 1024 * 1024 элемента и заполним её случайными байтами (хотя это и не требуется, но на всякий случай):
А теперь пройдёмся по ней и для каждого элемента посчитаем такую свёртку: взять сумму элементов сверху, снизу, слева и справа, и разделить на 4. Т.е. получится некий фильтр размытия. Это полная условность, так как нас будет интересовать не результат, а просто скорость выполнения операций.
Обратите внимание на неудобство. Когда координаты (x, y) находятся на краю матрицы, то невозможно получить кого-то из соседей. Если при x = 0 попытаться взять x - 1, то выпадет ошибка. Приходится сначала проверять, есть ли сосед вообще, и только потом получать его значение.
Кроме того, если было доступно только 3 соседа, то и делить надо на 3, а если 2, то на 2. Значит, дополнительно надо ещё считать величину делителя (это переменная div).
Ветвления это плохо
На каждом шаге цикла исполняется 4 инструкции if. А всего – 4 184 304.
Условия порождают ветвления, а ветвления тормозят процессор, потому что он не может предсказать их выполнение и загрузить нужный код заранее.
Чтобы сократить количество условий, рассмотрим два альтернативных решения.
Сегментация циклов
Мы можем спокойно пройти по матрице без всяких условий, если не будем заходить на её края. А вот края надо будет пройти отдельно. Посчитаем верхнюю и нижнюю строку по своим правилам, а внутри всех строк будем ещё отдельно считать первый и последний элемент.
Получится вот так:
От этого кода рябит в глазах, но если не спеша его рассмотреть, то это просто куча отдельных операций и циклов. Зато посмотрите – ни одного условия. И ещё в каждом случае мы точно знаем, на сколько нужно делить, поэтому считать делитель не требуется.
Логические операции
Ещё один способ избавиться от условий это заменить их хитрыми логическими или математическими операциями.
Принцип тут такой. Допустим, к числу a надо прибавить число b. Но только если выполняется условие x > y.
if (x > y) { a += b; }
Но то же самое можно сделать, превратив условие x > y в множитель, равный 1 или 0:
a += b * (x > y);
Видите, здесь мы умножили b прямо на само выражение (x > y). Оно даёт результат true или false, которые автоматически конвертируются в 1 или 0. Следовательно, если условие выполняется, к a прибавится b * 1, а если нет, то b * 0.
А что, так можно было?
В общем случае – не всегда. В частных – сколько угодно. Читайте также:
А теперь тесты!
Запустим каждый тест по 4 раза с замерами времени, чтобы избежать случайных вариаций:
Результат (время выполнения в секундах):
Итак, мы видим, что сегментированный тест выполняется практически в 2 раза быстрее обычного. А вот тест с логическими операциями подвёл – оказался самым медленным. Видимо, операций получилось слишком много, чтобы дать выигрыш в скорости.
А что же JavaScript?
Я для сравнения написал такой же код на JS, его можно запускать онлайн:
https://js.do/nandakoryaaa/convo
Там картина такая же. Сегментированный тест самый быстрый, а логический самый медленный (хотя и не очень заметно). Но...
Эти числа – миллисекунды. То есть тест на Питоне выполняется около 0.5 секунды (500 миллисекунд), а такой же на JS – 10 миллисекунд. Это разница в 50 раз!
Я не знаю, почему. Пытался найти ошибки в коде JS, но не нашёл.
Погонять питона также можно онлайн:
https://onlinegdb.com/BvEQSovqV
В общем, оставляю вас онемевать от этого факта :)
А мне придётся подумать вот над чем. В Пироге карта будет отрисовываться не в размере 1024 * 1024, но вполне вероятно что может быть и 512 * 512, то есть о производительности надо думать вот уже сейчас.
Но прорвёмся.
P.S. Новые результаты с Python JIT: