Как писать быстрые программы

[wrest]

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

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

Ессно! Если теоретическая вычислительная сложность сильно меньше практически получаемой вами -- то надо заняться математикой. Но если не сильно, то надо заняться программированием.
В случае заняться программированием - это то о чём писали мы с Dmitriy40

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

повторных вычислений, лишних вызовов функций, лишних присваиваний больших данных.

wrest в сообщении #1709105 писал(а):

надо внимательно вычищать неоптимальности в коде -- лишние/повторные вычисления, лишние присваивания и т.п.

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

вникать в математику задачи. Чего, как понял, вы делать не желаете.

Неа

-- 13.11.2025, 19:17 --

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

Хорошо, послушался вас: выделил почти 4 ГБ. 256 МБ ему тоже оказалось мало.

Компилируете с опцией -g ?

-- 13.11.2025, 19:25 --

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

К советам ИИ в такой довольно сложной задаче пока отношусь скептически.

Вы немного не в ту степь. Тут надо мухи и котлеты в разные тарелки. Дело не только в сложности задачи (математическая часть), а в том если вы к примеру миллион раз вычисляете один и тот же синус, это ошибка в программировании, которую ИИ легко увидит. Или если вы вычисляете миллион разных синусов во внутреннем цикле, но используете только один во внешнем -- это тоже ошибка, которую легко видеть. Это алгоритмическая часть.

[Dmitriy40]

wrest
Пока текущие задачи из внутренних циклов не возвращают ничего, вся проверка и вывод делается в самой глубине.
А вот вынос вычислений из циклов или однократное сохранение в лишнюю переменную может пригодиться.

И помнится не так давно делали разбор советов ИИ на аналогичной задаче, как помню там половина была бред, ещё треть банальности, и оставшийся один-два (из 10 или 11 советов) были правильными но слишком теоретическими.

[Yadryara]

wrest в сообщении #1709148 писал(а):

Компилируете с опцией -g ?

Да. Один раз куда-то случайно делся этот ключ. Но затем всё время использовал.

Самое интересное что в первом потоке вполне хватило 256 МБ на все 80 комплектов. То есть посчитал всё что надо.

А во втором потоке не хватило даже 4 ГБ. Что за...

9.   1 1   1 2   1 1     13 8   17 5   19 2
3483261727778118145149867977411324671351953940        1 1 11    11 1   111    1        11

3063229202359273780638449225077229086901107540        1 111   1 111 11 111             13

10.   1 1   1 2   1 2     13 8   17 5   19 3
  *** init_Rab_41: Warning: increasing stack size to 536870912.

11.   1 1   1 2   1 3     13 8   17 5   19 4
12.   1 1   1 2   1 4     13 8   17 5   19 12
  *** init_Rab_41: Warning: increasing stack size to 1073741824.

2679211119591444499742247412051777913552169940        1 1 111 1 1   1 1111             12

13.   1 1   1 2   1 5     13 8   17 5   19 14
 14.   1 1   1 2   1 6     13 8   17 5   19 16
15.   1 1   1 2   1 7     13 8   17 5   19 18
  *** init_Rab_41: Warning: increasing stack size to 2147483648.

3528990856474405723050249827738486681269123540        1 111  11 1 111111 1             14

16.   1 1   1 2   1 8     13 8   17 5   19 19
17.   1 1   1 3   1 1     13 8   17 12   19 2
18.   1 1   1 3   1 2     13 8   17 12   19 3
  *** init_Rab_41: Warning: increasing stack size to 4000002048.

3279694359470076358591238915740293829811352340        1 1 11 11111 1     1             11

19.   1 1   1 3   1 3     13 8   17 12   19 4
3271971224970694939473409848928636111874649940        1 1 11    1  1  1                7

20.   1 1   1 3   1 4     13 8   17 12   19 5
  ***   at top-level: init_Rab_41()
  ***                 ^-------------
  *** init_Rab_41: the PARI stack overflows !
  current stack size: 4000002048 (3814.699 Mbytes)
  [hint] you can increase 'parisizemax' using default()

  ***   Break loop: type 'break' to go back to GP prompt
break>

То есть комп всё увеличивал-увеличивал память пока не доувеличивался

