Здравствуйте, Sinclair, Вы писали:

S>Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?

Если поля описаны как const, то мутировать их никак.
Есть еще ключевое слово mutable — это когда к полю можно обращаться из const this метода.

Например, интрузивные счётчики ссылок часто описывают как mutable, потому что они работают над совместным владением объектами, без вмешательства в потенциально read-only семантику прикладных данных. Чаще всего такие счётчики размещают как приватные в неких базовых классах, т.е. эти счётчики недоступны затем наследуемому "прикладному" коду, предоставляя, однако, через функциональность этих базовых классов требуемую инфраструктуру по ссылочному шаренью целевых данных.


V>>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
V>>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.

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


V>>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
S>Счётчики ссылок, очевидно, дёргаются при любом копировании.

Дергаются не у всего дерева, а только у непосредственных детей вновь создаваемых узлов при перестроении, а это log N.
Т.е. еще зависит от вида дерева — RB, AVL или еще какие с арностью более 2 — тогда будет еще меньше дерганий счётчиков ссылок.

Плюс, в промежуточных операциях (при нескольких поворотах, например, вставка может породить два поворота, а удаление из AVL до 5-ти поворотов) можно исключить дерганье счётчиков ссылок в процессе, пробежавшись по новым узлам уже по окончании операций.


S>Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.

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

И опять же, смотря как реализовано дерево. Ссылочные ноды RB-деревьев могут хранить value-кластер тройки узлов {R, B, R}, т.е. в общем случае меньше дерганий счетчиков ссылок (вдвое меньше "ссылочная" высота дерева), как и для более арных деревьев.


V>>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
V>>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
V>>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
S>Это если у вас хватает размера региона на полную работу алгоритма.

Память выделяется страницами, выделенные страницы хранятся по единственной ссылке, бо связаны в однонаправленный список.
Аллокаторы обычно настраиваются compile-time константами-параметрами, например, размером страницы и величиной выравнивания (выравнивание порой нужно не на слово, а на линейку кеша).

Эти техники, считай, обязательные в реализациях нейтивных веб-серверов, баз данных, компиляторов и т.д., бо региоальная память хорошо себя показывает в сценариях "выделить память для отдельной операции и всю её освободить по окончании операции". Боюсь даже представить, как работали бы БД или компиляторы без региональной памяти, на обычном malloc на каждый чих. ))

Плюс, в отличие от распределителей на основе пула ячеек одинакового размера (аллокатор по степени двойки связывает ячейки одинакового размера в линейные списки, где пустые ячейки друг на друга ссылаются, т.е. первое слово свободной ячейки интерпретируется как адрес следующей ячейки), у региональной памяти всё неплохо с локальностью. Зато плохо с долгоживучестью у grow-only аллокатора, поэтому сей подход и нашел себя в обслуживании указанных относительно короткоживущих сценариев.


S>Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.

А оно и не требуется.
Каждая трансформация — отдельная операция, т.е. для временных данных можно юзать такие аллокаторы, длительностью жизни в операцию.
Потом у аллокатора вызывается некий reset и он переиспользуется для другой операции и т.д.

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

Это ж азы, а не "уникальность".
Это сегодня мы разбалованы современными высокоуровневыми подходами...
В более хардокорном прошлом это всё из разряда не уникальности, а must have, то бишь, не новинка, а наоборот, традиции.


S>А как только вы исчерпали регион — добро пожаловать в честное копирование.

Регион — это несколько страниц.

Вот у тебя тройка указателей:

void * page_end;
void * cursor;
void * page_begin;

Курсор просто ползёт до page_end, после этого выделяется новая страница, а на старую ссылаются в первом слове новой страницы.
Соответственно, у первой выделенной страницы первое слово всегда null — конец списка.


V>>В целом оно на порядки эффективнее, чем в дотнете.
S>"В целом" — вряд ли. В частных случаях — может быть.

В целом — это сам этот подход.
Просто можно и его испортить, разумеется. ))

Например, в дотнете аллокатор расположен в TLS-слоте (что тоже далеко не верх эффективности — просто получить ссылку на аллокатор, у которого попросить память).
В твоей же реализации могут быть разные подходы — тоже на TLS или некий передаваемый в операции явно context (а в нём даже несколько таких аллокаторов для нескольких подсистем) и т.д.

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


