Сверхсовременные иммутабельные структуры данных

    Годами эксперты в С++ рассуждают о семантике значений, иммутабельности и разделении ресурсов за счет коммуникации. О новом мире без мьютексов и гонок, без паттернов Command и Observer. На деле все не так просто. Главная проблема по-прежнему в наших структурах данных.



    Иммутабельные структуры данных не меняют своих значений. Чтобы что-то с ними сделать, нужно создавать новые значения. Старые же значения остаются на прежнем месте, поэтому их можно без проблем и блокировок читать из разных потоков. В итоге ресурсы можно совместно использовать более рационально и упорядоченно, ведь старые и новые значения могут использовать общие данные. Благодаря этому их куда быстрей сравнить между собой и компактно хранить историю операций с возможностью отмены. Все это отлично ложится на многопоточные и интерактивные системы: такие структуры данных упрощают архитектуру десктопных приложений и позволяют сервисам лучше масштабироваться. Иммутабельные структуры — секрет успеха Clojure и Scala, и даже сообщество JavaScript теперь пользуется их преимуществами, ведь у них есть библиотека Immutable.js, написанная в недрах компании Facebook.

    Под катом — видео и перевод доклада Juan Puente с конференции C++ Russia 2019 Moscow. Хуан рассказывает про Immer — библиотеку иммутабельных структур для C++. В посте:

    • архитектурные преимущества иммутабельности;
    • создание эффективного персистентного векторного типа на основе RRB-деревьев;
    • разбор архитектуры на примере простого текстового редактора.




    Трагедия архитектуры, основанной на значениях


    Чтобы понять значимость иммутабельных структур данных, обсудим семантику значений. Это очень важная особенность С++, я считаю её одним из главных достоинств этого языка. При всем при этом использовать семантику значений так, как нам хотелось бы, очень сложно. Я считаю, что в этом трагедия архитектуры, основанной на значениях, и дорога к этой трагедии вымощена благими намерениями. Предположим, нам необходимо написать интерактивное ПО на основе модели данных с репрезентацией редактируемого пользователем документа. При архитектуре, основанной на значениях, в основе этой модели используются простые и удобные типы значений, которые уже есть в языке: vector, map, tuple, struct. Логика приложения создается из функций, которые принимают документы по значению и возвращают новую версию документа по значению. Этот документ может изменяться внутри функции (как это происходит ниже), но семантика значений в С++, применяемая к аргументу по значению и возвращаемому типу по значению, обеспечивает отсутствие побочных эффектов.



    Такую функцию очень легко анализировать и тестировать.



    Раз мы работаем со значениями, попробуем реализовать отмену действия. Это бывает непросто, но при нашем подходе это тривиальная задача: у нас есть std::vector с различными состояниями различных копий документа.



    Предположим, у нас также есть UI, и, чтобы обеспечить его отзывчивость, отображение UI необходимо сделать в отдельном потоке. Документ пересылается в другой поток сообщением, и взаимодействие происходит тоже на основе сообщений, а не через предоставление общего доступа к состоянию с использованием mutexes. Когда копия получена вторым потоком, там можно выполнять все необходимые операции.



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



    Далее, предположим, у нас есть ещё и поток управления звуком. Как я уже говорил, я много работал с музыкальным ПО, и звук является еще одним представлением нашего документа, он обязательно должен быть в отдельном потоке. Поэтому для этого потока также необходима копия документа.

    В итоге у нас получилась очень красивая, но не слишком реалистичная схема.



    В ней постоянно приходится копировать документы, история действий для отмены занимает гигабайты, и для каждой отрисовки UI нужно сделать глубокую копию документа. В общем, все взаимодействия оказываются слишком затратными.



    Что в этой ситуации делает разработчик на С++? Вместо того, чтобы принимать документ по значению, логика приложения теперь принимает ссылку на документ и обновляет её при необходимости. Возвращать в этом случае ничего не нужно. Но теперь мы имеем дело не со значениями, а с объектами и местоположениями. Это создает новые проблемы: если есть ссылка на состояние с общим доступом, для него нужен mutex. Это крайне затратно, поэтому здесь будет некоторое представление нашего UI в виде крайне сложного дерева из различных Widget-ов.

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



    Пользователи уже привыкли к картинке песочных часов, так что ничего страшного, если они немного подождут. Страшно другое — нашим кодом теперь правит макаронный монстр.

    В какой момент у нас всё пошло под откос? Мы отлично спроектировали наш код, а затем из-за копирования нам пришлось идти на компромиссы. Но в С++ копирование обязательно для передачи по значению лишь для мутабельных данных. Если же объект иммутабельный, то оператор присваивания можно реализовать так, чтобы он копировал только указатель на внутреннее представление и ничего больше.

    const auto v0 = vector<int>{};

    Рассмотрим структуру данных, которая могла бы нам помочь. У вектора ниже все методы отмечены как const, поэтому он иммутабельный. При выполнении .push_back не происходит обновления вектора, вместо этого возвращается новый вектор, к которому добавлены переданные данные. К сожалению, квадратными скобками при таком подходе мы пользоваться не можем из-за того, как они определены. Вместо этого можно использовать функцию .set, которая возвращает новую версию с обновленным элементом. Наша структура данных теперь обладает свойством, которое в функциональном программировании называется персистентность. Имеется ввиду не то, что мы сохраняем эту структуру данных на жёсткий диск, а тот факт, что при её обновлении старое содержимое не удаляется — вместо этого создается новый форк нашего мира, то есть структуры. Благодаря этому мы можем сравнивать прошлые значения с настоящими — это делается при помощи двух assert.

    const auto v0 = vector<int>{};
    const auto v1 = v0.push_back(15);
    const auto v2 = v1.push_back(16);
    const auto v3 = v2.set(0, 42);
    
    assert(v2.size() == v0.size() + 2);
    assert(v3[0] - v1[0] == 27);

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

    Другое важное свойство — структурный общий доступ (structural sharing). Теперь у нас не происходит копирования всех данных для каждой новой версии структуры данных. Даже при .push_back и .set копируются не все данные, а лишь небольшая их часть. Все имеющиеся у нас форки имеют общий доступ к компактному представлению, которое пропорционально количеству изменений, а не количеству копий. Отсюда также следует, что сравнение выполняется очень быстро: если всё хранится в одном блоке памяти, в одном указателе, то можно просто сравнить указатели и не исследовать элементы, которые находятся внутри них, в случае, если они равны.

    Поскольку такой вектор, как мне кажется, крайне полезен, я реализовал его в отдельной библиотеке: это immer — библиотека иммутабельных структур, проект с открытым кодом.

    При написании его мне хотелось, чтобы его использование было привычным для разработчиков на С++. Есть много библиотек, которые реализуют концепции функционального программирования в С++, но при этом создается впечатление, что разработчики пишут для Haskell, а не для С++. Это создает неудобства. Кроме того, я добивался хорошей производительности. Люди используют С++, когда наличные ресурсы ограничены. Наконец, мне хотелось, чтобы библиотека была настраиваемой. Это требование связано с требованием производительности.

    В поисках волшебного вектора


    Во второй части доклада мы рассмотрим, как устроен этот иммутабельный вектор. Проще всего понять принципы такой структуры данных, начав с обычного списка. Если вы немного знакомы с функциональным программированием (на примере Lisp или Haskell), вы знаете, что списки — наиболее часто встречающиеся иммутабельные структуры данных.



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



    Также можем создать форк реальности, то есть создать новый список, у которого то же окончание, но отличающееся начало.

    Такие структуры данных изучаются уже давно: Крис Окасаки (Chris Okasaki) написал основополагающую работу Purely Functional Data Structures. Кроме того, весьма интересна предложенная Ральфом Хинце (Ralf Hinze) и Россом Патерсоном (Ross Paterson) структура данных Finger Tree. Но для С++ такие структуры данных подходят плохо. Они используют небольшие узлы, а мы знаем, что в С++ небольшие узлы означают отсутствие эффективности кэширования.

    Кроме того, они зачастую полагаются на свойства, которых у С++ нет, например, отложенность (laziness). Поэтому для нас значительно полезнее работа Фила Бэгуэлла (Phil Bagwell) по иммутабельным структурам данных — ссылка, написанная в начале 2000-х, а также труд Рича Хики (Rich Hickey) — ссылка, автора языка Clojure. Рич Хики создал список, который на самом деле является не списком, а основан на современных структурах данных: векторах и хэш-мэпах. Эти структуры данных обладают эффективностью кэширования и прекрасно взаимодействуют с современными процессорами, для которых нежелательно работать с небольшими узлами. Такие структуры вполне можно использовать в С++.

    Как построить иммутабельный вектор? В основе любой структуры, хотя бы отдаленно напоминающей вектор, должен быть массив. Но массив не обладает структурным общим доступом. Чтобы изменить любой элемент массива, при этом не теряя свойства персистентности, необходимо скопировать весь массив. Чтобы не делать этого, массив можно разбить на отдельные куски.

    Теперь при обновлении элемента вектора нам необходимо скопировать только один кусок, а не весь вектор. Но сами по себе такие куски не являются структурой данных, они должны быть так или иначе объединены. Поместим их в другой массив. Вновь возникает та проблема, что массив может оказаться очень большим, и тогда копирование его опять займёт слишком много времени.

    Поделим и этот массив на куски, поместим их вновь в отдельный массив, и повторим эту процедуру до тех пор, пока не останется один корневой массив. Получившаяся структура называется дерево остатков. Это дерево описывается константой M = 2B, то есть показатель ветвления дерева (branching factor). Этот показатель ветвления должен быть степенью двойки, и мы очень скоро узнаем, почему. В примере на слайде использованы блоки из четырех символов, но на практике используются блоки размером в 32 символа. Существуют эксперименты, при помощи которых можно найти оптимальный размер блока для определенной архитектуры. Это позволяет добиться наилучшего соотношения структурного общего доступа и времени доступа: чем дерево ниже, тем меньше время доступа.

    Читая это, разработчики, пишущие на С++, наверное, думают: но ведь любые структуры на основе дерева очень медленные! Деревья растут при увеличении числа элементов в них, и из-за этого ухудшается время доступа. Именно поэтому программисты предпочитают std::unordered_map, а не std::map. Спешу вас успокоить: наше дерево растёт очень медленно. Вектор, содержащий все возможные значения 32-битного int, в высоту содержит всего 7 уровней. Можно экспериментально показать, что при таком размере данных отношение кэша к объему нагрузки значительно больше влияет на производительность, чем глубина дерева.

    Давайте посмотрим, как выполняется доступ к элементу дерева. Предположим, необходимо обратиться к элементу 17. Мы берём бинарное представление индекса и разбиваем его на группы размером с фактор ветвления.



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



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

    Кстати говоря, существует значительно более старая структура данных, которая очень похожа на ту, которую я описал. Это страницы памяти (memory pages) с деревом таблицы страниц. Управление ей тоже осуществляется при помощи вызова fork.

    Попытаемся улучшить нашу структуру данных. Предположим, нам необходимо соединить два вектора. Пока что описанная структура данных обладает теми же ограничениями, что и std::vector: в ней есть пустые ячейки в самой правой её части. Поскольку структура идеально сбалансирована, эти пустые ячейки не могут находиться в середине дерева. Поэтому если существует второй вектор, который мы хотим объединить с первым, нам необходимо будет скопировать элементы в пустые ячейки, что создаст пустые ячейки во втором векторе, и в итоге придётся копировать целиком второй вектор. Такая операция обладает вычислительной сложностью O(n), где n – размер второго вектора.

    Попытаемся добиться лучшего результата. Существует изменённый вариант нашей структуры данных, который называется relaxed radix balanced tree. В этой структуре узлы, которые не находятся на самом левом пути, могут иметь пустые ячейки. Поэтому в таких неполных (или расслабленных) узлах необходимо подсчитывать размер поддерева. Теперь можно выполнить сложную, но логарифмическую операцию объединения. Эта операция постоянной временной сложности — О(log(32)). Поскольку деревья неглубокие, время доступа является константой, хоть и относительно большой. Благодаря тому, что у нас есть такая операция объединения, relaxed вариант этой структуры данных называют сливающимся (confluent): помимо того, что она персистентная, и можно сделать её форк, две таких структуры можно объединить в одну.



    В том примере, с которым мы до сих пор работали, структура данных очень аккуратная, но на практике реализации в Clojure и других функциональных языках выглядят иначе. В них создаются контейнеры для каждого значения, то есть каждый элемент в векторе находится в отдельной ячейке, а листовые узлы содержат указатели на эти элементы. Но такой подход крайне неэффективный, в С++ обычно не помещают каждое значение в контейнер. Поэтому будет лучше, если эти элементы будут находиться в узлах напрямую. Тогда возникает другая проблема: у разных элементов разные размеры. Если элемент по размеру совпадает с указателем, наша структура будет выглядеть так, как показано ниже:



    Но если элементы обладают большим размером, то структура данных теряет измеренные нами свойства (время доступа О(log(32)()), потому что копирование одного из листов теперь занимает больше времени. Поэтому я изменил эту структуру данных так, чтобы при увеличении размера содержащихся в ней элементов уменьшалось количество этих элементов в листовых узлах. Напротив, если элементы маленькие, то их теперь может поместиться больше. Новый вариант дерева называется embedding radix balanced tree. Оно описывается уже не одной константой, а двумя: одна из них описывает внутренние узлы, а вторая — листовые. Реализация дерева в С++ может рассчитать оптимальный размер листового элемента в зависимости от размеров указателей и самих элементов.

    Наше дерево работает уже весьма неплохо, но его ещё можно улучшить. Взглянем на функцию, похожую на функцию iota:

    vector<int> myiota(vector<int> v, int first, int last)
    {
        for (auto i = first; i < last; ++i)
            v = v.push_back(i);
        return v;
    }
    

    Она принимает на вход vector, выполняет push_back в конец вектора для каждого целого числа между first и last, и возвращает то, что получилось. С правильностью этой функции всё в порядке, но она работает неэффективно. Каждый вызов push_back копирует самый левый блок без всякой нужды: следующий вызов выполняет push ещё одного элемента и копирование повторяется заново, а скопированные предшествующим методом данные удаляются.

    Можно попробовать другую реализацию этой функции, в которой мы отказываемся от персистентности внутри функции. Можно использовать transient vector с мутабельным API, который совместим с API обычного vector. Внутри такой функции каждый вызов push_back изменяет структуру данных.

    vector<int> myiota(vector<int> v, int first, int last)
    {
        auto t = v.transient();
        for (auto i = first; i < last; ++i)
            t.push_back(i);
        return t.persistent();
    }
    

    Такая реализация более эффективная, и она позволяет повторно использовать новые элементы на самом правом пути. В конце функции выполняется вызов .persistent(), который возвращает иммутабельный vector. Возможные побочные эффекты остаются невидимы извне функции. Изначальный vector как был, так и остается иммутабельным, изменяются только данные, созданные внутри функции. Как я уже говорил, важное преимущество такого подхода в том, что можно использовать std::back_inserter и стандартные алгоритмы, которые требуют мутабельных API.

    Рассмотрим другой пример.

    vector<char> say_hi(vector<char> v)
    {
        return v.push_back('h')        
                .push_back('i')        
                .push_back('!');       
    }
    

    Функция не принимает и возвращает vector, а внутри выполняется цепочка вызовов push_back. Здесь, как и в прошлом примере, может происходить ненужное копирование внутри вызова push_back. Обратим внимание, что первое значение, с которым выполняется push_back, является именованным (named value), а остальные — r-value, то есть анонимные ссылки. Если у вас используется подсчёт ссылок, то метод push_back может обратиться к счетчикам ссылок для узлов, для которых выделена память в дереве. И в случае с r-value, если количество ссылок является единицей, становится ясно, что никакая другая часть программы к этим узлам не обращается. Здесь производительность ровно такая же, как и в случае с transient.

    vector<char> say_hi(vector<char> v)
    {
        return v.push_back('h')        ⟵ named value: v
                .push_back('i')        ⟵ r-value value
                .push_back('!');       ⟵ r-value value
    }
    

    Далее, чтобы помочь компилятору мы можем выполнить move(v), поскольку v больше нигде в функции не используется. У нас появилось важное преимущество, которого не было в transient варианте: если функции «say_hi» передать возвращенное значение другого «say_hi», то не возникнет никаких лишних копий. В случае же с transient существуют границы, на которых может происходить лишнее копирование. Иначе говоря, мы имеем персистентную, иммутабельную структуру данных, производительность которой зависит от действительного объема общего доступа в рантайме. Если же общего доступа нет, то производительность будет такой же, как и у мутабельной структуры данных. Это крайне важное свойство. Пример, который я вам уже показывал выше, можно переписать с методом move(v).

    vector<int> myiota(vector<int> v, int first, int last)
    {
        for (auto i = first; i < last; ++i)
            v = std::move(v).push_back(i);
        return v;
    }
    

    До сих пор мы говорили о векторах, а помимо них есть ещё и хэш-мэпы. Им посвящён очень полезный доклад Фила Нэша (Phil Nash): The holy grail. A hash array mapped trie for C++. Там описываются хэш-таблицы, реализованные на основе тех же принципов, о которых я сейчас говорил.

    Уверен, у многих из вас есть сомнения относительно производительности подобных структур. Быстро ли они работают на практике? Я провел множество тестов, и вкратце мой ответ: да. Если вы хотите подробнее познакомиться с результатами тестирования, они опубликованы в моей статье для International Conference of Functional Programming 2017. Сейчас, я думаю, лучше обсудить не абсолютные значения, а то влияние, которое эта структура данных оказывает на систему в целом. Конечно же, update нашего вектора выполняется медленнее, поскольку необходимо скопировать несколько блоков данных и выделить память для других данных. А вот обход нашего вектора выполняется почти с такой же скоростью, как и обычного. Мне было очень важно этого добиться, поскольку чтение данных выполняется значительно чаще, чем их изменение.

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

    EWIG


    Не буду голословным и продемонстрирую мою структуру данных на примере. Я написал небольшой текстовый редактор. Это интерактивный инструмент под названием ewig, в нём документы представлены иммутабельными векторами. У меня на диске сохранена копия всей википедии на эсперанто, она весит 1 гигабайт (вначале я хотел скачать английскую версию, но она чересчур уж большая). Каким бы текстовым редактором вы ни пользовались, я уверен, что этот файл ему не понравится. А при загрузке этого файла в ewig его сразу же можно редактировать, потому что загрузка идет асинхронно. Навигация файла работает, ничего не висит, нет mutex, нет синхронизации. Как видим, загруженный файл занимает 20 млн. строк кода.

    Прежде, чем рассматривать самые важные свойства этого инструмента, обратим внимание на забавную деталь.



    В начале строки, выделенной белым в нижней части изображения, вы видите два дефиса. Этот UI, скорее всего, знаком пользователям emacs, дефисы там означают, что документ никак не был изменён. Если же внести какие-либо изменения, то вместо дефисов отображаются звездочки. Но, в отличие от других редакторов, если в ewig затем удалить эти изменения (не отменить, а именно удалить), то вместо звёздочек вновь отобразятся дефисы, поскольку в ewig сохраняются все предшествующие версии текста. Благодаря этому не нужен специальный флаг, показывающий, изменён ли документ: наличие изменений определяется сравнением с исходным документом.

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

    Возврат к архитектуре, основанной на значениях




    Начнём с того, как к этой архитектуре нельзя вернуться: с помощью обычных Controller, Model и View в стиле Java, которые чаще всего и используются для интерактивных приложений в С++. Ничего плохого в них нет, но для нашей проблемы они не подходят. С одной стороны, паттерн Model-View-Controller позволяет добиться разделения задач, но с другой, каждый из этих элементов является объектом, как с объектно-ориентированной точки зрения, так и с точки зрения С++, то есть это участки памяти с мутабельным состоянием. View знает о Model; что значительно хуже — Model косвенно знает о View, потому что почти наверняка существует некоторый callback, через который View получает оповещение при изменении Model. Даже при лучшей реализации объектно-ориентированных принципов мы получаем множество взаимных зависимостей.



    По мере роста приложения и добавления новых Model, Controller и View возникает ситуация, когда для изменения какого-либо сегмента программы необходимо знать о всех связанных с ним частях, обо всех View, которые получают оповещение через callback, и т. д. В итоге за всеми этими зависимостями начинает проглядывать знакомый нам всем макаронный монстр.

    Возможна ли другая архитектура? Есть альтернативный подход к паттерну Model-View-Controller, который называется «Архитектура с однонаправленным потоком данных». Это понятие придумал не я, оно используется довольно часто в веб-разработке. В Facebook это называется архитектура Flux, но в С++ пока что она не применяется.



    Элементы такой архитектуры нам уже знакомы: Action, Model и View, но значение блоков и стрелок другое. Блоки являются значениями, а не объектами и не участками с мутабельным состоянием. Это касается даже View. Далее, стрелки не являются ссылками, поскольку без объектов не может быть ссылок. Здесь стрелки — это функции. Между Action и Model существует функция update, которая принимает текущую Model, т. е. текущее состояние мира, и Action, которая является представлением некоторого события, например, щелчка мышкой, или события другого уровня абстракции, например, вставки элемента или символа в документ. Функция update обновляет документ и возвращает новое состояние мира. Model соединяется с View функцией render, который принимает Model и возвращает представление. Для этого требуется фреймворк, в котором можно представлять View в качестве значений.

    При веб-разработке это делает React, но в С++ пока ничего подобного нет, хотя кто знает, если найдутся желающие заплатить мне, чтобы я написал нечто подобное, то может в скором времени и появится. Пока же можно пользоваться Immediate mode API, в которых функция draw позволяет создавать значение в качестве побочного эффекта.

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

    application update(application state, action ev);
    
    void run(const char* fname)
    {
        auto term  = terminal{};
        auto state = application{load_buffer(fname), key_map_emacs};
        while (!state.done) {
            draw(state);
            auto act = term.next();
            state = update(state, act);
        }
    }
    

    За исключением асинхронного сохранения и загрузки это код, который используется в только что представленном редакторе. Здесь есть объект terminal, который позволяет выполнять чтение и запись из командной строки. Далее, application — это значение Model, в нём сохраняется всё состояние приложения. Как видно вверху экрана, есть функция, которая возвращает новую версию application. Цикл внутри функции выполняется до тех пор, пока приложению не нужно будет закрыться, т. е. пока !state.done. В цикле происходит отрисовка нового состояния, затем выполняется запрос следующего события. Наконец, состояние сохраняется в локальной переменной state, и цикл запускается снова. У этого кода есть очень важное достоинство: лишь одна мутабельная переменная существует на протяжении всего выполнения программы, это объект state.

    Разработчики Clojure называют это одноатомной архитектурой (single-atom architecture): на всё приложение есть одна единственная точка, через которую выполняются все изменения. Логика приложения никак не участвует в обновлении этой точки, это делает специально для этого предназначенный цикл. Благодаря этому логика приложения целиком состоит из чистых функций, вроде функции update.

    При таком подходе к написанию приложений меняется и образ мышления о софте. Работа теперь начинается не с UML-диаграммы интерфейсов и операций, а собственно с данных. Здесь есть некоторое сходство с data-oriented design. Правда, data-oriented design обычно используется с целью получения максимальной производительности, здесь же помимо скорости мы стремимся к простоте и правильности. Акцент немного другой, но есть важные сходства в методологии.

    using index = int;
    
    struct coord
    {
        index row = {};
        index col = {};
    };
    
    using line = immer::flex_vector<char>;
    using text = immer::flex_vector<line>;
    
    struct file
    {
        immer::box<std::string> name;
        text content;
    };
    
    struct snapshot
    {
        text content;
        coord cursor;
    };
     
    struct buffer
    {
        file from;
        text content;
        coord cursor;
        coord scroll;
        std::optional<coord> selection_start;
        immer::vector<snapshot> history;
        std::optional<std::size_t> history_pos;
    };
    
    struct application
    {
        buffer current;
        key_map keys;
        key_seq input;
        immer::vector<text> clipboard;
        immer::vector<message> messages;
    };
    
    struct action { key_code key; coord size; };

    Выше представлены основные типы данных нашего приложения. Основное тело приложения состоит из line, которая является flex_vector, а flex_vector, это vector, для которого можно выполнять операцию объединения. Далее, text является вектором, в котором хранятся line. Как видим, это очень простое представление текста. Text сохраняется при помощи file, у которого есть имя, т. е. адрес в файловой системе, и собственно text. В file используется еще один тип, простой но очень полезный: box. Это контейнер на один элемент. Он позволяет поместить в кучу и перемещать объект, копирование которого может быть слишком ресурсозатратным.

    Другой важный тип: snapshot. На основе этого типа действует функция отмены. В нём содержится документ (в виде text) и положение курсора (coord). Это позволяет возвращать курсор на то положение, в котором он был во время правки.

    Следующий тип — buffer. Это термин из vim и emacs, так там называются открытые документы. В buffer есть файл, из которого был загружен текст, а также содержание текста — это позволяет проверять наличие изменений в документе. Для выделения части текста есть необязательная переменная selection_start, указывающая на начало выделения. Вектор из snapshot — это история текста. Заметьте, мы не используем паттерн Команда, история состоит только из состояний. Наконец, если только что была выполнена отмена, нам необходим индекс положения в истории состояний — history_pos.

    Следующий тип: application. В нём содержится открытый документ (buffer), key_map и key_seq для комбинаций клавиш, а также вектор из text для буфера обмена и другой вектор для сообщений, отображаемых внизу экрана. Пока что в дебютной версии приложения будет только один поток и один тип действий, принимающий на вход key_code и coord.

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

    Отмена


    Правильно написать отмену без соответствующей инфраструктуры не так-то просто. В моём редакторе я реализовал её по образцу emacs, так что вначале пару слов об основных ее принципах. Команда возврата здесь отсутствует, и благодаря этому нельзя потерять работу. Если необходимо сделать возврат, в текст вносится любое изменение, и тогда все действия отмены становятся снова частью истории отмены.



    Этот принцип изображен выше. Красный ромб здесь показывает позицию в истории: если только что не была выполнена отмена, красный ромб всегда в самом конце. Если выполнить отмену, ромб переместится на одно состояние назад, но одновременно в конец очереди добавится еще одно состояние — такое же, какое в данный момент видит пользователь (S3). Если выполнить отмену ещё раз и вернуться к состоянию S2, в конец очереди добавится состояние S2. Если теперь пользователь выполнит какое-то изменение, оно добавится в конец очереди как новое состояние S5, и на него будет перемещён ромб. Теперь при отмене прошлых действий вначале будут пролистаны прошлые действия отмены. Чтобы реализовать такую систему отмены, достаточно следующего кода:

    buffer record(buffer before, buffer after)
    {
        if (before.content != after.content) {
            after.history = after.history.push_back({before.content, before.cursor});
            if (before.history_pos == after.history_pos)
                after.history_pos = std::nullopt;
        }
        return after;
    }
    
    buffer undo(buffer buf)
    {
        auto idx = buf.history_pos.value_or(buf.history.size());
        if (idx > 0) {
            auto restore = buf.history[--idx];
            buf.content = restore.content;
            buf.cursor = restore.cursor;
            buf.history_pos = idx;
        }
        return buf;
      }
    

    Тут два действия, record и undo. Record выполняется при любой операции. Это очень удобно, поскольку нам нет необходимости знать, произошло ли какое-либо редактирование документа. Функция прозрачна для логики приложения. После любого действия функция проверяет изменился ли документ. Если изменение произошло, выполняется push_back содержания и положения курсора для history. Если действие не привело к изменению history_pos (то есть полученные на вход buffer не вызваны действием отмены), то history_pos присваивается значение null. Если же необходимо выполнить undo, мы проверяем history_pos. Если у него нет значения, мы считаем, что history_pos находится в конце истории. Если история отмены не пуста (то есть history_pos не в самом начале истории), выполняется отмена. Текущие content и cursor заменяются, и изменяется history_pos. Неотменяемость операции отмены достигается функцией record, которая также вызывается при операции отмены.

    Итак, мы имеем операцию undo, которая занимает 10 строк кода, и которую без изменений (или с минимальными изменениями) можно использовать практически в любом другом приложении.

    Путешествия во времени


    О путешествиях во времени. Как мы сейчас увидим, это тема, связанная с отменой. Я продемонстрирую работу фреймворка, который добавит полезную функциональность любому приложению с похожей архитектурой. Фреймворк здесь называется ewig-debug. В этой версии ewig включены некоторые возможности отладки. Сейчас из браузера можно открыть отладчик, в котором можно исследовать состояние приложения.



    Мы видим, что последним действием было изменение размера, поскольку я открыл новое окно, и мой диспетчер окон автоматически поменял размер уже открытого окна. Конечно, для автоматической сериализации в JSON мне пришлось добавить аннотацию для struct из специальной библиотеки reflection. Но в остальном система вполне универсальная, её можно подключить к любому подобному приложению. Теперь в браузере можно увидеть всё совершённые действия. Конечно, есть и начальное состояние, у которого нет действия. Это состояние, которое было до выполнения загрузки. Больше того, двойным щелчком мыши я могу возвратить приложение к предыдущему состоянию. Это очень полезный инструмент отладки, который позволяет отследить возникновение неисправности в приложении.

    Если вам интересно, то можете послушать мой доклад на CPPCON 19, The most valuable values, там я в подробностях рассматриваю этот отладчик.



    Кроме того, там подробнее обсуждается архитектура, основанная на значениях. В нём я также рассказываю, как следует реализовывать действия и организовывать их иерархически. Это обеспечивает модульность системы и позволяет не держать всё в одной большой функции update. Кроме того, в том докладе говорится об асинхронности и о многопоточной загрузке файла. Есть ещё одна версия этого доклада, в которой полчаса дополнительного материала — Postmodern immutable data structures.


    Подведем итоги


    Думаю, пришло время подвести итоги. Приведу цитату Энди Винго (Andy Wingo) — он отличный разработчик, посвятил много времени V8 и компиляторам в целом, наконец, он занимается поддержкой Guile, реализацией Scheme для GNU. Недавно он написал в своём твиттере: «Чтобы добиться небольшого ускорения работы программы, мы измеряем каждое небольшое изменение и оставляем только те, которые дают положительный результат. А действительно существенного ускорения мы добиваемся, вслепую, вкладывая большие усилия, не имея 100%-й уверенности и руководствуясь только интуицией. Какая странная дихотомия».

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

    Juan Puente выступил на конференции C++ Russia 2019 Moscow и рассказал о структурах данных, которые позволяют делать интересные вещи. Часть магии этих структур кроется в сopy elision — именно об этом на грядущей конференции расскажут Антон Полухин и Роман Русяев. За обновлениями программы следите на сайте.
    JUG Ru Group
    Конференции для программистов и сочувствующих. 18+

    Комментарии 57

      0
      очень интересно, спасибо за инфу
        +8
        Я правильно понял, что свой вектор не гарантирует размещения подряд в памяти и потому не является полноценной заменой контейнеру из std?
        Описание на английском
        The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets to regular pointers to elements. This means that a pointer to an element of a vector may be passed to any function that expects a pointer to an element of an array.

        В таком случае не очень понятно зачем брать интерфейс именно vector в качестве отправной точки и менять семантику, называя вектором то, что в мире плюсов вектором не является.
        Возможно, что для тренировки пользователей библиотеки и их способности вчитываться в документацию.
          0

          Вот тоже сразу бросилось в глаза. Доклад интересный, но может сложиться ложное впечатление "меняем стандартный вектор на иммутабельное творение автора, и здравствуй безопасная многопоточность".

            +1

            У меня почему-то не возникло с этим проблем, потому что логика была такая: вам нужен вектор с дешевым копированием, вот он immer::vector. То есть интерфейс в виде методов именно от ветктора, однако под капотом другая структура данных. Вроде как посмотрев доклад я бы и не ожидал drop-in replacement для std::vector.

              +3
              В мире плюсов контейнер vector хранит данные последовательно в памяти.
              Интерфейс от вектора предполагает, что он ведет себя как вектор. И то, что автор начинает с листов, потом сравнивает с вектором, но ограничивает требования только работой с итераторами тоже вносит путаницу.
              Плюс комментраии типа «игнорируйте строгую математическую сложность» — тоже не радуют.

                0

                В плюсах std::vector является тем чем вы считаете оно является, immer::vector не обязан быть таким же. В том что его назвали vector есть логика, это не ассоциативный неупорядоченный контейнер с random access доступом — т.е. математично это вполне вектор. Возможно есть более удачное имя, если есть идеи я думаю всегда предложить его автору через issue на github. Возможно еще придется придумать название для immer::map и immer::set.

                  0
                  Именно так. Автор начинает сравнивать с вектором(в самом начале при «наивной реализации»
                  цитата
                  Это бывает непросто, но при нашем подходе это тривиальная задача: у нас есть std::vector с различными состояниями различных копий документа.
                  ), у которого довольно строгое ограничение на размещение в памяти и приводит свою реализацию, как решающую проблему с «неоптимальным копированием» именно в озвученном контейнере. Либо надо было сравнивать с реализацией list/map/set из std/boost/whatever, либо не упоминать вектор как «неоптимальное решение».
                    +2
                    В плюсах std::vector является тем чем вы считаете оно является, immer::vector не обязан быть таким же. В том что его назвали vector есть логика, это не ассоциативный неупорядоченный контейнер с random access доступом — т.е. математично это вполне вектор.

                    В плюсах то что Вы называете «вектором» называется std::deque.
                    А std::vector гарантирует что данные лежат в памяти последовательно и это существенно используется.
                  +4
                  storing the data in contiguous chunks of 2BL elements. By default, when sizeof(T) == sizeof(void*) then B=BL=5, such that data would be stored in contiguous chunks of 32 elements.


                  Судя по всему immer::vector в с++ называется deque.
                  +1

                  Думаю потому что затраты времени на операции у него ближе к вектору, чем к списку.

                  +1

                  Flux приехал в мир C++?

                    +1
                    Тоже показалось, даже вспомнил про React Redux)
                    +1
                    Вроде Rust чуть более чем полностью построен на этой концепции, только вот на пару порядков (если верить его адептам) удобнее крестов в плане если ружьё в ногу направишь, то до курка просто не дотянешься…

                    P.S. в чём такие красивые диаграмки рисуют?
                      +1

                      Если не нужен интероп с С и прочими частями, которые ожидают последовательного размещения в памяти — то, конечно, подробные реализации контейнеров — отличный вариант упростить жизнь и себе, и компилятору.
                      Ну и у плюсов(как экосистем) есть проблема с поддержанием обратной совместимости с условным "стандартом 98 года", потому довольно тяжело идут нововведения, особенно в такие фундаментальные сущности как std:: vector, что, снова, позволяет Rust и подобным быть намного более гибкими.

                        +1
                        то до курка просто не дотянешься

                        Нет, если продолжать аналогию, то там просто предохранитель стоит. Кроме того всем на входе зачитали технику безопасности и табличку unsafe поставили.

                          –6
                          до курка просто не дотянешься

                          Нет, просто на курок кто-то от души плюнул, поэтому первый раз или два ты инстинктивно отдёрнешь палец. Потом, правда, быстро привыкнешь лезть в это в скафандре.
                            +2

                            Rust в плане иммутабильности вроде бы ничем особым от C++ не отличается, или я чего-то не понимаю. Вектор в расте такой же как вектор в плюсах, мутабельные данные, используйте .clone() чтобы это было иммутабельно. В C++ автор этого доклада сделал библиотеку immer которая типа должна поддерживать иммутабельность эффективнее чем .clone(). В расте вроде тоже можно найти библиотеку которая делает аналогичную структуру данных.

                              +2

                              В Rust совершенно другая концепция — проверка корректности совместного доступа к памяти на уровне компилятора.
                              Иммутабельные данные — это скорее про Haskell.

                                0

                                Так там по-умолчанию все данные подразумеваются иммутабельными если явно не указано обратного. Так что оно by design использует эту концепцию.

                                  +2

                                  Концепция автора немного в другом. Раст не даст вам создать две мутабельные ссылки на вектор, например, так что вам нужно будет решать эту проблему: например вы думать как безопасно расшарить эти данные чтобы вас borrow checker не ругал (через interior mutability с рантайм костами, например) или вы будете использовать .clone(). В обоих случаях получается как в плюсах или геморно (но безопаснее чем в плюсах) или медленно. У раст есть свой crate для immutable data structures, который насколько я понимаю решает аналогичную проблему (https://docs.rs/im/14.2.0/im/). Т.е. автор предлагает использовать подход с меньшим геморроем и более оптимальный чем обычный .clone()

                                    0

                                    Ну вот давайте сравним. Одна и та же операция set.


                                    C++: https://sinusoid.es/immer/containers.html#_CPPv2NK5immer6vector3setE9size_type10value_type
                                    Rust: https://docs.rs/im/14.2.0/im/struct.Vector.html#method.set


                                    В C++ надо обязательно писать так: v = v.set(index, value)
                                    В Rust можно написать так: v.set(index, value), а освободившееся возвращаемое значение используется чтобы вернуть прошлое значение ячейки.


                                    Почему такое различие в API? Потому что Rust может проверить, что других ссылок на v не осталось, а C++ — нет.

                                      0

                                      Я так понимаю, функциональность этого Vector из im для раста и обсуждаемого "вектора" из C++ все ж не эквивалентна. Насколько я понимаю, то, что делает вектор из im — это реализует implicit sharing для хранимых данных а-ля Qt, с lazy cloning. Это не то же самое, что иммутабельность самого вектора, что обеспечивает обсуждаемый в статье "вектор" из C++. Продемонстрированная вами разница в API обусловлена главным образом этим. То есть если этот вектор из im поместить в контейнер с interior mutability, то ожидать, что он не будет меняться, нельзя. Но я так понимаю, что это нормально, так как изначально цель его создания была совсем другая.

                                        +1

                                        Если у вас есть контейнер с interior mutability — то вы никак не отличите ситуацию "там лежит изменившийся вектор" от ситуации "там лежит новый иммутабельный вектор" (до тех пор, пока у вектора нет уникального адреса в памяти).

                                        0
                                        Почему такое различие в API? Потому что Rust может проверить, что других ссылок на v не осталось, а C++ — нет.

                                        Вы предполагаете что immer добавили immutable API из-за ограничений (точнее отсутствия оных) C++, я думаю что может да, а может и нет. Я думаю что у функционального стиля могут быть свои фишки.


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

                                      +2

                                      В rust ничего не мешает взять и написать let mut, мутабельность там в принципе возможна, и, конечно, активно используется. Корректность совместного доступа обеспечивается компилятором с помощью borrow checker'а.
                                      Рассматриваемые же структуры данных вообще не требуют писать let mut при их использовании. Они изначально потокобезопасны, без всяких borrow checker'ов. За счёт несколько меньшей производительности, да (но не таких тормозов, как если бы каждый раз копировался весь массив).

                                        0

                                        В терминах обсуждаемой библиотеки, в Rust нет необходимости разделять иммутабельные структуры и их transients: обе сущности спокойно живут под одним и тем же именем. И возможность так делать даёт именно что borrow checker.

                                          –1
                                          мутабельность там в принципе возможна

                                          Скажем, в плюсах даже с его иммутабельными данными почти наверняка возможна магия


                                          const_cast<T*>
                                          #include <iostream>
                                          #include <vector>
                                          
                                          int main()
                                          {  
                                              unsigned n;
                                              std::cin >> n;
                                              using Vec = std::vector<unsigned>;
                                              const Vec vec;
                                              // vec.push(n); // так - ошибка компиляции
                                              const auto* cvecptr = &vec;
                                              auto vecptr = const_cast<Vec*>(cvecptr);
                                              for (unsigned i = 0; i < n; ++i) {
                                                vecptr->push_back(n);// а так - нормально
                                              }
                                              std::cout << vec.size() <<std::endl;
                                              return 0;
                                          }
                                          

                                          В расте такое разве что с unsafe провернуть возможно, если не вовсе только со внешними байндингами к тем же плюсам.


                                          Как вариант иммутабельных структур наверное можно привести кучку gc-арен на расте, которые выделяются лениво раз и больше не меняются.


                                          За счёт несколько меньшей производительности

                                          Ржавый Arc тоже не бесплатный, но в сравнении с оверхедом плюсов наверняка дешевле. Ну, и ниже сбросили там ржавую вариацию списков и и всяких деревьев. Ваша точка зрения понятна.

                                            0
                                            Скажем, в плюсах даже с его иммутабельными данными почти наверняка возможна магия

                                            Невозможна, это UB.

                                              0

                                              Вы хотели сказать: такая магия возможна, но это UB. Компилируется и выполняется. В данном примере даже корректно (на определённом компиляторе при определённых флагах и т.д).

                                                0

                                                Нет, я хотел сказать именно то, что написано в предыдущем комментарии.


                                                В коде на C++ UB не бывает, поэтому этот код не на C++ и демонстрировать что бы то ни было в контексте возможностей C++ он не может.

                                                  0

                                                  Согласен по сути, уточнил бы что код с UB не соответствует стандарту C++, а потому не является репрезентативным примером.

                                                    +2

                                                    Проблема этого определения в том, что код на C++ визуально неотличим от кода с UB. Помимо этого можно заметить, что количество серьёзных программ, написанных на C++ пренебрежимо мало.

                                                      0
                                                      Проблема этого определения в том, что код на C++ визуально неотличим от кода с UB.

                                                      Увы, такое определение дал комитет по стандартизации C++.


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

                                      +1

                                      Не хватает сравнений производительности с std::vector и с std::vector с мьютексами в реальных случаях.


                                      На scala эти ваши иммутабельные структуры данных (не только Vector) заметно проигрывают мутабельным по скорости. Мне не понравилось.
                                      Я пришёл к решению использовать мутабельные структуры, но оставлять их изменения лишь в месте, где структура создаётся, например. При совместном многопоточном доступе просто используется только чтение, но не запись, тех же мутабельных структур данных, иногда через иммутабельные адаптеры. Обмен между потоками реализуется какой-либо передачей сообщений, да хоть через Future, а не изменением состояния.
                                      Подход rust'а с проверкой доступа при компиляции, опять же, менее затратен в рантайме (вообще не затратен).


                                      Интересно, есть ли более-менее реальные примеры, где полная иммутабельность структур данных оправдана?

                                        0

                                        Как я понял посыл в том чтобы упростить код программы. Автор по сути говорит, смотрите, если вы будете использовать данные by value, вы сможете вот так упростить код вашей программы. А если вас расстраивает что вы будете копировать большие коллекции, то вот вам оптимизация в виде immer.


                                        Если сложность работы с mutable типами вас не очень парит, то и смысла видимо нет. Я смотрел доклад какое-то время назад и мне концепция показалась интересной чтобы попробовать где-нибудь.

                                          0
                                          Вообще он говорил в докладе, что оно benchmark-driven.
                                          Что нашел по ссылке с github-а
                                          public.sinusoid.es/misc/immer/reports
                                            0

                                            Я не совсем понял с чем вы спорите.

                                          0
                                          Не хватает сравнений производительности с std::vector и с std::vector с мьютексами в реальных случаях.


                                          Автор просто взял похожее название (по-моему зря) — сравнивать с std::vector смысла никакого нет, конечно же std::vector будет производительней.

                                          Интересно, есть ли более-менее реальные примеры, где полная иммутабельность структур данных оправдана?

                                          Базы данных, например. Изоляция транзакций и всё такое.
                                            0
                                            Не хватает сравнений производительности с std::vector и с std::vector с мьютексами в реальных случаях.

                                            Особенно там, где компилятор может что-нибудь векторизовать, ага.

                                            +1
                                            А в геймдеве оно как-то применимо? Потому что подобные структуры данных очень бы помогли в майнкрафто-подобных играх, как мне кажется.
                                            чем условный 'майнкрафт' отличается от не менее условного 'батлфилда'
                                            Объемом постоянно изменяемых данных. Если во втором постоянно бегают только человечки и машинки, что есть не больше, чем пара мегабайт (в худшем случае). То у игр, с полностью изменяемым миром это десятки и сотни мегабайт. Причем изменяются эти данные с частотой 60 раз в секунд.

                                            Обычно это решается так:
                                            1) Один поток (который thread) на игровую логику и рендер (и похожие задачи, где надо всегда знать все состояние мира), что медленно, особенно на процессорах с низкой тактовой частотой, но большим количеством ядер.
                                            2) Двойная/тройная буферизация всего состояния мира (во всяких контер-страйках это не проблема, т.к. там постоянно меняются только переменные позиций игроков, что есть всего несколько килобайт.
                                            3) Всяческие замысловатые синхронизации с блокировками, что есть сложно для реализации и более подвержено багам, чем остальные варианты.
                                              0

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

                                                0
                                                Игровой движок и должен быть таким, по-хорошему. Иммутабельность позволяет распараллеливать код на кучу ядер. Чем сложнее игра, тем больше польза такого подхода.
                                                  0
                                                  Иммутабельность упрощает архитектуру софта, но у неё есть и цена. Цена, особенно невыносимая для разработчиков игр. Когда иммутабельные типы данных будут не только «достаточно быстрыми» но ещё и «не медленнее передачи указателя и захвата блокировки», тогда, и только тогда, можно говорить что эта парадигма «созрела».
                                                    0
                                                    При правильной реализации оверхед минимален, работать легко может быстрее чем с блокировками. Плюс стотыщ к надежности системы и огромная экономия времени на отладку которая позволяет освободившееся время потратить на более содержательную оптимизацию. Я правда не игры пишу, но 3d сканер строящий модель поверхности в реальном времени тоже высоконагруженная система :)
                                                      0
                                                      3d сканер строящий модель поверхности

                                                      Неужели у вас получилось иммутабельные структуры использовать так же быстро, как и мутабельные? Я пробовал в т.ч. и на всяких алгоритмах триангуляции — иммутабельные структуры были медленнее на полпорядка-порядок.

                                                        0
                                                        Ну просто так подставить иммутабельную структуру вместо мутабельной и получить ускорение действительно не получится, будет в разы медленее :). Но если изначально проектировать систему под иммутабельность данных и грамотно выбрать размер «иммутабельного блока» то работать все будет очень быстро. Оверхед будет, но не в разы и он иногда даже меньше чем оверхед от блокировок.
                                                          0
                                                          Ну просто так подставить иммутабельную структуру вместо мутабельной и получить ускорение действительно не получится, будет в разы медленее :)

                                                          Я делал ровно наоборот — подставлял мутабельную взамен иммутабельной и получал ускорение.


                                                          Но если изначально проектировать систему под иммутабельность данных

                                                          Это как? В неком алгоритме мне нужна функциональность таблицы. В scala тогда были иммутабельные и мутабельные treemap и мутабельный hashmap (позднее появился и иммутабельный hashmap). Пишем код на иммутабельных treemap — он явно тормозит, задействуем (мутабельный) hashmap — становится получше. Мутабельный TreeMap несколько быстрее, чем иммутабельный. Конечно, эксперимент не слишком чистый (hashmap вместо treemap всё-таки), но и mutable.Buffer вместо Vector как-то слишком быстр. Наверно, мои случаи как раз не те, в которых можно иммутабельность задействовать без потерь.
                                                          Но, в конце концов, на текущем железе нет ничего проще, чем выполнить команду mov, архитектура железа располагает к мутабельности, но не иммутабельности.

                                                            0
                                                            Иммутабельность мне нужна только там где идет разделение данных между разными потоками. Это наверное не единственный use-case для иммутабельных структур, но для меня он основной. А дальше Вашу задачу надо описывать в терминах какие потоки пишут в таблицу а какие читают — от этого зависит то каким будет решение задачи. Для одного потока, например, иммутабельную структуру делать заведомо бессмысленно.

                                                            Конечно, эксперимент не слишком чистый (hashmap вместо treemap всё-таки),

                                                            Ну дык у Вас есть и «чистая» версия: Мутабельный TreeMap несколько быстрее, чем иммутабельный

                                                            У нас одна из основных структур данных, к слову — иммутабельный hashmap. Отлично работает.
                                                0
                                                В бухгалтерии и в банках это должно быть давно реализовано, ведь банковские операции типа перевода денег и бухгалтерские проводки удалять или редактировать нельзя, там можно только добавлять корректирующие операции. Обычно, это делают в базе данных, но наверное есть и c++ библиотеки для этого.
                                                  0
                                                  Да и собственно базы данных с их транзакциями должны реализовывать похожий принцип.
                                                  0
                                                  Я не очень понял, (скорее всего, в силу своей глупости), эти структуры потокобезопасны? В том смысле, что
                                                  v1 = v0.push_back(threadId);
                                                  

                                                  или
                                                  v1 = v0.set(0, threadId);
                                                  

                                                  не «поломают» контейнер, будучи вызванными из нескольких потоков? Я вроде бы понимаю, что мы в разные потоки передаем условно разные «копии» одних и тех же данных. Но вроде как clone или move без изменений не меняют ничего в памяти. Просто это выглядит так, будто остался один шаг до реализации software transaction memory
                                                    0
                                                    Насколько я понимаю, это зависит от выбранной memory policy для контейнера. Там есть две политики — политика управления кучей и политика подсчета ссылок. Скажем, есть immer::refcount_policy, которая использует атомики для подсчета ссылок на элементы контейнера, а есть immer::unsafe_refcount_policy, которая использует просто int'ы, она быстрее, но не thread safe. По умолчанию используются immer::free_list_heap_policy для управления кучей и immer::refcount_policy для подсчета ссылок, оба thread safe.
                                                      0
                                                      То есть, грубо говоря, можно сделать
                                                      start transaction

                                                      commit or rollback (а тут проверить, не разошлись ли «головы»)
                                                        0
                                                        Хотя нет, туплю. В теории единственный писатель должен успешно завершить транзакцию, а читатели — откатиться. Тут этого не будет похоже.
                                                          0
                                                          Ну тут как бы писатель всегда создает «свою» персональную версию самим фактом записи, а у читателей всегда остается та же версия, что у них была изначально, неважно, что при этом делает писатель и есть ли он вообще.
                                                            0
                                                            Ага. Не STM в общем
                                                    0

                                                    Симпатичные блок-схемы, через какую программу такие возможно создать?

                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                    Самое читаемое