Меньше работы — медленнее

Всем привет! Меня зовут Александр Схрейдер, в рейтинге Кубка СЭРПАС 2026 я был под ником verstappen21. Да, в честь Ферстаппена. Учитывая, что всё соревнование в итоге было про скорость, ник подошёл.

Кирилл Ерохин уже рассказал на Хабре, как он проводил Кубок: про серверы, платформу, защиту решений и финал. Эта статья — взгляд с другой стороны баррикад. Я расскажу, как решал три отборочные задачи и финальный лабиринт, что сработало на Эльбрусе, а что сделало только хуже. И главное, почему интуиция с Intel и AMD на e2k подводит чаще, чем хотелось бы.

Сразу предупрежу: статья длинная, с цифрами и табличками. Все цифры — медианы судейских прогонов, которые я записывал по ходу соревнования. В подкасте Pure Virtual Cast Тимур посоветовал написать разбор, а Кирилл обещал его прокачать, так что отступать было некуда.

Предыстория, которую можно пропустить

Как-то вечером я листал интернет в поисках интересного хакатона. Хотелось чего-то не очередного «сделайте веб-сервис за выходные», а чтобы было про железо и скорость. И наткнулся на соревнование, где нужно писать быстрый код под Эльбрус. Про Эльбрус я тогда знал примерно то же, что и все: что он есть и что он где-то стоит. Подумал: а когда ещё будет шанс пощупать его по-настоящему? Зарегистрировался в тот же вечер.

Довольно быстро выяснилось, что быстрый код я писать вроде бы умею, но всё, что я про это знаю, я знаю про x86. На Эльбрусе половина привычных вещей просто не работает, а часть делает хуже. Это и оказалось самым интересным.

Немного контекста для тех, кто не читал статью Кирилла. Активных участников было 112, все три задачи решили 46 человек. Важно было не просто решить задачу, а решить её быстро и экономно по памяти. Оценка на отборе считалась так:

E(t, m) = \left(\frac{t}{T_0}\right)^{\alpha} \cdot \frac{m}{M_0}, \qquad \alpha = \frac{\ln 1{,}2}{\ln (1/0{,}9)} \approx 1{,}73

Слоган Кирилла звучал так: «10% прироста скорости стоят не более 20% увеличения памяти». Ранжировали по медиане десяти прогонов, плюс обязательный Valgrind без ошибок. Лимиты: 10,5 секунды, от 128 до 512 МБ в зависимости от задачи и не больше семи потоков.

Отбор шёл на платформе Codenrock, которая специально ради Кубка научилась запускать решения на Эльбрусах Кирилла. Пишешь код, отправляешь и через минуту видишь время и память на настоящем Эльбрус-8СВ. Поэтому каждая идея превращалась в маленький эксперимент: отправил, посмотрел, понял, почему стало быстрее или медленнее. Я версионировал каждую отправку и записывал, что поменял и что получилось. В задаче 1 таких версий набралось больше двадцати, в задаче 3 — одиннадцать. Без этого журнала статьи бы не было.

Коротко про Эльбрус, или кухня без шефа

Разницу между Эльбрусом и привычными процессорами я себе объяснял через кухню.

У Intel на кухне стоит шеф. Он смотрит на заказы и на ходу всё перекидывает: суп варится, давай пока порежем салат. Процессор сам заглядывает вперёд по программе, находит независимые команды и выполняет их параллельно. Это out-of-order исполнение, и оно прощает очень многое.

У Эльбруса шефа нет. Есть заранее расписанный план: в этот такт трое режут, двое жарят. Повара выполняют его очень быстро и очень дружно, но если в плане написано «ждём бульон», они стоят и ждут. План пишет компилятор LCC, когда собирает программу, и упаковывает независимые операции в широкие команды (VLIW). Если компилятору нечего упаковать, широкая команда уходит полупустой.

Отсюда весь мой стиль работы под e2k:

давать компилятору много независимой работы;
читать память подряд, без прыжков;
поменьше ветвлений;
и всё мерить, потому что интуиция с x86 постоянно подводит.

Как говорит Кирилл, задача программиста под Эльбрус — упростить жизнь компилятору, а дальше он всё сделает сам. С этим я полностью согласен, и всё, что ниже, по сути про то, как придать коду правильную форму.

Задача 1: сотрудники и доступы

Что спрашивали