И кстати код на PARI занимает всего лишь чуть больше 5 КБ, а на Сях — 42 КБ.

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

Правда, сделал объединённую прогу на 240 комплектов. Теперь вся надежа на Демиса

-- 14.11.2025, 07:53 --

wrest в сообщении #1709148 писал(а):

Дело не только в сложности задачи (математическая часть), а в том если вы к примеру миллион раз вычисляете один и тот же синус, это ошибка в программировании, которую ИИ легко увидит. Или если вы вычисляете миллион разных синусов во внутреннем цикле, но используете только один во внешнем -- это тоже ошибка, которую легко видеть.

Вот именно что легко видеть. И давно заметили бы безо всякого ИИ.

[wrest]

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

В общем пока стало только хуже: в итоге я не считаю ни старым,

А что вам мешает считать старым способом?

[Yadryara]

Во-первых, только что написал: как оказалось, память очень нужна новым прогам.

Во-вторых, для надёжной засечки времени работы, желательно комп другими задачами не нагружать.

[wrest]

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

То есть комп всё увеличивал-увеличивал память пока не доувеличивался

Да, это странно, еслииопция -g точно использовалась. Из функций, потенциальный потребитель памяти это chinese(), наверное. Либо во внутренних циклах не убирается стек.
В коде на C в конце каждого цикла должен быть if (gc_needed(btop, 1)) и затем чистящая стек процедура gerepileall(btop, ...) с длинным списком переменных, которые могли изменяться в цикле.

-- 14.11.2025, 08:57 --

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

Самое интересное что в первом потоке вполне хватило 256 МБ на все 80 комплектов. То есть посчитал всё что надо.

А во втором потоке не хватило даже 4 ГБ. Что за...

Скажите, что за потоки?

-- 14.11.2025, 09:03 --

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

Во-вторых, для надёжной засечки времени работы,

Уже ведь выяснили, что имеете примерно двукратное ускорение при компиляции.

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

желательно комп другими задачами не нагружать.

Так вы же всё это делаете не для того, чтобы время считать, а чтобы ваши комплекты обсчитывать. Упадёт у вас скорость, и что? Пусть бы ваш pari.exe считал бы там себе в сторонке и считал, пока вы доводите до ума новый способ...

[Yadryara]

wrest в сообщении #1709206 писал(а):

В коде на C в конце каждого цикла должен быть if (gc_needed(btop, 1)) и затем чистящая стек процедура gerepileall(btop, ...) с длинным списком переменных, которые могли изменяться в цикле.

А вы ещё и в Сях разбираетесь? Здорово. Есть такая, да:

if (gc_needed(btop, 1))
gerepileall(btop, 2, &bad, &ost);

wrest в сообщении #1709206 писал(а):

Скажите, что за потоки?

Старый способ. Я просто открывал ещё одно окно консоли и в нём запускал ещё один вариант программы на PARI. Итого было 12 открытых окон.

Вчера я решил начать со старого способа. Открыл два окна Убунту и в них запускал варианты программы.

wrest в сообщении #1709206 писал(а):

Уже ведь выяснили, что имеете примерно двукратное ускорение при компиляции.

Это только для одного потока. А как для 12-ти? Я это не выяснил до сих пор. В новом запуске тоже не хватило памяти. Правда, это случилось позже, то есть счёт прошёл дальше, прежде чем прерваться:

14.   1 1   1 2   1 6     13 8   17 5   19 16
15.   1 1   1 2   1 7     13 8   17 5   19 18
3528990856474405723050249827738486681269123540        1 111  11 1 111111 1             14

 16.   1 1   1 2   1 8     13 8   17 5   19 19
17.   1 1   1 3   1 1     13 8   17 12   19 2
18.   1 1   1 3   1 2     13 8   17 12   19 3
  ***   at top-level: init_Rab_41()
  ***                 ^-------------
  *** init_Rab_41: the PARI stack overflows !
  current stack size: 536870912 (512.000 Mbytes)
  [hint] set 'parisizemax' to a nonzero value in your GPRC

  ***   Break loop: type 'break' to go back to GP prompt
break>

wrest в сообщении #1709206 писал(а):

