Почему функциональное реляционное программирование (иногда) быстрее, чем ООП, часть 1

Теперь доступна новая версия компилятора/транспилятора для языка программирования Cell, и хотя оптимизация все еще находится в стадии разработки, производительность уже очень высока.

Cell — это единственная реализация малоизвестной парадигмы функционального реляционного программирования, которая была впервые описана в статье 2006 года Out Of The Tar Pit. Его хорошая производительность полностью обусловлена этой базовой парадигмой, а точнее моделью/представлением данных, на которой он основан.

В тесте, который состоит из загрузки набора данных среднего размера (~ 140 МБ файлов CSV) из набора текстовых файлов и выполнения ряда запросов и обновлений, версия программы Cell явно превосходит в среднем эквивалентный объект. -ориентированная программа на Java, часто в 2-3 раза, а иногда и больше, несмотря на то, что Cell является языком гораздо более высокого уровня, чем Java (а функциональное реляционное программирование является парадигмой гораздо более высокого уровня, чем ООП), и разрыв становится еще больше, если сравнивать с эквивалентной программой на C#.

Cell также менее требователен к памяти: как только набор данных полностью загружается в ОЗУ, Cell использует около двух третей памяти, используемой Java и C# (и в зависимости от того, как именно выполняются тесты, это может быть даже меньше). Аналогичны результаты для пикового использования памяти. Эти результаты следует воспринимать с долей скептицизма, поскольку ни одна из трех версий программы не была оптимизирована для потребления памяти, поэтому цифры могли бы отличаться (но, вероятно, ненамного), если бы они были.

Вы можете прочитать больше о тестах и их результатах здесь, а оттуда вы можете скачать код, проверить его и запустить самостоятельно, если хотите. В этой серии из 6 частей я хочу глубоко погрузиться в реализацию и объяснить, почему Cell быстрее (когда он быстрее) и где он все еще медленнее (и что с этим можно сделать) по сравнению с эквивалентным объектно-ориентированным. код.

Обзор

Вообще говоря, есть три основных фактора, которые дают функциональному реляционному программированию преимущество в производительности по сравнению с ООП:

Структуры данных, используемые в функциональном реляционном программировании, естественным образом поддаются реализации с использованием методов, аналогичных тем, которые используются в архитектуре «сущность/компонент/система» и в программировании, ориентированном на данные (в некотором смысле функциональное реляционное программирование можно рассматривать, по крайней мере, в форма, которая реализована в Cell, как своего рода высокоуровневая версия ECS). Одним из преимуществ этих структур данных является то, что они очень удобны для кэширования, поскольку связанные данные хранятся вместе в памяти, а не разбросаны по разным местам, как в объектно-ориентированных системах.
В функциональном реляционном программировании существует четкое различие между логическим определением структуры данных и ее физической реализацией. Для любой структуры данных, определенной в вашем коде, компилятор выбирает из библиотеки возможных реализаций, основываясь на ее типе, наложенных на нее ограничениях (таких как ключи и внешние ключи) и способах ее использования. Компилятор пытается выбрать наиболее эффективную реализацию среди тех, которые обеспечивают требуемые функции. Более того, компилятор выполняет то, что мы могли бы назвать глобальной оптимизацией: то есть он полностью оптимизирует группы связанных структур данных, а не каждую по отдельности. Мы увидим, что именно это означает позже.
Дизайн Cell и его модель выполнения обеспечивают чрезвычайно эффективную сборку мусора, которая во многих случаях очень близка к нулевым накладным расходам. Отчасти это связано с использованием реляционных структур данных, а также с физическим разделением долгоживущей памяти, используемой для хранения состояния приложения, и временной памяти, используемой для вычислений, которые собираются мусором совершенно разными способами.

