Воспроизводимость результатов

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

Если программа работает недетерминированно, то поиск ошибок превращается в какой-то кошмар. То баг воспроизводится, то нет. Как понять из-за чего получается разный результат? Если вы пишете на C++, то с довольно большой вероятностью у вас Undefined Behavior, поздравляю. Можно поискать его с разными санитайзерами, иногда помогает.

В Rust таких проблем почти нет, но иногда все равно программы работают по-разному. В такие моменты думаешь, где ты поиспользовал random и забыл об этом. Так вот, два последних раза, когда у меня так было, я сложил какие-то объекты в хеш-таблицу, а потом проитерировался по ней. В Rust хеш-таблицы специально используют разный seed на каждом запуске, и это хорошо. Например, так сложнее подобрать данные, на которых она начнет тормозить. А еще заставляет программистов не закладываться на конкретную реализацию хеш-функций.

В общем с одной стороны хорошо, а с другой — источник недетерминизма, о котором постоянно забываешь. Хочу линтер, который предупредит меня в следующий раз, когда я захочу проитерироваться по хеш-таблице. Или вообще автоматику, которая говорит в каком месте программа работает не так, как в прошлый раз.

Собираем пазлы

Disclaimer: на подготовку этого поста я потратил очень много времени, так что буду рад, если вы его прочитаете, поставите лайк или расскажите о нем друзьям.

Когда я только начинал этот канал, я долго пытался придумать о чем тут писать. Хотелось рассказывать о чем-то интересном, и при этом создавать какой-то уникальный контент, который вряд ли можно прочитать где-то еще. Так появились посты про использование SIMD оптимизаций на Rust в олимпиадном программировании. И правда, кто еще об этом напишет, если не я? :)

Примерно в то же время я попытался собрать пазлы, которые подарили за участие в Google HashCode, но в какой-то момент остались только полностью белые части, собирать которые было очень скучно. В тот момент я подумал, что прикольно было бы написать программу, которая по фотке пазла сможет собрать его автоматически. Идея показалось прикольной, но до реализации руки не доходили.

Прошло много времени и я таки решил попробовать это сделать. Что из этого вышло читайте (или хотя бы посмотрите на картинки!) тут: https://teletype.in/@bminaiev/jigsaw-puzzle-solver

Ради интереса я купил себе абсолютно белый пазл, состоящий из 1000 кусочков, каждый размером где-то 1х1см. Как думаете, можно ли написать программу, которая соберет его по этой одной картинке?

Всем оптимистам из предыдущего опроса предлагаю решить следующую задачу. Пусть мы уже правильно соединили кусочки #926, #999 и #574. Помогите алгоритму правильно выбрать четвертый кусочек (рядом с каждой картинкой указана правдоподобность по мнению алгоритма, меньше - лучше).

Судя по предыдущему посту, чтобы получить много лайков, нужно чтобы текст состоял из одного смайлика. Но все равно рискну запостить что-то более длинное.

Я наконец-то написал вторую часть истории про сборку пазлов. Кажется, все предыдущие разы, когда я заканчивал текст словами "читайте продолжение во второй части", на самом деле второй части никогда не случалось, потому что все самое интересное уже написано в первой, и интерес к написанию терялся.

В этой статье получилось меньше про какие-то конкретные алгоритмы, а больше просто таймлайн с фоточками и комментариями, но надеюсь все равно будет интересно.

Заодно перенес статьи на другой домен: https://bminaiev.github.io/jigsaw-puzzle-solver-2

Common Mistakes in Competitive Programming and How to Avoid Them

Это очень смешно. Вчера на CodeForces вышел пост со списком типичных ошибок на контестах типа "не передавайте массив по значению, программа будет работать долго".

А после этого вышел другой пост: https://codeforces.com/blog/entry/111254. С тем же самым списком ошибок, но кусочками кода на Rust и комментариями "не нужно так писать, вы получите ошибку компиляции".

В общем используйте языки, которые защищают вас от глупых ошибок!

Simulated Annealing (отжиг) — самый важный алгоритм в оптимизационных соревнованиях. Если открыть случайное решение с Topcoder Marathon, с довольно большой вероятностью вы его там найдете. Проблема с оптимизационными алгоритмами в том, что нет единого правильного способа их написания. В одной задаче работает что-то одно, в другой — другое. В зависимости от конкретной задачи нужно выбирать разные константы. В итоге, если читать статью в википедии про SA, то там написано много всего, но совершенно не понятно как написать работающий код.

