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

[Dmitriy40]

Yadryara
Константа .mm больше не нужна, это же для 2 и 3 вариантов, с командой bt. Как и регистр R13 в общем больше не нужен.
Команда align 32 перед .mm тоже не особо нужна (но и не мешает), до неё все константы длиной кратно 32. Я обычно специально разделяю и группирую константы длиной 32 (AVX), 16 (SSE), и более короткие.

Не работает потому что длина каждой из констант c0, c2, mods, noteq должна быть по 32 байта (размер регистра AVX ymm), а у Вас получилось по 48 байт, беда, все константы при выполнении перемешались.

Раз хотите проверять по три модуля, надо хранить остатки по трём модулям. Значит в регистр 32 байта влезет лишь floor(32/3)=10 итераций вместо 16. Значит надо сделать 3 пункта:

1. Шаг в add R15,16 меняем на 10.

2. Кусок

Используется синтаксис ASM

                mov     EAX,EBX
                shr     EAX,16
                or      EAX,EBX                         ;Объединяем по or старшую и младшую половину битовой маски (запрет по 13 и по 17)
                not     EAX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                and     EAX,0xFFFF                      ;Выделяем только младшие 16 битов

меняем для обработки трёх полей по 10 битов каждое:

Используется синтаксис ASM

                mov     EAX,EBX
                shr     EAX,10                          ;Сдвинем среднее поле в младшие биты
                or      EAX,EBX                         ;Объединяем по or младшую и среднюю часть битовой маски (запрет по 13 и по 17)
                shr     EBX,20                          ;Сдвинем старшее поле в младшие биты
                or      EAX,EBX                         ;Объединяем третье поле с первыми двумя
                not     EAX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                and     EAX,0x3FF                       ;Выделяем только младшие 10 битов

3. Меняем константы чтобы были по 3 поля по 10 чисел (плюс неиспользуемый остаток в 2 числа):

Используется синтаксис ASM

.c0:            db      0,1,2,3,4,0,1,2,3,4, 0,1,2,3,4,5,6,0,1,2, 0,1,2,3,4,5,6,7,8,9, 0,0      ;[0..9]%5, [0..9]%7, [0..9]%11, неиспользуемые обнулим и менять не будем
.c2:            db      10 dup( 0), 10 dup( 3), 10 dup(10), 0,0         ;10%5=0, 10%7=3, 10%11=10, неиспользуемые увеличивать не будем
.mods2:         db      10 dup( 5), 10 dup( 7), 10 dup(11), 0,0         ;и вычитать простое тоже не будем
.noteq2:        db      10 dup( 3), 10 dup( 0), 10 dup( 9), 255,255     ;неиспользуемые как были 0, так и останутся, и 0<>255 так что неиспользуемые разрешены всегда

Теперь заработает.

Конечно c0 и c2 можно и вычислять по mods2 и шагу, а их - по списку простых и его длине, т.е. необходимы лишь список простых primes[] и список запрещённых остатков bad[] (по которому вычислится noteq2[]) одинаковой длины, но мне лень, проще все задать константой.

[Yadryara]

Не, не заработало. Более того, на выдаче число странное, 4 отличных от нуля цифры:

2277000000000, time: 3.219s

[Dmitriy40]

Где-то недоправили? Вот мой полный текст (код в цикле между vmovmskb и popcnt уже чуть поменял, но для работы несущественно, зато так чуть понятнее):

Используется синтаксис ASM

format PE64 console
include 'win64axp.inc'

.code
main:
frame
                invoke  GetTickCount            ;Запросим текущее время в мс
                mov     [time0],RAX
                invoke  GetStdHandle, STD_OUTPUT_HANDLE ;Получить handle консоли вывода
                mov     [hOut],RAX
                invoke  GetStdHandle, STD_ERROR_HANDLE  ;Получить handle консоли ошибок
                mov     [hErr],RAX
                mov     R15,0                   ;i
                mov     R14,0                   ;kpod
                vzeroupper
                vmovdqu         ymm0,[.c0]              ;Начальные значения остатков
