Хабр Курсы для бэкендеров
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 10
хардкорный разбор, у вас вышел!) зацепило использование CSR-раскладки для значений = перенос концепта из разреженных матриц в плоскую структуру чанка ради GC-локальности довольно красиво. демонстрация Alternate Lookup из .NET 9 фича долгожданная, и тут она встала как влитая для zero-allocation парсинга. я вот подзалип на моменте с MergeSorted и Task.WhenEach. Подскажите, а когда отложенные MoveNextAsync улетают в flight, вы не замеряли, как это влияет на ThreadPool в пике (при 200плюс чанках)? Рантайм успевает переиспользовать потоки, или когда шпиндель HDD начинает неизбежно тупить на случайном чтении, пул задач не пытается агрессивно раздуваться?
Прогон на 100ГБ показал что при 200 с мелочью чанках получалось 86, это то что видел Windows. Сколько там потоков для рантайма, а сколько для пула я не смотрел.
Реальные завершения чтения случаются нечасто из-за больших буферов, а backpressure по всей цепочке возвращает в пул потоки, которые отдыхают.
Ещё вопрос к кодеку промежуточных чанков. На случайных строках Brotli почти не выигрывает в объёме, но платит на декодировании в обеих фазах, а на HDD любой сэкономленный байт — это сэкономленное время шпинделя. Если после переписанного мержа диск уже загружен под 90%, следующий выигрыш логичнее искать не в параллелизме, а в отказе от Brotli на промежуточных чанках: Zstd уровня 1 жмёт быстрее и распаковывается кратно дешевле, и на плохо сжимаемых данных суммарное время обычно падает. На 77 ГБ промежуточных данных это может дать больше, чем ещё одна стадия параллелизма — если, конечно, замеры не показывают обратного, и тогда интересно, какой коэффициент вышел у Brotli на случайных строках.
В коде сейчас используется zstd - бэкпорт библиотеки которая войдет в .net11
Уровень сжатия - 9. Дает небольшой эффект случайных строках по объему и успевает выполняться параллельно с другими фазами не увеличивая длительность записи.
Я пробовал с zstd=1 и zstd=3 - эффекта на случайных строках нет. Небольшое снижение IO начинается на 6.
Пробовал также на zstd=16, но там уже сильно растет время сжатия, но объем не падает.
какой коэффициент вышел у Brotli на случайных строках.
К сожалению не сохранил результат.
Но это и не важно. Одна из целей - использование стандартных библиотек в .NET. Из внешнего только библиотека для тестирования и разбора параметров командной строки.
Про Zstd — это моя ошибка: Brotli я взял из описания прошлой версии, а в текущем коде уже Zstd, так что предложение снимается. Зато из ваших цифр вылезает кое-что поинтереснее. Сложим весь трафик: 100 ГБ чтения исходника, около 77 ГБ записи чанков, столько же на их чтение и 100 ГБ записи результата — это порядка 354 ГБ за 52 минуты, то есть примерно 113 МБ/с. Ровно порядок последовательной скорости обычного HDD. Похоже, пайплайн уже упёрся в шпиндель, и тогда дальнейшая борьба за параллелизм и уровни сжатия упрётся в то же число: выигрыш даст только сокращение байт, которые вообще двигаются, вплоть до отказа от промежуточной записи там, где чанк успевает сливаться на ходу. Замеряли ли вы потолок самого диска на этом файле обычным последовательным чтением? Если он тоже 110–120 МБ/с, то 52 минуты — это практически предел двухфазной схемы, и дальше смотреть имеет смысл только на схемы без промежуточной записи.
Спасибо за коммент от ИИ.
Я конечно замерял просто чтение и запись линейно, 113-117 мб\сек выдает без кэша ОС.
Суть решения и есть в том, чтобы:
- загрузить диск на 100% (сейчас выдает 97,6%)
- загрузить при этом CPU по максимуму
- использовать при этом минимум памяти - у меня получилось не более 10гб при чанках в 500 мб
Ну вот, стоит несколько лет не работать на когда-то любимом языке программирования, и уже столько новых интересных фичей.
А что касается самой задачи, то, так как у всех разные диски, процессоры, и их количество, кажется, важны такие вопросы:
Сколько всего строк на 100GB - миллиард по 100B или миллион по 100KB?
Какой у алгоритма Read/Write amplification - сколько байт всего нужно прочитать и записать за время его работы
Не очень понял, зачем нужен zstd, если строки случайные, и данные не сжимаются. Также, зачем дедупликация, если дубликатов совсем мало?
Сколько времени занимает генерация ключа для сравнения, и сколько раз он генерится - это может быть как самая медленная операция, так и самая быстрая, если в .NET есть happy path для ascii-строк
Сколько времени занимает само сравнение, и сколько таких сравнений? Есть ли смысл их ускорять (используя SIMD или radix sort)?
Тогда будет понятно, где узкое место, в зависимости от оборудования.
строки рандомные, от 1 до 1000 символов - в среднем 512 байт + число, точка и пробел. 536 байт получалось, на 100ГБ это порядка 200 млн строк
читает исходный файл 100ГБ + пишет чанки суммарным объемом 77ГБ + читает чанки одни раз и записывает 100ГБ результат. чуть меньше 2. В реальности зависит от того насколько строки случайные.
Строки случайные это worst case, а алгоритм хочется универсальный эффективный. zstd и другие алгоритмы сжатия внезапно помогают, потому что упорядоченные случайные строки дают повторы в узком окне, которые жмутся.
Генерация ключей сравнения - самая медленная операция, без распараллеливания увеличивает время работы на 7 минут. Генерируется ключ для каждого уникального текста на чанк при сплите. И один раз для каждого уникального текста во всех чанках. Для Ordinal сравнения есть happy path в коде, там вообще не генерируются ключи.
само сравнение массивов (sort key) в .net уже ускорено SIMD. Radix sort не получается быстрее, проверял бенчмарками.
Прогоны показывают что узкое место - диск. 130мб\сек - потолок. Но надо еще написать программу так, чтобы она успевало CPU-intensive операции делать пока диск работает, при этом не распухало по памяти.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сортировка слиянием, часть 2