The One Billion Row Challenge

[malor]

https://www.morling.dev/blog/one-billion-row-challenge/
https://github.com/gunnarmorling/1brc
https://nnethercote.github.io/perf-book/

• Умови змагання:
  • "великий" текстовий файл (1 мільярд рядків; ~13 GiB) із значеннями температури повітря по якійсь метереологічній станції
  • треба якомога швидше порахувати мінімальну/cередню/максимальну температуру по кожній із станцій
  • відсортувати по назві станції і надрукувати на stdout
  • тестували на Hetzner AX161 dedicated server (32 core AMD EPYC™ 7502P (Zen2), 128 GB RAM)
• Реалізація пана Романа (https://github.com/malor/one-brc; Ryzen 7700 / 32 GB RAM)
  • Наївна реалізація на Rust (~68s)
    • один потік
    • BufReader
    • ітератор по рядках lines()
  • Профілювання
    • perf
    • FlameGraph
    • frame pointer проти DWARF для отримання стек трейсів (https://www.brendangregg.com/blog/2024-03-17/the-return-of-the-frame-pointers.html)
    • особливості Rust (стандартна бібліотека зібрана без frame pointer і DWARF символів)
  • Аллокації пам'яті
    • read_line() замість lines(): ~54.8s
    • update-or-insert замість entry(): ~42.4s
  • Флаги компіляції (~37.7s)
    • оптимізації (-O3, -C target-cpu=native)
    • LTO
    • PGO
  • Багатопоточність (~4.3s)
    • що параллелити (парсинг рядків, парсинг чисел, рядки між потоками, шматки файлу між потоками)
    • як розподіляти роботу між потоками (гранулярність даних)
  • mmap() і кеш файлової системи (~4.1s)
    • ідея: не копіювати дані із ядра в юзерспейс і далі із буфера BufReader в свій об'єкт String
  • Реалізації хеш функцій (~3.3s)
    • https://nnethercote.github.io/perf-book/hashing.html
  • memchr + unsafe (~2.3s)
• Оптимізації із інших реалізацій
  • Парсинг чисел
  • Хеш-функції
  • https://github.com/dolthub/swiss