.cycle:         vpcmpeqb        ymm7,ymm0,[.noteq2]     ;если i%p==no тогда FF, иначе 00
                vpmovmskb       EBX,ymm7                ;В EAX биты из старшего бита каждого байта из ymm7
                not     EBX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                mov     EAX,EBX
                shr     EBX,10                          ;Сдвинем среднее поле в младшие биты
                and     EAX,EBX                         ;Объединяем младшую и среднюю часть битовой маски (запрет по 5 и по 7)
                shr     EBX,10                          ;Сдвинем старшее поле в младшие биты
                and     EAX,EBX                         ;Объединяем третье поле с первыми двумя (запрет по 11)
                and     EAX,0x3FF                       ;Выделяем только младшие 10 битов
                popcnt  EAX,EAX                         ;Подсчитываем количество единичных битов, т.е. подходящих i
                add     R14,RAX                         ;Добавляем к счётчику
                vpaddb          ymm0,ymm0,[.c2]         ;i++
                vpsubb          ymm7,ymm0,[.mods2]      ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p
.next:          add     R15,10
                mov     RAX,3850000000
                cmp     R15,RAX
                jc      .cycle
                invoke  GetTickCount            ;Запросим текущее время в мс
                add     RAX,1                   ;Нулевых интервалов времени работы недопускаем, лучше пусть будет погрешность
                sub     RAX,[time0]             ;Вычтем время старта, получим время работы в мс
                xor     RDX,RDX                 ;Старшее слово обнулим
                mov     RCX,1000                ;Будем делить EDX,EAX на 1000 (количество мс в секунде)
                div     RCX                     ;Поделим время на два числа, в секундах и мс
                mov     R9,RAX
                mov     R10,RDX
                cinvoke wsprintf, buf, .fmt1, R14, R9, R10
                invoke  WriteFile, dword [hErr], buf, RAX, temp, 0
                invoke  ExitProcess,0
endf
.fmt1:          db      '%I64u, time: %u.%03us',13,10,0
align 32
.c0:            db      0,1,2,3,4,0,1,2,3,4, 0,1,2,3,4,5,6,0,1,2, 0,1,2,3,4,5,6,7,8,9, 0,0      ;[0..9]%5, [0..9]%7, [0..9]%11
.c2:            db      10 dup( 0), 10 dup( 3), 10 dup(10), 0,0 ;10%5=0, 10%7=3, 10%11=10
.mods2:         db      10 dup( 5), 10 dup( 7), 10 dup(11), 255,255
.noteq2:        db      10 dup( 3), 10 dup( 0), 10 dup( 9), 255,255

.data
align 32
time0:          rq      1
hOut:           rq      1
hErr:           rq      1
temp:           rq      1
buf:            rb      1000
.end main

[Yadryara]

Да, Ваш последний работает. Сравню позже.

Сегодня жутко плохой доступ к форуму. Уже и с 3-5-го раза не срабатывает.

Вот сравнительные данные между двумя и тремя модулями:

24-35
1. PARI        240000000      80.2 s
2. PARI        240000000      60.6 s
1. Fasm     240000000000      16.2 s

Между PARI:                на 32% быстрее.
Между PARI-2 и Fasm-1: в 3700 раз быстрее.


240-385
1. PARI        240000000     101.9 s
2. PARI        240000000      63.2 s
1. Fasm     240000000000      34.4 s

Между PARI:                на 61% быстрее.
Между PARI-2 и Fasm-1: в 1800 раз быстрее.

-- 04.10.2025, 22:23 --

Dmitriy40
Ну разница в том, что у меня есть вот это длиннющее число, которое я вычислял для PARI-2:

Используется синтаксис ASM

<div class="codetitle"><b>Код:</b></div><div class="codecontent">.mm:            dq      0x7ADCF3B56F4B9C76,
0xB73CED79D6A795AE,
0xCD3B1EF5B8E74BDA,
0xC6D6BD4E79DA77AD,
0x95EB5B1E66BDEB33,
0x7BC6E59DAF72DCF3,
0x1
</div>

И вот код для для PARI-2:

{t0=getwalltime();print;
for(i=0, 385*10^5-1,
if(bittest(0X17BC6E59DAF72DC... , i%385), kpod++;
)); print(kpod);
print;print(strtime(getwalltime()-t0));print;
}quit;

Число полностью выписывать не стал.

[Dmitriy40]

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

-- 04.10.2025, 22:26 --

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

Ну разница в том, что у меня есть вот это длиннющее число, которое я вычислял для PARI-2:

Ни в Вашем, ни в моём коде метка .mm больше не используется, поищите поиском по тексту, встречается ровно один раз (у Вас) с этим числом, она нужна лишь для 2 и 3 вариантов. Соответственно эту строку можно спокойно удалить, ничего измениться не должно. А если меняется - где-то ещё ошибка.

