[HN Gopher] A proof of concept of a semistable C++ vector container
___________________________________________________________________
A proof of concept of a semistable C++ vector container
Author : joaquintides
Score : 25 points
Date : 2025-12-16 12:18 UTC (4 days ago)
(HTM) web link (github.com)
(TXT) w3m dump (github.com)
| thechao wrote:
| Neat. Here's what I'd keep: just an epoch saying when the last
| valid element of the vector is. The iterator just needs a ptr to
| the vector and the vector's data. It's a constant time lookup,
| with somewhat heavier iterators. I guess this is something like
| MSFT's old debug iterators?
| unnah wrote:
| Interesting that they chose not to implement any method to detect
| whether a given iterator has been invalidated, even though the
| implementation would be easy. Seems it would be a useful
| extension, especially since any serious usage of this vector type
| would already be relying on functionality not provided by the
| standard vector class.
| quotemstr wrote:
| Adorable: they've reinvented Emacs markers
| fooker wrote:
| Why do you think there's a re in research?
| shin_lao wrote:
| What is the core use case for this structure? Because it seems
| like a very heavy price to pay just to keep value stable, as
| opposed to make a copy of that value when you need it.
| wavemode wrote:
| A stable vector generally improves append performance (because
| you never have to move the data), allows storing data that
| can't be moved, and allows for appending while iterating. The
| downside is slightly worse performance for random lookups
| (since the data is fragmented across multiple segments) and
| higher memory usage (depending on implementation).
|
| This "semistable" vector appears to only do the "allow
| appending while iterating" part, but still maintains a
| contiguous buffer by periodically moving its contents.
| eps wrote:
| It's basically a form of reference-counted data access as I
| understand it.
|
| If the code here operates with a bit of data from some
| container, the container will ensure that this bit will persist
| until all references to it are gone even if the bit is removed
| from the container.
|
| Depending on the datamodel this may be handy or even required.
| Consider some sort of hot-swappable code when both retired and
| new code versions running in parallel at some point. That sort
| of thing.
| omoikane wrote:
| > The same iterator object can't be used concurrently in
| different threads, even for nominally const operations such as
| dereferencing (internally, thread-unsafe epoch traversal is
| triggered)
|
| If I understand correctly:
| thread safety random access stable iterators
| ------------- ------------- ----------------
| std::list thread-compatible no yes
| std::vector thread-compatible yes no
| std::deque thread-compatible yes no
| semistable::vector thread-unsafe yes yes
|
| I think there are more times when I wanted concurrent reads and
| (random access OR stable iterators), than when I wanted both
| random access AND stable iterators but not concurrent reads. I
| wonder what's the intended application?
___________________________________________________________________
(page generated 2025-12-20 23:02 UTC)