S>То, что вы называете "региональной памятью", другие люди называют ареной

Регион, арена...
Термин не так давно устоялся, что забавно и то, из-за использованных идентификаторов в некоторых реализациях и языках.


S>и это, в целом, аналог поколений в современных GC, только на ручном приводе.

Не скажи...
Например, нулевое поколение — это просто список объектов с некоей "головы".
Затем уплотнения может и не быть (не было неявных освобождений), но голову по окончании цикла GC переназначат.

Сравнивать эти подходы сложновато, потому что в их основе лежат принципиально разные стратегии из-за принципиально разных принятых допущений.
"Просто другая стратегия", всё.

Не обязательно пытаться найти ассоциативную связь со знакомым материалом. ))
За одно только сязывание выделяемых объектов в списки в GC-системах убить мало. ))


S>И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными.

Ес-но, граф владения разрабатывается под механику этого владения.
А так-то можно на любой чих получить зацикливание на тех же счётчиках ссылок, привет VB/VBA. ))

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

Разумеется, автоматическое управление памятью кое-где сильно развязывает руки.
А кое-где сильно связывает.
Не изобрели еще серебрянной пули. ))


S>Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.

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

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


V>>merge — потому что такова природа сущности "множество". ))
S>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.

И чем плоха копия такого объекта:

class ImmutableSet<T> {
   const RBNode<T> * root_;   
};

где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.

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

Так для чего ж тогда ImmutableSortedSet<> объявлен ссылочным типом?
А, ну да, ну да...
— из-за встроенного дефолтного конструктора value-типов, который хоть уже и можно переопределить, но он вызывается не всегда.
Пусть в своём коде я могу обложиться Debug.Assert() и требовать, чтобы был вызван недефолтный конструктор или статический метод-фабрика, но в библиотеке платфрменного уровня таких дыр быть не должно, она должна быть защищена от дурака.

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


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

Позволяют что угодно, хосподя.
Как напишешь — так и будет.

Мой схематичный подход через "обертки" позволяет гарантировать иммутабельность для изначально описанных мутабельных типов.
Например, узел Node может быть описан мутабельным, но если мы создаём эти узлы внутри реализации и помещаем в константную ссылку/указатель, то тип становится readonly.

Т.е., реализация builder-а не требует дополнительных флагов, типа frozen (как в дотнетной реализации Immutable-узлов, и это почему появилсь отдельные read-only Frozen типы, где не требуется управлять еще и этими флагами). Достаточно по окончании построения присвоить граф константной ссылке/указателю (как говорил с самого начала).

В вашем подопечном-защищаемом дотнетном Immutable совсем всё смешно — набили дерево мильоном узлов в билдере, а потом сказали ему Freeze() — и оно пошло честной стековой рекурсией обходить дерево для установки флага.
"Не об этом я мечтала, когда замуж выходила..." (С) ))


V>>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
S>Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).

Deep-копия автоматом только для плоской памяти.
По указателю если — это надо расписывать ручками.
Если используется интрузивный счётчик ссылок и иммутабельность, то копирование вызовет лишь +1 у счётчика cсылок корня:
Рыба такая:

template<typename T>
class SharedHolder {
  intrusive_ptr<T> ptr_;

public:
  T * get() {
    return ptr_.get();  
  }

  const T * get() const {
    return ptr_.get();  
  }
};

template<typename T>
class Node;

template<typename T>
using NodeRef = SharedHolder<Node<T>>;

template<typename T>
class Node {
    T value;
    NodeRef<T> left_, right_;
    
public:    
    Node * left() { return left_.get(); }
    const Node * left() const { return left_.get(); }

    Node * right() { return right_.get(); }
    const Node * right() const { return right_.get(); }
};

template<typename T>
class AvlTreeSet {
    NodeRef<T> root_; 

public:
    typedef T value_type;

    void insert(const T & value) {
       root_ = mutable_merge(root_, value);
    }
   
    AvlTreeSet<T> insert(const T & value) const {
       return immutable_merge(root_, value);
    }
};

template<typename TSet>
class ImmutableSet {
    const TSet set_; 
    
    explicit ImmutableSet(TSet && s) : set_(s) {}
   
public:
    ImmutableSet() {}
    
    const TSet & set() const {
       return set_;
    }
   
