GLM-5.1 придумал для меня новый алгоритм

[Shalundrive]

Автор, спасибо за статью и за демонстрацию сессии с ИИ, это отличный кейс того, как современные LLM умеют жонглировать низкоуровневыми концептами. Однако радоваться новому алгоритму пока рано. ИИ здесь не изобрёл ничего нового (это классический Broadword Computing / Parallel LUT, который лет 10 используется в биоинформатике и парсерах вроде simdjson), но, что гораздо важнее, предложенный ИИ код содержит критическую ошибку и архитектурный дефект производительности. Давайте разберем по пунктам: Критическая ошибка в префиксных суммах (алгоритм ломается на AVX2) Векторный сниппет подсчета префиксных сумм:

ps = mm256add_epi8(ps, mm256slli_si256(ps, 1)); ps = mm256add_epi8(ps, mm256slli_si256(ps, 2)); // …

Инструкция mm256slli_si256 (vpslldq) работает intra-lane, то есть независимо внутри каждой 128-битной половины (lane) 256-битного регистра. Она не переносит биты/байты через границу 128 бит. Это значит, что на 16-м байте (начало старшего лейна) префиксная сумма начнется заново с нуля, полностью проигнорировав накопленный excess из младшей половины регистра. На строках длиннее 64 бит (16 нибблов) алгоритм начнет выдавать мусор. Чтобы это починить, после сдвигов нужен межлейновый пермутейт (_mm256_permute2x128_si256) и докидывание сумм, что сводит на нет всю элегантность четырех строчек.
Использовать pdep (Parallel Bits Deposit) для раскидывания масок после vpmovmskb, это известный трюк времён Intel Haswell (2013-2015 гг.). Но у него есть огромная проблема кроссплатформенности. На процессорах AMD (вплоть до архитектуры Zen 2 включительно) инструкции pdep/pext не имели аппаратной поддержки в кремнии и были реализованы через микрокод. Одна инструкция pdep на AMD выполнялась до 18–20 тактов, в то время как на Intel — 1 такт. Если ваш код запустится на условном Ryzen 5 3600 или серверном EPYC тех лет, весь ваш быстрый SIMD превратится в тыкву и будет работать в разы медленнее обычного скалярного baseline. В современных Zen 3/4 это исправили, но закладывать такую мину в универсальный алгоритм — плохая практика. 3. Иллюзия новизны комбинации vpshufb как параллельного LUT для 4-битных нибблов, это стандартный паттерн (так работает, например, подсчет popcount по алгоритму Мулы или валидация строк). ИИ просто взял готовый паттерн из одной области (парсинг/сжатие) и перенёс в задачу RMQ/LCA, попутно набажив в логике межлейнового сдвига AVX2. LLM в очередной раз показала себя как крутой генератор ассоциаций, который умеет красиво сочетать интринсики, но абсолютно не понимает топологию данных внутри регистра и особенности исполнения инструкций на реальных CPU. Код требует полной переработки межлейнового обмена и избавления от скалярного pdep в пользу чистого SIMD-маскирования.

[malkovsky]

Она не переносит биты/байты через границу 128 бит. Это значит, что на 16-м байте (начало старшего лейна) префиксная сумма начнется заново с нуля, полностью проигнорировав накопленный excess из младшей половины регистра.

Я перепиоверю, но вроде как с этим проблемы не было, разве что в варианте с AVX-512.

ИИ здесь не изобрёл ничего нового (это классический Broadword Computing / Parallel LUT, который лет 10 используется в биоинформатике и парсерах вроде simdjson)

Иллюзия новизны комбинации vpshufb как параллельного LUT для 4-битных нибблов, это стандартный паттерн (так работает, например, подсчет popcount по алгоритму Мулы или валидация строк).

С этим я и не спорю, это прям даже в промпт было “применить именно этот метод, потому что он универсальный”

ИИ просто взял готовый паттерн из одной области (парсинг/сжатие) и перенёс в задачу RMQ/LCA

Когда вы комбинируете уже известные алгоритмы неизвестным до этого способом, разве вы не получаете новый алгоритм? Тогда болтшинство научных статей не содержат новизны

Код требует полной переработки межлейнового обмена и избавления от скалярного pdep в пользу чистого SIMD-маскирования.

Исходный вариант применялся к блокам по 64 бита и указанной проблемы быть не должно. Впоследствии пдеп я убрал и писал об этом в статье

[malkovsky]

Прошу прощения за неточность, Исходный вариант где использовался pdep, работал с SSE, не AVX. Соответственно проблемы с переносом по 128битым лейнам там не было

[malkovsky]

Перепроверил, полностью используемый вариант на AVX-2 для вычисления сумм выглядит вот так

    __m256i ps = _mm256_shuffle_epi8(vdelta, nibbles);
    ps = _mm256_add_epi8(ps, _mm256_slli_si256(ps, 1));
    ps = _mm256_add_epi8(ps, _mm256_slli_si256(ps, 2));
    ps = _mm256_add_epi8(ps, _mm256_slli_si256(ps, 4));
    ps = _mm256_add_epi8(ps, _mm256_slli_si256(ps, 8));

    __m128i ps_lo = _mm256_castsi256_si128(ps);
    __m128i ps_hi = _mm256_extracti128_si256(ps, 1);
    __m128i carry = _mm_set1_epi8((int8_t)_mm_extract_epi8(ps_lo, 15));
    ps_hi = _mm_add_epi8(ps_hi, carry);
    ps = _mm256_inserti128_si256(_mm256_castsi128_si256(ps_lo), ps_hi, 1);

Тут мой косяк как автора, а не AI, дополню статью. По поводу pdep AI при анализе всю ту же информацию про Zen 2 выдал и предлагал фолбэк на несколько умножений. Здесь есть еще один нюанс касающийся и 128-битных регистров: excess принимает значения [-128; 128] и не влезает в байт, поэтому надо что-то с этим делать, но и тут как-будто всё аккуратно сведено