-- 04.10.2025, 22:47 --

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

Не, не заработало. Более того, на выдаче число странное, 4 отличных от нуля цифры:

Покажите этот вариант кода если остался, сравню/поизучаю ...

[Yadryara]

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

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

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

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

Покажите этот вариант кода если остался, сравню/поизучаю ...

Специально сохранил. Метку .mm сейчас выбросил. Перезапустил — тот же результат.

Используется синтаксис ASM

format PE64 console
include 'INCLUDE\win64axp.inc'

.code
main:
frame
                invoke  GetTickCount            ;Запросим текущее время в мс
                mov     [time0],RAX
                invoke  GetStdHandle, STD_OUTPUT_HANDLE ;Получить handle консоли вывода
                mov     [hOut],RAX
                invoke  GetStdHandle, STD_ERROR_HANDLE  ;Получить handle консоли ошибок
                mov     [hErr],RAX
                mov     R15,0                   ;i
                mov     R14,0                   ;kpod
                mov     R13,0                   ;i%385

                vzeroupper
                vmovdqu         ymm0,[.c0]              ;Начальные значения остатков
.cycle:
                vpcmpeqb        ymm7,ymm0,[.noteq2]     ;если i%p==no тогда FF, иначе 00
                vpmovmskb       EBX,ymm7                ;В EAX биты из старшего бита каждого байта из ymm7
                mov     EAX,EBX
                shr     EAX,10                          ;Сдвинем среднее поле в младшие биты
                or      EAX,EBX                         ;Объединяем по or младшую и среднюю часть битовой маски (запрет по 13 и по 17)
                shr     EBX,20                          ;Сдвинем старшее поле в младшие биты
                or      EAX,EBX                         ;Объединяем третье поле с первыми двумя
                not     EAX                             ;Инвертируем, теперь 1 отвечает подходящим значениям
                and     EAX,0x3FF                       ;Выделяем только младшие 10 битов                popcnt  EAX,EAX                         ;Подсчитываем количество единичных битов, т.е. подходящих i
                add     R14,RAX                         ;Добавляем к счётчику
                vpaddb          ymm0,ymm0,[.c2]         ;i++
                vpsubb          ymm7,ymm0,[.mods2]      ;i-p
                vpminub         ymm0,ymm0,ymm7          ;(i++)%p

.next:          add     R15,10

                                                        ;inc     R15

                mov     RAX,38500000000
                cmp     R15,RAX
                jc      .cycle
                invoke  GetTickCount            ;Запросим текущее время в мс
                add     RAX,1                   ;Нулевых интервалов времени работы не допускаем, лучше пусть будет погрешность
                sub     RAX,[time0]             ;Вычтем время старта, получим время работы в мс
                xor     RDX,RDX                 ;Старшее слово обнулим
                mov     RCX,1000                ;Будем делить EDX,EAX на 1000 (количество мс в секунде)
                div     RCX                     ;Поделим время на два числа, в секундах и мс
                mov     R9,RAX
                mov     R10,RDX
                cinvoke wsprintf, buf, .fmt1, R14, R9, R10
                invoke  WriteFile, dword [hErr], buf, RAX, temp, 0
                invoke  ExitProcess,0
endf
.fmt1:          db      '%I64u, time: %u.%03us',13,10,0
align 32
.c0:            db      0,1,2,3,4,0,1,2,3,4, 0,1,2,3,4,5,6,0,1,2, 0,1,2,3,4,5,6,7,8,9, 0,0      ;[0..9]%5, [0..9]%7, [0..9]%11, неиспользуемые обнулим и менять не будем
.c2:            db      10 dup( 0), 10 dup( 3), 10 dup(10), 0,0         ;10%5=0, 10%7=3, 10%11=10, неиспользуемые увеличивать не будем
.mods2:         db      10 dup( 5), 10 dup( 7), 10 dup(11), 0,0         ;и вычитать простое тоже не будем
.noteq2:        db      10 dup( 3), 10 dup( 0), 10 dup( 9), 255,255     ;неиспользуемые как были 0, так и останутся, и 0<>255 так что неиспользуемые разрешены всегда

align 32

.data
align 32
time0:          rq      1
hOut:           rq      1
hErr:           rq      1
temp:           rq      1
buf:            rb      1000
.end main

 

[Dmitriy40]

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

Специально сохранил. Метку .mm сейчас выбросил. Перезапустил — тот же результат.

