Оптимизация деления uint_32 на константу на современных 64-битных процессорах.

похоже, я упирался в это в своей реализации printf

И какое практическое значение? В браузере ускорение на 0.00001%?

Дак это и так 1 инструкция процессора, как ее можно ускорить?

Разница в их собственных бенчах - быстрее в полтора-два раза.

Речь не про деление на произвольное число, а о делении на константу. Деление на константу известную во время компиляции можно заменить на комбинацию сдвигов и умножения. Это выполняется быстрее, чем один вызов idiv; в некоторых ситуациях раз в десять быстрее.

1 инструкция процессора, как ее можно ускорить?

На Zen2 самый медленный idiv с 13-44 latency, а на Zen3 тот же idiv c 9-17 latency. По спецификациям.

Баловался с простыми числами. Сильно удивлялся, что Zen3 считал заметно быстрее при меньших частотах.

Т.е. можно и инструкции ускорять, оказывается.

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

о как:
https://github.com/ridiculousfish/libdivide
это тоже самое?

Оптимизация деления

Сунь Цзы ещё в III веке н. э. © (wikipedia.org) оптимизировал деление в СОК © (wikipedia.org). но нужна специфическая аппаратная реализация.

TL;DR:

Есть древний способ оптимизировать деления на константу, основывающийся на том что умножение для проца - заметно более быстрая операция. Формулу x/a (x - переменная, a - константа) можно представить в виде x*(1/a), где 1/a можно посчитать ещё на этапе компиляции. Но надо оставаться в рамках целых чисел, поэтому делаем так: x*(2**32/a)/2**32. Однако, точности целочисленной величины 2**32/a хватает не для всех a, поэтому иногда приходилось использовать костыли. Суть прорывной оптимизации вот в чём: а давайте заменим в этой формуле 2**32 на 2**64, раз уж наш проц поддерживает 64-битную арифметику. На этом, собственно, всё. Все остальные простыни, которые наплодились как в arxiv.org так и в новостях - формализм или вода.

Сунь Цзынь

https://www.youtube.com/watch?v=uUYpIyWPKGk

хорошо, ждем когда дебиан пересоберт все пакеты на новом gcc

Дело не в умножении 1/x, это прошлый век.

Вот, например, замена деления на 1001:

        imul    rax, rax, 1098413215
        mov     rcx, rax
        shr     rcx, 63
        sar     rax, 40

Это и есть умножение на 1/x. Всякие доп. фокусы со сдвигами я уж опустил, чтобы не засорять суть. Твоя константа 1098413215 это 2**40/1001+1.

Только у тебя код не для unsigned а для signed, и ты не весь код сюда процитировал, там ещё add rax,rcx должно быть.

Да, я кажется несколько наврал с разрядностями, т.к. на 32-битных процах тоже делалось с 2**40 масштабом, это там никто не мешает, твой код например был бы такой:

        mov     edx,1098413215
        imul    edx
        mov     eax,edx
        shr     eax,31
        sar     edx,8
        add     eax,edx

А вот с unsigned твой код не годится, у него начиная с (2502080*1001+1000) входного числа накапливается ошибка в единицу вверх, которую надо вычесть либо из исходного всегда, либо из результата при доп. условии. Это всё очевидно усложнит алгоритм. Минимальная константа, с которой эта ошибка выходит за пределы 32-битного диапазона входных данных - 2**42/1001+1 (со сдвигом на 42 после), но с ней другая проблема: оставшихся 22 битов (если хранить промежуточное число в 64-битном регистре) чуть-чуть не хватает на результат. Поэтому на 32-битных процах, где других вариантов нет, приходится заниматься коррекцией ошибок.

Зато можно вот так, если у нас 64-битный проц, умеющий умножать в 128-битный результат:

mov rdx,18428315757951601
mul rdx
ответ в rdx

18428315757951601 это 2**64/1001+1

но в статье про которую речь - используется инструкция mulx примерно так

mov rdi,rax
mov rsi,18428315757951601
mulx rax,{garbage},rdi

Наверно этот способ ещё по каким-то причинам быстрее того что выше.

Это делается не для тех, у кого основной софт «браузер», но тем не менее и в том числе.

А почему драма? Или читать на arxiv.org?

