Стендап Сьогодні 📢 Канал в Telegram @stendap_sogodni

🤖🚫 AI-free content. This post is 100% written by a human, as is everything on my blog. Enjoy!

07.03.2024

1 Billion Row Challenge... на Ruby?

До моєї уваги потрапив 1 Billion Row Challenge - нещодавнє мінізмагання з програмування, де потрібно якнайшвидше агрегувати мільярд рядків з інформацією. Хоча офіційно розвʼязок повинен бути на Java, проте вже зʼявилися й спроби на Go, Rust і так далі. Але на Ruby нічого немає. Мені стало цікаво — чому так та що з цього може вийти?

Почав з того, щоб зрозуміти межі можливого. Взяв версію на Go з цієї статті (бо Go мені більш зрозуміло ніж Java.) На моїй машині найшвидша версія без паралелізму займає близько 30 секунд.

Потім зробив тривіальну версію на Ruby (бо над розвʼязком задачі взагалі думати не треба — складність в оптимізації.) Вийшло 586 секунд. А тривіальний розвʼязок на Go - 105 секунд. Цифри хоч би однакового порядку, тобто можна й погратись. Можна обчислити, що гарним результатом для оптимізованого розвʼязку на Ruby буде десь 160 секунд.

Тепер — абсолютний мінімум. Просто підрахувати рядки в цьому файлі на Ruby займає 80 секунд. Я пішов ще далі: просто порахувати до мільярда - 23 секунди.

Моєю першою ідеєю було — замість ітерування рядками зробити такий собі побайтовий процесор зі скінченним автоматом. Мене чекала несподіванка — читання файлу байтами, а не рядками триває набагато довше - 350 секунд! (Може, ця ідея і вкотить на Go, потім спробую.)

Інтуїція, що читання байтами “простіше” та тому швидше, не спрацювала ось чому: в Ruby читання є функцією на С, причому досить складною, з купою перевірок. Робити їх на кожний байт дуже дорого.

Щоб поки зупинитись, зазначу: будь-який ефективний розвʼязок на Ruby буде використовувати більш високорівневі абстракції, де логіки менше в Ruby та більше в C. Можливо, StringScanner.