Я на ноутбуке (Windows 10, Intel Core i7-6700HQ) скачал Firefox и проверил количество итераций в секунду на всех скоростях на всех трех браузерах:
Я так понимаю, у них разные движки, но все равно такая разница удивительна.
Спасибо за фидбек, у меня нет опыта в UI, и для меня такие вещи не очевидны.
2х-50х примерно на одинаковой скорости работают
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
Я, когда готовил статью и искал интересные шаблоны, работал с Golly, но в основном на Hashlife. Я сейчас мельком посмотрел на код qlifealgo.cpp, и там тоже огромное количество оптимизаций, при чем они все равно используют quadtree, так что его скорость тоже растет с улучшением регулярности. Хотя SIMD они не используют. Я сейчас запустил его на рандомно заполненном поле размера 1920x1080 с коэффициентом 0.5 (то есть, примерно половина клеток — живые, половина — мертвые), и за первую секунду он обработал 1000 итераций, за вторую — уже 10000, и на статической картинке скорость стабилизировалась где-то на 50000 в секунду. На картинке из КПДВ он работает стабильно примерно со скоростью 5000 в секунду.
Согласен, это тоже классическая оптимизация, которую было бы неплохо применить. Я, честно говоря, поленился: суммарно оба массива не превышают одного мегабайта, и должны помещаться в кеш третьего уровня, так что копирование должно быть быстрым по сравнению с довольно большим количеством логических операций. Но так как эта оптимизация не усложняет код, то кажется логичным ее применить, даже если она даст только 10% выигрыша.
А как лучше эту проблему решить? Просто уменьшить размер поля на высоту панели? или скриптом проверять размер экрана и скейлить канвас? или можно как-то подобрать значение meta name=«viewport», чтобы браузер сам все за нас сделал? Я имеюю в виду даже не технический аспект, а юзабилити — какой способ даст наиболее логичное с точки зрения пользователя поведение?
да, это тот самый Hashlife, я его упомянул в статье. Интересно было бы попробовать применить вышеописанные оптимизации к нему (исключительно для саморазвития: эту игру люди исследуют уже 50 лет, и все, что можно было оптимизировать, думаю, уже давно соптимизировали)
Можно даже дальше пойти: разбить плоскость на квадраты и кешировать результат итераций для каждого квадрата. Собственно, эта идея лежит в основе того самого Hashlife.
А исполнялась программа под 64-битную ява машину или 32-битную? В 32-битных процессах длинная арифметика медленнее, так как 64-битные регистры процессора недоступны.
Хотя я согласен, битовая арифметика будет замедляет алгоритм в любом случае.
Теоретически, если искать простые числа не в одном большом массиве на гигабайты, а разделить его на куски по несколько мегабайт, чтобы весь битовый массив поместился в кеш третьего уровня, может, тогда ускорение доступа к памяти может исправить замедление от битовых операций.
Можете подробнее про Ваш вариант рассказать?
Оптимизация таких числодробилок иногда бывает очень нетривиальна. У меня, например, скорость увеличивается в полтора раза, только если закомментарить строку if (n >= Length) throw new ArgumentException(«Number too big»);
Возможно, она как-то препятствует jit-у инлайнить метод, не изучал вопрос.
Кстати, получить итератор по всем простым числам в возрастающем порядке (самый частый use-case) можно эффективнее, чем проверять на простоту числа последовательно от 1 до ста миллионов (используя, как раз, массив BIT_TO_INDEX), просто я старался сделать код как можно проще, даже ценой ухудшения производительности.
Можно сжать, если проверять на простоту с помощью МТФ — хранить только те, которые не являются простыми но проходят проверку.
Нашел в Викпедии, что Baillie–PSW primality test, который является комбинацией двух вероятностных тестов на простоту (Ферма и Лукаса), вообще не имеет исключений для 64-битных чисел. Больше того, даже для произвольно больших чисел за сорок лет ни одного исключения так и не нашли. Так что Ваша идея тут кстати: размер базы будет нулевой практически всегда. А если вдруг кто-нибудь найдет составное число, проходящее этот тест, он даже получит премию в 30 долларов!
А из более поздних исследований нашел эту статью 2015 года — они утверждают, что их алгоритм самый быстрый (скорость проверки — чуть больше миллиона 64-битных чисел в секунду) из класса алгоритмов, не требующих предварительных вычислений.
Забавно, но я у них нашел такую цитату:
If we expect that we’ll need to test a significantly large number of small integers for primality, the best solution might be precomputing all possible answers
and then answering each query in constant time. The canonical implementation
uses one bit for each odd number, i.e., 2b/16 bytes of memory if the valid inputs are b-bit integers
То есть, они тоже считают, что для некоторых случаев битовая таблица — лучшее решение, но даже они говорят о бите на каждое нечетное число! Хотя Wheel factorization широко известен, почему-то даже ученые его игнорируют при практическом применении
Вы абсолютно правы, у меня в изначальной версии был именно ulong[]. Просто я не упомянул еще некоторые неудобства:
1) массив байт можно сохранить в файл одним вызовом File.Write
2) в .NET Framerork массив ulong-ов все равно просто так не создать
3) если мы захотим считать простые числа, например, до триллиона (вдруг у нас есть 30 гб памяти), массив ulong сам станет больше двух миллиардов элементов.
Верхняя планка чисел всегда ограничена количеством памяти на компьютере и разрядностью. Поправьте меня, если я ошибаюсь, но стандартная de-facto вычислительная модель, если не оговорено обратное — машина Тьюринга, что эквивалентно компьютеру с бесконечным количеством памяти.
Интересная идея! Насколько я понимаю, все же, скорость проверки не удастся сохранить O(1).
Впрочем, далеко не во всех задачах требуется константная скорость проверки, тогда, действительно, можно пожертвовать скоростью ради уменьшения размера базы. В предельном случае, если я правильно понимаю, можно вообще ничего не хранить, и применять AKS-тест каждый раз заново.
При генерации простых чисел будет много random writes, боюсь, будет слишком медленно. Лучше тогда использовать сегментированное решето Эратосфена, вычислять в памяти по кускам и скидывать найденные куски на диск. Тогда можно будет генерить простые числа, в принципе, до бесконечности.
А при использовании готовой базы — да, конечно, вместо того, чтобы загружать базу в память, можно просто читать с диска по нужному смещению.
Я нашел одну реально работающую оптимизацию, с помощью которой удалось ускорить алгоритм примерно в пять раз, и добить до N=70 (запустив на ночь на восьмиядерной машине). К сожалению,
Суть оптимизации вот в чем:
Понятно, что первые два числа в последовательности не могут быть одновременно четными, так как тогда все остальные числа тоже будут четными. Более того, четных чисел только N/2, поэтому два подряд четных числа могут встретиться только во второй половине последовательности. Аналогично, если два идущих подряд числа делятся на три, то все следующие числа тоже делятся на три, поэтому они могут встретиться только в последней трети последовательности. Обобщая, если два идущих подряд числа a, b имеют наибольший общий делитель g, то индекс числа a не может быть меньше N — N/g. В частности, в первой половине последовательности идущие подряд числа взаимно просты.
Я так понимаю, у них разные движки, но все равно такая разница удивительна.
Вы имеете в виду с целью выяснить умение пользоваться JOIN, или в данном случае у него есть преимущества над EXCEPT?
А в данном случае нельзя использовать EXCEPT?
А какой у Вас браузер? У меня в Хроме на скорости 2x — 120 итераций в секунду, на 50x — 220. В Edge и на мобильном телефоне на всех 1x-50x скорость одинаковая — примерно 17 итераций в секунду, но, думаю, это из-за движка яваскрипта.
Хотя я согласен, битовая арифметика будет замедляет алгоритм в любом случае.
Теоретически, если искать простые числа не в одном большом массиве на гигабайты, а разделить его на куски по несколько мегабайт, чтобы весь битовый массив поместился в кеш третьего уровня, может, тогда ускорение доступа к памяти может исправить замедление от битовых операций.
Оптимизация таких числодробилок иногда бывает очень нетривиальна. У меня, например, скорость увеличивается в полтора раза, только если закомментарить строку if (n >= Length) throw new ArgumentException(«Number too big»);
Возможно, она как-то препятствует jit-у инлайнить метод, не изучал вопрос.
Кстати, получить итератор по всем простым числам в возрастающем порядке (самый частый use-case) можно эффективнее, чем проверять на простоту числа последовательно от 1 до ста миллионов (используя, как раз, массив BIT_TO_INDEX), просто я старался сделать код как можно проще, даже ценой ухудшения производительности.
1) P = 1 — ( 1/2 * 2/3 * 3/4 *… * 89/90 * 90/91 ) = 1 — 1/91 = 90/91 ~ 0.989
2) P = 1 — ( (1*3)/(2*2) * (2*4)/(3*3) * (3*5)/(4*4) *… * (89*91)/(90*90) * (90*92)/(91*91) ) = 1 — 1/2 * 92/91 = 45/91 ~ 0.495
Нашел в Викпедии, что Baillie–PSW primality test, который является комбинацией двух вероятностных тестов на простоту (Ферма и Лукаса), вообще не имеет исключений для 64-битных чисел. Больше того, даже для произвольно больших чисел за сорок лет ни одного исключения так и не нашли. Так что Ваша идея тут кстати: размер базы будет нулевой практически всегда. А если вдруг кто-нибудь найдет составное число, проходящее этот тест, он даже получит премию в 30 долларов!
А из более поздних исследований нашел эту статью 2015 года — они утверждают, что их алгоритм самый быстрый (скорость проверки — чуть больше миллиона 64-битных чисел в секунду) из класса алгоритмов, не требующих предварительных вычислений.
Забавно, но я у них нашел такую цитату:
То есть, они тоже считают, что для некоторых случаев битовая таблица — лучшее решение, но даже они говорят о бите на каждое нечетное число! Хотя Wheel factorization широко известен, почему-то даже ученые его игнорируют при практическом применении
1) массив байт можно сохранить в файл одним вызовом File.Write
2) в .NET Framerork массив ulong-ов все равно просто так не создать
3) если мы захотим считать простые числа, например, до триллиона (вдруг у нас есть 30 гб памяти), массив ulong сам станет больше двух миллиардов элементов.
Понятно, спасибо. Я почему-то думал, что MT — это обобщенное название класса машин, эквивалентных классической MT с одномерной лентой.
Впрочем, далеко не во всех задачах требуется константная скорость проверки, тогда, действительно, можно пожертвовать скоростью ради уменьшения размера базы. В предельном случае, если я правильно понимаю, можно вообще ничего не хранить, и применять AKS-тест каждый раз заново.
А при использовании готовой базы — да, конечно, вместо того, чтобы загружать базу в память, можно просто читать с диска по нужному смещению.
N: 52; Results: 0; Time: 89 sec
N: 53; Results: 0; Time: 213 sec
N: 54; Results: 0; Time: 204 sec
N: 55; Results: 0; Time: 336 sec
N: 56; Results: 0; Time: 316 sec
N: 57; Results: 0; Time: 438 sec
N: 58; Results: 0; Time: 453 sec
N: 59; Results: 0; Time: 1109 sec
N: 60; Results: 0; Time: 974 sec
N: 61; Results: 0; Time: 2230 sec
N: 62; Results: 0; Time: 2357 sec
N: 63; Results: 0; Time: 3099 sec
N: 64; Results: 0; Time: 3016 sec
N: 65; Results: 0; Time: 4896 sec
N: 66; Results: 0; Time: 4462 sec
N: 67; Results: 0; Time: 9399 sec
N: 68; Results: 0; Time: 9157 sec
N: 69; Results: 0; Time: 12960 sec
N: 70; Results: 0; Time: 12709 sec
Суть оптимизации вот в чем:
Понятно, что первые два числа в последовательности не могут быть одновременно четными, так как тогда все остальные числа тоже будут четными. Более того, четных чисел только N/2, поэтому два подряд четных числа могут встретиться только во второй половине последовательности. Аналогично, если два идущих подряд числа делятся на три, то все следующие числа тоже делятся на три, поэтому они могут встретиться только в последней трети последовательности. Обобщая, если два идущих подряд числа a, b имеют наибольший общий делитель g, то индекс числа a не может быть меньше N — N/g. В частности, в первой половине последовательности идущие подряд числа взаимно просты.