    ImmutableSet<TSet> operator|(const typename TSet::value_type & b) const {
       return ImmutableSet<TSet>(move(set_.insert(b)));
    }

    ImmutableSet<TSet> operator|(const ImmutableSet<TSet> & b) const {
       TSet tmp = set_;
        
       b.for_each([&](const auto & value) {
          tmp = static_cast<const TSet &>(tmp).insert(value);
       });
        
       return ImmutableSet<TSet>(move(tmp));
    }
};

int main()
{
    using Set = ImmutableSet<AvlTreeSet<int>>;
    auto s1 = Set() | 1 | 2 | 3;

    return 0;
}

V>>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
S>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.

Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:

  T * get() {
  const T * get() const {

  Node * left() { 
  const Node * left() const {

  Node * right() {
  const Node * right() const {

По константной ссылке-указателю может быть вызвана только const-this версия метода, соответственно, у меня одно описание на все случаи жизни.
См. тут:

    void insert(const T & value) {
       root_ = mutable_merge(root_, value);
    }
   
    AvlTreeSet<T> insert(const T & value) const {
       return immutable_merge(root_, value);
    }

Константное поле у меня лишь в декораторе ImmutableSet<TSet>, далее констрантность распространяется.
Что я могу себе позволить, чтобы мои абстракции не протекли:
— дефолтный конструктор ImmutableSet (в примере auto empty = ImmutableSet<AvlTreeSet<int>>())
— конструктор от значений или других ImmutableSet.

Чего нельзя:
— публичные конструкторы от мутабельных типов.

Ф-ии навроде mutable_merge или immetable_merge могут быть внешними. При непосредственном вызове этих ф-ий над иммутабельными типами ничего гарантировать нельзя, разумеется.
Наверно, тебя именно это беспокоило несколько лет назад и в этом обсуждении снова.
Я же тебе говорил, что я могу распространить гарантии так, что они не протекут.
На самый худой конец их можно распространить на самое дно — поля целевых типов. ))

Просто никто так не делает обычно.
А как делают — показал.
Т.е. распространяют гарантии константности и создают невозможность протечки абстракций через доступное публичное АПИ.

Чего нельзя:
— публичные конструкторы от мутабельных типов.

В целях эффективности класс ImmutableSet может содержать вложенный класс Builder, который манипулирует мутабельным TSet на стадии напихивания данных, и в какой-то момент передаёт владение набором данных в иммутабельный ImmutableSet. Т.е. классу Builder будет доступен приватный конструктор декоратора ImmutableSet, а тебе нет. И что забавно, всего одна реализация ImmutableSet и Builder на все реализации set с нужными наборами методов.


V>>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
S>Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable?

Я там вообще мало чего интересного вижу и вряд ли когда буду пользоваться этой неэффективной реализацией.
В упор не понимаю, чем тебя заинтересовало это убожество.
Это ж для хомячков.
"Чтобы было!" (С)


V>>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Это — бесполезная идея.

"Это потому что ты не понимаешь иммутабельности" (С)
Для структур оказалась крайне полезной, потому что иначе возникал диссонанс с readonly-полями value-типов.

Пришлось ввести readonly-методы, что есть полный аналог const-this методов в С++.


S>Она одновременно не даст никаких гарантий иммутабельности

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

S>потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные

Хосподя, ну так за этим и предлагается, иначе смысла не будет.


S>и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.

В конструкторе поля можно изменять многократно, это не проблема.
А утекание абстракций контроллировать компилятором/верификатором, чтобы он запрещал изменение полей после того как из конструктора утёк this (будучи переданным некоему аргументу, допустим, для регистрации созданного объекта где-то там).

В этой схеме невозможно создать циклические ссылки объектов друг на друга, как их невозможно создать в ФП, но никто не жалуется.
Если уж требуются наработки иммутабельности из ФП — то берите их готовые.


V>>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
S> Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const.

-1
Раассуждая таким образом можно договориться до того, что и язык Ассемблера даёт гарантии.
Конечно, С++ даёт несравнимо больше гарантий в плане проектирования иммутабельных типов.

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

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

Говорить "это одно и то же" — сверкать ярчайшим нубством, сорри.
Хоть бы посмотрел на readony ref, scope и readonly методы структур в дотнете.
Похоже, ты со всем этим еще не разбирался, но мнение имеешь.


S>Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.

Это из-за необычно сильно ограниченного твоего мышления, через которое я уже устал продираться.
Как тебе недавно введенные управляемые ссылки как поля ref-структур?
Я об этом говорил еще примерно в 2005-м, но некоторые столь же узко мыслящие даже не понимали — а зачем?

Ты хоть понимаешь — зачем?
И почему это стало возможно только с введением readonly ref?

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


V>>Пусть по-мелочам больше думает машина, чем программист.
S>Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.

Да пофик.
Первый раз сказал "не вижу" — объяснили.
Если и после этого "не вижу" — списали на берег.


V>>Хорошо, что согласился хоть с чем-то. ))
V>>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
S>Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?

Ты говорил, дословно, "как мне знать, что тип иммутабельный"?
Разночтений быть не может, ты говорил о неизвестном потенциальном типе для своих алгоримов, соответственно, речь должна были идти об абстракциях.
А дотнете абстракции живут на интерфейсах и на ограничениях ими генериков.


V>>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
S>"Оно" — это кто?

Это объект-состояние ДКА для автомата.


V>>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
V>>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
S>Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".

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


V>>А как тебе arg... — семантика?
S>У меня со времён params в С# такой синтаксис удивления не вызывает.

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


S>А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию

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

При надобности оно рассматривается как initializer_list.

Я вообще удивляюсь, как ты дожил до своих лет и тебя до сих пор не прибили за аксиматическую позицию "все вокруг дураки", когда реальность подтверждает обратное? ))


