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

[Yadryara]

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

Я, кстати, ваш код ускорил процентов на 10 примерно, просто явной типизацией счётчиков циклов и других переменных.

Спасибо!
У меня до таких вещей ещё руки не дошли. Я всё ещё занят оргвопросами. Вот только сегодня объединил счёт по обычным и по зеркальным паттернам в одной проге.

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

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

Как это как понять?? Я же внятно написал, что новым способом у меня раз за разом получается переполнение.

А старым — прекрасно считаются и 12, и иногда 13 потоков. И никаких глюков с записью в логи пока не замечал, я периодически смотрю контрольные суммы.

[Yadryara]

wrest, а чего же вам возиться с той тестовой прогой.

Давайте я вам пришлю ту рабочую, где переполнение возникает. Меняешь всего один бит: potok = 1 на potok = 0 и памяти почему-то вполне хватает.

[wrest]

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

Давайте я вам пришлю ту рабочую, где переполнение возникает. Меняешь всего один бит: potok = 1 на potok = 0 и памяти почему-то вполне хватает.

Можно, но вы тогда по всем скалярным целочисленным переменным (кроме совсем временных типа счётчиков циклов) сделайте сводку -- какие точно меньше $2^{63}$ и какие могут быть больше.

-- 14.11.2025, 18:02 --

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

Стоит научиться компилировать и сам полученный C файл

Там вообще чёрт ногу сломит в этом коде, из-за того что это же код, который должен совмещаться с libpari и libgmp, там почти всё такое что вместо a=(b+c)*2+3 будет a = gaddgs(gmulsg(gaddgs(b,c)),gen_2),stoi(3)) ну и всякие "изящества" pari/gp превращаются в сущий кошмар. Создаётся куча новых вспомогательных функций и т.п. Компилятору то пофиг, но это не очень человекочитаемый и челоаекоисправляемый код.

например, есть такая строчка на pari