Дана бинарная таблица прав: строки — сотрудники, столбцы — ресурсы, единица означает, что доступ есть. Нужно посчитать, сколькими способами можно выбрать двух сотрудников и два ресурса так, чтобы у обоих был доступ к обоим. То есть число квадратиков 2×2 из одних единиц.

Матриц пять, самые большие 12288×6144, 6144×12288 и 9216×9216. На вход приходит около 236 МБ нулей и единиц текстом. В лоб это месяц счёта.

Одна формула

Возьмём пару строк. Если у них $c$ общих единиц, то прямоугольников на этой паре ровно

\binom{c}{2} = \frac{c(c-1)}{2},

Это биномиальный коэффициент: любые две общие позиции дают один прямоугольник. Вся задача превращается в «для каждой пары строк посчитай одно число».

Клетка — это бит, значит в 64-битное слово влезает 64 клетки. Общие единицы считаются как popcount(a & b), а у Эльбруса есть отдельная команда для popcount (__builtin_e2k_popcntd). 64 сравнения превращаются в пару операций.

Сначала выкинуть лишнее

Меньшая ось. Число пар растёт квадратично, поэтому для матрицы 12288×6144 пары считаются по столбцам. Для этого матрица транспонируется битовой «бабочкой» 64×64, параллельно всеми потоками (было около 50 мс, стало около 15).
Одинаковые строки. В условии была подсказка, что у некоторых сотрудников права совпадают полностью. Ну, типа все бухгалтеры одинаковые. Такие строки я хранил один раз с кратностью, а пары внутри группы считал формулой. Поиск через хеш, но после совпадения хеша строки всегда сравниваются целиком через memcmp, чтобы коллизия ничего не испортила. Уникальных строк осталось 5376 из 6144 и 8064 из 9216, минус примерно четверть пар.

Тридцать две пары сразу

Если считать по одной паре, получается длинная цепочка: прибавил, прибавил, прибавил, и каждое сложение ждёт предыдущее. На Эльбрусе это означает, что большая часть широкой команды пустует.

Поэтому горячее ядро берёт 16 строк с одной стороны и 2 с другой и считает 32 пары одновременно, у каждой свой счётчик:

// упрощённо: 16 левых векторов × 2 правых = 32 независимых аккумулятора
for (int w = 0; w < words; ++w) {
    uint64_t r0 = right0[w], r1 = right1[w];
    for (int i = 0; i < 16; ++i) {
        uint64_t l = left[i][w];              // одно чтение, два использования
        acc0[i] += __builtin_e2k_popcntd(l & r0);
        acc1[i] += __builtin_e2k_popcntd(l & r1);
    }
}

Компилятору есть что раскладывать параллельно, и каждое слово из памяти используется дважды. Я пробовал шире: 16×4 и 8×4 оказались хуже, кончились регистры, и компилятор начал гонять значения через память. 16×1 — мало параллелизма. Лучшая точка нашлась где-то посередине, и найти её удалось только перебором.

Интересно прикинуть, сколько железо делает за такт. На матрице 9216×9216 около 32,5 млн пар по 144 слова, то есть примерно 4,7 млрд операций «AND + popcount + сложение» за ~238 мс на семи ядрах по 1,5 ГГц:

\frac{4{,}7 \cdot 10^{9}}{0{,}238\ \text{с} \cdot 7 \cdot 1{,}5 \cdot 10^{9}\ \text{Гц}} \approx 1{,}9\ \text{слова за такт на ядро}.

А это пять с лишним полезных операций за такт. На обычном C, без ассемблера. Вот так выглядит VLIW, когда код правильной формы.

Чтение в освободившуюся память

Когда счёт стал быстрым, заметным стало чтение. Матриц пять, и просто распарсить текст занимает ощутимое время. Хотелось читать следующую матрицу, пока считается текущая. Но память шла в оценку, и держать второй большой буфер не хотелось.

Потом я заметил, что посчитанный блок строк больше не нужен. Значит, следующую матрицу можно писать прямо поверх него, по мере того как блоки освобождаются. Это как въезжать в квартиру, пока прошлые жильцы ещё съезжают: заносишь вещи в комнату, как только её освободили, главное в занятую не залезть. Технически это флаги done[ib] с release/acquire и «безопасный фронт», который двигается только по непрерывному префиксу готовых блоков. В итоге около 115 мс чтения спряталось за счётом, а всё решение жило примерно в 15 МБ.