У Вас команда popcnt в строке 28 уехала в комментарий к предыдущей строке и не выполняется. Если вернуть на следующую строку, то считает правильно.

[Yadryara]

Да, из-за большой ширины не увидел. Эта первая версия чуть медленней. Вот сравнения по 2-м и 3-м модулям:

Программа     2 модуля   3 модуля   Замедл.

PARI-1           8.1 s    101.9 s      12.6
PARI-2           6.1 s     63.2 s      10.4
Fasm-1-2        16.2 s    347.1 s      21.4

Стоит перейти от 2-х модулей к 3-м — замедление в 21 раз.

-- 05.10.2025, 02:12 --

Хотя нет, я не согласен, что надо XX выравнивать. Надо количество кандидатов выравнивать. То есть чтобы $35x = 385у$.

[Dmitriy40]

В обычной проге диапазон i в 221млрд (или 385млрд или любой другой) соответствует именно количеству проверяемых простых на одном из мест паттерна. Которое пропорционально (с некоторой константой) проверяемому диапазону натуральных чисел. И нас обычно интересует время проверки последнего диапазона, а значит и интервала по i. А не сколько в итоге останется кандидатов. По скольким бы модулям их не отфильтровывать, это вообще неважно и влияет лишь на коэффициент фильтрации и скорость, но не на исходный диапазон проверки.

Не знаю как Вы насчитали 21 раз, у меня замедление менее 2 раз (2.6 раз для 4 модулей) на интервале 38.5млрд (только асм, PARI не запускал):
26400000000, time: 3.448s - по модулям 5,7
24000000000, time: 6.272s - по модулям 5,7,11
22153846156, time: 8.987s - по модулям 5,7,11,13
Правильность последнего числа легко установить изменив диапазон на кратный 5005000.

-- 05.10.2025, 03:26 --

Кстати для случая 1,2,4,8 модулей есть красивый финт, требующий иной раскладки данных в константах (кроме 1 модуля), зато раза в полтора быстрее (на 4-х модулях):

Используется синтаксис ASM

.cycle:
                vpcmpeqb        ymm7,ymm0,[.noteq2]     ;Если i%p==no тогда FF, иначе 00
                vpcmpeqd        ymm7,ymm7,[.c0000]      ;Сравнение с нулём, превращает каждые 4 байта в 0xFFFFFFFF если все равны 0 или в 0x00000000 если есть хоть один ненулевой (т.е. запрещённый остаток)
                vpmovmskb       EBX,ymm7                ;В EAX биты из старшего бита каждого байта из ymm7
                popcnt  EAX,EBX                         ;Подсчитываем количество единичных битов, т.е. подходящих i
                shr     EAX,2                           ;Каждое число посчитали 4 раза (по 4 модулям), потому поделим на 4
                add     R14,RAX                         ;Добавляем к счётчику
...
                add     R15,8                           ;Или 31,16,8,4 для 1,2,4,8 модулей
...
.c0:            db      0,0,0,0, 1,1,1,1, 2,2,2,2, 3,3,3,3, 4,4,4,4, 0,5,5,5, 1,6,6,6, 2,0,7,7  ;for(j=0,7, j%5, j%7, j%11, j%13)
.mods2:         db      8 dup(5,7,11,13)
.c2:            db      8 dup(3,1, 8, 8)        ;8%5=3, 8%7=1, 8%11=8, 8%13=8
.noteq2:        db      8 dup(3,0, 9, 9)        ;i%5<>3, i%7<>0, i%11<>9, i%13<>9
.c0000:         db      32 dup(0)               ;Тупо векторные 0 для экономии регистров, от числа модулей не зависит

Это для 4-х модулей, для 1 или 2 или 8 меняется лишь суффикс второй команды vpcmpeqX (b,w,d,q для 1,2,4,8) и число в shr (0,1,2,3 соответственно, если 0 то команду можно и убрать). Зато две новые команды заменяют собой 9 (для 4-х модулей, для 8-ми ещё больше) отсутствующих команд. Причём shr можно и вытащить из цикла и сдвинуть уже R14 перед показом.
В константах для 1,2,4,8 модулей будет соответственно 32,16,8,4 групп (их число и указывается перед dup) по 1,2,4,8 чисел.

[Yadryara]

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

Не знаю как Вы насчитали 21 раз,

Это я уже понял, что хрень насчитал. И это потому что я выравнивал по XX, как Вы посоветовали. А надо было по количеству кандидатов, как я и планировал вначале.

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

