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

[Yadryara]

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

Но ваш комп имеет термопакет что-то около 150 ватт, если я правильно помню. Или какой?

Не знаю. Где это посмотреть?

Но можно поступить проще. Бинарник и экзешник это одно и то же? Если у вас он есть, пришлите почтой или выложите, я скачаю, запущу у себя и можно будет сравнить получше. Ну так, навскидку, видимо, будет секунд 25-35.

[Dmitriy40]

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

Но ваш комп имеет термопакет что-то около 150 ватт, если я правильно помню. Или какой?

65Вт. 6 ядер с гипертрейдингом. AMD.

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

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

В некотором смысле одно и то же.
Но Вам не поможет - на планшете очевидно не винда (тем более что там ARM64).
Конечно на вычислительных задачах скорость не должна зависеть от типа ОС, но ... дьявол в деталях. А уж система команд ARM совершенно другая чем у Intel/AMD. Так что бинарник на другой ОС точно не запустится (если только в виртуалке Вин11, она вроде умеет запускать линуксовские приложения нативно, но о скорости говорить тогда не приходится, аппаратура же другая!).
Единственное что можно сделать (правда непонятно зачем) - доработать С исходник для работы под виндой, перекомпилить под винду и сравнить скорость.

[Yadryara]

А то, что у меня WSL через Убунту есть, не поможет?

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

Единственное что можно сделать (правда непонятно зачем)

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

Есть и другие способы сравнить... Но да, не очень вроде нужно, вот если бы было сказано не про 40 секунд, а про 1-2 на планшете.

[wrest]

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

Единственное что можно сделать (правда непонятно зачем) - доработать С исходник для работы под виндой, перекомпилить под винду и сравнить скорость.

Я это сделал, но не под винду (там нет у меня инструментов) а под WSL2. Скорость как на планшете. Там у меня в ноутбуке i7-8565U, венда в WSL2 вроде отдаёт все ядра если надо.

Ну после параллелизации скорость подросла, правда, и на планшете, до ~20с на расчёт 0 90.

Однопоточный бенчмарк для i7-8565U (geekbench) 1395 многопоточный 4192 (на чистом линуксе, т.е. без WSL2, но разница небольшая должна быть). Для планшета бенчмарк 1542 и 3507 соответственно.
Но я так понимаю главное тут ещё - L3 кэш который в планшете 6МБ, а в ноутбуке 8МБ

-- добавлено через 7 минут --

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

Я так понял, что wrest хотел сравнить скорость.

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

Dmitriy40
Кстати, а у вас в программе на асме коэффициенты точно считаются или с погрешностью какой-то?

Ну и: до диаметров 128 хватает 64-битных масок (т.к. простые только на чётных позициях могут быть), а потом всё медленее должно становиться если регистры остаются 64-битными.

-- добавлено через 7 минут --

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

Ну после параллелизации скорость подросла, правда, и на планшете, до ~20с на расчёт 0 90.

Тут кстати хотел заметить, что оказывается, на планшете вполне доступна параллелизация. Но вот реализация например в pari/gp использует "небезопасные" по мнению гугла функции, которых в андроидном аналоге glibc (который bionic) просто нет, и потому параллельность pari/gp невозможна (только если два инстанса gp в разных сессиях - тогда возможна).

[Dmitriy40]

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

А то, что у меня WSL через Убунту есть, не поможет?

Не поможет: WSL это запуск приложения от другой ОС, но на той же аппаратуре (процессор).
А ARM от x86 отличается кардинально, один и тот же поток байтов означает для процессоров кардинально разное. Это как незнакомый иностранный язык - даже напечатанный в том же шрифте и на той же бумаге текст понимания не добавит.

Вот если бы сравнивать скорость не бинарника/езешника, а промежуточной формы (LLVM или байт-код джавы с питоном), которая и на планшете и на коме при запуске докомпилится в выполняемый код, вот тогда сравнение обосновано. Но с С в LLVM умеет вроде только компилятор Clang, не gcc. Впрочем я не в курсе.

-- добавлено через 15 минут --

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

Кстати, а у вас в программе на асме коэффициенты точно считаются или с погрешностью какой-то?

Конечно с погрешностью: для всех чисел используется формат FPU с 64 битами мантиссы, так что точные значения только пока результат 19 и менее цифр, выше точность может падать. Заморачиваться с длинной арифметикой ради точности 20+ цифр я посчитал излишним (и тормозным!), обычно нам для расчётов достаточно точности в 4-6 цифр. Акцент был на скорость счёта, ценой в том числе и точности, ведь медленно и точно считалось на PARI.
Кроме того при суммировании множества чисел есть известная проблема округлений и потери точности, в версии -time она никак не решается и потому верных цифр может оказаться и меньше 10 из 19, решение предпринято в версии -time2, которая в общем обеспечивает точность в 19 цифр на всех проверенных тестах (но зато чуть медленнее, порядка 5%). Антон упорно предпочитает первую, менее точную и чуть быстрее, ну это его выбор.

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

