Structures de données persistantes dans C++

Question

Existe-t-il des implémentations de structures de données persistantes dans C++ similaires à celles de clojure?

Answer 1

Si je comprends bien la question, ce que vous cherchez est la capacité de dupliquer un objet sans réellement payer pour la duplication quand c'est fait, seulement quand c'est nécessaire. Les modifications apportées à l'un ou l'autre objet peuvent être effectuées sans endommager l'autre. Ceci est connu comme "copie sur écriture".

Si c'est ce que vous cherchez, cela peut assez facilement être implémenté en C++ en utilisant des pointeurs partagés (voir shared_ptr de Boost, comme une implémentation). Initialement, la copie partagerait tout avec la source, mais une fois les modifications effectuées, les parties pertinentes des pointeurs partagés par l'objet sont remplacées par d'autres pointeurs partagés pointant vers des objets copiés en profondeur nouvellement créés. (Je réalise que cette explication est vague - si c'est bien ce que vous voulez dire, la réponse peut être élaborée).

Answer 2

La principale difficulté pour obtenir une structure de données persistante est en effet l'absence de garbage collection.

Si vous ne disposez pas d'un système de collecte des ordures approprié, vous pouvez en obtenir un mauvais (à savoir le comptage des références), mais cela signifie que vous devez prendre soin de ne PAS créer de références cycliques.

Il modifie le noyau même de la structure. Par exemple, pensez arbre binaire. Si vous créez une nouvelle version d'un nœud, vous avez besoin d'une nouvelle version de son parent pour y accéder (etc ...). Maintenant, si la relation est bidirectionnelle (enfant < -> parent), alors vous dupliquerez en fait toute la structure. Cela signifie que vous aurez soit une relation parent -> enfant, soit le contraire (moins commun).

Je peux penser à implémenter un arbre binaire, ou un B-Tree. Je vois à peine comment obtenir un tableau approprié par exemple. Par contre, je suis d'accord que ce serait bien d'avoir des outils efficaces dans les environnements multithread.

Answer 3

J'ai roulé le mien mais il y a le immer library comme un exemple assez complet et il est spécifiquement inspiré de clojure. Je me suis tout excité et j'ai roulé le mien il y a quelques années après avoir écouté un discours de John Carmack où il sautait partout dans le train de la programmation fonctionnelle. Il semblait pouvoir imaginer un moteur de jeu tournant autour de structures de données immuables. Bien qu'il ne soit pas entré dans les détails et même si cela semblait une idée vague dans sa tête, le fait qu'il la considérait sérieusement et ne semblait pas penser que les frais généraux réduiraient fortement les taux de trame était suffisant pour m'exciter. à propos de l'exploration de cette idée. Je l'utilise en fait comme un détail d'optimisation qui peut sembler paradoxal (il y a un surcoût à l'immuabilité), mais je veux dire dans un contexte spécifique. Si je veux absolument faire:

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

... et je ne veux absolument pas la fonction de provoquer des effets secondaires afin qu'il puisse être thread-safe et ne jamais sujettes à une mauvaise utilisation, alors je n'ai pas le choix mais pour copier la structure de données énorme (qui pourrait couvrir un gigaoctet). Et là, je trouve une petite bibliothèque de structures de données immuables extrêmement utile dans un tel contexte, car cela rend le scénario ci-dessus relativement bon marché par une simple copie superficielle et en référençant des parties inchangées.Cela dit, je viens d'utiliser la plupart du temps une structure de données immuable qui est essentiellement une séquence d'accès aléatoire, comme ceci:

Et comme d'autres ont mentionné, il ne nécessite des soins et mise au point et des tests complets et beaucoup VTune des séances pour rendre le filetage sûr et efficace, mais après avoir mis dans la graisse de coude, il a définitivement fait les choses un tout, beaucoup plus facile. En plus de la sécurité automatique des threads, chaque fois que nous utilisons ces structures pour écrire des fonctions sans effets secondaires, vous obtenez également des modifications non destructives, des systèmes d'annulation triviaux, des exceptions exceptionnelles (pas besoin de revenir en arrière) effets à travers des gardes de portée dans une fonction qui n'en provoque aucun dans des chemins exceptionnels), et laisser les utilisateurs copier et coller des données et les utiliser sans prendre beaucoup de mémoire jusqu'à/à moins qu'ils modifient ce qu'ils collent en bonus. J'ai trouvé ces bonus encore plus utiles au quotidien que la sécurité des threads.

J'utilise (« constructeurs » aka) « transitoires » comme un moyen d'exprimer des changements à la structure de données, comme suit:

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(); 
} 

J'ai même une bibliothèque d'images immuable que j'utiliser pour l'édition d'image banaliser l'édition non destructive. Il utilise une stratégie similaire à la structure ci-dessus en traitant les images comme des tuiles comme ceci:

Lorsqu'un passager est modifié et nous obtenons une nouvelle immuable, seules les parties modifiées sont rendues uniques. Le reste des tuiles sont copiés peu profonds (juste indices 32 bits):

Je ne les utiliser dans des zones assez critiques performance comme maillage et le traitement vidéo. Il y avait un peu de réglage de la quantité de données que chaque bloc devrait stocker (trop et nous gaspillons trop de données et trop de données, trop peu et nous gaspillons le traitement et la mémoire en copiant trop peu de pointeurs avec des verrous plus fréquents). Je ne les utilise pas pour le lancer de rayons car c'est l'un des domaines critiques les plus extrêmes que l'on puisse imaginer et le moindre surcoût est perceptible pour les utilisateurs (ils comparent et remarquent des différences de performance de l'ordre de 2%), mais la plupart du temps, ils sont assez efficaces, et c'est un avantage assez impressionnant quand vous pouvez copier ces énormes structures de données dans leur ensemble pour simplifier la sécurité des threads, annuler les systèmes, éditer de manière non destructive, etc., sans vous soucier à propos de l'utilisation de la mémoire explosive et des retards notables dépensés en profondeur tout copier.