Боря программирует

Contest platform Будем считать, что после вчерашнего поста все уже умеют решать задачу коммивояжера быстрее чем за n!, а значит вы можете помочь мне протестировать тестирующую систему! Мне очень нравился формат задач на Google HashCode (никак не связано с тем фактом, что мы его два раза выиграли :). Там давали какую-то задачу, у которой нет точного решения, и тесты, которые нужно решить. Тесты давались в открытом виде, т.е. их можно скачать, посмотреть на них, как-то повизуализировать, найти какие-то закономерности и как-то сгенерировать для них ответы. Причем нет почти никаких ограничений на то, как именно ответы должны быть получены. Можно хоть в Excel решать! К сожалению, Google HashCode больше не проводится :( Есть и другие соревнования в похожем формате (например, последние пару лет ICFPC), но проводятся они довольно редко, а еще реже там дают интересные задачи. Проблема с проведением такого соревнования в том, что нужно не только придумать интересную задачу, но еще и написать тестирующую систему, которая будет проверять решения участников, и интерфейс, через который участники смогут с ней общаться. Поэтому я решил написать свою платформу, на которой можно было бы проводить такие соревнования. Уже даже есть сайт, на котором можно попробовать решить тестовую задачу: https://bminaiev.github.io/contest-platform/ Если у вас есть свободное время, то я буду рад, если вы зарегистрируетесь, попробуете попользоваться системой и расскажите ваши впечатления (чего не хватает? что можно улучшить? какие есть баги?). P. S. задача, конечно, тестовая, но написать для нее нормальное решение тоже может быть интересно!

Гамильтонов цикл. Вчера читал статью на викиконспектах итмо про нахождение гамильтонова цикла наименьшей стоимости. В статье приведен псевдокод, а вот мой вольный перевод на С++:

double findCheapest(int i, int mask) {
  if (d[i][mask] != inf) return d[i][mask];

  for (int j = 0; j < N; j++)
    if ((mask & (1 << j)) != 0)
      d[i][mask] =
          std::min(d[i][mask], findCheapest(j, mask - (1 << j)) + w[i][j]);

  return d[i][mask];
}

double start() {
  for (int i = 0; i < N; i++)
    for (int mask = 0; mask < (1 << N); mask++) d[i][mask] = inf;
  d[0][0] = 0;
  return findCheapest(0, (1 << N) - 1);
}

Отгадайте за сколько он работает? Правильно, за O(n!). Например, если в графе вообще нет гамильтонова пути, то все d[i][mask] будет равны inf и каждый раз будут вычисляться заново. А теперь давайте представим, что между всеми вершинами в графе есть ребра. За сколько будет работать теперь? Неправильно, все еще за O(n!). Отгадайте почему. Если вы смотрите на этот код уже 5 минут, и не верите мне, то попробуйте запустить его локально: https://pastebin.com/ZhzYqRmx

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

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

Минимум в массиве Если долго не писать посты, то так можно совсем забить на канал, так что напишу хотя бы о чем-нибудь простом. Как найти минимальный элемент в массиве (желательно побыстрее)? Сразу оговорюсь, что результаты сильно зависят от того, в каком окружении вы запускаете код, так что воспроизводимость результатов не гарантирую, а все тесты проводились локально на ноутбуке. Пусть есть массив из 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, то знайте, что это можно сделать быстрее чем за секунду.

AI Contest: результаты Сегодня закончилась "официальная" часть https://aicontest.dev, поздравляю топ-3 участников: 1. al13n — 175 баллов 2. progiv-rust-main — 160 баллов 3. eulersche_Zahl — 150 баллов Учитывая, что стандартный бот набирал примерно 60 баллов, это очень крутые результаты! Пожалуйста, напишите мне в личку свои логин/пароль и кошелек, на который отправлять выигранные TONы. Сервер с игрой пока что будет продолжать работать, так что если кто-то очень хотел поучаствовать, но не успел, то у вас все еще есть шанс :) Кстати, зацените классную визуализацию решения: https://t.me/bminaiev_blog/39?comment=316 Если у вас есть какие-то идеи как можно было бы улучшить это соревнование или идеи других подобных игр — обязательно расскажите в комментариях. Спасибо всем, кто поучаствовал!

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 соответственно.

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 никогда не завершится, и новые соединения не будут приниматься.

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

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 еще далеко.