Отдельно про потоки. OpenMP-потоки держат заметно больше памяти (стеки, runtime), а память входила в оценку. Я написал свой постоянный пул на pthread: 6 рабочих потоков плюс main, стеки по 64 КиБ, блоки раздаются через atomic_fetch_add. Скорость та же, памяти сильно меньше.

Самый большой прирост под конец

И уже под конец, когда казалось, что всё сделано, следующая версия дала почти 10%, и в ней не было ни одной новой вычислительной идеи. Я просто поменял, что main-поток делает первым. Работа неравная: первые блоки самые тяжёлые. Теперь main сначала забирает себе 15–16 самых тяжёлых блоков, потом уходит читать следующую матрицу, а если писать ещё некуда, помогает остальным считать. Чтобы никто не сидел без дела. 698 → 629 мс.

Версия	Медиана	Что изменилось
v5	~778 мс	упаковка в биты, дедупликация, плотное ядро
v10	~766 мс	свой пул потоков: та же скорость, сильно меньше памяти
v11	~728 мс	параллельная транспозиция
v15	~724 мс	ядро 16×2
v17	~698 мс	одна арена под матрицы, чтение поверх посчитанного
v18	~629 мс	main берёт тяжёлые блоки первым
v19	626,5 мс	загрузки с подсказкой кэша (`ld_64s_t1`), лучшая медиана

Итого с 778 до 626 мс, около 15 МБ памяти. Из 626 мс примерно 545 — чистый счёт, ввод почти полностью спрятан.

Как я сделал меньше работы, и стало медленнее

А теперь моя любимая история из всего соревнования.

Я заметил, что многие строки не одинаковые, но почти одинаковые. Ну, думаю, посчитаю одну, а для похожих только разницу. Работы стало на 60% меньше, я был прям доволен.

Отправляю — стало медленнее. Причём «драматически».

Сначала я подумал, что что-то сломал, перепроверил. Всё правильно, просто медленнее. Потом дошло. Старый вариант был тупой, но ровный: загрузил, сравнил, посчитал, сложил, и так миллиарды раз. Компилятор раскладывает такое идеально. А в новом появились проверки, прыжки по памяти, ветвления. Intel частично переварил бы это своим out-of-order, а на Эльбрусе всё это вылезает напрямую.

С тех пор я на Эльбрусе сначала смотрю, насколько код ровный, и только потом, сколько в нём операций. Сократить работу можно двумя способами: выбросить ненужное, не ломая структуру доступа к памяти, — это выигрыш. Заменить плотную работу на разреженную — на e2k почти всегда проигрыш.

Ещё одна неудача, которую я так и не объяснил: 128-битные операции, которые по идее вдвое быстрее, на одной из матриц дали 139 → 402 мс. Видимо, без разбора ассемблера широкий SIMD лучше не трогать.

Задача 2: свёртки сигналов

Что спрашивали

Свёртку проще всего объяснить через эхо. Хлопнул в ладоши в комнате — пошёл затухающий отклик. Хлопаешь много раз с разной силой, и микрофон в каждый момент слышит сумму всех этих откликов. Это и есть свёртка, и она везде: фильтры звука, размытие картинок, сигналы с датчиков.

В задаче $K$ каналов, у каждого свой сигнал $a_r$ и своя импульсная характеристика $b_r$ длины $N$ (степень двойки). Нужно точно, в целых числах, посчитать сумму циклических свёрток:

y[t] = \sum_{r=1}^{K} \sum_{i=0}^{N-1} a_r[i] \cdot b_r\big[(t - i) \bmod N\big].

Самые тяжёлые тесты — $N = 524\,288$ при $K = 16$ и $N = 2\,097\,152$ при $K = 4$ , коэффициенты от −7 до 7. Лимит памяти жёсткий: 128 МБ. В лоб это $O(KN^2) \approx 4 \cdot 10^{12}$ операций.

Почему NTT, а не FFT

Свёртка — это то же самое, что умножение многочленов, а многочлены быстро умножаются через быстрое преобразование Фурье за $O(KN \log N)$ . Переводишь в значения в особых точках, перемножаешь поточечно и переводишь обратно.