На самом деле есть еще кое-что, например, тот факт, что функциональное реляционное программирование с его дисциплинированным подходом к изменчивости и его предпочтением неизменности является гораздо более удобной для параллелизма парадигмой, но это то, чем Cell в настоящее время не пользуется, поэтому мы выиграли. не обсуждайте их здесь. Также вероятно, что более низкое использование памяти способствует повышению производительности за счет лучшего использования кэш-памяти, но я не знаю, как количественно оценить влияние этого.

Функциональное реляционное программирование также имеет ряд недостатков производительности по сравнению с ООП:

При проектировании структур данных вам потребуется указать ряд ограничений целостности (ключи и внешние ключи), которые необходимо проверять каждый раз при обновлении состояния приложения. Этот тип накладных расходов обычно невелик, но обычно его можно измерить. Простой способ избежать этого — добавить возможность пропускать проверку ограничений в сборках релизов для обновлений, которые уже хорошо протестированы и критически важны для общей производительности. Хотя на данный момент компилятор не предлагает эту опцию, реализовать ее в будущей версии будет тривиально.
Все обновления состояния в Cell происходят внутри транзакции: если транзакция терпит неудачу, обновление отменяется, а его последствия откатываются. Это часто является основным источником накладных расходов. Опять же, теоретически можно отказаться от транзакций для определенных обновлений, в правильности которых разработчик уверен, или когда семантика транзакций просто не имеет смысла, но в данном случае это намного сложнее и потребует расширения языка, которое планируется, но еще не реализовано.
В Cell запросы (то есть все типы вычислений, которые не обновляют состояние приложения и единственной целью которых является вычисление результата) написаны на функциональном языке. Функциональное подмножество Cell достаточно быстрое, и обычно оно близко по производительности к Java, когда вы можете написать сопоставимый код на двух языках, но часто вы не можете, потому что ограничения на изменчивость, типичные для функциональных языков, часто вынуждают вас писать код способами, которые менее эффективны, чем то, что вы могли бы сделать на императивном языке. Грубо говоря, быстрая часть функционального реляционного программирования — это реляционная часть, а не функциональная. Одним из способов решить эту проблему было бы введение большей изменчивости в функциональное подмножество языка, что можно было бы сделать, не отказываясь от хороших свойств функционального программирования. Гораздо лучшим подходом было бы расширение языка дополнительными декларативными функциями, и это направление будет выбрано в будущих версиях Cell. Декларативный язык предлагает гораздо больше возможностей для оптимизации, чем функциональный или императивный. В последнем посте этой серии мы увидим, как будет выглядеть такой язык и как он может (потенциально) резко улучшить производительность запросов.

Есть также еще пара факторов, которые следует учитывать, эффект которых может быть в любом случае:

Разделение между логическим определением и физической реализацией применяется ко всем структурам данных Cell, как реляционным, так и функциональным. Например, словарь/карта могут быть прозрачно представлены под капотом как отсортированный массив пар ключ/значение или (сбалансированное) двоичное дерево или что-то среднее между ними, а среда выполнения может (прозрачно) переключаться с одного представления на другое всякий раз, когда это может улучшить производительность. Для реляционных структур данных это неоспоримое преимущество. Для функциональных эффект положительный в большинстве, но не во всех случаях.
Как мы уже упоминали, функциональные структуры данных в Cell концептуально неизменяемы и могут обновляться императивно только «по возможности», то есть только тогда, когда компилятор может доказать, что прямая мутация не изменит семантику программы. Хотя в целом это вредно для производительности, бывают случаи, когда это становится преимуществом, потому что компилятор может применять оптимизации, которые в противном случае были бы небезопасными.

Но что такое функциональное реляционное программирование?

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

Основным новым программным артефактом в Cell является реляционный автомат. Вы можете думать об этом как о своего рода классе, который кодирует свое внутреннее состояние, используя отношения. Если вы знакомы с архитектурой Entity/Component/System, вы можете думать о ней как о высокоуровневом эквиваленте одного компонента или группы тесно связанных компонентов. Последняя аналогия является лучшей, но первая подойдет для целей нашего обсуждения.

