> 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?
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.
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.
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.
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.
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?
> 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:
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?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.
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.
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.
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.
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?
Adorable: they've reinvented Emacs markers
Why do you think there's a re in research?