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.group-telegram.com/bminaiev_blog.com/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.

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

Гамильтонов цикл.

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

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);
}

Отгадайте за сколько он работает?

Правильно, за θ(n!). Например, если в графе вообще нет гамильтонова цикла, то все d[i][mask] будет равны inf и каждый раз будут вычисляться заново. А теперь давайте представим, что между всеми вершинами в графе есть ребра. За сколько будет работать теперь?

Неправильно, все еще за θ(n!). Отгадайте почему.

Если вы смотрите на этот код уже 5 минут, и не верите мне, то попробуйте запустить его локально: https://pastebin.com/ZhzYqRmx

Contest platform

Будем считать, что после вчерашнего поста все уже умеют решать задачу коммивояжера быстрее чем за n!, а значит вы можете помочь мне протестировать тестирующую систему!

Мне очень нравился формат задач на Google HashCode (никак не связано с тем фактом, что мы его два раза выиграли :). Там давали какую-то задачу, у которой нет точного решения, и тесты, которые нужно решить. Тесты давались в открытом виде, т.е. их можно скачать, посмотреть на них, как-то повизуализировать, найти какие-то закономерности и как-то сгенерировать для них ответы. Причем нет почти никаких ограничений на то, как именно ответы должны быть получены. Можно хоть в Excel решать!

К сожалению, Google HashCode больше не проводится :(

Есть и другие соревнования в похожем формате (например, последние пару лет ICFPC), но проводятся они довольно редко, а еще реже там дают интересные задачи.

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

Поэтому я решил написать свою платформу, на которой можно было бы проводить такие соревнования. Уже даже есть сайт, на котором можно попробовать решить тестовую задачу: https://bminaiev.github.io/contest-platform/

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

P. S. задача, конечно, тестовая, но написать для нее нормальное решение тоже может быть интересно!

slice.reverse

Вчера решал задачу на КФ, где нужно было уметь делать следующее. Дана строка длиной 2*10^5 символов, к ней нужно применить 2*10^5 операций. Каждая операция — развернуть какой-то подотрезок этой строки. TL=1с.

Это довольно известная задача, которую можно решать, например, с помощью декартового дерева за O(log n) на запрос.

После контеста в комментариях рассказали прикольный трюк, как можно получить АС с решением, которое делает O(n) операций на запрос. Вместо того чтобы просто хранить строку s, будем еще дополнительно хранить ее развернутую копию s_rev. Тогда, чтобы развернуть подстроку s[fr..to], можно просто скопировать готовую подстроку из s_rev:

fn reverse(&mut self, fr: usize, to: usize) {
let n = s.len();
let s = &mut self.s[fr..to];
let s_rev = &mut self.s_rev[n - to..n - fr];
s.swap_with_slice(s_rev);
}

Например, s='abcde'. Сохраним s_rev='edcba'. Как развернуть подстроку s[1..3]='bc'? Поменяем ее с s_rev[(5-3)..(5-1)]='cb'. Теперь s='acbde', а s_rev='edbca'.

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

Это решение получало АС за 889мс. Потом оказалось, что в задаче плохие тесты и на самом деле оно работает в 2 раза дольше, но все равно довольно быстро!

Самое смешное, что решение, которое просто вызывает .reverse на нужной подстроке (правда с указанием, что нужно использовать avx2) работает еще в два раза быстрее:

#[target_feature(enable = "avx2")]
unsafe fn reverse(s: &mut [u8]) {
s.reverse();
}

Running Transformers using SMPC

Почти год назад я написал пост про SMPC (Secure multi-party computation) — технологию, которая позволяет запускать вычисления на данных нескольких участников таким образом, что все узнают итоговый результат вычислений, но при этом ничего не могут понять про исходные данные других участников.

План был в том, чтобы написать три поста:
1. Смотрите, какая прикольная вещь, можно не раскрыть ни одного бита информации про свои данные, но все равно посчитать что-то интересное.
2. На самом деле делать такие вычисления довольно сложно, потому что это накладывает кучу ограничений.
3. Несмотря на то, что это сложно, можно все равно делать довольно сложные вещи с помощью SMPC — например, тренировать ML модели не раскрывая исходных данных.

Но второй пост я так и не написал, потому что сложно простыми словами доказывать, что что-то делать сложно :)

Зато теперь есть третий пост, где мы рассказываем как надо запускать трансформеры на SMPC, когда у вас нет if-ов, циклов, чисел с плавающей точкой и всего такого: https://www.pyte.ai/blog/making-transformers-based-ai-algorithms-secure-using-secure-multi-party-computation-smpc

Lazy Fenwick Tree

Чтобы канал не пустовал расскажу о простом трюке, который возможно не все знают. Допустим нам нужна структура данных, которая умеет поддерживать массив чисел a и обрабатывать две операции:
+ l r x. Ко всем элементам на отрезке l..r добавить число x.
? pos. Узнать значение элемента a[pos].

Это стандартная задача, которая решается деревом отрезков или деревом Фенвика. Обе структуры данных используют O(n) памяти, где n — размер массива a.

Что делать, если мы хотим обрабатывать такие же запросы, но для массива размером 10^9 элементов? Если все запросы известны заранее, то можно сжать координаты и свести задачу к предыдущей. А если нет, то можно написать Dynamic Segment Tree, в котором вершины дерева отрезков инициализируются в первый момент, когда к ним происходит обращение. Но в этом случае придется написать кода в несколько раз больше чем в обычном дереве Фенвика.