Вот как выглядит объявление реляционного автомата на примере, рассмотренном на странице вводный пример:

type UserId  = user_id(Int);
type GroupId = group_id(Int);

schema OnlineForum {
  // Unique id generation for users and groups
  next_id : Int = 0;

  // Users and their attributes
  // usernames must be unique, and date_of_birth is optional
  user(UserId)
    username       : String [unique],
    signup_date    : Date,
    first_name     : String,
    last_name      : String,
    date_of_birth? : Date;

  // Chat groups and their attributes
  chat_group(GroupId)
    name  : String,
    admin : UserId;

  // Foreign key integrity constraint. States that
  // every group administrator must also be a valid user
  admin(_, id) -> user(id);

  // Membership relationship between users
  // and groups, and its attributes
  member(UserId, GroupId)
    joined_on : Date,
    karma     : Int;

  // Another foreign key integrity constraint.
  // States that the member relation can only
  // reference valid users and chat groups
  member(u, g) -> user(u), chat_group(g);

  // Stores friendship information between user,
  // with its only attribute. The relation is
  // declared symmetric, the order in which the
  // user identifiers are stored doesn't matter
  friends(UserId | UserId)
    since : Time;

  // The friends relation can only reference valid users
  friends(u1, u2) -> user(u1), user(u2);
}

Состояние OnlineForumautomaton кодируется с помощью одной переменной-члена, next_id; два унарных отношения (набора), user и chat_group, в которых хранятся идентификаторы всех сущностей в наборе данных; ряд бинарных отношений, таких как username и signup_date, в которых хранятся атрибуты указанных сущностей; два других бинарных отношения, member и friends, которые кодируют соответствующие отношения; и, наконец, три тернарных отношения, joined_on, karma и since, в которых хранятся атрибуты member и friends.

В качестве примера возьмем пользовательские данные, которые в реляционной базе данных будут храниться в таблице USERS, подобной следующей:

В Cell одна и та же информация закодирована в нескольких различных отношениях/таблицах, показанных здесь:

Как видите, существует несколько основных различий между разновидностью реляционной модели, используемой в Cell, и той, которая используется в базах данных SQL:

В Cell столбцы/аргументы таблицы/отношения могут быть любого пользовательского типа.
В то время как в реляционных базах данных целые числа или строки обычно используются в качестве первичных ключей (и, следовательно, в качестве идентификаторов сущностей), идентификаторы сущностей в Cell имеют определяемые пользователем типы (в данном случае UserId и GroupId), как и в архитектуре ECS.
Все отношения в Cell атомарны в том смысле, что каждое из них кодирует один атрибут или отношение.
Существует также прямая поддержка иерархий наследования/классификации. Однако это не имеет отношения к производительности, поэтому мы не будем обсуждать это здесь.
Модульность (которая, очевидно, отсутствует в схемах баз данных) достигается за счет разделения состояния приложения на несколько разных типов автоматов, которые затем «связываются» вместе в процессе, который не сильно отличается от того, что вы делаете с компонентами ECS. Опять же, это не влияет на производительность и выходит за рамки нашего обсуждения.

Автоматы также имеют методы и обработчики сообщений. Методы — это просто функции, «привязанные» к автоматному типу. В отличие от своих ООП-аналогов, методы в Cell доступны «только для чтения» в том смысле, что им не разрешено изменять внутреннее состояние экземпляра автомата. Их единственная цель — вычислить и вернуть результат.

Чтобы изменить состояние экземпляра автомата, вам нужно отправить ему сообщение. Сообщение — это просто значение, то есть простой фрагмент данных. Для каждого типа сообщения, которое принимает автомат, существует соответствующий обработчик сообщений, который вызывается при получении сообщения. Обработчики сообщений могут изменять состояние автомата, но не возвращают результат. Они запускаются внутри транзакции: если при их выполнении возникает ошибка, сообщение отбрасывается, а все обновления состояния автомата откатываются, так что последний остается без изменений.