ЗЫ оптимизация это прямо вкусное, творческое. Давеча алгоритм (не деление) в нашем проекте оптимизировал. Первый подход дал ≈x1.25 прироста. Второй уже дал ≈x5 прироста. Третий - ≈x20 =-) правда ценой 256кБ памяти на поток. Но последнее допустимо.

И какой процент добавит в том числе для тех у кого браузер?

Ну раз такая пьянка пошла, то я придумал 3 оптимизации оператора switch, в случаях когда кэйсы не сильно похожи. И отправил feature-requst в llvm. Если примут, то это ускорит все программы скомпилированные llvm и в которых есть такие switch'и, а в некоторых случаях и память меньше есть будут. Если что ссылка вот - https://github.com/llvm/llvm-project/issues/195453.

По поводу первого пункта. Ещё в 90-х (максимум - в 2000-х) компиляторы поддерживали такие свитчи через двухуровневую таблицу переходов - сначала из выражения делается однобайтовый индекс, затем из индекса уже адрес для перехода. Шланг это до сих пор не умеет? Или может быть он это в -O3 не применяет т.к. авторы посчитали что одномерная таблица быстрее, хоть и занимает много памяти?

Шланг это до сих пор не умеет?

Умеет. Оптимизации не в этом. В реквесте достаточно подробно все описано с примерами кода.

Оптимизации «подробно описывают» на ассемблере, а у тебя там код на Си. Или ты хочешь сказать что вот это

     switch (
          (('\t' == letter) * 1) |
          ((' '  == letter) * 2) |
          (('\n' == letter) * 3) |
          (('!'  == letter) * 4) |
          (('0'  == letter) * 5) |
          (('9'  == letter) * 6) |
          ((':'  == letter) * 7) |
          (('@'  == letter) * 8) |
          (('A'  == letter) * 9) |
          (('Z'  == letter) * 10) |
          (('a'  == letter) * 11) |
          (('z'  == letter) * 12) |
          (('~'  == letter) * 13)
     ) {

Оптимизации «подробно описывают» на ассемблере

Кто описывает? На чём понятнее, на том и описывают, главное чтобы суть была понятна.

компилируется в 13 сравнений и умножений

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

работает быстрее чем взять адрес из таблицы?

Нет, это работает чуть медленнее чем взять адрес из таблицы, но при этом таблица становится примерно в 14 раз меньше, что уменьшает вероятность промаха кэша, а один промах будет медленнее чем весь этот switch со всеми его инструкциями, если бы они находились в кэше. Ну и основной вариант использует SIMD для ускорения, а этот вариант я привёл на тот случай, если у разработчиков появится мысли «а как же процессоры без SIMD инструкций?».
Так же, это оптимизация номер 1, а ради только её я бы заморачиваться не стал, основные оптимизации там номер 2 и 3, а первая главным образом указанна потому, что третья оптимизация, это объединение первой и второй.

Первый раз отвечая на твой комментарий, я вспомнил что забыл загрузить данные в кэш, а поскольку мои оптимизации приводили к уменьшению потребления памяти, соответственно и промахи кэша в коде с ними были меньше. Из-за чего в первой оптимизации SIMD вариант был в 5 раз быстрее чем код без оптимизации, а приведённый тобой код был быстрее в 2 раза. Я переделал бенчмарки, чтобы данные всегда были в кэше, и SIMD вариант стал быстрее оригинального в 4 раза, а без SIMD на 4 процента. Но когда я писал оригинальный реквест, я был очень уставший и не обратил внимания что simd версия в 5 раза быстрее, хотя не должна быть. Посмотрев весь ассемблерный код, я увидел что clang смог, благодаря моей оптимизации, вообще выбросить всю таблицу, но такое произойдёт только в некоторых случаях которые не так часто случаются. Я переделал бенчмарк, что бы таблица осталась и simd вариант получился на 8 процентов медленнее, чем вообще без оптимизаций, а без simd на 20 процентов медленнее. Но оба варианта всё ещё потребляли меньше памяти (примерно в 2 раза). Поэтому я удалил 1-ю и 3-ю оптимизацию (так как я рассчитывал на замедленнее около 1 процента), оставив только вторую оптимизацию, которая всё ещё релевантна и ускоряет switch в 2 раза, а ради неё всё и затевалось. На этот раз я внимательно посмотрел ассемблерный код и бенчмарки проведены с данными в кэше.