Нейросеть AlphaDev от Deepmind изобрела новый алгоритм сортировки, и он уже в LLVM!

Алгоритм то хоть верифицировали? А то получится второй тимсорт.

TLDR Набрутфорсили алгоритм (я не выдумываю, это в статье «научной»), дополняющей (не путать с генерирующей) сетью по начальному шаблону, молодцы.

Где компуктер сиенсе разбор алгоритма? Описание алгоритма. И всё вот это вот. В тут, в статье, в научпопе 90% всех букф водяная вода и нулевая конкретика и тонны маркетингового высера (извините что я ругаюсь).

которая стала на 70 %

4.2 В тестах нет этой цифры только 69.88 и только с данными на 4 элемента. Разница сортировки 4х элементов было 5.20ns стало 1.56ns. Если элементов больше чем 4 разница уже плавает в виде 1%~0,5% а не 69.

https://docs.google.com/document/d/1ULNoweKnNLI1Gf1Mj5FA1HtIFsQUPdgNpTzYk9XdUOM/edit#

Суть, оптимизировали частные случаи сортировки 4х элементов через if/else. Ор на весь двор.
Тестирование проводилось только на AMD Zen2 Intel Skylake ARMv8. Всё.

Внезависимости от того что я бубню в лужу, ускорили код, молодцы (без сарказма).

Быстрее, чем Быстрая стабильная сортировка от Игоря? :)
Или:
https://github.com/Morwenn/cpp-sort
https://github.com/zeux/nanosort

Сортировка гиперзвуковым турбопузырьком.

Табличным гиперзвуковым суперпузырьком. Это как таблица с синусом.

Будущее за квантовым нанопузырьком!

Мы рассматриваем это как важный шаг к использованию ИИ для оптимизации мирового кода, по одному алгоритму за раз.

Согласен

Почему код, обмазанный тернарным оператором, они называют branchless?

Он компилируется в cmov

Суть, оптимизировали частные случаи сортировки 4х элементов через if/else. Ор на весь двор.

Это получается, что на пяти элементах мы должны получить ухудшение производительности за счет добавления новой проверки длины массива? Правильно?

Проверка длинны массива и отдельная обработка случаев от 0 до 5 там уже была.

Мы сосредоточились на улучшении алгоритмов сортировки более коротких последовательностей из трех-пяти элементов.

Предлагаю Нобелевскую премию дать.

То есть на других архитектурах там всё-таки будет ветвление?

А какая разница? Разве не в этом смысл разных архитектур, чтобы использовали их сильные стороны?

Но вообще, применимо и к ARM: The libc++ benchmarks were run on isolated machines for Skylake, ARM and AMD architectures and achieve statistically significant improvement in sorting random integers on test cases from sort1 to sort262144 for uint32 and uint64.

То есть, сначала были запилены чудовищно переусложнённые процессоры, а теперь выясняется, что чтобы под них эффективный код компилировать, нужен ИИ, перебирающий все варианты ассемблера брутфорсом. Приехали, чо.

Нам п*здец)

Кстати, посмотрите как AlphaStar «побеждал» в СтарКрафте 2.

Комментарий с у-комбинатора, сойдёт за TLDR:

Несколько очень крутых улучшений в уже сильно оптимизированных алгоритмах. Они обнаружили, что в сортировочной сети, обрабатывающей 3 входа, ИИ нашел способ сохранить инструкцию, сократив операцию «min(A, B, C)» до просто «min(A, B)», воспользовавшись этим фактом. что предыдущие операции гарантировали, что B <= C. Они также обнаружили, что в сортировочной сети, обрабатывающей 4 входа, когда она является частью сети «сортировки 8», существуют аналогичные гарантии (D >= min(A, C) в этом case), что также можно использовать для удаления инструкции. Компилятор может быть не в состоянии конкурировать с написанным от руки ассемблером, но кажется, что ИИ может написать код на ассемблере от руки, который в некоторых случаях даже лучше.

Еще одно улучшение тоже очень крутое. Они обсуждают VarSort4, который берет список длиной 2, 3 или 4 элемента и сортирует его. Существующий алгоритм

    if (len = 4) { 
        sort4
    }
    elif (len = 3) {
        sort3
    }
    elif (len = 2) {
        sort2
    }

ИИ нашел алгоритм, который выглядит совершенно иначе:

    if (len = 2) {
        sort2
    }
    else {
        sort3
        if (len = 4) {
            sortspecial
        }
    }

Это довольно дико! Он немедленно запускает Sort3 для чего-то, что может состоять из 3 или 4 элементов, и только после этого проверяет, насколько это действительно длинно. Если это 3 элемента, мы закончили; в противном случае запустите Sort4, но поскольку (уже запустив Sort3) вы знаете, что первые три элемента отсортированы, вы можете использовать специальный и гораздо более простой алгоритм, чтобы просто поместить 4-й элемент в нужное место. Очень круто. Улучшение основных алгоритмов сортировки LLVM, которые уже были сильно оптимизированы вручную лучшими в мире, определенно вызывает чувство «это 1997 год, и Deep Blue побеждает чемпиона мира по шахматам».

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

На хабре отмечают, что победил тупо из-за нечеловеческого APM и прочих читов, а не стратегически, в отличие от побед в Го например или шахматах.

https://youtu.be/mpAUufSzaUo

Улучшение основных алгоритмов сортировки LLVM, которые уже были сильно оптимизированы вручную лучшими в мире, определенно вызывает чувство «это 1997 год, и Deep Blue побеждает чемпиона мира по шахматам».

Где-то заплакал Дональд-наш-Кнут :)

Дедушка старенький, ему всё равно. :)

Я думаю, Ожегов и Зализняк тоже млеют от такой стилистики.

Звучит невероятно