кортежи последовательных простых. ключ к 19-252

[maxal]

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

Не согласен, мои тесты показывают ускорение всего в 3 раза вместо 4 на 4 ядрах, при этом они все 4 загружены на 100%, кажется я приводил пример в теме про PARI/GP.

Дайте ссылку, я посмотрю. Если это вина именно PARI/GP (а не алгоритма как такового), то это исправимо.

[Dmitriy40]

maxal
Ссылку искать долго, сварганил готовый пример (похожий по логике на выложенный выше код, да и вообще на наши потуги в темах про кортежи):

{stop=precprime(10^7); export(stop); t0=getwalltime();
for(a=1,stop-1,
   my(x);
   x=lift(chinese(Mod(1,9699690),Mod(1,stop)));
   if(ispseudoprime(x), print(x));
);
print("Time: ",strtime(getwalltime()-t0));}

Запуск его под x64:
C:\TEMP>gp64 -q par.gp
Time: 4,367 ms
Запуск ровно того же кода многопоточным PARI/GP (загружен один поток):
C:\TEMP>gpp -q par.gp
Time: 18,740 ms
Меняю for на parfor, остальное оставляю как есть, запуск обычного PARI/GP:
C:\TEMP>gp64 -q par.gp
Time: 5,129 ms
И запуск в многопоточном режиме на 4 ядрах (общая загрузка 90%, из них треть в ядре):
C:\TEMP>gpp -q par.gp
Time: 29,099 ms

Если что, видно что print не вызывается ни разу, так что побочных эффектов нет.
Время соответствуют реальному (замеренному сторонними средствами).

Вы видите ускорение счёта в 4 раза? Я вот вижу замедление раз так в 5-6! При почти полной загрузке всех ядер и не пойми зафига вызываемым арбитраже (через ядро).

-- 24.08.2025, 21:49 --

Другой вариант кода:

{stop=precprime(10^7); export(stop); t0=getwalltime(); n=0;
parfor(a=1,stop-1,
   my(x,y=0);
   x=lift(chinese(Mod(1,9699690),Mod(a,stop)));
   if(ispseudoprime(x), y++);
   y
,r,n+=r
);
print("n=",n,"/",stop-1,", time: ",strtime(getwalltime()-t0));}

Запуск обычного PARI/GP:
C:\TEMP>gp64 -q par.gp
n=1876423/9999990, time: 15,758 ms
Запуск многопоточного (снова загрузка всех 4 ядер на 90% с третью в ядре):
C:\TEMP>gpp -q par.gp
n=1876423/9999990, time: 37,398 ms

Где ускорение, а, Зин?

-- 24.08.2025, 22:04 --

gris
Заодно померил скорость chinese относительно ispseudoprime. На последнем варианте кода, в однопоточном режиме.
Без if время выполнения 7.1с, с ним и одной ispseudoprime 15.8с, с двумя ispseudoprime (х и х+9699690) 17.4с. Так что в данном примере chinese+lift занимают 40%-45% общего времени. Не 5%.

[gris]

Dmitriy40 Отвечаю на уже наверное ненужный вопрос: С другой стороны, откуда Вы взяли цифру 5%, её реально измеряли или это просто прикидка на глазок?
В общем-то почти на глазок, потому что измерял по нескольким паттернам, периодам, числу и дальности периодов. Испытаний не очень много. Проверял полную программу и программу с выключенной проверкой. Кстати, я считаю хорошей проверку, которая заканчивается почти сразу . Тут есть ещё особенность старого алгоритма: если идёт поиск по тысяче периодов, то китайская формула при ей получении проверяется по всей тысяче и тогда соотношение ещё меньше. Впрочем, нужно смотреть именно по той программе, которая используется. Но я в ней не разбирался подробно, надеясь, что это сделают более опытные товарищи. Меня уже давно вынесло из интереснейшей темы, так что вряд ли я могу быть полезным
+++ Раскопал старую программку поиска 15-к. Запустил с проверкой на периоде 37# с номером 1344777771 number from 1344777771 number to
7420738134810 period
search in 9979243688104489308510 (1.0 E22) - 9979243695525227443320 (1.0 E22) L=7.42 E12
50462720 formulae
time = 23min, 21,826 ms.
С выключенным блоком проверки
time = 6min, 4,466 ms.
Если уменьшить проверяемый диапазон до Е18 и сделать поиск по 19#, то да, получится 50-60%.

[maxal]

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

{ n_threads = default(nbthreads);
stop=precprime(10^7); export(stop,n_threads); t0=getwalltime();
parfor(th=0, n_threads-1,
forstep(a=1,stop-1,Mod(th, n_threads),
   my(x);
   x=lift(chinese(Mod(1,9699690),Mod(1,stop)));
   if(ispseudoprime(x), print(x));
));
print("Time: ",strtime(getwalltime()-t0)); }

[Dmitriy40]

maxal
Не помогает:

