Meeting C++ 2025 - Persistence squared: persisting persistent data structures

Juan Pedro Bolívar Puente

On Day 1 at 16:00 (CET/Berlin) in Track E [Amethyst Room and online]

Persistent data structures are used to implement immutable containers, so that they are manipulated by producing new values, leaving the old ones intact. To do so efficiently, these new values do not contain a copy of the whole structure. Instead only the changed parts are created new, and the rest of the structure is shared internally between old and new values. We call this structural sharing , and is crucial feature to implement immutable data structures efficiently. It opens the door to radically simpler software architectures, specially for interactive applications or highly concurrent systems.

However, structural sharing is traditionally preserved in memory only. When serializing multiple values to disk, these are linearized—for example, by writing out sequences as JSON arrays—losing whatever sharing may exist between these values. A similar thing happens when transforming data structures (as with std::transform or a functional map() )

Here we present the new library immer::persist , that enables the serialization of pools of containers while preserving structural sharing. With it, we can also do in-memory transformation over large sets of data that considers and preserves structural sharing. This is novel technique, not present in any other implementation of persistent data structures. We will show when and how to use it, how it is implemented, and include some practical examples from our Digital Audio Workstation at BRONZE.

Please login to comment