Пусть бы ваш pari.exe считал бы там себе в сторонке и считал, пока вы доводите до ума новый способ...

В какой ещё сторонке? Одно с другим, видимо, связано. Вот недавно про отключение рассказывал.

[wrest]

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

Открыл два окна Убунту и в них запускал варианты программы.

А что значит "варианты" -- это разные программы, с разными именами файлов *.gp (и соответствующими *gp.c;*.gp.so; *.gp.run), и которые пишут логи в разные файлы?

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

Это только для одного потока. А как для 12-ти? Я это не выяснил до сих пор.

Не, 12 экземпляров программы не будут считать в 12 раз быстрее одного. Осетра придётся урезать, я думаю что больше 5-6 одновременных экземпляров практического смысла нет, но можете попробовать, конечно...

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

А вы ещё и в Сях разбираетесь?

Об опции -g написано в доках: https://pari.math.u-bordeaux.fr/pub/par ... le_and_run

[Dmitriy40]

wrest в сообщении #1709217 писал(а):

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

А должны. Ну пусть не в 12 (из-за гипертрейдинга), но раз в 8 таки должны. И уж точно не менее чем в 6 раз (количество физических ядер).
И тем более должен сохраняться выигрыш от компиляции, т.е. 12 потоков под WSL должны считаться (примерно вдвое) быстрее 12 потоков под виндой.

[Yadryara]

wrest в сообщении #1709217 писал(а):

А что значит "варианты" -- это разные программы, с разными именами файлов *.gp (и соответствующими *gp.c;*.gp.so; *.gp.run), и которые пишут логи в разные файлы?

В последнее время эта одна и та же программа, в которой меняется ровно одно число, которое принимает значения от 0 до 11. Можно считать это номером потока.

Имя файла .gp остаётся одним и тем же. Чтобы их не путать, в начале и в конце работы программы выводится инфа типа "Potok 10". И все 12 программ пишут инфу в два файла .txt. В одном прогресс, в другом — находки. Фалов с логами именно 2, а не 24.

wrest в сообщении #1709217 писал(а):

Осетра придётся урезать,

Уж давно урезал. Не карась даже, а пескарик какой-то на дне трепыхается.

wrest в сообщении #1709217 писал(а):

Об опции -g написано

Только длинного списка я не наблюдаю. Вроде только bad и ost.

[Dmitriy40]

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

Фалов с логами именно 2, а не 24.

Не стоит так делать, мнопоточная запись в файлы слишком глючна (и в некоторых вариантах просто не работает), пишите в отдельные файлы, а собирайте вместе уже после окончания счёта.

-- 14.11.2025, 14:53 --

wrest, Yadryara
Стоит научиться компилировать и сам полученный C файл без компиляции gp файла если это ещё не сделано - например после исправления/оптимизации С файла.

[wrest]

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

Имя файла .gp остаётся одним и тем же.

Это плохо.
Получается, вы скомпилировали вашу программу и получили файлы myprog.gp;myprog.gp.c.;myprog.gp.so;myprog.gp.run
и запускаете (ну gp2c за вас запускает) команду gp myprog.gp.run которая устанавливает вашу функцию в gp и связывает её с myprog.gp.so)
Затем, пока это всё работает в одной сессии линукса, вы вносите изменения в myprog.gp и по-новой создаёте myprog.gp.c.;myprog.gp.so;myprog.gp.run на тех же местах -- но уже другие, и запускаете.

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

Имя файла могло бы быть одним и тем же, если бы это была функция PentaDecaDream(potok_number), в которую вы передаёте параметр potok.

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

И все 12 программ пишут инфу в два файла .txt.

Одновременно?

-- 14.11.2025, 15:15 --

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

Стоит научиться компилировать и сам полученный C файл без компиляции gp файла если это ещё не сделано - например после исправления/оптимизации С файла.

да в принципе, команды компиляции gp2c записывает виде комментариев в *.gp.c так что в общем-то остаётся только их скопипастить в командную строку. Ну я вот не пробовал.
Мне кажется оптимизировать сишный код вышедший из-под gp2с -- это хождение по минному полю.

[Yadryara]

wrest в сообщении #1709229 писал(а):

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

Имя файла .gp остаётся одним и тем же.