Ну и: до диаметров 128 хватает 64-битных масок (т.к. простые только на чётных позициях могут быть), а потом всё медленее должно становиться если регистры остаются 64-битными.

У меня в программе диаметры до 2047 и до 99 загрязнений (констант). Адресация битовых полей в современных x86 процессорах вполне быстрая (при наличии их в кэше), конечно не как с регистрами, но и не сильно тормозит (там немало и других операций).

[Yadryara]

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

Антон упорно предпочитает первую, менее точную и чуть быстрее, ну это его выбор.

Ну это не догма. Надо будет, поменяю. Кстати, добрый человек, который помогает считать константы, похоже пользуется другой версией вашей программы. Но я специально проверил несколько чисел — первые 17-18 цифр в константах всегда совпадали с моими. С тех пор насчёт точности пока не парюсь.

[wrest]

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

Конечно с погрешностью: для всех чисел используется формат FPU с 64 битами мантиссы, так что точные значения только пока результат 19 и менее цифр, выше точность может падать.

Вероятно я потерялся в терминологии. Для диаметра 0 60 вот эти числа

[572556600, 4908898560, 19058897448, 44275879872, 68497116236, 74303160400, 57941831774, 32750959046, 13353970000, 3859063126, 764861984, 98561550, 7586778, 302746, 4480]

Это что, как вы их называете? Вот они точно считаются?

[Dmitriy40]

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

Но я специально проверил несколько чисел — первые 17-18 цифр в константах всегда совпадали с моими.

Несовпадения будут там где складывается много чисел, т.е. где много вариантов загрязнения, обычно это не первые и не последние константы, а где-то ближе к границе первой и второй трети констант. Вот как будут суммироваться миллионы вариантов - так и набежит погрешность.
Пример:
>hl1-vc-time2.exe 10 0 120
[1215599399289925650e2, 1842791168403046400e3, 1325119262687753586e4, 6012014986245608228e4, 1931001153266447684e5, 4670037575318920974e5, 8830509492400826625e5, 1338106833191830983e6, 1652333656803286333e6, 1681717813884577438e6, 1421414585715742397e6]
>hl1-vc-time.exe 10 0 120
[1215599399289925650e2, 1842791168403046400e3, 1325119262687753586e4, 6012014986245608228e4, 1931001153266447650e5, 4670037575318920962e5, 8830509492400822721e5, 1338106833191831071e6, 1652333656803287446e6, 1681717813884575612e6, 1421414585715740803e6]
Неверные цифры подчеркнул. Тут их не более 4-х из 19-ти, но на других паттернах я видел и больше неверных цифр.
Или:
>hl1-vc-time2.exe 4 0 360
[1195096756453029014e51, 4487282864719589932e52, 8256993027103026918e53, 9924607583565253718e54, 8763181003999358840e55]
>hl1-vc-time.exe 4 0 360
[1195096756453029014e51, 4487282864719589932e52, 8256993027103026892e53, 9924607583565253704e54, 8763181003999358926e55]

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

Это что, как вы их называете?

Да, речь про эти.
Но у Вас они маленькие (меньше 2^64), потому у меня будут посчитаны точно. Пока меньше 2^64. Смотрите:
>hl1-vc-time.exe 99 0 60
[572556600e0, 4908898560e0, 19058897448e0, 44275879872e0, 68497116236e0, 74303160400e0, 57941831774e0, 32750959046e0, 13353970000e0, 3859063126e0, 764861984e0, 98561550e0, 7586778e0, 302746e0, 4480e0] - они все точные.
А чуть выше посмотрите на пример погрешностей.

[wrest]

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

Но у Вас они маленькие (меньше 2^64), потому у меня будут посчитаны точно.

А, так у меня больше 2^64 и не считаются пока :)
В том документе что выкладывал Klein

Klein в сообщении #1727603 писал(а):

Если коротко, то здесь : https://gofile.io/d/tJWuPp

написано

Цитата:

При переполнении программа завершает работу с явной ошибкой. Молчаливого перехода по
модулю 2^64, усечения или приближения нет. Точная строка результата направляется в stdout, а
время и диагностические сообщения — в stderr.

[Dmitriy40]

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

А, так у меня больше 2^64 и не считаются :)

Значит уже паттерн 0 94 Вам доступен не полностью (6-я с нуля константа больше 2^64), а паттерн 0 118 недоступен совсем (уже нулевая константа больше 2^64).
Я не просто так использовал плавающую точку в вычислениях. Вплоть до 10^4932. А в версии -time2 дополнительно боролся за точность (благо оказалось несложно и не слишком медленно).

[Yadryara]

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

Вероятно я потерялся в терминологии. Для диаметра 0 60 вот эти числа

Есть немного. 0 60, в более привычной записи [0, 60] это паттерн, у которого диаметр — 60.

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

Это что, как вы их называете?