Только обычный FFT считает в double, и в конце вместо целого числа получается что-то с кучей девяток после запятой. Скорее всего, округлится правильно. Но «скорее всего» меня не устраивало: одна неверная цифра — и всё решение мимо. Поэтому я взял NTT: тот же алгоритм, но в остатках по модулю простого числа

p = 998\,244\,353 = 119 \cdot 2^{23} + 1.

Там всё целое и точное, а корни из единицы нужных степеней существуют для всех $N$ задачи.

Ответ при этом получается по модулю, и нужно восстановить знак. Максимальный модуль ответа можно оценить заранее: $|y| \le 411\,041\,792 < p/2$ . Значит, остаток меньше $p/2$ — это плюс, больше — минус, путаницы нет. Одного модуля хватило, китайская теорема об остатках не понадобилась.

Что ещё срезал

Один обратный NTT на всех. Фурье линеен, поэтому произведения всех каналов накапливаются в одном спектре $\sum_r \hat{A}_r \cdot \hat{B}_r$ , и обратно переводится только сумма.
Одинаковые отклики. Условие намекало, что характеристики каналов могут совпадать. Тогда $a_1 * b + a_2 * b = (a_1 + a_2) * b$ : сигналы складываются до преобразования, и одна свёртка вместо двух.
Постоянные отклики. Если $b$ — константа, свёртка вырождается в $b_0 \cdot \sum_i a[i]$ во всех точках, и NTT не нужен вовсе.
Без деления. Внутри преобразования очень много «взять остаток», а деление медленное. Для известных заранее корней из единицы — умножение Шоупа, для произведения двух спектров — Монтгомери, плюс ленивая редукция в диапазоне $[0, 2p)$ . В горячем коде делений нет.
Под VLIW. Бабочки radix-4 (две стадии за один проход по памяти), развёрнутые на четыре независимых индекса, а последние три стадии делаются на восьми значениях прямо в регистрах.

Память

Числа от −7 до 7 — это четыре бита, так что я хранил по два в байте. А потом заметил, что после первых двух стадий большое преобразование разваливается на четыре независимых четверти, и их можно считать по очереди. Все временные массивы стали в четыре раза меньше, а распаковка из 4-битного формата совмещена с первыми стадиями, так что полный массив длины $N$ вообще не появляется. Большие буферы через mmap/munmap, чтобы страницы реально возвращались системе. Память ушла с 53 до 34 МБ.

Чтение оказалось самым медленным

Когда математика стала быстрой, я посмотрел профиль: из 826 мс 365 уходило просто на чтение чисел из текста. Пришлось делать параллельный разбор: main читает stdin большими блоками, потоки парсят свои куски, границы сдвигаются до ближайшего пробела, чтобы не разрезать число, а префиксная сумма раскладывает результат без гонок. Вывод тоже параллельный, через таблицу трёхзначных групп цифр.

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

Версия	Время	Память
v1	~1042 мс	53,2 МБ
v4	~987 мс	33,7 МБ
v5	826 мс	33,8 МБ

Задача 3: карта и пункты выдачи

Эта задача мне понравилась больше всех.

Что спрашивали

Город в клеточку, в некоторых клетках стоят пункты выдачи. Для каждой клетки нужен квадрат расстояния до ближайшего пункта, а на выход — сводка: общая сумма, максимум, сколько клеток с максимумом и первая из них, суммы по каждой строке и каждому столбцу. Главная карта 7680×10240, это 78,6 млн клеток, пунктов 73 000.

Параболы

Классический алгоритм (Felzenszwalb–Huttenlocher) раскладывает расстояние на вертикаль и горизонталь и решает задачу по одной строке. В строке каждый столбец $q$ с пунктами даёт параболу

P_q(x) = (x - q)^2 + f_q,

где $f_q$ — квадрат вертикального расстояния до ближайшего пункта в этом столбце. Ответ в каждой точке — самая нижняя из парабол. У нижней огибающей есть приятное свойство: каждая парабола выигрывает на одном сплошном куске. Поэтому строка описывается коротким списком кусков и строится за один проход со стеком.

Карту можно не строить

Обычно дальше заполняют всю карту расстояний и потом её суммируют. А мне не хотелось держать 78 миллионов чисел только ради того, чтобы их сложить.

На каждом куске $[L, R]$ огибающей расстояние — обычный квадратный многочлен

D(x) = x^2 + b\,x + c.

Значит:

сумма по куску считается формулой: $\sum_{x=L}^{R} D(x) = \sum x^2 + b \sum x + c\,(R - L + 1)$ , где суммы $\sum x$ и $\sum x^2$ берутся из префиксных массивов;
максимум выпуклой параболы на отрезке всегда на краю, так что проверяются только $D(L)$ и $D(R)$ ;
суммы по столбцам получаются красивее всего. Если сложить многочлены всех строк для столбца $x$ , у них просто складываются коэффициенты. Коэффициенты $b$ и $c$ копятся в разностных массивах на отрезке куска, а в конце

\mathrm{ColSum}(x) = H \cdot x^2 + B(x) \cdot x + C(x),

потому что коэффициент при $x^2$ у каждой из $H$ строк равен единице. Две записи на кусок — и никакого второго прохода.

Получается, что клеток 78 миллионов, и ни в одну я по-настоящему не зашёл. Уже первая версия так работала с памятью в единицы мегабайт при лимите 350. Правда, работала за 444 мс, потому что для каждой строки всё ещё перебирались все пункты.

Точное отсечение

Большинство пунктов, очевидно, ни при чём: пункт на другом конце города никогда не будет ближайшим. Но отсекать нужно так, чтобы это никогда не ошибалось. Никаких эвристик.

Логика простая. Карта режется на полосы по 32 строки и тайлы по 64 столбца. Если я знаю, что из любой точки тайла до какого-то пункта не больше $U$ , то все пункты, до которых даже от ближайшей точки тайла больше $U$ , можно выкинуть: они всегда проиграют. Одна эта идея дала 444 → 187 мс.

Вороной

А дальше то, чем я, наверное, горжусь больше всего.

Есть ячейки Вороного: для каждого пункта это все точки, для которых он ближайший, его «район». Ячейки выпуклые и содержат сам пункт.

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

Вывод: кандидаты для полосы — это пункты внутри неё плюс те, что появляются на непрерывных нижних огибающих верхней и нижней границы. Всех остальных можно выкинуть, и это доказано. Касание ровно в одной точке я специально сохраняю, чтобы не потерять граничный случай. Кандидатов стало 172 834 вместо 265 061, время 137 → 110 мс.

Потом я повторил то же самое внутри полосы на подполосах 14, 10 и 6 строк. Без граничных строк это $12 + 8 + 4$ , то есть ровно пачки по четыре строки — под SIMD, о котором дальше. 88 → 71 мс.

Четыре строки разом

В 128-битный регистр Эльбруса влезает четыре 32-битных числа, а для соседних строк вычисление вертикального минимума одинаковое. Через qpsubw, qpmullw и qpminuw я считал вертикальные составляющие сразу для четырёх строк, а дальше строил четыре независимые огибающие. Пробовал восемь и тридцать две строки — медленнее, опять не хватало регистров.

Профайлер против судьи

В самом конце у меня было две версии. Мой профайлер говорил, что новая быстрее (48,6 против 51,1 мс на основном счёте), а судья говорил, что быстрее старая. Я отправил старую. В моменте было обидно, но считает в итоге судья.

Судья показывал только стандартный вывод, поэтому в коде был отдельный режим, который специально выдавал неправильный ответ, зато печатал разбивку времени по этапам. Один WA ради профиля — нормальная цена.

Правильность я проверял перебором на 300 маленьких случайных картах: совпали все 5773 числа.

Версия	Судья	Идея
V1	444 мс	огибающая без хранения карты, суммы формулами
V2	~187 мс	пространственный индекс, точное отсечение
V3	~137 мс	балансировка потоков, SIMD на 4 строки
V5	~110 мс	фильтр Вороного по границам полосы
V7	~88 мс	дешёвая подготовка индекса
V8	~70 мс	иерархия подполос 14/10/6, быстрый парсер
V10	70–75 мс	лучше по профайлеру, хуже у судьи — не отправлен

С 444 до 70 мс, в 6,3 раза. Это мой самый большой выигрыш за соревнование.

Финал: бот в лабиринте

Правила

Финал Кирилл придумал очень классно. Лабиринт 48×48 с пещерами, коридорами и тупиками, два бота стартуют в противоположных углах и бегут одновременно. Нужно добежать до одного из боковых углов, потом в центр, потом в другой угол и в конце — на старт соперника. Кто быстрее, тот выиграл.

