32 vs 64

[Yadryara]

Продолжение разговора о скорости работы х32 и х64 компов.

Dmitriy40 в сообщении #1623582 писал(а):

Это я выше проверил, замедление примерно 1.5 раза.

Ну так Вы разве можете это полноценно проверить на 64-м компе? См. ниже.

Dmitriy40 в сообщении #1623582 писал(а):

Да, а для x64 граница резкого замедления $2^{64}$, это связано с тестом простоты по малой теореме Ферма (точнее его развития BPSW, где малая теорема Ферма отрабатывает первой в составе одной итерации теста Миллера-Рабина), реализуемым как вычисление возведения в степень по модулю проверяемого числа. Пока проверяемое число влезает в регистр есть аппаратная команда взятия остатка (деления с остатком), как только перестаёт влезать - надо деление выполнять программно, что заметно медленнее.

Так я именно об этом и говорю. Для чисел больших, чем $2^{32}$, но меньших чем $2^{64}$ (а у нас как раз такой случай) мой 32-й уступает Вашему 64-му не в полтора раза, а в 5-7 раз. Чтобы точнее определить, надо одну и ту же прогу запускать.

[Dmitriy40]

Надо уточнить что речь идёт о скорости PARI/GP, а не просто компа.

Yadryara в сообщении #1623604 писал(а):

Ну так Вы разве можете это полноценно проверить на 64-м компе?

На вычислительных задачах - могу, почему нет: запускаю gp32 вместо gp64 для той же программы и всё. И пока он не обращается к ОС он будет работать в режиме x32. А разницей в скорости редких системных вызовов (опрос очереди сообщений ОС, переключение задач) под x32 и x64 ОС можно просто пренебречь.

Вообще да, сама ispseudoprime сильно тормозит, вот оставил в проверке только их и сравнил, 33с vs 177с, в 5.4 раза. Но у меня то ведь перед ними выполняется проверка просто по модулям, а там лишь одно деление (взятие остатка) и быстрый поиск в массиве, и тогда разница в скорости лишь 42с (да, как ни странно это в x64 в этот раз почему-то медленнее, хотя раньше было в 1.5 раза быстрее) vs 53с, в 1.26 раза. Это явная польза более простых тестов, не ispseudoprime, а setsearch([],x%p).

Так что сравнивать надо не просто комп или PARI/GP, а конкретную программу.


Ради интереса подправил Вашу программу (убрал 29# оставив только 23#; сократил длину проверки до 10e9; убрал вывод найденных цепочек; добавил вывод времени этапов; чуть сократил вывод) и сравнил скорость:

x64:
552960/223092870, time: 1,745 ms
24330245/21, time: 1min, 7,701 ms
x32:
552960/223092870, time: 1,635 ms
24330245/21, time: 5min, 29,404 ms

Да, разница в 5 раз это именно разница в скорости ispseudoprime. Стоит добавить более быструю предпроверку перед ними.
Например проверку начального числа по простым модулям 30-200 (сильно больше ставить уже нет смысла):
перед основным циклом добавить заполнение нового массива запрещённых остатков: mm=vector(200,i,[]); forprime(p=30,#mm, mm[p]=Set(-v%p));
в основном цикле перед проверкой ispseudoprime добавить предпроверку по остаткам: forprime(p=30,#mm, if(setsearch(mm[p], kan%p), next(2)));
Это уменьшит время с 68.1с до 50.9с под x64 и с 330с до 71с под x32 (с основной таблицей лишь по 23#, 29# проверяйте сами). Новых Вам кэфов!

[Dmitriy40]

У меня была небольшая ошибка, в логах выше число 24330245 некорректное, должно быть 25436160, не так поставил условие пропуска цепочек ниже start и выше fin (это ещё одно изменение что внёс). Но на отношение скоростей это практически не влияет.
Эту проверку, попадания цепочки в указанный диапазон, лучше перенести из конца в начало, сразу после вычисления kan добавить if(kan<start || kan>=fin, next);. Так не будут долго проверяться цепочки точно за границей диапазона. Впрочем это важно лишь для коротких диапазонов, меньше десятков миллиардов.

Ещё полезно отсортировать массив o[], это в 1.5 раза замедляет инициализацию, зато потом счёт быстрее примерно на 15% (после переноса проверки и для диапазона 10e9).

[Yadryara]

Спасибо, буду разбираться.

Dmitriy40 в сообщении #1623573 писал(а):

Насчитала 1339шт. Одна где-то потерялась. Да и плевать.

Подозреваю, что нельзя плевать. Хотя, может Вы уже поняли в чём дело и исправили.

[Dmitriy40]

Да, это тот же глюк у меня, посчитал что массив o[] сортирован и последний блок недосчитался. Сейчас поправил и да, 1340шт.

[Yadryara]

Наконец дошли руки разобраться с этими идеями.

Dmitriy40 в сообщении #1623617 писал(а):

Это уменьшит время с 68.1с до 50.9с под x64 и с 330с до 71с под x32 (с основной таблицей лишь по 23#, 29# проверяйте сами).

Проверил. В 15 раз ускорение для 29#, в 42 раза для 23# и в 34 раза для 19#.

Естественно проверку по setsearch переносил: 24-200 и 20-200 соответственно.

Результат лучше ожиданий!

Самые последние идеи ускорения пока не тестировал. Может напишу в исходной теме.

[wrest]

Dmitriy40 в сообщении #1623617 писал(а):

Надо уточнить что речь идёт о скорости PARI/GP, а не просто компа.

Я бы ещё доуточнил, что в вашем случае речь так же идёт об исполнении pari/gp в двух разных окружениях - mingw32 и (вероятно) mingw64, что, как мне кажется, добавляет изрядно перца (или соли) в вопрос.

[Dmitriy40]

Понятия не имею ни про какие окружения, есть один единственный файл .exe (точнее два, gp32.exe и gp64.exe) и больше ничего не нужно. Если даже оно где-то внутри винды (Win7Pro x64 или WinXPPro x32 что ещё сомнительней) или этого вот .exe и есть, то это вообще не мои проблемы. В винде и море .dll есть (и друг дружку вызывают), ну и что. Вопрос-то чисто практический.

[wrest]

Dmitriy40 в сообщении #1627440 писал(а):

или этого вот .exe и есть, то это вообще не мои проблемы.

Не ваши, просто это добавляет неопределенность в качество сравнения 32vs64.