За функционалното програмиране и неизменността

О, колко прост беше светът преди, имахме единични процесори в компютъра, интернет не роди YouTube, Facebook или Instagram и софтуерът беше прост поради ограниченията на хардуера. Уви, не можеше да продължи вечно!

Около 2019 г. програмите и софтуерът са проникнали във всичко, от ръчни часовници до самоуправляващи се автомобили. Ограниченията на хардуера бяха заобиколени с помощта на множество процесори и нуждата ни да създаваме по-бързи и мащабируеми неща стана експоненциално висока. Софтуерът се използва от лекари, адвокати, правителство и дори за запознанства, очевидно трябва да има по-добър начин за писане на по-надеждни програми и все пак да има лесна за разбиране концепция зад тези програми.

През последните 50 години компютрите се развиха експоненциално, но направихме ли същото? Вероятно не!

Мисловните модели, които ни помогнаха да създадем софтуер за ограничен хардуер, не работят толкова добре в тази епоха и за да разберем бъдещето, за да решаваме проблемите чисто, трябва да погледнем назад в историята на компютърните науки. Поглеждайки назад, ние преоткриваме парадигмата на програмиране за използване на по-прости градивни елементи, които могат да бъдат тествани лесно, за използване на математически разсъждения, за да се сведат до минимум шансовете програмата да прави грешни неща и да помогне на инженерите да се съсредоточат върху правилния инструмент за проектиране за надеждно решаване на проблема .

Clojure и Scala приемат основния поток на функционалното програмиране

Успехът на езиците за функционално програмиране като Clojure и Scala доказа, че най-накрая е настъпил правилният момент за идеята за функционално програмиране. И двата известни JVM езика разчитат в голяма степен на използването на Чисто функционални структури от данни, както и на Неизменносткато философия на дизайна, вградена в ДНК-то на самите езици.

Днес ще говорим за една такава структура от данни, която е помогнала на тези удобни за паралелност езици също да бъдат производителни, Релаксирани радиксни балансирани дървета (RRB дървета).

RRB дървета: Ефективни неизменни вектори — Фил Багуел и Тиарк Ромпф (2012)

Ще разгледаме оригиналната статия, написана от динамичните (или по-подходящо статично въведени :) ) Фил Багуел и Тиарк Ромпф.

Документът произхожда от структурите от данни в езика за програмиране Scala в EPFL — École polytechnique fédérale de Lausanne и може да бъде намерен в PapersWeLove Github repo.

Уместността на тази структура от данни за Clojure и Scala е, защото и двата езика предлагат удобни за паралелност Неизменни векторикато частот техните стандартни библиотеки и се използват от стотици хиляди инженери ежедневно. Целта на RRB дърветатае да подобри производителността на стандартните неизменни вектори, като направи операцията Свързване на вектори, вмъкване, както и разделяне много по-производителна, без да засяга Скорости на индексиране, актуализиране и итерацияна оригиналните неизменни вектори.

Нека първо да помислим защо общата структура на масив от данни няма да бъде идеална за едновременно програмиране. Има определени предимства от използването на Array, като възможността за достъп до елементи за постоянно O(1) време, а не за линейно O(n) време, също така разединените части на масива, т.е. подмасивите могат да бъдат ефективно обработвани в паралел изчислителен начин. Въпреки това, проблемът с тази структура на данните е, че тя разчита на променливостта на актуализации на елементи на място, което носи отговорността за неизменността на програмиста. За съжаление, отново и отново, хората се оказаха не много дисциплинирани, като се има предвид тази отговорност за поддържане на състоянието на програма, което доведе до много грешки за милиони долари.

Не бихте искали да загубите милион долара, нали? Хайде неизменно :)

Обратно в неизменния свят, ефикасно противоположно на структурата от данни на масива, т.е. индексируема подредена последователност от стойности, е малко досадно да се създаде, тъй като опростен директен превод към неизменна версия в крайна сметка ще има неприемливи линейни разходи за актуализиране на отделни елементи и като по този начин се намалява производителността на структурата от данни.

В Clojure неизменните вектори са критична част от езика и неговият създател, Рич Хики, разчита на Hashed Array Mapped Tries (HAMT), наричан още като Ideal Hash Tries, за внедряване на не една, а две от основните структури на данни, а именно вектор и хеш -карта. Полученият дизайн осигурява ефективна итерация и добавяне на един елемент за постоянно време, индексиране за (l/5 logN) време и актуализации за (32/5 logN) време.