Фишка в том, что каждая клетка — это задача, одна из трёх отборочных. Чтобы шагнуть в новую клетку, получаешь данные, решаешь, отправляешь ответ. Решатели те же, что на отборе, и улучшать их нельзя, только адаптировать ввод-вывод и число потоков. Видно на восемь клеток вокруг, через стены не видно.

И есть стан — штраф за память во времени:

D_{\text{стан}} = \frac{1}{512\ \text{МиБ}} \int M(t)\,dt.

Чем больше и дольше держишь память, тем дольше потом стоишь перед контрольной точкой, пока соперник бежит. Для понимания масштаба: 64 МиБ в течение минуты — это $64 \cdot 60 / 512 = 7{,}5$ секунды стояния.

Из-за всего этого у каждого бота свои скорости на разных типах клеток, а значит, свой оптимальный маршрут. Финалистам дали по 31 ядру четырёхпроцессорного сервера на Эльбрус-8СВ. Кстати, мои отборочные решатели Кирилл взял как эталон для калибровки времени клеток, чем я, если честно, немного горжусь.

Туман

Первое решение: что делать с клетками, которые бот ещё не видел. Если считать их опасными, бот будет топтаться на месте. Я сделал так, что неизвестное считается проходимым, просто подороже. Бот идёт в туман, упирается в стену, пересчитывает путь.

Клетка	Стоимость входа
Стена	∞
Уже решена мной	10 мс + сохранённое время решения
Свободна, тип виден	10 мс + выученная стоимость типа
Свободна, тип не виден	10 мс + ожидание по трём типам
Вообще не видна	то же ожидание × вес участка маршрута

Поиск пути

Путь ищется через A*. Точный A* «заливал» карту: самая дешёвая клетка намного дешевле типичной, и эвристика получается слабой. С весом 2 маршруты стали хуже на 0,3%, а планирование ускорилось в три раза.

Но больше всего дало другое. Сначала планировщик думал про весь маршрут сразу, со всеми этапами. Генератор карт Кирилла умел строить лабиринты и до 192×192, и я прикинул, что на таком размере бот тратил бы на раздумья около 50 секунд за гонку. Потом заметил, что цена клетки не зависит от того, как ты в неё пришёл. Значит, маршрут — просто сумма участков, и чтобы решить, куда шагнуть сейчас, достаточно искать путь до следующей контрольной точки. Переписал, и даже на большой карте планирование стало занимать ~2,5 мс на ход вместо ~44. На финальных 48×48 бот думал практически мгновенно.

Зеркало

Лабиринт был симметричен при повороте на 180°. Значит, каждая клетка, которую я вижу, показывает мне ещё и зеркальную у соперника. Иду к своему углу, вижу коридоры — и уже знаю, какие коридоры у него. На второй половине маршрута путь по сути известен заранее.

Но реально увиденная клетка всегда важнее догадки. А если путь вдруг не находится, бот выкидывает все зеркальные догадки и ищет как обычно, чтобы ни при каком генераторе не сломаться. Можно ли так использовать симметрию, я, конечно, сначала спросил у Кирилла.

Одну вещь бот заранее просчитать не может: к какому углу бежать первым. Со старта это почти не угадать, и в этом своя интрига: даже при хороших решателях каждая карта немного лотерея, и смотреть за этим на стриме было очень интересно.

Как бот узнаёт цены

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

Сначала бот ещё мерил скорость на прогреве перед стартом. И я увидел, что из-за шума одна и та же карта проходилась то быстро, то заметно медленнее: немного другие цифры в начале, другие первые решения, и весь маршрут другой. В итоге я зафиксировал стартовые значения, замеренные заранее (344, 292 и 131 мс для трёх типов), и всё стало стабильно.

Двенадцать потоков быстрее тридцати

Ядер тридцать одно, логично же дать всем по тридцать потоков. Для первой задачи так и сделал: свой пул с маленькими стеками, он нормально масштабируется. А в двух других каждый живой OpenMP-поток держит около мегабайта, а память — это стан. Свёртка на 16 и 30 потоках работала ещё и медленнее, чем на 12. Один из замеров: 30/30 потоков — финиш за 151 с, 12/12 — за 134,5 с. Так что двенадцать оказались и быстрее, и дешевле. В итоге стан занимал около 6–7% времени гонки.

Симулятор и баг, который поймал Кирилл

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