Статей в интернете про него очень много, но из них ничего не понятно, так что естественно я решил написать еще одну. Она то точно будет понятной! Кстати, внутри много графиков, которые лучше смотреть с компьютера, а не с телефона.

https://bminaiev.github.io/simulated-annealing

Secure multi-party computation

У меня последнее время появилось новое хобби. Я пытаюсь простыми словами рассказывать о том, что такое SMPC, зачем оно может быть нужно, и как оно работает. Расскажу и тут, вдруг вам будет интересно. SMPC это криптографические протоколы, которые позволяют нескольким участникам произвести вычисления над данными, но таким образом, чтобы все узнали итоговый результат, но при этом никто не узнал ничего про данные, которыми владели другие участники.

Например, я хочу порекомендовать вам какой-нибудь хороший телеграм канал. Например, https://www.tgoop.com/experimentalchill. Как узнать насколько такая рекомендация будет актуальна? Один из способов — посмотреть на список подписчиков моего канала и список подписчиков Experimental chill. Если все уже и так подписаны на него, то зачем еще раз вам о нем рассказывать? Или наоборот, если никто не подписан, то скорее всего тематика очень разная и никому не будет интересно.

Но как посчитать количество людей, которые подписаны на оба канала? Автор каждого канала знает список людей, которые на него подписаны. Но делиться им в plaintext формате не хочется. SMPC как раз таки позволяет в том числе вычислить размер пересечения двух множеств, не раскрыв при этом вообще никакой дополнительной информации!

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

Cache misses

На контестах полезно уметь оценивать, сколько будет работать какое-то решение. Не только помнить константы "10^6 операций с сетом работают меньше 1с, а 10^7 больше", но и понимать почему.

Типичная проблема — обращения к памяти. Как оценить насколько они дорогие? Зависит от количества используемой памяти. Если у нас массив на 1000 элементов, то он легко поместится в L1 кеш и все будет очень быстро. А если массив занимает 100мб, то не хватит и L3 кеша, и все будет тормозить. Давайте научимся определять размеры кешей и насколько дорого к ним обращаться.

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

let n = 500_000;
let p = gen_perm(n);
let mut a = vec![0; n];
for i in 0..n {
a[p[i]] = p[(i + 1) % n];
}
let mut pos = 0;
for _ in 0..100_000_000 {
pos = a[pos];
}

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

$ perf stat -e mem_load_retired.l1_miss,mem_load_retired.l2_miss,mem_load_retired.l3_miss ./a

99,569,765 mem_load_retired.l1_miss
71,453,658 mem_load_retired.l2_miss
22,025 mem_load_retired.l3_miss

Количество L3 промахов маленькое, так что можно считать, что вся память помещается в L3. А вот количество L2 промахов говорит о том, что 71.4% массива не поместилось в L2 кеш (а 28.6% поместилось). Целиком массив занимает 500_000 * 8 = 4мб, значит размер L2 кеша 4мб * 0.286 = 1.14мб.

Учитывая реальный размер L2 кеша, оценка довольно хорошая:

$ getconf -a | grep LEVEL2_CACHE_SIZE
LEVEL2_CACHE_SIZE 1310720