S>и принудительная замена итерации рекурсией не выглядит шибко привлекательно.

ЧТД, вот тебе пример того, что дураков вовсе не вокруг искать надо.

При вычислении вложенных вызовов ф-ий для arg... получается линейный код вычисления аргументов ф-ий от самых глубоких к внешним.
Это абсолютно линейный код верхнего уровня, последовательность call.

Итерация там только в процессе работы компилятора.
А как бы оно вообще могло работать, неужели даже не попытался представить?
В любом случае, я тебе показал во что реально превращается тот код.


S>Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.

То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.

Здравствуйте, Sinclair, Вы писали:

S>Эти слова я читал. Я не понимаю, как вы будете их применять. Что именно помешает "по невнимательности" добавить в ImmutableValue<T> мутирующих методов?

Если поля описаны как const, то мутировать их никак.
Есть еще ключевое слово mutable — это когда к полю можно обращаться из const this метода.

Например, интрузивные счётчики ссылок часто описывают как mutable, потому что они работают над совместным владением объектами, без вмешательства в потенциально read-only семантику прикладных данных. Чаще всего такие счётчики размещают как приватные в неких базовых классах, т.е. эти счётчики недоступны затем наследуемому "прикладному" коду, предоставляя, однако, через функциональность этих базовых классов требуемую инфраструктуру по ссылочному шаренью целевых данных.


V>>С одной стороны, это не более чем эксплуатация выразительных ср-в языка, что мы гарантии прописываем через синтаксис (а не комментарии) и контроллируем их через систему типов.
V>>Создание копий иммутабельных данных может быть полезным для региональной памяти, когда необходимо сохранить данные в своём регионе.
S>Это опять какие-то вырожденные экзотические сценарии, нужные примерно никогда.

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


V>>Счётчики обычно дергаются при перестроении, допустим, графа на иммутабельных узлах, поэтому доп. накладные расходы не настолько уж велики, чтобы говорить о дне, бо перестраивается только часть узлов.
S>Счётчики ссылок, очевидно, дёргаются при любом копировании.

Дергаются не у всего дерева, а только у непосредственных детей вновь создаваемых узлов при перестроении, а это log N.
Т.е. еще зависит от вида дерева — RB, AVL или еще какие с арностью более 2 — тогда будет еще меньше дерганий счётчиков ссылок.

Плюс, в промежуточных операциях (при нескольких поворотах, например, вставка может породить два поворота, а удаление из AVL до 5-ти поворотов) можно исключить дерганье счётчиков ссылок в процессе, пробежавшись по новым узлам уже по окончании операций.


S>Как раз "перестроенные" узлы, которых мало, получают счётчики == 1.

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

И опять же, смотря как реализовано дерево. Ссылочные ноды RB-деревьев могут хранить value-кластер тройки узлов {R, B, R}, т.е. в общем случае меньше дерганий счетчиков ссылок (вдвое меньше "ссылочная" высота дерева), как и для более арных деревьев.


