[PLDI'26] Persistent Iterators with Value Semantics

https://www.youtube.com/watch?v=cq33C5nXEh0

14 Upvotes

86% Upvoted

This is something I have tried to implement a while ago too, but didnt have enough time to make performant enough for our use case. Do you have timed benchmarks?

3

u/mttd 4d ago

Not the author, but found it interesting; the talk has a bit on performance around 10 minutes in, more in Section 6 Evaluation of the paper, https://www.comp.nus.edu.sg/%7Egregory/papers/pldi2026.pdf

4

u/FollowingHumble8983 4d ago

Quickly skimming the constant factors section it appears they ran into the same performance issues I had unfortunately. Wanted closer to normal performance for raw iteration with only some hits on updates. Still an interesting library that makes some implementations much more trivial.

3

u/Gungan_Boss_Nass premature cleverization 3d ago

My N=1 deploying something equivalent was a performance boost: we replaced a lock with a write-lock for a container that had a 3:1 reader/writer ratio. Internally, the structure is held in a ref-counted tree. Only writers use the lock, readers just grab the head and run. Stale items live on until the last reader/writer is done with them.

2

u/Fabulous-Meaning-966 3d ago

You can even avoid making the readers take a refcount:

https://arxiv.org/abs/1803.08617

2

u/FollowingHumble8983 3d ago edited 3d ago

Yea this was something I was aiming for but with a different use case, benchmarks showed a marked decrease in performance over lock-free/reallocation so unfortunately I had to abandon it. My case dealt with vectors/lists with thousands of elements per fiber so iteration performance was crucial.

2

u/zoomT 3d ago

Paper author here. Yes, the aim of the paper was a comparable iterator abstraction with similar asymptotic complexities. Since persistent containers/iterators use tree-based/zipper data-structures, they generally are not competitive against array-backed containers like std::vector in terms of constant factors.

u/mttd 4d ago

Repo: LibF++: Persistent Containers and Iterators for C++, https://github.com/GJDuck/libfpp

Paper: https://www.comp.nus.edu.sg/~gregory/papers/pldi2026.pdf

Abstract:

Iterators are a fundamental programming abstraction for traversing and modifying elements in containers in mainstream imperative languages such as C++ . Iterators provide a uniform access mechanism that hides low-level implementation details of the underlying data structure. However, iterators over mutable containers suffer from well-known hazards including invalidation, aliasing, data races, and subtle side effects. Immutable data structures, as used in functional programming languages, avoid the pitfalls of mutation but rely on a very different programming model based on recursion and higher-order combinators ( map , foldl , traverse , etc.) rather than iteration. However, these combinators are not always well-suited to expressing certain algorithms, and recursion can expose implementation details of the underlying data structure.

In this paper, we propose persistent iterators —a new abstraction that reconciles the familiar iterator-based programming style of imperative languages with the semantics of persistent data structures. A persistent iterator snapshots the version of its underlying container at creation, ensuring safety against invalidation and aliasing. Iterator operations (++, erase , etc.) operate on the iterator-local copy of the container, giving true value semantics: variables can be rebound to new persistent values while previous versions remain accessible. We implement our approach in the form of LibFpp —a C++ container library providing persistent vectors, maps, sets, strings, and other abstractions as persistent counterparts to the Standard Template Library (STL). Our evaluation shows that LibFpp retains the expressiveness of iterator-based programming, eliminates iterator-invalidation, and achieves asymptotic complexities comparable to STL implementations—albeit with the higher constant-factor overheads of persistence. Our design targets use cases where persistence and safety are desired, while allowing developers to retain familiar iterator-based programming patterns.