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

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

08.03.2024

Прискорення 1BRC на Ruby

Ось мій наївний розвʼязок, давайте з ним щось зробимо. (Тільки вивід результатів тут поки примітивний, але на швидкодію він не впливає.)

1. З таким кодом пошук міста відбувається щоразу для кожного поля. Натомість можна один раз знаходити дані для міста, та решту операцій робити вже над ними. Прискорення 14%

2. Ані хеш, ані обʼєкт — не найшвидша структура даних в Ruby. Найшвидшою буде масив. Хеш з містами доведеться залишити, а от дані для кожного міста можна організувати в масив з 4 елементів. Прискорення 12% (А ще — так само швидко буде зі Struct, бо Struct всередині має масив. В реальному коді я б саме Struct і вжив, а в цьому вона заважала профайлеру, тож зробив з масивом.)

3. Операція split в топі наших витрат. Вона буде швидше, якщо вказати кількість сегментів, які ми хочемо отримати. В цьому разі .split(';', 2) прискорює на неймовірні 10%.

4. Замість явної перевірки на наявність даних в хеші можна створити хеш зі даними за замовчуванням. Дрібниці, але 1% прискорення це дає.

5. Виявилося, що якщо потрібно взяти з масиву всі 4 значення, то швидше це робити з spread operator ніж по одному. Отримуємо ще 1% прискорення.

6. Тепер, беремося за читання з файлу. По-перше, читання в UTF-8 (тобто за замовчуванням) буде уповільнено необхідною перевіркою на багатобайтові символи. Щоб знайти крапки з комою та нові рядки, нам це не потрібно. Перехід до двійкового кодування (або ж ASCII8) дає дуже приємні 7%.

7. Нарешті, взагалі можна позбавитись розбиття рядка, якщо відразу читати окремо назву міста та температуру. Для того в метод readline можна передати символ “кінця рядка”, який цілком може бути крапкою з комою. Є тільки один нюанс: насправді readline повертає рядок з кінцевим символом. Поки що нам це не заважало тому, що операція to_f відкидає всі зайві символи. А що робити з зайвою крапкою з комою в кінці назви? Обрізати її вийшло надто дорого; тому я залишаю назви з зайвим символом, а обрізаю вже під час виводу. Такий підхід дає ще 9% прискорення.

8. Що не дало ніяких результатів: вкладення перевірки на max в перевірку на min; заміна split на rindex; використання цілих чисел замість дробових. Взагалі, всякі нестандартні операції не окупають додаткових витрат — наприклад, на ручний розбір температури в ціле число. До того ж арифметика на дробових та цілих числах в Ruby практично однакова за швидкістю.

9. Також нічого не дала явна буферизація файлу: ані з експериментальним класом IO::Buffer, ані з читанням великого (128Мб!) рядка в памʼять та подальшою обробкою через StringIO. Роблю висновок, що нормальне читання з файлу вже й так достатньо буферизоване.

10. Остаточне покращення: з 10 хвилин до 5 з половиною. Непогано, хоча все ще в 3 рази повільніше ніж наївний розвʼязок на Go. Це повинно продемонструвати, що “Ruby повільна мова” та такі задачі, як 1BRC, краще відразу робити якоюсь іншою. Проте, з іншого боку, навіть таку щільну задачу можна простими способами прискорити у 2 рази — чого на практиці може бути достатньо.