V>>А региональная память — это когда некая подсистема сама распределяет память на низком уровне, обращаясь к операционке только за относительно большими страницами памяти.
V>>В таких распределителях память обычно выделяется как grow-only, простым смещением текущего указателя свободной области, т.е. выделение происходит с эффективностью дотнета.
V>>А освобождается затем и вовсе бесплатно, целиком одной операцией возврата операционке страницы (страниц).
S>Это если у вас хватает размера региона на полную работу алгоритма.

Память выделяется страницами, выделенные страницы хранятся по единственной ссылке, бо связаны в однонаправленный список.
Аллокаторы обычно настраиваются compile-time константами-параметрами, например, размером страницы и величиной выравнивания (выравнивание порой нужно не на слово, а на линейку кеша).

Эти техники, считай, обязательные в реализациях нейтивных веб-серверов, баз данных, компиляторов и т.д., бо региоальная память хорошо себя показывает в сценариях "выделить память для отдельной операции и всю её освободить по окончании операции". Боюсь даже представить, как работали бы БД или компиляторы без региональной памяти, на обычном malloc на каждый чих. ))

Плюс, в отличие от распределителей на основе пула ячеек одинакового размера (аллокатор по степени двойки связывает ячейки одинакового размера в линейные списки, где пустые ячейки друг на друга ссылаются, т.е. первое слово свободной ячейки интерпретируется как адрес следующей ячейки), у региональной памяти всё неплохо с локальностью. Зато плохо с долгоживучестью у grow-only аллокатора, поэтому сей подход и нашел себя в обслуживании указанных относительно короткоживущих сценариев.


S>Заранее сказать, сколько потребуется памяти для хранения мусора, порождаемого компилятором при анализе AST, весьма затруднительно.

А оно и не требуется.
Каждая трансформация — отдельная операция, т.е. для временных данных можно юзать такие аллокаторы, длительностью жизни в операцию.
Потом у аллокатора вызывается некий reset и он переиспользуется для другой операции и т.д.

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

Это ж азы, а не "уникальность".
Это сегодня мы разбалованы современными высокоуровневыми подходами...
В более хардокорном прошлом это всё из разряда не уникальности, а must have, то бишь, не новинка, а наоборот, традиции.


S>А как только вы исчерпали регион — добро пожаловать в честное копирование.

Регион — это несколько страниц.

Вот у тебя тройка указателей:

void * page_end;
void * cursor;
void * page_begin;

Курсор просто ползёт до page_end, после этого выделяется новая страница, а на старую ссылаются в первом слове новой страницы.
Соответственно, у первой выделенной страницы первое слово всегда null — конец списка.


V>>В целом оно на порядки эффективнее, чем в дотнете.
S>"В целом" — вряд ли. В частных случаях — может быть.

В целом — это сам этот подход.
Просто можно и его испортить, разумеется. ))

Например, в дотнете аллокатор расположен в TLS-слоте (что тоже далеко не верх эффективности — просто получить ссылку на аллокатор, у которого попросить память).
В твоей же реализации могут быть разные подходы — тоже на TLS или некий передаваемый в операции явно context (а в нём даже несколько таких аллокаторов для нескольких подсистем) и т.д.

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


S>То, что вы называете "региональной памятью", другие люди называют ареной

Регион, арена...
Термин не так давно устоялся, что забавно и то, из-за использованных идентификаторов в некоторых реализациях и языках.


S>и это, в целом, аналог поколений в современных GC, только на ручном приводе.

Не скажи...
Например, нулевое поколение — это просто список объектов с некоей "головы".
Затем уплотнения может и не быть (не было неявных освобождений), но голову по окончании цикла GC переназначат.

Сравнивать эти подходы сложновато, потому что в их основе лежат принципиально разные стратегии из-за принципиально разных принятых допущений.
"Просто другая стратегия", всё.

Не обязательно пытаться найти ассоциативную связь со знакомым материалом. ))
За одно только сязывание выделяемых объектов в списки в GC-системах убить мало. ))


S>И применяется, как правило, там, где потребности в памяти можно предсказать — либо мало кросс-ссылок между данными.

