О функциональном программировании и неизменяемости
О, каким простым был мир раньше, у нас были одни процессоры в компьютере, интернет не породил YouTube, Facebook или Instagram, а программное обеспечение было простым из-за ограничений железа. Увы, это не могло длиться вечно!
Примерно в 2019 году программы и программное обеспечение проникли во все, от наручных часов до беспилотных автомобилей. Аппаратные ограничения были преодолены с помощью нескольких процессоров, и наша потребность в создании более быстрых и масштабируемых вещей стала экспоненциально высокой. Программное обеспечение используется врачами, юристами, правительством и даже для свиданий, очевидно, что должен быть лучший способ писать более надежные программы и при этом иметь простую для понимания концепцию этих программ.
За последние 50 лет компьютеры развивались экспоненциально, но сделали ли мы то же самое? Возможно нет!
Ментальные модели, которые помогли нам создать программное обеспечение для ограниченного оборудования, не так хорошо работают в наше время, и чтобы понять будущее, чтобы решать проблемы чисто, мы должны оглянуться назад в историю информатики. Оглядываясь назад, мы заново открываем для себя парадигму программирования с использованием более простых строительных блоков, которые можно легко протестировать, использовать математические рассуждения, чтобы свести к минимуму вероятность того, что программа будет делать неправильные вещи, и помочь инженерам сосредоточиться на правильном инструменте проектирования для надежного решения проблемы. .
Clojure и Scala делают функциональное программирование мейнстримом
Успех языков функционального программирования, таких как Clojure и Scala, доказал, что наконец настало подходящее время для идеи функционального программирования. Оба этих известных языка JVM в значительной степени полагаются на использование чисто функциональных структур данных, а также на неизменяемостьв качестве философия дизайна, встроенная в ДНК самих языков.
Сегодня мы поговорим об одной такой структуре данных, которая помогла этим дружественным к параллелизму языкам стать более производительными, Relaxed Radix Balanced Trees (RRB Trees).
Деревья RRB: эффективные неизменяемые векторы - Фил Бэгвелл и Тиарк Ромпф (2012)
Мы будем рассматривать исходную статью, написанную динамическими (или, точнее, статически типизированными :) ) Филом Бэгвеллом и Тиарком Ромпфом.
Статья основана на структурах данных на языке программирования Scala в EPFL — École polytechnique fédérale de Lausanne и может быть найдена в репозитории PapersWeLove Github.
Актуальность этой структуры данных для Clojure и Scala заключается в том, что оба этих языка предлагают дружественные к параллелизму неизменяемые векторы как частьсвоих стандартных библиотек и используются сотнями тысяч инженеров. ежедневно. Целью деревьев RRB является повышение производительности стандартных неизменяемых векторов за счет повышения производительности операций конкатенации, вставки и разделения векторов без ущерба для Скорость индексирования, обновления и итерации исходных неизменяемых векторов.
Давайте сначала рассмотрим, почему универсальная структура данных массива не идеальна для параллельного программирования. Существуют определенные преимущества использования массива, такие как возможность доступа к элементам за постоянное время O (1), а не за линейное время O (n), а также непересекающиеся части массива, т. е. подмассивы могут быть эффективно обработаны в параллельном режиме. вычислительная манера. Однако проблема с этой структурой данных заключается в том, что она зависит от изменчивости обновлений элементов на месте, что возлагает ответственность за неизменность на программиста. К сожалению, снова и снова люди оказывались не очень дисциплинированными, учитывая эту ответственность за поддержание состояния программы, что приводило к ошибкам на многие миллионы долларов.
Вы бы не хотели потерять миллион долларов, верно? Давайте без изменений :)
Вернувшись в неизменяемый мир, эффективную копию структуры данных Array, то есть индексируемую упорядоченную последовательность значений, создать немного утомительно, поскольку упрощенный прямой перевод в неизменяемую версию в конечном итоге будет иметь неприемлемые линейные затраты на обновление отдельных элементов и тем самым снижая производительность структуры данных.
В Clojure неизменяемые векторы являются важной частью языка, и его создатель Рич Хикки полагался на сопоставленные попытки хэшированного массива (HAMT), также называемые идеальными попытками хеширования, для реализации не одной, а двух основных структур данных, а именно, вектора и хэша. -карта. Полученный дизайн обеспечивает эффективную итерацию и добавление одного элемента за постоянное время, индексацию за время (1/5 logN) и обновление за время (32/5 logN).
Использование массивов шириной 32 в качестве узлов дерева делает структуру данных более удобной для кэширования. Индексированное обновление требует только O(1/5 logN) непрямых обращений к памяти, а это означает, что для практических целей все операции несут затраты «постоянного времени». Однако параллельная обработка требует эффективной конкатенации векторов, разделения и вставки по заданному индексу, которые нелегко поддерживаются структурой. Работа, представленная в этой статье, расширяет базовую векторную структуру для поддержки конкатенации и вставки вместо линейного времени без ущерба для производительности O(logN) существующих операций. Эта новая структура данных обеспечивает более эффективное распараллеливание распространенных типов понимания. Вектор можно разделить на разделы, которые затем можно оценивать параллельно. Для многих распространенных операций, таких как фильтрация, размер результатов отдельных разделов заранее неизвестен. Результирующие подвекторы могут быть объединены для получения результирующего вектора без линейного копирования. Таким образом, преимущества параллельной обработки не теряются при повторной сборке подвекторов.
Это базовая векторная структура с 4-ветвящейся структурой. Обратите внимание, что узлы на разных уровнях дерева связаны значением индекса 1, если только в поддереве нет больше листьев.
Эта взаимосвязь более наглядно поясняется диаграммой ниже. На этом рисунке показана базовая структура дерева RRB. Узел дерева A содержит массив указателей, указывающих на поддеревья C, D и E. С этим массивом связан массив диапазонов, который содержит накопленное общее количество листовых элементов в этих поддеревьях. Для удобства мы будем называть указатель и связанный с ним диапазон слотом. В примере слот 0 указывает на узел C и содержит 3
поддерева, которые в данном случае являются конечными элементами.
Теперь вы можете спросить, почему мы специально выбрали четырехстороннее дерево? — Хороший вопрос!
Причина заключается в том, что при эмпирическом анализе между временем, затрачиваемым на индексацию и обновлением структуры данных, оптимальное значение оказывается равным 4, и мы достаточно заботимся о производительности, чтобы измерить это в масштабе наносекунд!
Конкатенация
Теперь давайте рассмотрим ядро алгоритма, которое сосредоточено на повторной сборке части конвейера параллельной обработки, и посмотрим, как это делает алгоритм более эффективным, чем текущая векторная реализация.
Наивный подход к объединению их в один вектор требует «сдвига влево» и копирования всех узлов из правого вектора в соответствующие позиции
в объединенном векторе, процесс, линейный по размеру правого вектора. . В качестве альтернативы можно пройти по правому вектору
и добавить элементы к левому вектору, опять же линейный процесс.
Но алгоритм дерева RRB предполагает, что мы могли бы также достичь тех же результатов в наихудшем случае стоимости конкатенации, пропорциональной O (log N), просто полагаясь на указатель на поддеревья, которые хранятся в подвекторах с уровня выше и запуск процесса конкатенации либо снизу вверх, либо сверху вниз.
Сначала мы двигаемся вниз по правому краю левого дерева и по левому краю правого дерева. Затем мы поднимаемся на один уровень вверх. Чтобы иметь правильно сформированное дерево, мы должны перебалансировать узлы, заключенные в прямоугольник, чтобы они соответствовали инварианту. Это требует, чтобы мы копировали записи ветвей справа налево, пока счетчик каждого слота не окажется между m-1 и m. Далее нам нужно соблюдать последовательный порядок. В примере нам нужно скопировать элемент в 3-м узле и три элемента в 4-м узле в новый узел, который теперь соответствует инварианту. Однако в общем случае может потребоваться скопировать несколько или даже все узлы, прежде чем они удовлетворят инварианту.
Исходная реализация Scala и Clojure Vector использует внутренние узлы с массивом, несущим 32-стороннюю ветвь. В этой реализации массив увеличивается на единицу, когда узел преобразуется в узел дерева RRB. Нулевой элемент содержит ссылку на массив, содержащий значения диапазона. Накладные расходы на векторы, которые не были объединены, отсутствуют. Кроме того, использование отдельного массива диапазонов, а не объекта диапазона/указателя, не влияет на скорость итерации, распространенный вариант использования.
После конкатенации на некоторых узлах нулевой элемент
будет указывать на массив значений диапазона. Поскольку только внутренние узлы
несут этот дополнительный элемент, дополнительная нагрузка на память близка к единице
в м² или 1 к 1024 и может считаться незначительной.
Во второй части мы будем использовать библиотеку clojure core.rrb на основе исследования производительности RRB-Tree.
В части 1 я опустил математические детали в пользу концептуального понимания, и в дальнейшем мы будем изучать документ RRB-Tree, основанный на реализации Clojure концепции, метко названной core. rrb-vector Я также создал сопутствующий репозиторий на github, чтобы продемонстрировать эталонные тесты между нативным clojure vector и rrb-vector.