Използването на 32-широки масиви като възли на дърво прави кеша на структурата на данните удобен. Индексираната актуализация изисква само O(1/5 logN) индиректни достъпи до паметта, което означава, че за практически цели всички операции имат разходи за „постоянно време“. Въпреки това паралелната обработка изисква ефективна векторна конкатенация, разделяне и вмъквания при даден индекс, които не се поддържат лесно от структурата. Работата, представена в този документ, разширява основната векторна структура, за да поддържа конкатенация и вмъквания в, а не в линейно време, без да компрометира изпълнението на O(logN) на съществуващите операции. Тази нова структура на данни се поддава на по-ефективно паралелизиране на общи типове разбирания. Един вектор може да бъде разделен на дялове, които след това могат да бъдат оценени паралелно. За много често срещани операции като филтриране размерът на резултатите от отделния дял не е известен предварително. Получените под-вектори могат да бъдат конкатенирани, за да върнат резултатен вектор без линейно копиране. Така предимствата на паралелната обработка не се губят при повторното сглобяване на подвекторите.

Това е основна векторна структура с 4-посочна разклонена структура. Забележете внимателно, че възлите на различни нива на дървото са свързани чрез стойността на индекса 1, освен ако няма повече листа в поддървото.

Тази връзка е по-ясно обяснена от диаграмата по-долу. Тази фигура илюстрира основната структура на RRB дърво. Дървовидният възел A се състои от масив от указатели, които сочат към поддървета, C, D и E. Свързан с този масив е масивът от диапазони, който съдържа натрупания общ брой листни елементи в тези поддървета. За удобство ще наричаме указателя и свързания с него диапазон слот. В примера слот 0 сочи към възел C и се казва, че съдържа 3
поддървета, които в този случай са листа.

Сега може да попитате защо избрахме специално 4-посочно дърво? — Това е добър въпрос!

Причината се крие във факта, че при емпиричен анализ между времето, необходимо за индексиране и актуализациите на структурата на данните, оптималната стойност се оказва 4 и ние се интересуваме достатъчно от производителността, за да измерим това спрямо мащаба на наносекунди!

Конкатенация

Сега нека разгледаме ядрото на алгоритъма, който се концентрира върху повторното сглобяване на тръбопровода за паралелна обработка и нека видим как прави алгоритъма по-ефективен от текущата векторна реализация.

Наивният подход за свързването им в един вектор изисква „изместване наляво“ и копиране на всички възли от десния вектор в съответните позиции
в конкатенирания вектор, процес, линеен в размера на десния вектор . Като алтернатива човек може да премине през десния вектор
и да добави елементите към левия вектор, отново линеен процес.

Но алгоритъмът на RRB Tree предлага, че можем да постигнем същите резултати и в най-лошия случай, цената на конкатенацията, пропорционална на O(log N), просто като разчитаме на указателя към поддърветата, които се съхраняват в подвекторите от ниво по-горе и стартиране на процеса на конкатенация по начин отдолу нагоре или отгоре надолу.

Първо се придвижваме надолу по десния ръб на лявото дърво и по левия ръб на дясното дърво. След това се придвижваме с едно ниво нагоре. За да имаме добре оформено дърво, трябва да ребалансираме възлите, затворени в полето, за да съответстват на инварианта. Това изисква да копираме записи за разклонения отдясно наляво, докато броят на всеки слот е между m-1 и m. Освен това трябва да поддържаме последователния ред. В примера трябва да копираме елемента в 3-тия възел и трите елемента в 4-тия възел в нов възел, който сега отговаря на инварианта. Въпреки това, като цяло може да се наложи няколко или дори всички възли да бъдат копирани, преди да срещнат инварианта.

Оригиналното изпълнение на Scala и Clojure Vector използва вътрешни възли с масив, носещ 32-посочно разклонение. В тази реализация масивът се увеличава с единица, когато възел се преобразува във възел на RRB дърво. Нулевият елемент носи препратка към масива, съдържащ стойностите на диапазона. Няма допълнителни разходи за вектори, които не са свързани. Освен това чрез използване на отделен масив от диапазони, а не обект от диапазон/указател, скоростта на итерация, обичаен случай на употреба, не се влияе.

След конкатенация на някои от възлите нулевият елемент
ще сочи към масива от стойности на диапазона. Тъй като само вътрешните възли
носят този допълнителен елемент, допълнителното натоварване на паметта е близо до едно
в m² или 1 на 1024 и може да се счита за незначително.

В Част-2 ще използваме базираното на clojure core.rrb изследване на ефективността на RRB-Tree

В Част-1 премълчах математическите детайли в полза на концептуалното разбиране и напред ще проучим документа за RRB-Tree, базиран на реализацията на Clojure на концепцията, уместно наречена core. rrb-vector Също така създадох придружаващо хранилище в github, за да покажа сравнителните показатели между родния clojure vectorи rrb-vector.