А не сколько в итоге останется кандидатов.

Нет, прошедшие проверку это kpod (Количество (пока) ПОДходящих).

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

я не согласен, что надо XX выравнивать. Надо количество кандидатов выравнивать. То есть чтобы $35x = 385у$.

То есть $x$ и $y$ надо подбирать так, чтобы количество кандидатов совпало. На всякий случай всё пересчитал и для наглядности добавил колонку с количеством кандидатов:

5 7                                       264-385                              
                   kan           kpod        time
1. PARI      385000000      264000000      88.9 s
2. PARI      385000000      264000000      67.9 s
3. fasm   385000000000   264000000000      17.8 s
  
5 7 11                                    240-385
                   kan           kpod        time
1. PARI      385000000      240000000     103.0 s
2. PARI      385000000      240000000      63.8 s
3. fasm   385000000000   240000000000      34.4 s


Программа     2 модуля   3 модуля   Замедл.

PARI-1          88.9 s    103.0 s      16 %
PARI-2          67.9 s     63.8 s      -6 %
fasm            17.8 s     34.4 s      93 %

Да, это длиннющее число даёт ускорение в PARI на 6%. Вот такая любопытность обнаружилась. Не зря его решил проверить.

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

26400000000, time: 3.448s - по модулям 5,7
24000000000, time: 6.272s - по модулям 5,7,11
22153846156, time: 8.987s - по модулям 5,7,11,13
Правильность последнего числа легко установить изменив диапазон на кратный 5005000.

Не ну кэфы-то понятно какие. Сначала kpod уменьшается в $\frac{11}{10}$ раза, а затем в $\frac{13}{12}$. Дальше (при 5-ти младших модулях) будет меньше в $\frac{17}{16}$ раза.

Заметил, что, видимо, вместо игрека русскую "у" поставил, что ли. Не вижу игрека в формуле.

[Yadryara]

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

требующий иной раскладки данных в константах (кроме 1 модуля), зато раза в полтора быстрее (на 4-х модулях):

Да, сработало. Вот табличка:

5 7 11 13                                 221-385
                   kan           kpod        time
1. PARI      385000000      221538463     119.0 s
2. PARI  
3. fasm   385000000000   221538461540      41.8 s


Программа       5*7     5*7*11   5*7*11*13          Замедление
PARI-1       88.9 s    103.0 s     119.0 s        16 %    16 %
PARI-2       67.9 s     63.8 s                    -6 %
fasm         17.8 s     34.4 s      41.8 s        93 %    22 %

Для 2-го варианта PARI не стал считать. Если для 3-х модулей было 97-значное 16-ричное число, то для 4-х модулей оно будет 1252-значным.

Что в сухом остатке. Для 4-х младших модулей отбраковка терапевтичеких исключений в 2800 раз быстрее чем в исходной проге на PARI.

Dmitriy40
Я правильно понимаю, что идея объединения модулей для терапевтики не применялось в программах на асме (ускорителях) три года назад?

[Dmitriy40]

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

Я правильно понимаю, что идея объединения модулей для терапевтики не применялось в программах на асме (ускорителях) три года назад?

Правильно.
И вот почему не применялось и сейчас не думаю что выгодно: 1) объединение модулей "размножает" запрещённые остатки, их становится не по одному на модуль, а по несколько на объединённый модуль, а такое условие (несколько запрещённых значений) проверяются кратно дольше одного, правда кроме проверки остальные операции не замедляются; 2) объединение почти гарантированно даёт модуль более 128, т.е. до этого порога (чтобы в регистр AVX помещалось до 32 остатков) можно объединить лишь 5,7,11,13,17,19,23 максимум попарно, что даёт минимум 11 запрещённых остатков даже для комбинации 5*7, что будет проверяться уже в 11 раз дольше; 3) при этом без объединения в регистр влезало почти три модуля (11 проверяемых мест по 3 модуля лишь чуть больше 32) и они проверялись одной командой.
Вообще, объединение модулей хорошо тогда когда есть медленная команда (деления) и надо пореже её выполнять, тогда да, лучше делить на сильно больше модуль, а всё остальное (проверка остатка и организация цикла) от величины модуля зависит слабо. Но с AVX медленных команд нет, они все быстрые, потому нет нужды сильно сокращать количество одних ценой резкого увеличения количества других.
Хотя в принципе вопрос можно рассмотреть подробнее и подумать, может тут есть здравое зерно.