Zadrot & FrostByte
Эй, FrostByte, тут копался с алгоритмом, который оптимизирует распределение ресурсов при ограничениях – кажется, задачка, которую нам обоим под силу. Что думаешь?
Звучит как типичная задача оптимизации, знаешь, такие ограничения могут превратить даже самый элегантный алгоритм в настоящий клубок. Какие у тебя ограничения? Может, вместе сможем найти какую-нибудь скрытую закономерность.
Я сейчас смотрю на три жестких ограничения: память ограничена 256 мегабайт, задержка должна быть менее 50 миллисекунд на каждый запрос, и сеть поддерживает только UDP, поэтому мне придётся самому реализовывать надёжность. Если мы сможем заменить фрагменты с большой пропускной способностью на сжатые, предварительно рассчитанные части, мы, возможно, нарушим эту симметрию. Ты сможешь найти, где можно немного оптимизировать?
Запомни, эти ограничения памяти – как ходить по канату: держи в кэше только самые нужные заранее вычисленные фрагменты, а остальное пересчитывай по ходу дела. Чтобы снизить задержку, попробуй упорядочить UDP-пакеты и добавь простую схему подтверждения – это сэкономит немного времени, но следи за дополнительными затратами на передачу туда-обратно. И сжимай большие фрагменты с помощью кодека без потерь, который быстро распаковывается; даже один дополнительный цикл работы процессора на пакет – лучше, чем внезапная задержка в 30 миллисекунд. И проверь контрольную сумму – для UDP обычно хватает 16-битной CRC, это экономит циклы по сравнению с полным SHA. Вот где можно немного оптимизировать, да?
Вот неплохой план. 256 мегабайт – это на грани, поэтому используй жадную, но детерминированную политику вытеснения кэша – возможно, LRU для каждого блока. 50 миллисекунд задержки – жестко, но легкое подтверждение на каждый пакет будет работать, а лучше "подгрузи" его к следующему пакету данных. Кодек без потерь? Snappy или ZSTD с уровнем 1 дадут хороший компромисс. 16-битный CRC будет достаточно для большинства UDP; просто перепроверь этот случай, когда поток данных превращается в ошибку, как при проблемах с DNS. Я подкорректирую конвейер, чтобы попытаться еще немного ускорить работу – на 3-5 миллисекунд. Что думаешь?
Понятно, это именно то, что нужно — придерживайся строгой политики выгрузки, чтобы всегда знать, что в кэше. Хитрость с перехватыванием ACK – отличная идея; только убедись, что размер пакета все еще помещается в один UDP-датаграмму. Snappy или ZSTD‑1 обеспечат дешевую декомпрессию; если возникнет ошибка вроде DNS, можешь сначала использовать простой контроль суммы. Снижение на 3–5 миллисекунд вполне реально, если ты сможешь объединять больше пакетов перед тем, как доберешься до порога в 50 миллисекунд. Напиши, как выглядят результаты после изменений.
Вот данные: средняя задержка – 44 миллисекунды, использование памяти – 240 мегабайт, процент попаданий в кэш – 93. Один случай всё же доходит до 48 миллисекунд, но в остальном доработка работает. Что-нибудь ещё нужно проверить?
Выглядит неплохо—среднее время 44 миллисекунды, и 240 мегабайт в пределах нормы. Этот скачок в 48 миллисекунд настораживает; следи за всплесками трафика, которые могут переполнить UDP-буфер. И обрати внимание на фрагментацию памяти, если выделяешь много мелких блоков; небольшая доработка распределителя поможет поддерживать этот объем в 240 мегабайт стабильным. Загрузка процессора скачет при пересчете из-за промахов в кэше—профилируй этот участок, чтобы не превысить лимит в 50 миллисекунд, когда частота промахов растет. В остальном, ты закрыл большинство очевидных проблем.
Отличная работа с бюджетом, но эти 48 миллисекунд всё равно ощутимы; если выпустить партию из тысячи пакетов, UDP просто рухнет. Может, зафиксировать размер буфера на максимальный размер датаграммы и отбрасывать всё, что превышает его. По поводу фрагментации – используй выделение памяти из slab для блоков по 8 килобайт; так и будет порядок на куче. А насчёт пересчётов – добавь быстрый путь, который предварительно вычисляет наиболее часто встречающиеся сегменты в отдельном потоке, чтобы промахи кэша попадали в холодный буфер, а не нагружали процессор. Следи за кривой промахов; если она пойдёт вверх – снова будем у 50 миллисекунд. Молодец, нужно ещё немного подкрутить.
Отлично, изменения удачные. Ограничение буфера одним датаграммой решит проблему переполнения, а выделение памяти блоками по 8 килобайт избавит от фрагментации. Запуск фонового потока предварительных вычислений – отличный ход, чтобы держать часто используемые фрагменты в памяти. Продолжай следить за кривой промахов; если она начнет расти, придется увеличить размер кэша или перенастроить логику предварительных вычислений. Кажется, мы почти у цели.