Стойкие структуры данных в С++

Ответ 1

Основная трудность получения постоянной структуры данных - это, по сути, отсутствие сбора мусора.

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

Он меняет саму структуру. Например, подумайте о двоичном дереве. Если вы создаете новую версию node, вам нужна новая версия его родителя для доступа к ней (и т.д.). Теперь, если отношение является двусторонним (child ↔ parent), вы фактически дублируете всю структуру. Это означает, что у вас будет либо родительское → дочернее отношение, либо противоположное (менее распространенное).

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

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

Ответ 2

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

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

// We only need to change a small part of this huge data structure.
HugeDataStructure transform(HugeDataStructure input);

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

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

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

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

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

Immutable transform(Immutable input)
{
    Transient transient(input);

    // make changes to mutable transient.
    ...

    // Commit the changes to get a new immutable
    // (this does not touch the input).
    return transient.commit();
}

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

Когда переходный процесс изменяется, и мы получаем новый неизменный, только измененные части становятся уникальными. Остальные фрагменты неглубоко скопированы (всего 32-разрядные индексы):

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

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

Ответ 3

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

Если это то, что вы ищете, это довольно легко реализовать на С++ с помощью общих указателей (см. shared_ptr от Boost, как одна реализация). Первоначально копия будет делиться всем с источником, но после внесения изменений соответствующие части общих указателей объекта заменяются другими общими указателями, указывающими на вновь созданные, глубоко скопированные объекты. (Я понимаю, что это объяснение является неопределенным - если это действительно то, что вы имеете в виду, ответ может быть разработан).