I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity: http://bannalia.blogspot.com/2008/09/introducing-stablevector.html If there is interest in the community this could be grown into a full-fledged proposal for Boost (either by me or by any other interested colleague). Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Sun, Sep 14, 2008 at 9:42 AM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
Could you compare the space requirements and complexity of operations of your stable_vector and std::deque (which has stable references as well)? Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
Hi Emil, ________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Emil Dotchevski [emil@revergestudios.com] Enviado el: domingo, 14 de septiembre de 2008 19:35 Para: boost@lists.boost.org Asunto: Re: [boost] request for interest: stable vector On Sun, Sep 14, 2008 at 9:42 AM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
Could you compare the space requirements and complexity of operations of your stable_vector and std::deque (which has stable references as well)? std::deque has no stable references in general; 23.2.2.3/19 (on std::deque insertion operations) says: Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Sun, Sep 14, 2008 at 10:44 AM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
Hi Emil, ________________________________________ De: boost-bounces@lists.boost.org [boost-bounces@lists.boost.org] En nombre de Emil Dotchevski [emil@revergestudios.com] Enviado el: domingo, 14 de septiembre de 2008 19:35 Para: boost@lists.boost.org Asunto: Re: [boost] request for interest: stable vector
On Sun, Sep 14, 2008 at 9:42 AM, JOAQUIN M. LOPEZ MUÑOZ <joaquin@tid.es> wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
Could you compare the space requirements and complexity of operations of your stable_vector and std::deque (which has stable references as well)?
std::deque has no stable references in general; 23.2.2.3/19 (on std::deque insertion operations) says:
Effects: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.
Sure, I meant stable references when you insert or erase at either end. This is plenty good for many use cases that need stable references. I'm still interested in the comparison though. :) Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
Emil Dotchevski escribió:
Could you compare the space requirements and complexity of operations of your stable_vector and std::deque (which has stable references as well)? [...] Sure, I meant stable references when you insert or erase at either end. This is plenty good for many use cases that need stable references.
I'm still interested in the comparison though. :)
Sure. At first blush I'd say std::deque probably perform worse than stable_vector both at push_back and operator[], because although the operations have the same big-O complexities in both containers (amortized constant insertion, constant access), the implementation of std::deque is more convoluted. I need to subtantiate this, though. I'll try to do some actual measurements and will be back to you in a few days. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Emil Dotchevski <emil <at> revergestudios.com> writes:
On Sun, Sep 14, 2008 at 9:42 AM, JOAQUIN M. LOPEZ MUÑOZ <joaquin <at> tid.es>
wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
Could you compare the space requirements and complexity of operations of your stable_vector and std::deque (which has stable references as well)?
Hi Emil, as promised, some profile results are shown at: http://bannalia.blogspot.com/2008/09/profiling-stablevector.html Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Sun, Sep 21, 2008 at 8:01 AM, Joaquin M Lopez Munoz <joaquin@tid.es> wrote:
Emil Dotchevski <emil <at> revergestudios.com> writes:
On Sun, Sep 14, 2008 at 9:42 AM, JOAQUIN M. LOPEZ MUÑOZ <joaquin <at> tid.es> wrote: Hi Emil, as promised, some profile results are shown at:
http://bannalia.blogspot.com/2008/09/profiling-stablevector.html
This is interesting, so basically the stable iterators/references are achieved by allocating each object in a separate node. This got me thinking, from certain point of view the difference between std::list and your stable_vector is the ability of the latter to return elements by index in O(1). Isn't it possible to decouple this ability from the container itself? In other words, could your code be refactored to provide indexing over any type of "host container"? OTOH, I'm guessing that the only type of "host container" that would make sense is std::list, since the other "stable containers" don't preserve the ordering between the elements (which makes indexing impractical) so maybe it isn't worth the effort. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
Emil Dotchevski escribió:
On Sun, Sep 21, 2008 at 8:01 AM, Joaquin M Lopez Munoz <joaquin@tid.es> wrote:
Hi Emil, as promised, some profile results are shown at:
http://bannalia.blogspot.com/2008/09/profiling-stablevector.html
This is interesting, so basically the stable iterators/references are achieved by allocating each object in a separate node.
This got me thinking, from certain point of view the difference between std::list and your stable_vector is the ability of the latter to return elements by index in O(1). Isn't it possible to decouple this ability from the container itself? In other words, could your code be refactored to provide indexing over any type of "host container"?
Well, sort of. Basically, that's what you can achieve by adding a random access index (http://tinyurl.com/4ruu2c ) to a multi_index_container.
OTOH, I'm guessing that the only type of "host container" that would make sense is std::list, since the other "stable containers" don't preserve the ordering between the elements (which makes indexing impractical) so maybe it isn't worth the effort.
Indexing (as implemented by random access indices) is decoupled from other indices: you can have an element occupy position i-th in the random access index and j-th in other index, with i!=j. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
On Mon, Sep 29, 2008 at 12:56 AM, <joaquin@tid.es> wrote:
Emil Dotchevski escribió:
On Sun, Sep 21, 2008 at 8:01 AM, Joaquin M Lopez Munoz <joaquin@tid.es> wrote:
Hi Emil, as promised, some profile results are shown at:
http://bannalia.blogspot.com/2008/09/profiling-stablevector.html
This is interesting, so basically the stable iterators/references are achieved by allocating each object in a separate node.
This got me thinking, from certain point of view the difference between std::list and your stable_vector is the ability of the latter to return elements by index in O(1). Isn't it possible to decouple this ability from the container itself? In other words, could your code be refactored to provide indexing over any type of "host container"?
Well, sort of. Basically, that's what you can achieve by adding a random access index (http://tinyurl.com/4ruu2c ) to a multi_index_container.
I wasn't trying to achieve anything, except to point out that perhaps it is possible to decouple the indexing functionality from the storage functionality, in principle. Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode
JOAQUIN M. LOPEZ MUÑOZ skrev:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
If there is interest in the community this could be grown into a full-fledged proposal for Boost (either by me or by any other interested colleague).
I think there is. In a number of situations, particular in combination with intrusive graphs, where I use deque today, that this is interesting. I briefly want to discuss an alternative design, which might be worth considering. In psudo code it would be implemented a bit like this: struct index { size_t from, to; }; struct segment { T* array; size_t size; }; class stable_vector { unordered_map<index,segment> data; }; The idea here is that we store segments of arbitrary size. To implement random access, we look up the appropriate segment. To implement iteration betwen segments, we lookup index.to+1 assuming the hash function only uses index.from. (A more effecient, segement based, non-in-order iteration can also be provided). Furthermore, I think insert/erase can know be done in O(M) time, where M is the average size of the segments. -Thorsten
Thorsten Ottosen escribió:
JOAQUIN M. LOPEZ MUÑOZ skrev:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
If there is interest in the community this could be grown into a full-fledged proposal for Boost (either by me or by any other interested colleague).
I think there is. In a number of situations, particular in combination with intrusive graphs, where I use deque today, that this is interesting.
I briefly want to discuss an alternative design, which might be worth considering. In psudo code it would be implemented a bit like this:
struct index { size_t from, to; };
struct segment { T* array; size_t size; };
class stable_vector { unordered_map<index,segment> data; };
The idea here is that we store segments of arbitrary size. To implement random access, we look up the appropriate segment. To implement iteration betwen segments, we lookup index.to+1 assuming the hash function only uses index.from. (A more effecient, segement based, non-in-order iteration can also be provided).
Furthermore, I think insert/erase can know be done in O(M) time, where M is the average size of the segments.
The structure you describe is AFAICS equivalent to the usual implementation of std::queue (http://tinyurl.com/68l9e7 ), except that std::queue uses an array for data instead of an unordered_map. So, I don't see how one could provide stability for middle insertions. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
joaquin@tid.es skrev:
Thorsten Ottosen escribió:
class stable_vector { unordered_map<index,segment> data; };
The structure you describe is AFAICS equivalent to the usual implementation of std::queue (http://tinyurl.com/68l9e7 ), except that std::queue uses an array for data instead of an unordered_map. So, I don't see how one could provide stability for middle insertions.
You're right: that requires a segment size of 1. Damn. -Thorsten
JOAQUIN M. LOPEZ MUÑOZ wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
Very interesting.
If there is interest in the community this could be grown into a full-fledged proposal for Boost (either by me or by any other interested colleague).
Yes. I'would be interested in an Interprocess-friendly version ;-). Since it's a node-based container and competes against std::vector and its well known performance, I think stable_vector is a perfect candidate to use a bit more unconventional allocators like these (using burst allocation for nodes and reallocation for the index vector): http://www.drivehq.com/web/igaztanaga/allocplus/ And if I'm not wrong, unlike std::vector, stable_vector could support non-copyable and non-movable objects.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Regards, Ion
Ion Gaztañaga escribió:
JOAQUIN M. LOPEZ MUÑOZ wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
[...] Yes. I'would be interested in an Interprocess-friendly version ;-). Since it's a node-based container and competes against std::vector and its well known performance, I think stable_vector is a perfect candidate to use a bit more unconventional allocators like these (using burst allocation for nodes and reallocation for the index vector):
Ion, where can I grab allocplus source code?
And if I'm not wrong, unlike std::vector, stable_vector could support non-copyable and non-movable objects.
Well, to do that it would have to implement emplace, but that's the only requisite. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Joaquin: it just occurred to me (from the thought that your stable vector could also be implemented as a wrapper on top of a vector of share ptrs where the vector iteratir stores an index and reference to vector; it's not as good impl as yours but also provides stable iters and refs) that you can provide an additional fctn release() to "export" your object from vector, with interface similar to erase and returning a shared ptr owning the node and pointing to the object within. Importing would work also in my design but not in yours, unless you import a pair of ptr, object (but that exposes your impl in the interface, not good)... I prefer emplace. Just a thought, HB Sent from my iPhone On Sep 17, 2008, at 4:56 AM, joaquin@tid.es wrote:
Ion Gaztañaga escribió:
JOAQUIN M. LOPEZ MUÑOZ wrote:
I recently wrote up the implementation of a *stable* vector, a container mimicking the interface of std::vector except that it provides iterator and reference stability at the expense of losing memory contiguity:
http://bannalia.blogspot.com/2008/09/introducing-stablevector.html
[...] Yes. I'would be interested in an Interprocess-friendly version ;-). Since it's a node-based container and competes against std::vector and its well known performance, I think stable_vector is a perfect candidate to use a bit more unconventional allocators like these (using burst allocation for nodes and reallocation for the index vector):
Ion, where can I grab allocplus source code?
And if I'm not wrong, unlike std::vector, stable_vector could support non-copyable and non-movable objects.
Well, to do that it would have to implement emplace, but that's the only requisite.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Wed, Sep 17, 2008 at 2:01 PM, Herve Bronnimann <hervebronnimann@mac.com> wrote:
Joaquin: it just occurred to me (from the thought that your stable vector could also be implemented as a wrapper on top of a vector of share ptrs where the vector iteratir stores an index and reference to vector; it's not as good impl as yours but also provides stable iters and refs) that you can provide an additional fctn release() to "export" your object from vector, with interface similar to erase and returning a shared ptr owning the node and pointing to the object within.
Or better, on top of ptr_vector. Export would return an auto_ptr. -- gpd
Giovanni Piero Deretta skrev:
On Wed, Sep 17, 2008 at 2:01 PM, Herve Bronnimann <hervebronnimann@mac.com> wrote:
Joaquin: it just occurred to me (from the thought that your stable vector could also be implemented as a wrapper on top of a vector of share ptrs where the vector iteratir stores an index and reference to vector; it's not as good impl as yours but also provides stable iters and refs) that you can provide an additional fctn release() to "export" your object from vector, with interface similar to erase and returning a shared ptr owning the node and pointing to the object within.
Or better, on top of ptr_vector. Export would return an auto_ptr.
I'm not certain this is possible if you also want iterator stability in addition to reference stability for middle insertions. But I guess it is a good question if iterator stability is important enough to have. -Thorsten
Thorsten Ottosen <thorsten.ottosen <at> dezide.com> writes:
Giovanni Piero Deretta skrev:
[...]
Or better, on top of ptr_vector. Export would return an auto_ptr.
I'm not certain this is possible if you also want iterator stability in addition to reference stability for middle insertions. But I guess it is a good question if iterator stability is important enough to have.
I'm not sure I'm getting this: what does export has to do with stability? Once you've exported a node, that node is no longer part of the container, so stability issues seem not to apply. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
I guess Thorsten referred to iterator validity of ptr_vector. Sent from my iPhone On Sep 19, 2008, at 1:45 PM, Joaquin M Lopez Munoz <joaquin@tid.es> wrote:
Thorsten Ottosen <thorsten.ottosen <at> dezide.com> writes:
Giovanni Piero Deretta skrev:
[...]
Or better, on top of ptr_vector. Export would return an auto_ptr.
I'm not certain this is possible if you also want iterator stability in addition to reference stability for middle insertions. But I guess it is a good question if iterator stability is important enough to have.
I'm not sure I'm getting this: what does export has to do with stability? Once you've exported a node, that node is no longer part of the container, so stability issues seem not to apply.
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Herve Bronnimann escribió:
Joaquin: it just occurred to me (from the thought that your stable vector could also be implemented as a wrapper on top of a vector of share ptrs where the vector iteratir stores an index and reference to vector; it's not as good impl as yours but also provides stable iters and refs) that you can provide an additional fctn release() to "export" your object from vector, with interface similar to erase and returning a shared ptr owning the node and pointing to the object within.
Yes, this seems doable, but what use cases are you envisioning?
Importing would work also in my design but not in yours, unless you import a pair of ptr, object (but that exposes your impl in the interface, not good)...
AFAICS in your design it would also expose the implementation, since you can't import a shared_ptr<T> as is, you'd have to provide something like a shared_ptr<stable_vector_node<T> >. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
joaquin@tid.es wrote:
Ion, where can I grab allocplus source code?
http://igaztanaga.drivehq.com/allocplus.zip I haven't compile it since I released it. But it should be compatible with Boost 1.36
And if I'm not wrong, unlike std::vector, stable_vector could support non-copyable and non-movable objects.
Well, to do that it would have to implement emplace, but that's the only requisite.
I guess someone is going to request it in the review ;-)
Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Nice work! Ion
Ion Gaztañaga escribió:
http://igaztanaga.drivehq.com/allocplus.zip
I haven't compile it since I released it. But it should be compatible with Boost 1.36
Thank you! [...]
Well, to do that it would have to implement emplace, but that's the only requisite.
I guess someone is going to request it in the review ;-)
Obviously it this were evolved to a mature proposal it would have to be C++09-compliant. But I don't think I can prepare the proposal myself :-/ at least not in the short term, my spare time is already consumed by the other Boost libs I'm in charge of. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
participants (9)
-
Emil Dotchevski -
Giovanni Piero Deretta -
Herve Bronnimann -
Ion Gaztañaga -
Joaquin M Lopez Munoz -
JOAQUIN M. LOPEZ MUÑOZ
-
joaquin＠tid.es
-
Thorsten Ottosen -
Thorsten Ottosen