Ес-но, граф владения разрабатывается под механику этого владения.
А так-то можно на любой чих получить зацикливание на тех же счётчиках ссылок, привет VB/VBA. ))

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

Разумеется, автоматическое управление памятью кое-где сильно развязывает руки.
А кое-где сильно связывает.
Не изобрели еще серебрянной пули. ))


S>Какой-нибудь видео и аудиопроцессинг с этим будет работать хорошо, а вот компиляторы и прочие трансформации графов — вряд ли.

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

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


V>>merge — потому что такова природа сущности "множество". ))
S>Вы распишите, что у вас там вместо // .... Поскольку у вас под капотом — заранее неизвестный мутабельный тип, то всё, что вы можете — это состряпать его копию, к которой потом будет применена манипуляция с изменением.

И чем плоха копия такого объекта:

class ImmutableSet<T> {
   const RBNode<T> * root_;   
};

где ImmutableSet<T> используется с семантикой значения, в данном случае значения-ссылки.

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

Так для чего ж тогда ImmutableSortedSet<> объявлен ссылочным типом?
А, ну да, ну да...
— из-за встроенного дефолтного конструктора value-типов, который хоть уже и можно переопределить, но он вызывается не всегда.
Пусть в своём коде я могу обложиться Debug.Assert() и требовать, чтобы был вызван недефолтный конструктор или статический метод-фабрика, но в библиотеке платфрменного уровня таких дыр быть не должно, она должна быть защищена от дурака.

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


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

Позволяют что угодно, хосподя.
Как напишешь — так и будет.

Мой схематичный подход через "обертки" позволяет гарантировать иммутабельность для изначально описанных мутабельных типов.
Например, узел Node может быть описан мутабельным, но если мы создаём эти узлы внутри реализации и помещаем в константную ссылку/указатель, то тип становится readonly.

Т.е., реализация builder-а не требует дополнительных флагов, типа frozen (как в дотнетной реализации Immutable-узлов, и это почему появилсь отдельные read-only Frozen типы, где не требуется управлять еще и этими флагами). Достаточно по окончании построения присвоить граф константной ссылке/указателю (как говорил с самого начала).

В вашем подопечном-защищаемом дотнетном Immutable совсем всё смешно — набили дерево мильоном узлов в билдере, а потом сказали ему Freeze() — и оно пошло честной стековой рекурсией обходить дерево для установки флага.
"Не об этом я мечтала, когда замуж выходила..." (С) ))


V>>Для случая активного изменения данных я выберу ссылочную семантику, для случая frozen-данных выберу семантику по-значению, разумеется.
S>Просто при передаче вашего ImmutableValue() по значению, будет создаваться deep-копия вложенных в него данных. Со стоимостью O(N).

Deep-копия автоматом только для плоской памяти.
По указателю если — это надо расписывать ручками.
Если используется интрузивный счётчик ссылок и иммутабельность, то копирование вызовет лишь +1 у счётчика cсылок корня:
Рыба такая:

template<typename T>
class SharedHolder {
  intrusive_ptr<T> ptr_;

public:
  T * get() {
    return ptr_.get();  
  }

  const T * get() const {
    return ptr_.get();  
  }
};

template<typename T>
class Node;

template<typename T>
using NodeRef = SharedHolder<Node<T>>;

template<typename T>
class Node {
    T value;
    NodeRef<T> left_, right_;
    
public:    
    Node * left() { return left_.get(); }
    const Node * left() const { return left_.get(); }

    Node * right() { return right_.get(); }
    const Node * right() const { return right_.get(); }
};

template<typename T>
class AvlTreeSet {
    NodeRef<T> root_; 

public:
    typedef T value_type;

    void insert(const T & value) {
       root_ = mutable_merge(root_, value);
    }
   
    AvlTreeSet<T> insert(const T & value) const {
       return immutable_merge(root_, value);
    }
};

template<typename TSet>
class ImmutableSet {
    const TSet set_; 
    
    explicit ImmutableSet(TSet && s) : set_(s) {}
   
public:
    ImmutableSet() {}
    
    const TSet & set() const {
       return set_;
    }
   
    ImmutableSet<TSet> operator|(const typename TSet::value_type & b) const {
       return ImmutableSet<TSet>(move(set_.insert(b)));
    }