Можно провести такой же эксперимент для разных значений n и узнать параметры всех уровней кешей, но в телеграмме есть ограничение на длину постов :(

Parallel Simulated Annealing

Недавно мы участвовали в Reply Challenge. Соревнование похоже по формату на Google HashCode. На 4 часа дают одну задачу, у которой нет оптимального решения, и несколько тестов к ней. Нужно как можно лучше решить эти тесты используя любые средства.

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

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

Когда у нас есть какое-то валидное решение, к нему можно применять локальные оптимизации (о которых я уже писал). Можно случайным образом совсем немного поменять решение, и проверить, улучшаются ли от этого набранные баллы. Если улучшаются — сохранить новое решение и продолжить.

Такой подход часто приводит к локально оптимальному ответу, который не получается улучшить. Чтобы этого избежать можно использовать отжиг (о нем тоже писал).

Если отжигу дать больше времени, то он найдет решение лучше. Но соревнование ограничено по времени, поэтому можно попробовать его распараллелить. В Rust есть библиотека rayon, которая позволяет распараллелить программу просто заменив слово iter на par_iter (магия!). Единственное условие — код внутри итераций не должен модифицировать одни и те же данные.

Проблема отжига в том, что он по своей сути однопоточный. Есть какой-то текущий ответ, для него генерируются случайные изменения, которые иногда применяются. Текущий ответ меняется со временем и поэтому его нельзя обновлять внутри par_iter.

Во время контеста я сделал следующее. Вместо выбора одного случайного изменения, давайте создадим 20 потоков, в каждом посмотрим 1000 случайных изменений и выберем лучшее из них. После этого есть 20 лучших изменений, их попробуем синхронно применить к решению как в обычном алгоритме отжига. Повторим. Отгадайте почему это плохо работает.

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

Понятно, что это решение не идеально, но оно точно лучше однопоточного кода. А может быть можно еще лучше?

Parallel Simulated Annealing && GPT-4

Я все никак не мог найти время, чтобы написать продолжение поста про Parallel Simulated Annealing. Поэтому, чтобы не отставать от трендов, попросил GPT-4 написать многопоточный отжиг на Rust вместо меня. На удивление ответ получился довольно адекватный. Он в точности написал то, что я предлагал в предыдущем посте (запустить 20 отжигов параллельно, а потом взять лучший результат), правда с гораздо большим количеством асинхронных примитивов чем просто par_iter. И поэтому, если попробовать воспользоваться этим кодом as-is, то ничего не получится, потому что сложно передавать лямбды, у которых не 'static lifetime, в треды.

Но я решил не унывать, допилил код до работающего состояния и решил померять, насколько лучше он работает на реальной задаче из Reply Challenge, которую я решал неделю назад. Тест был такой: 15 раз запускаю отжиг на минуту, каждый следующий запуск начинает с лучшего решения, найденного на предыдущем запуске. Смешной факт состоит в том, что первые несколько минут однопоточный вариант работает сильно лучше многопоточного. Отгадайте почему! К концу 15 минут они примерно сравниваются по итоговому результату.

Еще я написал вариант, в котором все треды поддерживают копию текущего состояния, а все изменения кладутся в общую очередь. Тред может добавить новое изменение, только если оно применяется к самому последнему состоянию (иначе изменение отбрасывается, тред применяет новые изменения, и начинает искать заново). Естественно я спросил GPT-4 как лучше написать такую очередь, он мне опять предложили самый банальный вариант с Arc<Mutex<...>>, который работает чуть лучше исходной однопоточной версии.

Потом я переписал код на использование RwLock и наконец-то результат стал сильно лучше чем однопоточная версия. Интересно, что если использовать 20 тредов, то результат получается сильно хуже, чем если 10.

В общем пока можно быть спокойным, до AGI еще далеко.

Memory profiler на коленке

Недавно я хотел понять, почему программа на Rust использует много памяти. Для этого существует много разных тулов. Вначале я попробовал heaptrack. С помощью LD_PRELOAD он подменяет функции malloc/free/… на свои, которые подсчитывают статистику, и вызывают обычные обработчики.

Проблема была в том, что судя по резузльтату heaptrack, программа использовала 500 мегабайт, а на самом деле VmRss у нее был больше 3 гигабайт. Почему так бывает? malloc внутри себя обычно просит большие куски памяти у операционной системы через mmap, а потом разбивает ее на более маленькие части.

Чтобы лучше понять, откуда получается такой большой VmRss, я решил воcпользоваться небольшой утилитой mevi, которая как раз отслеживает все системные вызовы типа mmap. Кстати, у автора этой утилиты очень хороший блог про Rust!

Но судя по результату ее работы, моя программа вообще работает почти идеально и использует только 200 мб! Чтобы проверить, что я не совсем схожу с ума, и память действительно используется, я посмотрел на вывод pmap <pid> и увидел там много блоков размером около 64 мб, которые почему-то не отображаются в mevi.

Наконец-то мы дошли до момента поста, где вы узнаете про самый лучший memory profiler:

strace -o ~/strace.out -f -e trace=mremap,mmap,munmap,brk -k <command>

Такая команда отслеживает все вызовы mmap, которые делает <command>, и сохраняет для них стектрейсы. strace также показывает конкретные адреса памяти, которые были выделены, так что, например, можно понять, откуда взялись те самые блоки по 64мб из вывода pmap. Оказывается, что стандартный аллокатор вызывает mmap с PROT_NONE, и отдельно делает mprotect на части этой памяти, поэтому mevi не замечает такие куски памяти.

Кстати, если вы пофиксили проблему и хотите построить график, который показывает количество используемой памяти от времени, то вот вам лучший тул для этого:

while true; do cat /proc/<pid>/status | grep VmRSS | awk '{ print $2 }' ; sleep 1; done

AndThen

Хотел в честь 300 подписчиков на этом канале запустить прикольную штуку, но кодить я ее начал, когда подписчиков было уже 298, так что естественно я не успел. Поэтому расскажу пока историю одного бага, который я очень долго пытался поймать.

У нас есть сервис на Rust, который слушает какой-то порт, принимает там соединения, проверяет TLS и дальше как-то общается с каждым клиентом. Код, который это делает, выглядит примерно вот так:

let incoming = tokio_stream::wrappers::TcpListenerStream::new(
  tokio::net::TcpListener::bind(address).await?
);
let incoming = incoming.and_then(|stream| tls_acceptor.accept(stream));
…
let server = hyper::Server::builder(incoming)...;

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

Как такое дебажить не очень понятно. Можно добавлять какие-то логи, запускать много инстансов системы, а потом ждать несколько часов.

Кстати, вы умеете просто добавлять логи внутрь внешних библиотек? Я научился это делать, но может быть можно проще.
• Вначале запускаем cargo tree и смотрим какой версии библиотека используется. Скорее всего это будет не та же версия, которая написана в Cargo.toml из-за других зависимостей.
• Скачиваем локально исходный код библиотеки, делаем git checkout на нужную версию, добавляем логи.
• Дописываем библиотеку в Cargo.toml через [patch.crates-io].

После недели дебага я таки понял, в чем была проблема. incoming.and_then гарантирует, что порядок, в котором подключились пользователи, и порядок, в котором они придут в hyper::Server::builder, будет один и тот же. А это значит, что если tls_acceptor.accept для какого-то соединения будет работать долго, то все следующие соединения будут его ждать. Например, если пользователь разорвет соединение во время TLS-handshake, то tls_acceptor.accept никогда не завершится, и новые соединения не будут приниматься.

AI Contest (https://aicontest.dev): напиши бота и выиграй 100 TON (≈189$)

Когда-то давно в Польше проходило соревнование Deadline24. Формат примерно такой. Команды приезжают в какое-то конкретное место и в течении 24 часов пишут ботов для нескольких игр. В каждой игре бот должен подключиться по tcp к серверу, получить информацию про состояние игры, отправить какие-то команды в ответ, дождаться следующего хода, опять отправить команды и так далее. Игры состоят из раундов по несколько минут каждый. В зависимости от того, какое место игрок занимает в раунде, его команде дают сколько-то очков. Причем чем ближе к концу соревнования, тем дороже стоят игры.

Как именно игрок принимает решение, какие команды отправлять — личное дело самого игрока. Например, можно написать визуализатор для игры и играть вручную. Правда тогда придется 24 часа не спать. Или можно сделать какой-то гибридный вариант.

К сожалению, после 2018 года Deadline24 больше не проводили, и мне стало интересно, насколько сложно провести соревнование похожего формата.

Для эксперимента я выбрал игру с очень простыми правилами. Игрок управляет кругом, который перемещается по полю и должен собрать как можно больше других кругов. Единственное усложнение состоит в том, что нельзя моментально менять скорость, можно только менять ускорение.

Уже сейчас можно в реальном времени посмотреть на текущую игру на https://aicontest.dev и написать своего бота (подробные правила написаны тут).

Чтобы стимулировать людей к написанию ботов, я решил раздать символические призы. Топ-3 человека из вкладки "Highest Scores" (самый большой скор, набранный за одну игру) на момент примерно через 2 недели получат 100, 50 и 25 TON соответственно.

AI Contest: результаты

Сегодня закончилась "официальная" часть https://aicontest.dev, поздравляю топ-3 участников:

1. al13n — 175 баллов
2. progiv-rust-main — 160 баллов
3. eulersche_Zahl — 150 баллов

Учитывая, что стандартный бот набирал примерно 60 баллов, это очень крутые результаты!

Пожалуйста, напишите мне в личку свои логин/пароль и кошелек, на который отправлять выигранные TONы.

Сервер с игрой пока что будет продолжать работать, так что если кто-то очень хотел поучаствовать, но не успел, то у вас все еще есть шанс :)

Кстати, зацените классную визуализацию решения: https://www.tgoop.com/bminaiev_blog/39?comment=316

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

Спасибо всем, кто поучаствовал!

Минимум в массиве

Если долго не писать посты, то так можно совсем забить на канал, так что напишу хотя бы о чем-нибудь простом. Как найти минимальный элемент в массиве (желательно побыстрее)?

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

Пусть есть массив из 10^6 элементов типа i32 и мы хотим найти минимум. Чтобы было удобно сравнивать алгоритмы, будем считать сколько раз за 1с можно запустить алгоритм. Например, если считать, что компьютер исполняет 10^9 операций min в секунду, то наш алгоритм выполнится примерно 10^3 раз.

Начнем с самой простой реализации:

fn find_min_iter(a: &[i32]) -> i32 {
    *a.iter().min().unwrap()
}

Один запуск такого алгоритма занимает 481µs, а значит за секунду его можно запустить 2079 раз.

Перепишем менее идиоматично:

fn find_min_for_loop(a: &[i32]) -> i32 {
    let mut min = a[0];
    for &x in a.iter() {
        if x < min {
            min = x;
        }
    }
    min
}

Такой код успевает сработать 7945 раз (почти в 4 раза быстрее!).

Аналогичный код на C (сильно зависит от компилятора) успевает сработать 5898 раз (кошмар, медленнее чем Rust!).

Если вы еще не читали статью Argmin with SIMD на algorithmica.org, то очень рекомендую! Там приведены различные реализации с SIMD интринсиками, которые работают еще быстрее. У меня локально такой алгоритм успевает сработать 14483 за секунду!

С одной стороны это в два раза быстрее чем на Rust, с другой стороны, если нам нужно будет найти минимум в [i64] вместо [i32], то придется все переписывать. Почему вообще компилятор на справляется сам написать такой же эффективный код?

Разгадка очень проста — в нашем алгоритме используются avx2 инструкции, которые по умолчанию не доступны компилятору. И это именно тот самый случай, когда добавление #pragma GCC target("avx2") в ваш код на самом деле ускорит его. И обычный цикл for станет таким же быстрым, как и написанный вручную код с simd инструкциями.

Конструкцию, аналогичную pragma, но для Rust, можно написать так:

fn find_min_iter_avx2(a: &[i32]) -> i32 {
    #[target_feature(enable = "avx2")]
    unsafe fn run(a: &[i32]) -> i32 {
        let mut min = a[0];
        for &x in a.iter() {
            if x < min {
                min = x;
            }
        }
        min
    }
    unsafe { run(a) }
}

И работает она так же быстро, как и версия на С (больше чем в 7 раз быстрее самой первой реализации)!

Так что если вам когда-нибудь надо будет 10^5 раз найти минимум в массиве длиной 10^5, то знайте, что это можно сделать быстрее чем за секунду.

Мне тут в комментариях рассказали, что вместо *a.iter().min().unwrap() надо писать a.iter().copied().min().unwrap(). И эта версия даже без модных avx инструкций работает так же быстро как и лучшие версии алгоритма из предыдущего поста!

И это в принципе логично! Сравнивать числа гораздо проще чем числа по ссылкам.

Деревья отрезков

Когда я учился писать деревья отрезков (ДО) в университете, у меня было примерно такое понимание. В каждой вершине дерева хранится какая-то информация. Когда заходим в вершину, нужно пропушить эту информацию детям. Когда выходим из вершины — мержим информацию из детей.

Для некоторых задач ДО можно писать без проталкивания отложенных операций. Например, если нужно прибавлять на отрезке и считать сумму на отрезке, то в каждой вершине можно запомнить, сколько нужно прибавить к ответу для всех запросов, которые включают эту вершину (e-maxx).

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

Как же улучшилась моя жизнь с приходом Rust!

В какой-то момент я решил написать ДО так, чтобы его можно было легко переиспользовать, и решать задачи на ДО стало гораздо приятнее!

Во-первых, "информацию в вершине" нужно разделить на два отдельных типа:
* Node. То, что мы хотим получить в ответе на get запрос (сумму чисел/минимум/...) и то, что нужно хранить для пересчета этой информации (количество чисел на отрезке, ...).
* Update. То, как мы хотим уметь обновлять значения.

Во-вторых, нужно понять какие условия есть на типы Node и Update:
* Нужно уметь пересчитывать информацию в Node через ее детей. fn join_nodes(left: &Node, right: &Node) -> Node.
* Нужно уметь применять Update к Node. fn apply_update(node: &mut Node, update: &Update).
* Нужно уметь выражать применение двух последовательных Update как один Update. fn join_updates(first: &Update, second: &Update) -> Update.

В-третьих, нужно перестать думать о ДО как о дереве с какой-то конкретной структурой. Не нужно думать о том, как внутри устроены отложенные операции. Не нужно думать о рекурсии. Важен только факт, что можно заимплементить три конкретные функции для нужных типов Node и Update.

А как вы пишете ДО?