Grand Prix of EPS. A.

https://contest.ucup.ac/contest/4207/problem/20715

Не будем вдаваться в детали задачи, но решение (авторское?), которое я решил написать, работает за 8*n*k*4+q*k, при том что n=10^5, q=3*10^5, k=800, т.е. делает примерно 3 миллиарда операций (и выделяет примерно столько же памяти). TL=4s и если это реально авторское, то мое уважение.

Так вот, написал я код, отправил, получил TimeLimit. https://pastebin.com/2VqTiGtU. Я специально старался не особо оптимизировать на этом этапе (например, выделял много памяти), зато хотелось написать без багов.

Локально код работал где-то 7с, что в целом давало надежду. Я в решении выделял трехмерный массив и часто делал операции в цикле типа:

for j in 0..k {
  dp[i + 1][1][j + 1] = dp[i + 1][1][j + 1].max(dp[i][0][j] + cur_val);
}

В идеальном мире компилятор такое должен очень хорошо оптимизировать со всякими avx, но ему тут явно не до этого. Например, он скорее всего вообще не понимает, что dp[i + 1] и dp[i] это разные участки памяти, поэтому можно все векторизовать. Еще, скорее всего он каждый раз делает "переход по ссылке", чтобы понять где находится dp[i + 1]. Поэтому я решил вынести dp[i + 1] в отдельный новый двухмерный массив, заполнить его, а потом скопировать в старых трехмерный. Локально это ускорило на пару секунд, но я все еще получил TimeLimit. https://pastebin.com/Rm4anpsa

В этой задаче мы в каком-то смысле делаем первый уровень вложенности алгоритма "разделяй и властвуй". Выбираем опорный элемент, считаем какую-то динамику слева, какую-то справа, а потом для каждого запроса, который пересекает центр, объединяем значения двух динамик. Причем центр выбирается так, что левая часть это 15% позиций, а правая 85%. Можно не выделять трехмерный массив для правой части, а хранить только два последних слоя, и сразу же отвечать на все запросы, которые заканчиваются в текущем слое. https://pastebin.com/tVF8cdDn. И тут я наконец-то получил WA вместо TL. Правда, работала программа на этом тесте 3897ms, так что даже если исправить WA, то не факт, что решение работает достаточно быстро.

Тут я понял, что я не до конца последовал своему изначальному плану "писать без оптимизаций, но без багов", потому что как раз таки добавил какую-то багу из-за неправильной оптимизации. После ее исправления, я получил AC за 3571ms! 🎉 https://pastebin.com/t31jUaTU

Мне стало интересно, насколько сильнее можно соптимизировать код. Я запустил свой код, рядом запустил perf top -p <pid>, было видно, что много времени тратится в циклах типа:

for left_cnt in 0..=k {
  best = best.max(dp_left[left_len][0][left_cnt] + dp[0][k - left_cnt]);
}

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

fn fast_conv(a: &[i32], b: &[i32]) -> i32 {
  let mut res = i32::MIN;
  let n = a.len();
  assert_eq!(n, b.len());
  for i in 0..n {
    res = res.max(a[i] + b[n - 1 - i]);
  }
  res
}

Также соптизировал какие-то простые циклы, которые просто копируют данные через .copy_from_slice(...). https://pastebin.com/8RPHsZ3S. 1685ms.

Если вы дочитали до этого места, то научите меня как эффективнее всего оптимизировать дальше. Как понять, какой код на самом деле тормозит? Стандартные perf record / perf report показывают что-то вроде "100% cpu тратится в функции solve, 14% вот в этих местах, а еще 86% непонятно где". Как понять где конкретно тратится время и на что?

В общем, мне стало лень оптимизировать дальше самому, и я попросил codex научить меня это делать и подсказать, что и где еще не эффективно. По дороге я еще ради прикола завайбкодил что-то вроде локального godbolt, но так и не понял, почему он чем-то лучше чем perf report.

В итоге сделал какие-то такие оптимизации:
- Заалоцировать память один раз вместо выделения в цикле (не особо помогло?)
- Использовать 2x меньше памяти (помогло). Видимо стало лучше в какие-то кеши помогать.
- Обернуть какие-то функции в #[target_feature(enable = "avx2")]. Тоже помогло на 100-200мс.
- Убрать ненужные copy_from_slice, где можно сразу посчитать новое правильное значение динамики.
- Написать отдельную функцию, которая делает ndp[j] = dp0[j].max(dp1[j] + cur_val) и вызвать ее с правильными slice. Помогло довольно сильно!
- Функция update_pref_max, которая по сути делала a[i] = a[i].max(a[i - 1]), всегда вызывалась на массиве, который вначале возрастал, а потом убывал. Поэтому можно было найти позицию максимума и сделать a[max_pos..].fill(max_value).
- Когда сохранял запросы, которые заканчиваются в конкретной позиции, вместо того, чтобы сохранить только индекс, сохранил весь запрос, чтобы не нужно было каждый раз доставать информацию из вектора. (еще 100мс!).
- Убрать update_pref_max вообще и перейти от динамики "взял k отрезков" к "взял не более k отрезков".
- Сохранять запросы не в Vec<Vec<...>>, а просто в отсортированный Vec<...> (на сервере столько же работает, локально быстрее).

Некоторые оптимизации помогали локально, но не особо помогали на сервере.

В итоге последняя версия кода выглядит вот так https://pastebin.com/GE2YyqrA, и получает AC за 367ms. Так что можно считать, что авторы выставили TimeLimit с запасом :)