Нещодавно дивився як в ClojureScript прискорити деякі операції в іммутабельних векторах. Вектор це типу масив, але усі операції на ньому створюють новий вектор і під капотом він імплементований як дерево з 32 нодами в кожній гілці. Отут можна більш детально почитати про імплементацію векторів https://hypirion.com/musings/understanding-persistent-vector-pt-1
Як порівняти два таких вектори? Типу зробити
[1 2 3] == [1 2 3]. По класиці — це пройтись по кожному елементу і порівняти їх. Це реалізовано через ітератор, порівнюємо кожні наступні значення поки не знайдемо пару відмінних значень it1.next() == it2.next(). Аллокація ітератору і виклик його методів займає час і пам'ять. Але є інший спосіб.Замість того, щоб використовувати загальний механізм (тут це ітератор), можна спеціалізувати код для порівняння двох векторів і використати деталі імплементації вектору щоб прискорити операцію порівняння. По суті можна пройтись по дереву, порівнюючи його гілки (масиви по 32 елементи). Так як вектор імутабельний, його гілки теж імутабельні. Тому порівняння пари гілок в більшості випадків можна робити по посиланню, а коли гілки відмінні по посиланню, то перевірити їх глибоким обходом.
Таким чином worst case виграш по швидкості виходить близько 30%, що дуже непогано.
Ще одна штука. Є в нас вектор
[1 2 3 4 5 6 7 8], і ми робимо йому (drop v 4) щоб видалити перші 4 значення. Під капотом насправді оригінальний вектор не змінюється, а огортається в тип даних ChunkedSeq (послідовність значень розбита на групи) і трекає позицію з якою ця послідовність починається. Якщо ми дропнули перші 4 значення у векторі, то chunked seq буде починати вичитувати значення з індексу 4 у оригінальному векторі.У реальному коді конвертація векторів у chunked seq відбувається доволі часто. Я помітив, що порівняння вектору з chunked seq повільніше ніж порівняння двох векторів між собою. Виявилось що як і у випадку з векторами, порівняння відбувається лінійниим перебором. А так як chunked seq тримає в собі оригінальний вектор, то задача оптимізації цього випадку по суті зводиться знов до порівняння двох векторів через спеціалізацію коду під цей випадок.
Тут результати бенчмарку показали приріст у швидкості операції від 300% до 500%.
Здавалося б що це непотрібні мікро оптимізації, але коли вони робляться у самій мові програмування чи її стандартній бібліотеці, то всі користувачі мови автоматично отримують покращення при цьому не сплачуючи за це ні центу.
Також це хороший приклад того, як на перших порах можна зробити працююче рішення на абстракціях і пізніше покращити конкретні кейси через спеціалізацію алгоритму на більш низькому рівні. В таких випадках точкове ускладнення коду цілком виправдане.