И методы, и обработчики сообщений являются детерминированными, поэтому возвращаемый ими результат или создаваемое ими новое состояние зависят только от их аргументов и начального состояния автомата.

Cell также имеет встроенную поддержку постоянства: вы можете сделать снимок состояния экземпляра автомата, который затем можно сериализовать, сохранить и использовать позже для создания клона исходного экземпляра, который продолжится с того места, где остановился оригинал. , и будет вести себя точно так же. Весь процесс полностью прозрачен для автомата и не требует дополнительных действий со стороны разработчика. Это уместно здесь, потому что в языке, который поддерживает автоматическое сохранение, вам необходимо предоставить возможность использовать данные, сохраненные более старыми версиями приложения, в новой, внутренние структуры данных которой могут быть изменены, и это ограничивает дизайн модели данных и система типов способами, которые без дополнительной оптимизации отрицательно сказались бы на производительности.

Это все, что вам нужно знать на данный момент. Мы будем добавлять больше деталей по мере продвижения.

Реализация бинарных отношений

Структура данных Cell, которая наиболее критична для производительности, — это бинарное отношение, поэтому мы начнем наше обсуждение с него. Мы начнем с особого случая, который допускает упрощенную реализацию, и будем строить оттуда.

Итак, давайте начнем с отношения username в схеме OnlineForum. Одной из особенностей username является то, что значения в любом из его столбцов уникальны: у каждого пользователя может быть только одно имя пользователя, и каждое имя пользователя не может быть связано более чем с одним пользователем. Вот он снова, с примерами данных:

Как упоминалось во введении, одним из преимуществ модели данных очень высокого уровня является то, что физическая реализация структуры данных может полностью отличаться от ее логического определения. В этом случае информация, содержащаяся в username, сначала преобразуется и разбивается на три разные структуры данных:

Магазины ценности

Две структуры данных вверху называются хранилищами значений. Их высокоуровневая цель — просто сопоставить каждое из значений, которые появляются в столбце отношения, с уникальным целым числом, называемым суррогатом. На практике вы можете думать о них как о массивах, содержащих все значения в соответствующем столбце соответствующего отношения. Суррогат каждого значения — это просто его индекс в массиве. Мы обсудим хранилища более подробно в одном из следующих постов, а пока вот что вам нужно знать:

Хранилища значений не содержат дубликатов. Даже если значение появляется в соответствующем столбце более одного раза, хранилище значений содержит только одну его копию.
После того как они вставлены во внутренний массив хранилища значений, значения никогда не перемещаются, и поэтому их индекс никогда не меняется. Другими словами, суррогаты стабильны: пока значение присутствует в соответствующем столбце, его суррогат никогда не меняется. Он может измениться только в том случае, если значение полностью удалено из столбца (и, следовательно, из хранилища значений) и повторно вставлено позже.
Значения в массиве не сортируются, и они не должны быть непрерывными: массив может и, как правило, будет содержать дыры, которые образуются при удалении значений. Затем отверстия снова заполняются при вставке новых значений.
В дополнение к основному массиву реализация каждого хранилища значений также содержит хеш-таблицу, которая используется для быстрого поиска суррогата любого содержащегося в нем значения. Следовательно, стоимость перехода от значения к суррогату — это один поиск в хеш-таблице, а для перехода от суррогата к значению требуется только доступ к массиву.

Суррогатные таблицы и их реализация

Структура данных в нижней части рисунка 4 называется суррогатной таблицей. Чтобы получить суррогатную таблицу из соответствующего отношения, все, что вам нужно сделать, это заменить каждое отдельное значение его суррогатом. Суррогатная таблица по-прежнему является логической структурой данных, хотя и на более низком уровне абстракции по сравнению с отношением, из которого она получена, и может быть реализована различными способами. Воспользовавшись тем, что суррогаты являются индексами массива и что в конкретном случае username значения в каждом столбце уникальны, мы можем реализовать эту конкретную суррогатную таблицу, используя пару массивов:

Чтобы увидеть, как данные закодированы в этих двух массивах, давайте возьмем первый кортеж/строку в суррогатной таблице, (8, 2). В левый массив записываем значение 2 по индексу 8. В правом делаем наоборот и пишем значение 8 по индексу 2. Затем мы делаем то же самое для всех остальных кортежей. Поскольку ни один из столбцов не содержит дубликатов, конфликтов быть не может.

Удалить кортеж из суррогатной таблицы также очень просто: если вы хотите удалить, скажем, (8, 2), все, что вам нужно сделать, это стереть содержимое элемента с индексом 8 в левом массиве и содержимое элемента с индексом 2. в той, что справа.

Давайте теперь посмотрим, как искать данные с помощью этой реализации. Допустим, у вас есть идентификатор пользователя (например, user_id(4)) и вы хотите найти соответствующее имя пользователя (в данном случае "john_doe"). Вот шаги, которые вам необходимо предпринять:

Запросите хранилище значений для первого столбца (тот, что слева на рисунке 4), чтобы получить суррогат вашего идентификатора пользователя: user_id(4) -> 2. Это поиск по хэш-таблице, который можно выполнить за амортизированное постоянное время.
Прочитайте левый массив рисунка 5, используя суррогат, полученный на предыдущем шаге, в качестве индекса, чтобы получить суррогат соответствующего имени пользователя: 2 -> 0
Найдите значение, связанное с суррогатом имени пользователя, полученным на предыдущем шаге, в хранилище значений справа на рисунке 4: 0 -> "john_doe"

Если вы хотите сделать обратное, то есть найти идентификатор пользователя по его имени пользователя, вы делаете то же самое, но в противоположном направлении и используете массив справа на рисунке 5: "john_doe" -> 0 -> 2 -> user_id(4). Обратите внимание, что затраты времени на выполнение двух операций (поиск и обратный поиск) почти идентичны для такого типа реализации.

Другая распространенная операция только для чтения — перебор элементов отношения. Для этого мы можем просто перебрать один из массивов (скажем, тот, что слева на рисунке 5): индекс каждого элемента — это суррогат идентификатора пользователя, а его значение — суррогат имени пользователя.

Стоит отметить, что любой из массивов на рис. 5 содержит достаточно информации для восстановления содержимого всей суррогатной таблицы. Причина, по которой у нас их два, заключается в том, что мы хотим иметь возможность эффективно выполнять как поиск, так и обратный поиск. Пока вы не сделаете первый обратный поиск в username, вам не нужен массив справа, который может быть построен «по требованию», то есть только тогда (и если) первый обратный просмотр действительно имеет место.

Совместное использование хранилищ ценности

Если вы еще раз посмотрите на рисунок 2, то увидите, что один и тот же набор значений (идентификаторы пользователей) повторяется в первом (или единственном) столбце всех отношений на картинке, а также в других отношениях, которые не показано там. Компилятор может легко определить, содержат ли два столбца одинаковый набор значений (или один из них является подмножеством другого), проверив внешние ключи. На практике это означает, что нам нужно только одно общее хранилище значений для всех этих столбцов, а не по одному для каждого из них. Это не только экономит память, но и имеет согласованное сопоставление между значениями и их суррогатными значениями во всем наборе данных или состоянии приложения, что также может значительно повысить производительность, как мы увидим позже.

Это, кстати, пример того, что я описал ранее как глобальную оптимизацию, то есть тот факт, что при сопоставлении логических структур данных высокого уровня с их низкоуровневыми реализации мы можем оперировать ими целиком, вместо того, чтобы иметь дело с каждым из них по отдельности. Мы увидим другие примеры этого в следующих постах.

Выводы

Это все для части 1. Во части 2 мы сначала обсудим универсальную реализацию бинарных отношений один ко многим и многие ко многим (то, что мы только что обсуждали, username, было -одно отношение), а также ряд конкретных оптимизаций, которые могут значительно повысить производительность.