{nth=default(nbthreads);
stop=precprime(10^7); export(stop,nth); t0=getwalltime(); n=0;
parfor(th=1,nth,
   my(x,y=0);
   forstep(a=th,stop-1,nth,
      x=lift(chinese(Mod(1,9699690),Mod(a,stop)));
      if(ispseudoprime(x) && ispseudoprime(x+9699690), y++);
   );
   y
,r,n+=r);
print("n=",n,"/",stop-1,", time: ",strtime(getwalltime()-t0));}

Запуск в один поток:
C:\TEMP>gp64 -q par.gp
n=349035/9999990, time: 15,506 ms
Запуск многопоточно (100% загрузка 4-х ядер, четверть в ядре):
C:\TEMP>gpp -q par.gp
n=349035/9999990, time: 15,869 ms
Задачи максимально большие. Ускорения ноль.

[maxal]

Dmitriy40
Вы видите ускорение при использовании nth=default(nbthreads); vs. nth=1; на одной и той версии (многопоточной) gp? В идеале оно должно быть кратно количеству тредов, но малых задачах может быть и меньше.
По поводу сравнения ваших gp64 и gpp - правильно ли я понял, в gp64 многопоточность запрещена на этапе компиляции? Т.е. у вас в принципе однопоточная версия gp работает быстрее многопоточной gp (безотносительно использования параллелизации)? Если так, я советую написать об этом авторам GP. Что-то здесь нечисто, но к внутреязыковой параллелизации это имеет опосредованное отношение.

[Dmitriy40]

maxal в сообщении #1699569 писал(а):

По поводу сравнения ваших gp64 и gpp - правильно ли я понял, в gp64 многопоточность запрещена на этапе компиляции?

Ну в исходник я не смотрел, но похоже что да, на этапе компиляции:

          GP/PARI CALCULATOR Version 2.13.4 (released)
  amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
   compiled: Mar 25 2022, gcc version 8.3-posix 20190406 (GCC)
                    threading engine: single
         (readline v8.0 enabled, extended help enabled)

maxal в сообщении #1699569 писал(а):

Т.е. у вас в принципе однопоточная версия gp работает быстрее многопоточной gp (безотносительно использования параллелизации)?

На параллельном коде - да, очень часто так и есть. Не всегда. Помню же что получал ускорение втрое (вместо вчетверо) на какой-то задаче.
Не параллельный же код выполняется параллельным PARI/GP в одном потоке вообще страшно медленно (18.7с против 4.4с, специально показал выше).

maxal в сообщении #1699569 писал(а):

Вы видите ускорение при использовании nth=default(nbthreads); vs. nth=1; на одной и той версии (многопоточной) gp?

Вижу, но далеко не в 4 раза (при полной загрузке всех 4 потоков):
C:\TEMP>gp64 -q par.gp
n=3021418/99999988, nth=1, time: 2min, 40,742 ms
C:\TEMP>gpp -q par.gp
n=3021418/99999988, nth=1, time: 5min, 49,685 ms
C:\TEMP>gpp -q par.gp
n=3021418/99999988, nth=4, time: 2min, 39,603 ms

Здесь увеличил объём работы до $10^8$, плюс добавил вывод актуального значения nth, в остальном код последний показанный.

Вот только такое ускорение не имеет смысла: оно с загрузкой всех 4 потоков всего лишь достигает скорости однопоточного приложения. Которое можно запускать в 4 потока руками и будет ровно в 4 раза быстрее (запустил лишь одну th, но nth=4 для деления задачи на 4 части):
C:\TEMP>gp64 -q par.gp
n=756677/99999988, nth=4, time: 40,623 ms
Т.е. за 40с можно посчитать всю задачу если и поделить и запустить её руками каждую часть в однопоточном режиме. За 40с, не 160с как многопоточная версия на всех 4 ядрах.

Вот примерно это я и имел в виду когда говорил что parfor на наших задачах работает плохо (а внутренние вычисления бывают и ещё значительно проще!). Мало того что его ещё подшамань (и не всегда это получается! например может тупо не хватить памяти под общие таблицы для всех потоков хотя можно было бы их хранить в одном экземпляре в общей памяти, да, знаю что MPI такое не позволяет), так и выигрыша может вообще не быть, а то и сильный проигрыш.

-- 25.08.2025, 00:29 --

Да, для справки: все 4 ядра физические, никакого гипертрейдинга, частоты ядер на время работы стабильные, проц тёплый (не перегревается). Причин тормозить многопоточному коду не вижу. При этом одновременно 4 однопоточных кода работают прекрасно. Как и мои многопоточные программы на С, Дельфи, Асме. Проблема считаю где-то в PARI/GP (gpp.exe). Наблюдалось и на нескольких предыдущих версиях, это не глюк конкретно этой. Более новые версии боюсь использовать, там у них постоянно глюки даже в forprime, а он мне нужен.

[maxal]

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

amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version

Попробуйте обновить версию gp. У вас она скопилирована на mingw, а Bill писал, что наилучшая производительность параллелизации под Windows достигается при использовании WSL. Вроде бы mingw больше и не используется, но я далек от мира винды.

-- Sun Aug 24, 2025 16:41:04 --

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

Более новые версии боюсь использовать, там у них постоянно глюки даже в forprime, а он мне нужен.

Так не нужно игнорировать новые версии, видите ошибку - посылайте bug report, девелоперы PARI/GP на них очень быстро реагируют и фиксят.

[Dmitriy40]

Проверил на последней версии, всё то же самое:
C:\TEMP>gp64 -q par.gp
n=349035/9999990, nth=1, time: 14,791 ms
C:\TEMP>gpp -q par.gp
n=349035/9999990, nth=4, time: 18,340 ms
Версия:

          GP/PARI CALCULATOR Version 2.17.2 (released)
  amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version
        compiled: Feb 28 2025, gcc version 12-posix (GCC)
            threading engine: pthread, nbthreads = 4
         (readline v8.0 enabled, extended help enabled)

А ошибок я не видел, просто почитал внимательно Changelog чтобы оценить насколько важны доработки и нужно ли обновляться - а там буквально через версию раза 3 или 4 исправления глюков в forprime ... После такого как-то мало уверенности что исправили всё (на тот момент, как сейчас не изучал). Не, такого счастья не надо, остальные исправления мне вообще не критичны.

Да и вон и в 2.18.0 (и 2.17.1) тоже исправлено (в очередной раз):
forprime(p=524288,1048576,1) -> crash [#2584]
forprime(p=1048607,1048617,1) -> oo loop
А в 2.17.2 исправили другой глюк: forprime(p=1099505335069-100000,1099505335069+10000,) -> crash
Т.е. по факту до конца так и не исправили, уже почти год как.
Ну и как тут быть уверенным что оно правильно работает?!

[maxal]

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

amd64 running mingw (x86-64/GMP-6.1.2 kernel) 64-bit version

Это также mingw. Они WSL сборку не выкладывают?

[Yadryara]

gris в сообщении #1699564 писал(а):

Но я в ней не разбирался подробно, надеясь, что это сделают более опытные товарищи.

А можно ли назвать этих более опытных товарищей поимённо?

maxal и wrest отлично разбираются в PARI, но у wrestа вроде нет интереса к кортежной тематике, а maxal давно от неё отошёл.
vicvolf кое-что понимает в кортежах, но я не замечал его за программированием на PARI.
Насколько понял, waxtep понимает в PARI и недавно заинтересовался кортежами. Но назвать уважаемого Шахтёра более опытным всё же не рискну.
Jarek, да, весьма много понимает и в кортежах, и в программировании. Но его весьма быстрые программы конечно были не на PARI, да и на форуме он давным-давно не появляется. Увы.
whitefox сильно помог: написал быструю программу сплошного поиска на сях, но его тоже лет 100 нет на форуме
впс. Да, вроде кое-что понимаю в кортежах. Но PARI я вряд ли знаю лучше вас и Map-ом пользоваться в бытовых вопросах не умею.

Остаётся Dmitriy40, который, подчёркиваю, прекрасно разбирается и в том и в другом. На мой взгляд не хуже Jarekа. И уже здорово помог. Подтверждаю: в кортежных темах есть масса полезной информации, которая НМ игнорируется. И нередко намеренно.

gris в сообщении #1699564 писал(а):

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

Где используется, кем используется? И почему надеетесь? Зачем это вам надо, чтобы более опытные товарищи разобрались, да ещё и подробно?

[Dmitriy40]

maxal в сообщении #1699580 писал(а):

Это также mingw. Они WSL сборку не выкладывают?

Понятия не имею, скачал все 4 варианта с ftp: gp64-2-17-2.exe, gppthread64-2-17-2.exe, gp64-readline-2-17-2.exe, gppthread64-readline-2-17-2.exe - они все mingw. Внутри большого 109М инсталятора Pari64-2-17-1-pthread.exe тоже mingw версия. Сам собирать из исходников не буду.

[maxal]

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

Понятия не имею, скачал все 4 варианта с ftp: gp64-2-17-2.exe, gppthread64-2-17-2.exe, gp64-readline-2-17-2.exe, gppthread64-readline-2-17-2.exe - они все mingw. Внутри большого 109М инсталятора Pari64-2-17-1-pthread.exe тоже mingw версия. Сам собирать из исходников не буду.

Значит, именно для вас преимущества параллелизации PARI/GP будут не доступны. Если поменяете свое мнение, то вот инструкция про установку полноценной версии PARI/GP под винду: https://pari.math.u-bordeaux.fr/PDF/PARIwithWindows.pdf

[Dmitriy40]

maxal
Так у Вас на моём коде получается ускорение работы пропорционально количеству потоков?