На самом деле можно все еще использовать дерево Фенвика, но хранить значения не в векторе, а в хеш таблице. Такая структура данных будет занимать O(Q * log(MAX_C)) памяти, где Q — количество запросов, а MAX_C — размер массива a. При этом код почти не отличается от обычного дерева Фенвика:

struct LazyFenwick {
    data: FxHashMap<i32, i32>,
    n: i32,
}

impl LazyFenwick {
    pub fn get_sum(&self, mut pos: i32) -> i32 {
        let mut res = 0;
        loop {
            res += self.data.get(&pos).copied().unwrap_or_default();
            pos = pos & (pos + 1);
            if pos == 0 {
                return res;
            }
            pos -= 1;
        }
    }

    pub fn add(&mut self, mut pos: i32, change: i32) {
        while pos < self.n {
            *self.data.entry(pos).or_default() += change;
            pos |= pos + 1;
        }
    }
}

Другой подход, который я подсмотрел в https://contest.ucup.ac/submission/229077, написать bottom-up дерево отрезков, которое тоже хранит значения в хеш-таблице:

ll N, Q;
unordered_map<ll, ll> seg;
void add(ll L, ll R, ll x) {
    L += N; R += N;
    for(; L < R; L >>= 1, R >>= 1) {
        if(L & 1) seg[L++] += x;
        if(R & 1) seg[--R] += x;
    }
}
ll get(ll i) {
    i += N;
    ll ans = 0;
    do ans += seg[i]; while(i >>= 1);
    return ans;
}

Telegram ML Competition. Решение.

Первая часть.

Я начал с того, что попытался собрать какой-то датасет из реальных кусков сообщений, которые люди оборачивают в кавычки. Скачивать реальные чаты через API мне показалось плохой идеей (явно же забанят довольно быстро), поэтому вместо чатов я скачивал каналы, которые можно смотреть по ссылке типа https://www.group-telegram.com/s/bminaiev_blog.com, которая не требует авторизации.

Я не нашел какого-то нормального списка из всех существующих каналов, поэтому я руками набрал какой-то небольшой список исходных каналов, а потом в них смотрел на репосты или ссылки на другие каналы и добавлял их в очередь для скачивания и так по кругу. В итоге у меня набралось порядка миллиона каналов, для каждого из которых я распарсил сколько-то последних сообщений, которые видны при открытии канала через www.group-telegram.com/s/.

Из этого датасета было довольно очевидно, что большинство вещей, которые обернуты в кавычки, это какой-то трэш, а не код. И если оценивать будут действительно количество правильно определенных текстов, то сделать решение, которое работает лучше, чем return OTHER; довольно сложно. Спойлер: всего два участника из ~100 написали что-то лучшее чем такой бейзлайн.

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

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

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

Чтобы побороться с первой проблемой я вначале думал просто добавить условие "если никакой язык программирования не набрал скор лучше какого-то барьера, то верни OTHER". Но из-за того, что трэша в датасете было много, работало это так себе. В итоге я нашел список ключевых слов для каждого языка программирования и сказал, что если в тексте нет ни одного ключевого слова, то он OTHER. Пришлось еще немного обработать эти списки и убрать из него слова типа "in", "or", "not". После этого результат получился уже относительно неплохой.

Рассказ получился длинный, но надеюсь кому-нибудь было интересно :)

Интересные Telegram каналы

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

Проблема с этой идеей была в том, что в Telegram довольно сложно находить интересные каналы. Я давно и с интересом читаю каждый пост в Experimental Chill. Но как найти каналы с похожем по качеству контентом — неясно.

Я быстро нашел много каналов про Machine Learning (они часто ссылаются друг на друга). Начиная от более попсовых типа Сиолошная или Время Валеры до более маленьких типа Wazowski Recommends или Information Retriever. Но в ML я разбираюсь довольно плохо, так что хотелось еще найти каналов про performance оптимизации, Rust или даже C++.

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

В предыдущем посте я научился получать длинный список около-программистских Telegram каналов и парсить посты из них. Я скачал где-то 100к постов и посчитал для них эмбеддинги через OpenAI API. Изначально я думал научиться считать эмбеддинги локально через какую-нибудь open source модель, он оказалось, что эмбеддинги у OpenAI API стоят супер дешево (суммарно потратил меньше 5$).

После этого я написал бота (@blog_finder_bot), который получает какой-то текст, считает от него эмбеддинг, и находит ближайшие посты по косинусному расстоянию. Ему можно отправить как просто запрос вида "Telegram contest про распознавание языков программирования", так и переслать какой-то существующий пост, чтобы он нашел похожие.

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

Пока тестировал бота, подписался на кучу новых каналов, посмотрим насколько будет интересно их читать. Выделить какие-то конкретные сложно, но пусть будет Записки cpu designer'а, Графики каждый день, C++95, MLE шатает Produnction и PLComp.

А на какие интересные каналы подписаны вы?

Вместо очередного технического поста, в качестве итогов 2023 года, тут будет фоточка со свадьбы! ❤️

Osijek Competitive Programming Camp, Winter 2024

С 17 по 25 февраля пройдет Osijek Competitive Programming Camp, Winter 2024. В один из дней будет контест, который подготовил я. Потратил кучу времени, но надеюсь, что задачи получились необычными и интересными (и сложными). Так что студентам рекомендую поучаствовать в этих сборах!

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

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