n0 = (lift(chinese([chinese([Mod(-j+1, v[j]) | j<-[1..#v]]),Mod(32-m32+1, 64),
Mod(9-m9+1, 27)])) + ip) / aa;

из неё получается

static GEN
anon_4(GEN j, GEN v) {
  pari_sp ltop = avma;
  GEN p1 = gen_0;
  p1 = gmodulo(gaddgs(gneg(j), 1), gel(v, gtos(j)));
  p1 = gerepilecopy(ltop, p1);
  return p1;
}

static GEN
wrap_anon_4(void * _cargs, GEN j) {
  GEN _args = (GEN) _cargs;
  GEN _res = anon_4(j, gel(_args, 1));
  return _res;
}
p30 = cgetg(4, t_VEC);
gel(p30, 1) = chinese1(vecapply(mkvec(v), wrap_anon_4, vecrangess(1, glength(v))));
gel(p30, 2) = gmodulo(gaddgs(gsubsg(32, m32), 1), stoi(64));
gel(p30, 3) = gmodulo(gaddgs(gsubsg(9, m9), 1), stoi(27));
n0 = gdiv(gadd(lift(chinese1(p30)), ip), aa);

[Dmitriy40]

И векторным тоже.
И меньше $2^{63}$.

-- 14.11.2025, 18:14 --

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

например, есть такая строчка на pari

Вот в ней все переменные маленькие, кроме p30 и n0. Но это мало поможет, тут тормозит chinese, остальное мелочи.

[Yadryara]

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

Можно, но вы тогда по всем скалярным целочисленным переменным (кроме совсем временных типа счётчиков циклов) сделайте сводку -- какие точно меньше $2^{63}$ и какие могут быть больше.

Уже не сегодня. А пока очень советую почитать тему-мечту.

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

например, есть такая строчка на pari

n0 = (lift(chinese([chinese([Mod(-j+1, v[j]) | j<-[1..#v]]),Mod(32-m32+1, 64),
Mod(9-m9+1, 27)])) + ip) / aa;

Да, это я к шестикратному шагу переходил. То есть для разных паттернов шаг всё равно шестикратный.

[wrest]

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

Вот в ней все переменные маленькие, кроме p30 и n0.

Я про то, в какой кошмар превращается код при трансляции
Что там руками-то править... вроде бы и нечего. И страшно

-- 14.11.2025, 19:10 --

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

Но это мало поможет, тут тормозит chinese, остальное мелочи.

Да, у меня оценка ~10..15% (но проявится только при компиляции). Т.е. компилированное будет считать не в 2 раза быстрее, а скажем в 2.2

По КТО -- Qwen вот тоже написал мне, что надо смотреть в теорию чисел, чтобы поменьше вызывать решение системы по КТО. Типа, а вдруг как-то оно там схлопывается при перестановках. Но не только КТО, там же по ходу дела много факторизаций.

Плюс ещё LLM предложило заменить все конструкции типа mesta2 = setminus(mesta02, Set(mesta1[j1])); на поиск по предварительно созданной таблице.

[Yadryara]

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

Можно, но вы тогда по всем скалярным целочисленным переменным (кроме совсем временных типа счётчиков циклов) сделайте сводку -- какие точно меньше $2^{63}$ и какие могут быть больше.

Не просто могут быть больше, а как правило больше:

m, n0, n, kanp, kan

Остальные вроде явно меньше.

[Dmitriy40]

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

Плюс ещё LLM предложило заменить все конструкции типа mesta2 = setminus(mesta02, Set(mesta1[j1])); на поиск по предварительно созданной таблице.

Очередной пример правильного и бессмысленного совета - насколько я помню эта конструкция вызывается не в самом глубоком цикле, а значит потребляет не так уж и много времени и оптимизировать её надо далеко не в первую очередь, проще увеличить количество итераций следующего по вложенности цикла.
Плюс ещё неизвестно будет ли поиск по таблице быстрее фильтрации одного короткого списка по другому ещё более короткому. Хотя точно можно заменить фильтрацию на битовые операции которые на порядки быстрее. Вопрос надо ли (можно потерять скорость в другом месте).

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

По КТО -- Qwen вот тоже написал мне, что надо смотреть в теорию чисел, чтобы поменьше вызывать решение системы по КТО. Типа, а вдруг как-то оно там схлопывается при перестановках.

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

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

Но не только КТО, там же по ходу дела много факторизаций.

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

[Yadryara]

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

насколько я помню эта конструкция вызывается не в самом глубоком цикле,

В смысле "насколько я помню"? Эту часть кода я написал сравнительно недавно. И пока не присылал Вам программу с ним.

Но да, конечно, не в самом глубоком цикле. И пытаться как-то ускорить — это та самая переоптимизация о которой Вы говорили выше.

Другой пример переоптимизации — не показывать приближения. Я этой фигнёй не страдаю — если приближение находится раз в 25 минут, то мне пока не жалко потратить 1-2 секунды на его обсчёт. Пользу от анализа приближений планирую сегодня ещё раз показать в профильной теме.

[wrest]

В общем я обернул глобальный код Yadryara в функцию, так думаю будет лучше. По ходу дела расставил отступы, чтобы выглядело феншуйно. Можно будет просто добавлять параметры в функцию (я добавил "potok"). На усмотрение Yadryara, конечно.
Все переменные пообъявлял через my(), стек должен теперь очищаться исправно.
Функции пишут логи в файлы с именами зависящими от параметра.
Но логи довольно жидкие, так что коллизий там не предвидится, даже если все инстансы будут писать в один файл.
Теперь надо посмотреть внимательно какие ещё переменные могут быть объявлены как small.
Заглянул в Сишный код сгенерированный gp2c и там по циклам видно что все циклы где не фигурируют большие числа (типа numdiv() по кандидатам), управляются счетчиками small.

-- 15.11.2025, 17:46 --

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

А вот от этого никуда не деться, нет других способов подсчитать количество делителей кроме как факторизацией.

Значит, только улучшать конструктор, чтобы он давал больше выхода годных...
Сейчас счёт идёт в диапазоне $\approx 10^{45}$, возможно надо идти в $10^{55}$ с примерно тем же временем факторизации, но с лучшими шаблонами.

-- 15.11.2025, 18:23 --

Хорошо. Значит возвращаемся в форум.

Мне Yadryara передал код.

Что я сделал.
1. Постарался не особо вникая в код, объявить малые целые типом small
2. removeprimes(addprimes()); я это отключил. памяти потребляется мало (см. ниже), а это лишняя операция. Ну может куда-то повыше ещё её перенести.
3. Обернул код так что теперь это функция ptk() которая принимает на вход номер потока, по умолчанию принимает присваивает 1.
4. Имена лог-файлов разные для разных потоков
5. Мои комментарии пометил как /* wrest:

Предварительные замеры производительности
Код Yadryara, отключена запись в лог:
Интерпретатор: Время до вывода второй строки 29 сек
Компиляция:время до вывода второй строки 16 сек
Код-функция ptk() с типизацией small и о чём выше написано, вызов ptk(1)
Интерпретатор: Время до вывода второй строки 28 сек
Компиляция:время до вывода второй строки 15 сек

По многозадачности.
Запустил четыре инстанса с номерами потоков 0 1 2 и 4 (почему-то тройку пропустил - не знаю).
За час среднее потребление памяти было по 19..25 мегабайт на инстанс. Рост примерно 3-5 мегабайт в час. Возможно, из-за отключения сброса кеша простых.
И никакого переполнения стека.
Напомню насчёт инстансов. Это пользовательские сессии в одну виртуальную машину линукс в WSL2. То есть, машина (виртуальная) одна, ядро линукс - одно.


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

[Yadryara]

Я так понял что Вы убрали default(factor_add_primes,1);. А для чего он нужен был я и не понимал, это придумка Дмитрия.

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

Сейчас счёт идёт в диапазоне $\approx 10^{45}$, возможно надо идти в $10^{55}$ с примерно тем же временем факторизации, но с лучшими шаблонами.

Это смелое заявление. Ведь наверху меньше кислорода (простых чисел).

[wrest]

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

Я так понял что Вы убрали default(factor_add_primes,1);. А для чего он нужен был я и не понимал, это придумка Дмитрия.

Нет, не убрал. Это нужно на случай если в факторизацию будут попадать простые числа, которые ранее уже факторизовались.
Они там накапливаются, в кеше, а removeprimes(addprimes()) этот кеш очищает.
Вопрос будут ли попадаться простые числа повторно в ходе счёта (речь конечно о больших простых, которые больше maxprime) - я не знаю. Если будут попадаться - то зачем тогда кеш очищать? Если не будут - то опять же зачем его очищать?

[Yadryara]

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

removeprimes(addprimes()) этот кеш очищает.

Понял, значит Вы его убрали. И это тоже придумка Дмитрия. Посмотрим что скажет.

[Dmitriy40]

wrest
Придумка вот для чего: в коде довольно много проверок типа factor(x,2^15), после которых оставшееся большое число проверяется на простоту. Проверка на простоту - не сильно быстрая операция (она уж точно медленнее поиска числа в кэше простых) и если у нас есть список точно простых ранее уже проверенных, то все последующие проверки (включая и финальный numdiv, который обычно довольно медленный) будут моментальными, сколько бы их ни было. Если в программе каждое место кортежа факторизуется лишь один раз - кэш простых не нужен. Но сейчас в программе может 3-5 раз факторизоваться каждое место если не предприняты специальные меры против этого (я сделал, но немного напортачил, и как сейчас у вас в коде не знаю). И идея в том что кэш больших простых эффективно с этим борется прозрачно для программиста.
Ну а очистка кэша на каждой итерации - очень уж мала вероятность что одно и то же большое простое (больше 16млн) окажется делителем чисел из разных кортежей, даже на разных местах в каждом. А память тратится. Потому очистка. По идее она должна быть быстрой, но сам не проверял. Можно очищать и пореже, но в большом кэше и поиск станет дольше.

[Yadryara]

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

Придумка вот для чего: в коде довольно много проверок типа factor(x,2^15),

Поскольку успешная проверка бывает довольно редко (в последнем поиске не чаще чем в среднем раз в 25 минут на поток), я оставил только factor(x,2^14), а factor(x,2^18) и factor(x,2^24) убрал — сразу проверяю цепочку до конца и вижу больше приближений.