Вот я и сказал что не придумал названия. И есть причина: я обычно запускаю эту прогу через обёртку на PARI, так вот она на выходе даёт не эти числа, а именно константы, которые и нужны для дальнейшего счёта. Пример:

v = [0, 10]

vC= [1.7604315089249855304741656267054820758, 8.5747457871576612972904039821790526340, 8.3023617264748315143305711239190750316]

437 ms

И кстати, их количество обычно на 1 больше чем первый параметр в программе Дмитрия, потому что нумерация с нуля. Вот здесь именно количество констант, включая нулевую:

Паттерн     Вариантов ненулевых            Ёлочный кэф
            загрязнений (констант)             (теор.)
            Теоретически   Практически         0 — 59#

[0,  30]               8             8            23.3
[0,  60]              15            15            44.5
[0,  90]              21            21            87.4
[0, 120]              26            27           168.1
[0, 150]              31*           33           329.4
[0, 180]              37*           38
[0, 210]              43*           42

[Yadryara]

Klein в сообщении #1727747 писал(а):

Попросил модель GPT‑5.6 Sol (Ultra) оптимизировать программу с поиском оптимальных алгоритмов.

.\hl1-c-windows-x86_64.exe  --wide --threads 8 90 0 110
[1184794736150025000e0, 16859671669800960000e0, 113402284046134888374e0, 479392457805790470144e0, 1428494592766413777574e0, 3189625825866809747296e0, 5538154844652822968774e0, 7658726745848271141284e0, 8570498175790734960094e0, 7841767030108829207254e0, 5903388996261958758904e0, 3667314316625188105690e0, 1880008791392177707080e0, 793072342272734288602e0, 273708728311875469998e0, 76575512538913594328e0, 17135473474146656486e0, 3009387016149433986e0, 403835051230427806e0, 39837681078866066e0, 2726178673625610e0, 117941760127526e0, 2736937010836e0, 23930334360e0]
Time: 1.837226900s

Как понимаю, 8-поточный вариант реализован. И посчитано всё точно. Но на каком железе и т. д. И да, это быстрее чем однопоток у меня отработал:

C:\HL1\Asm\CPAP-210>hl1-vc-time.exe 99 0 110
[1184794736150025000e0, 1685967166980096000e1, 1134022840461348883e2, 4793924578057904701e2, 1428494592766413771e3, 3189625825866809747e3, 5538154844652822563e3, 7658726745848271009e3, 8570498175790736731e3, 7841767030108829533e3, 5903388996261956918e3, 3667314316625188162e3, 1880008791392177767e3, 7930723422727342830e2, 2737087283118754750e2, 7657551253891359437e1, 1713547347414665648e1, 3009387016149433986e0, 403835051230427806e0, 39837681078866066e0, 2726178673625610e0, 117941760127526e0, 2736937010836e0, 23930334360e0]
Time: 15.251s

И, как понял, 120 тоже за 15 секунд.

Klein, круто!

Больше всего, конечно интересуют паттерны:

[0, 210]
[0, 210, 420]
[0, 210, 420, 630]
[0, 210, 420, 630, 840]
[0, 210, 420, 630, 840, 1050]
[0, 210, 420, 630, 840, 1050, 1260] — самый интересный.

[wrest]

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

Значит уже паттерн 0 94 Вам доступен не полностью (6-я с нуля константа больше 2^64), а паттерн 0 118 недоступен совсем (уже нулевая константа больше 2^64).

Уже доступно до 2^128. За счёт потери производительности, конечно. 0 94 считается за 32 сек в 64битном режиме (с неверным результатом) и за 42 сек в 128 битном.
Но дальше да, 256битных типов нет в Си как я понимаю и надо интегрироваться с GMP или переходить на плавающую точку и терять точность.
Но и время растёт, я просто не дотяну до тестирования больших диаметров
И так уже пришлось бороться с переполнением памяти обработкой по частям в несколько гигабайт . Надо решать алгоритмически.

[Dmitriy40]

Опять гигабайты (у Антона было 600МБ). Откуда?! Вы рекурсию разворачиваете в массив что ли?!

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

переходить на плавающую точку и терять точность.

Для расчётов обычно достаточно точности результата меньше десятка цифр, рабочий double c 15-16 цифрами часто даёт достаточную точность, а уж long double (который 80-битный FPU на x86) с 19 цифрами тем более.
Гнаться за большей точностью нет смысла, всё равно эти числа потом домножатся на плавающее число (правда оно в PARI может быть любой точности, но обычно 38 цифр). И пригодятся лишь старшие цифр 4-6. Тут главное получить точность результата не ниже скажем 6 цифр, чего даже double вполне обеспечивает (при аккуратном суммировании массивов).

[wrest]

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

Опять гигабайты (у Антона было 600МБ). Откуда?! Вы рекурсию разворачиваете в массив что ли?!

Маски хранятся, их нельзя все выкинуть без потери производительности. А алгоритма с О(1) по памяти у меня нет.