Это плохо.
Получается, вы скомпилировали вашу программу и получили файлы

Подождите! Точно скомпилировал? Я же Вам рассказываю старый способ счёта. То есть с помощью интерпретатора.

wrest в сообщении #1709229 писал(а):

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

Ну после компиляции я таким способом пока только два потока запускал. А сегодня специально запустил ровно один potok 1 и всё равно переполнение было. 512 МБ не хватило. А для интерпретатора 128 МБ всегда хватало.
Potok 0 ранее успешно уложился в 256 МБ.

wrest в сообщении #1709229 писал(а):

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

И все 12 программ пишут инфу в два файла .txt.

Одновременно?

Ну как бы да. Комп должен сам следить чтобы выстраивать в очередь желающих записаться. Или неправильно понимаю?

[wrest]

Yadryara

Я, кстати, ваш код ускорил процентов на 10 примерно, просто явной типизацией счётчиков циклов и других переменных.
Но там есть переменные которые вообще не используются, видимо у меня код неполный. По некоторым переменным непонятно могут они быть большими числами или не могут, не разбирая всю вермишель кода.
Ещё несколько процентов даст отказ от операций с множествами (setminus с предварительной конвертацией вектора во множество) во внутренних циклах, это малоэффективно и много раз делается. Во внутренних циклах так же создаются новые переменные. Это значит, что каждый раз когда внешний цикл вызывает внутренний, все эти переменные создаются заново и потом уничтожаются и так постоянно. Например на шестом (!) уровне вложенности у вас есть строчка s = vector(#v); при том что ранее s нигде не встречается. Мне так же показалось, что и присваиваний во внутренних циклах могло быть меньше.
Вот на эти аспекты гляньте.

-- 14.11.2025, 16:00 --

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

Подождите! Точно скомпилировал? Я же Вам рассказываю старый способ счёта. То есть с помощью интерпретатора.

А, ну тогда ок. Как вас понять, что у вас старое, а что новое...

-- 14.11.2025, 16:02 --

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

А сегодня специально запустил ровно один potok 1 и всё равно переполнение было. 512 МБ не хватило. А для интерпретатора всегда 128 МБ всегда хватало.

Ну так интерпретатор видать всё время чистит лишнее, на это уходит время...

-- 14.11.2025, 16:08 --

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

Комп должен сам следить чтобы выстраивать в очередь желающих записаться. Или неправильно понимаю?

Да, если вы или pari за вас, в программе следите за тем, чтобы файлы закрывались, освобождая их на запись.
И пока они стоят в очереди "желающих записаться", они же наверное ничего не считают, вы это понимаете же?
Ну и плюс в логе получаются записи от разных "потоков", хотя если там у вас структура такая, что это не мешает, то и хорошо.

[Dmitriy40]

wrest в сообщении #1709241 писал(а):

Например на шестом (!) уровне вложенности у вас есть строчка s = vector(#v); при том что ранее s нигде не встречается.

Так выше она и не нужна, она будет нужна ниже, а здесь её нужно обнулить, и именно на каждой итерации внутреннего цикла, можно и без выделения ей памяти (выделить где-то раньше), но в PARI нет удобного механизма обнуления переменных (именно заполнением нулями), потому проще было написать именно так.

-- 14.11.2025, 16:14 --

Я же говорю, код оптимизирован под интерпретатор PARI и под удобство программиста (меньше писанины и понятнее) ... ну когда это не противоречит скорости, но в интерпретаторе же.

-- 14.11.2025, 16:18 --

wrest в сообщении #1709241 писал(а):

Да, если вы или pari за вас, в программе следите за тем, чтобы файлы закрывались, освобождая их на запись.

В gp за этим точно не следят.
А вот следит ли PARI в write() за доступностью файла я сильно сомневаюсь, помню его вылеты по ошибке если файл занят другим процессом.
Так что арбитража доступа к файлам в PARI нет.
А в ОС - не знаю, в винде нет, она просто не пустит остальные потоки кроме первого и все они вернут ошибку (в момент открытие файла на запись, это где-то внутри write()) и что потом будут с ней делать неизвестно (у меня под виндой - вылетают в состояние break), так что никакого ожидания освобождения файла и очереди запросов думаю нет.