    ImmutableSet<TSet> operator|(const ImmutableSet<TSet> & b) const {
       TSet tmp = set_;
        
       b.for_each([&](const auto & value) {
          tmp = static_cast<const TSet &>(tmp).insert(value);
       });
        
       return ImmutableSet<TSet>(move(tmp));
    }
};

int main()
{
    using Set = ImmutableSet<AvlTreeSet<int>>;
    auto s1 = Set() | 1 | 2 | 3;

    return 0;
}

V>>Я рядом давал тебе ссылку на исходники SmallFrozenSet.
S>Да при чём тут ссылка? Вы просто опять уходите в решения для каких-то экзотических частных случаев.

Наоборот, говорил, что в плюсах есть возможность писать более обще, потому что у меня есть возможность распространять гарантии.
Обрати внимание на сигнатуры парами:

  T * get() {
  const T * get() const {

  Node * left() { 
  const Node * left() const {

  Node * right() {
  const Node * right() const {

По константной ссылке-указателю может быть вызвана только const-this версия метода, соответственно, у меня одно описание на все случаи жизни.
См. тут:

    void insert(const T & value) {
       root_ = mutable_merge(root_, value);
    }
   
    AvlTreeSet<T> insert(const T & value) const {
       return immutable_merge(root_, value);
    }

Константное поле у меня лишь в декораторе ImmutableSet<TSet>, далее констрантность распространяется.
Что я могу себе позволить, чтобы мои абстракции не протекли:
— дефолтный конструктор ImmutableSet (в примере auto empty = ImmutableSet<AvlTreeSet<int>>())
— конструктор от значений или других ImmutableSet.

Чего нельзя:
— публичные конструкторы от мутабельных типов.

Ф-ии навроде mutable_merge или immetable_merge могут быть внешними. При непосредственном вызове этих ф-ий над иммутабельными типами ничего гарантировать нельзя, разумеется.
Наверно, тебя именно это беспокоило несколько лет назад и в этом обсуждении снова.
Я же тебе говорил, что я могу распространить гарантии так, что они не протекут.
На самый худой конец их можно распространить на самое дно — поля целевых типов. ))

Просто никто так не делает обычно.
А как делают — показал.
Т.е. распространяют гарантии константности и создают невозможность протечки абстракций через доступное публичное АПИ.

Чего нельзя:
— публичные конструкторы от мутабельных типов.

В целях эффективности класс ImmutableSet может содержать вложенный класс Builder, который манипулирует мутабельным TSet на стадии напихивания данных, и в какой-то момент передаёт владение набором данных в иммутабельный ImmutableSet. Т.е. классу Builder будет доступен приватный конструктор декоратора ImmutableSet, а тебе нет. И что забавно, всего одна реализация ImmutableSet и Builder на все реализации set с нужными наборами методов.


V>>Не обошлись, там точно такая же магия для структур в ключевом слове readonly.
S>Я говорю конкретно про иммутабельность. Много ли readonly вы видите в System.Collections.Immutable?

Я там вообще мало чего интересного вижу и вряд ли когда буду пользоваться этой неэффективной реализацией.
В упор не понимаю, чем тебя заинтересовало это убожество.
Это ж для хомячков.
"Чтобы было!" (С)


V>>А было бы неплохо и для интерфейсов-классов, где IImuttableList мог быть объявлен как readonly interface IImuttableList, соответственно, все реализующие его классы должны были бы быть readonly IImuttableList : ImuttableList {...}
S>Это — бесполезная идея.

"Это потому что ты не понимаешь иммутабельности" (С)
Для структур оказалась крайне полезной, потому что иначе возникал диссонанс с readonly-полями value-типов.

Пришлось ввести readonly-методы, что есть полный аналог const-this методов в С++.


S>Она одновременно не даст никаких гарантий иммутабельности

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

S>потому, что внутри реализации ImmutableList — ссылка, которая, в том числе, может быть и на mutable данные

Хосподя, ну так за этим и предлагается, иначе смысла не будет.


S>и помешает некоторым сценариям, где иммутабл-объект изменяется в процессе конструирования.

В конструкторе поля можно изменять многократно, это не проблема.
А утекание абстракций контроллировать компилятором/верификатором, чтобы он запрещал изменение полей после того как из конструктора утёк this (будучи переданным некоему аргументу, допустим, для регистрации созданного объекта где-то там).

В этой схеме невозможно создать циклические ссылки объектов друг на друга, как их невозможно создать в ФП, но никто не жалуется.
Если уж требуются наработки иммутабельности из ФП — то берите их готовые.


V>>Но ты просил гарантии, поэтому я и продемонстрировал ср-ва для выражения гарантий.
S> Повторюсь: гарантии в продемонстрированном вами подходе никак не зависят от применения ключевого слова const.

-1
Рассуждая таким образом можно договориться до того, что и язык Ассемблера даёт такие же гарантии.
Конечно, С++ даёт несравнимо больше гарантий в плане проектирования иммутабельных типов.

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

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

Говорить "это одно и то же" — сверкать ярчайшим нубством, сорри.
Хоть бы посмотрел на readony ref, scope и readonly методы структур в дотнете.
Похоже, ты со всем этим еще не разбирался, но мнение имеешь.


S>Если вы его уберёте, ImmutableValue<> останется ровно на столько же иммутабельным, как и был.

Это из-за необычно сильно ограниченного твоего мышления, через которое я уже устал продираться.
Как тебе недавно введенные управляемые ссылки как поля ref-структур?
Я об этом говорил еще примерно в 2005-м, но некоторые столь же узко мыслящие даже не понимали — а зачем?

Ты хоть понимаешь — зачем?
И почему это стало возможно только с введением readonly ref?

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


V>>Пусть по-мелочам больше думает машина, чем программист.
S>Непонятно, что вы имеете в виду. Я всё ещё не вижу сценария, который вы предотвращаете при помощи этого ключевого слова.

Да пофик.
Первый раз сказал "не вижу" — объяснили.
Если и после этого "не вижу" — списали на берег.


V>>Хорошо, что согласился хоть с чем-то. ))
V>>Проблематика заданного именно тобой обсуждения как раз в интерфейсах — ты хотел писать обобщённые алгоритмы в условиях гарантий.
S>Разве? Может, я что-то подзабыл. Можно указать, где именно я настаивал на интерфейсах?

Ты говорил, дословно, "как мне знать, что тип иммутабельный"?
Разночтений быть не может, ты говорил о неизвестном потенциальном типе для своих алгоримов, соответственно, речь должна были идти об абстракциях.
А дотнете абстракции живут на интерфейсах и на ограничениях ими генериков.


V>>Оно и так в реальной жизни отродясь иммутабельно для State и до введения готовых Immutable-реализаций.
S>"Оно" — это кто?

Это объект-состояние ДКА для автомата.


V>>В общем, будет отличаться тем, бо абстракция ImmutableMapWrapper бесплатна, а обёрнут может быть не только конкретный std::map.
V>>Ну и, из-за наличия частичного определения шаблонов, может быть обёрнут даже тип, который не совместим по публичному интерфейсу в std::map.
S>Как только вы обернёте не только конкретный sdd::map, появится и возможность "хулиганить".

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


V>>А как тебе arg... — семантика?
S>У меня со времён params в С# такой синтаксис удивления не вызывает.

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


S>А семантика, на первый взгляд, слабже — не так удобно извлекать коллекцию

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

При надобности оно рассматривается как initializer_list.

Я вообще удивляюсь, как ты дожил до своих лет и тебя до сих пор не прибили за аксиматическую позицию "все вокруг дураки", когда реальность подтверждает обратное? ))


S>и принудительная замена итерации рекурсией не выглядит шибко привлекательно.

ЧТД, вот тебе пример того, что дураков вовсе не вокруг искать надо.

При вычислении вложенных вызовов ф-ий для arg... получается линейный код вычисления аргументов ф-ий от самых глубоких к внешним.
Это абсолютно линейный код верхнего уровня, последовательность call.

Итерация там только в процессе работы компилятора.
А как бы оно вообще могло работать, неужели даже не попытался представить?
В любом случае, я тебе показал во что реально превращается тот код.


S>Вот если бы ещё шарп починили, разрешив приписывать params к параметру любого типа, который реализован массивом. В частности, IEnumerable<T> и IList<T>.

То сделали бы эти случаи неразличимыми/конфликтующими, в то время как м/у ними сильное различие с т.з. эффективности.
В кишках дотнета голые массивы весьма входу и популярны.
Где приходится бороться за эффективность на юзверском уровне — тоже.