А ещё Кирилл перед финалом сам проверял, как адаптированы решатели, и нашёл у меня баг. В финальном профиле задачи 2 было 72 канала вместо максимум 16 на отборе, а сумма сигналов одинаковых каналов лежала в int8. На отборе всё влезало, а тут начало бы переполняться. Поправил одну строчку (int8 → int16) и добавил проверку оценки. Но запомнил: если оптимизировал под конкретные ограничения, а они поменялись, перепроверяй всё. Спасибо Кириллу, что поймал это до финала. Такое внимание организатора к коду участников, по-моему, дорогого стоит.

Как прошёл финал

В финале я играл с Ксенией Шкулевой и выиграл серию 2:0. Под конец Ксения навязала настоящую борьбу, а Кирилл до последнего ждал хотя бы одну ничью, но её так и не случилось.

Как я работал с нейронками

Раз уж выпуск подкаста назывался «Эпоха нейронок», скажу как есть. Я очень плотно работал с ИИ-агентами, которые пишут и правят код. Большую часть кода руками писал не я. Это разрешено правилами, и так сейчас работают очень многие.

Но интересно, что именно на Эльбрусе нейронка сама по себе мало что решает. Про e2k в интернете мало материалов, модели учились в основном на x86, и советы у них оттуда. А главное, нейронка не видит железо. Любая модель скажет, что на 60% меньше работы — это лучше, и почти везде это правда. Тут нет. Узнать это можно, только если отправить и посмотреть.

Так что в основном я ставил эксперименты. Придумал, что попробовать, агент написал, я отправил на Эльбрус, посмотрел цифры, решил, что дальше. Писать варианты агент ускоряет очень сильно, но какой вариант пробовать, что мерить и каким цифрам верить, решал я. Один раз симулятор финала показывал, что одна настройка лучше, а на реальном сервере она оказалась сильно хуже (104,8 с против 85,2). Такое никто не заметит, пока сам не перемеришь.

Поэтому защита решений — очень правильная штука. Сидишь перед камерой, без нейронок, запустить ничего нельзя, и тебя спрашивают: почему так, а что если поменять вот это. Мне как первому досталось по 12 вопросов на задачу, потом Кирилл сжалился и сократил до трёх. Я готовился к защите не меньше, чем к самим задачам, и в итоге понимаю свои решения лучше, чем если бы просто написал их сам и не думал.

Компилятор тоже делает за меня кучу работы. LCC раскладывает мои циклы лучше, чем я сделал бы руками, но никто не говорит, что победил LCC.

Что я вынес

Сначала выкинь лишнюю работу, потом ускоряй остальное. Самые большие скачки дали идеи вроде «не строить карту» или «считать одинаковое один раз»: в задаче 3 это ×6,3.
Но не ломай регулярность. На Эльбрусе ровный простой цикл часто быстрее хитрого.
У VLIW есть сладкая точка ширины. Меньше — пустые слоты в широкой команде, больше — кончаются регистры. 16×2 в задаче 1, четыре строки в задаче 3.
Мерь на целевом железе и оптимизируй то, что меряет судья. x86, профайлер и симулятор подводили меня по нескольку раз. Шум ±3–4%, одиночный прогон ничего не доказывает.
Память — тоже время. Свой пул вместо OpenMP, 4 бита на число, 12 потоков вместо 30.
Когда ядро быстрое, тормозит всё остальное: ввод, вывод, аллокации.
Записывай неудачи. Из неудачных экспериментов я узнал больше всего.

Благодарности

Огромное спасибо Кириллу Ерохину. Человек на свои деньги покупает Эльбрусы, сам всё поднимает, сам пишет задачи, сам пишет сервер для финала и при этом отвечает на вопросы почти в любое время суток. В финале я писал ему очень много вопросов, и он всегда отвечал, быстро и подробно. Без него этого соревнования просто не было бы.

Что дальше?

Дальше у меня стажировка в МЦСТ, которая была среди призов, и научная работа на оборудовании, которое предоставил Кирилл: сравнение Эльбрус-2С3 с современными x86 и исследование того, насколько хорошо нейросети оптимизируют код под Эльбрус. Результаты обещаю показать.

А если вы думаете, идти ли на следующий Кубок СЭРПАС, — идите. Даже если не выиграете, про процессоры узнаете очень много. И про то, что «меньше работы» не всегда значит «быстрее».