[container] Contributing 'stationary_vector' to Boost
Hi all, Happy new year! New mailing list member here. I've developed an STL-style stationary_vector class that retains elements in-place when growing. Very briefly, it is effectively a piecewise-contiguous vector, with the following advantages over vector: - Appending has O(1) overhead in the *worst* case (e.g., push_back() does not move elements) - Insertion and random-access can be done in parallel, as prior iterators & references remain valid This has a variety of benefits, including better UX (no "hiccups" due to reallocations), and the ability to simplify parallel processing of streaming data. It occurred to me the larger C++ community might find this useful. I was wondering if there would be interest in incorporating it into Boost.Container, and if so, what steps I could take to make that happen? I'm of course happy to discuss the design etc. with anyone who might be interested. Summary: https://github.com/mehrdadn/libvital/blob/master/doc/vital/container/station... Implementation: https://github.com/mehrdadn/libvital/blob/master/include/vital/container/sta... Thank you, Mehrdad
Hi,
On 4. Jan 2021, at 13:17, Mehrdad Niknami via Boost <boost@lists.boost.org> wrote:
Hi all,
Happy new year! New mailing list member here.
I've developed an STL-style stationary_vector class that retains elements in-place when growing. Very briefly, it is effectively a piecewise-contiguous vector, with the following advantages over vector:
- Appending has O(1) overhead in the *worst* case (e.g., push_back() does not move elements) - Insertion and random-access can be done in parallel, as prior iterators & references remain valid
This has a variety of benefits, including better UX (no "hiccups" due to reallocations), and the ability to simplify parallel processing of streaming data. It occurred to me the larger C++ community might find this useful.
I was wondering if there would be interest in incorporating it into Boost.Container, and if so, what steps I could take to make that happen?
It sounds like you reinvented a deque? https://en.cppreference.com/w/cpp/container/deque Best regards, Hans
Hi, It's similar, but not quite. std::deque uses fixed-size blocks and tends to be slow in my experience (at least in some implementations). stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at *least* doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and similarly to) std::vector. It may be what std::deque *should* have been, but isn't currently. Thanks, Mehrdad On Mon, Jan 4, 2021 at 6:17 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
Hi,
On 4. Jan 2021, at 13:17, Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Hi all,
Happy new year! New mailing list member here.
I've developed an STL-style stationary_vector class that retains elements in-place when growing. Very briefly, it is effectively a piecewise-contiguous vector, with the following advantages over vector:
- Appending has O(1) overhead in the *worst* case (e.g., push_back() does not move elements) - Insertion and random-access can be done in parallel, as prior iterators & references remain valid
This has a variety of benefits, including better UX (no "hiccups" due to reallocations), and the ability to simplify parallel processing of streaming data. It occurred to me the larger C++ community might find this useful.
I was wondering if there would be interest in incorporating it into Boost.Container, and if so, what steps I could take to make that happen?
It sounds like you reinvented a deque? https://en.cppreference.com/w/cpp/container/deque
Best regards, Hans
On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami@berkeley.edu> wrote:
It's similar, but not quite. std::deque uses fixed-size blocks and tends to be slow in my experience (at least in some implementations). stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and similarly to) std::vector. It may be what std::deque should have been, but isn't currently.
Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque? https://github.com/boostorg/container/blob/develop/include/boost/container/d...
Not quite - my container is single-ended. Mehrdad On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami@berkeley.edu> wrote:
It's similar, but not quite. std::deque uses fixed-size blocks and tends to be slow in my experience (at least in some implementations). stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and similarly to) std::vector. It may be what std::deque should have been, but isn't currently.
Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?
https://github.com/boostorg/container/blob/develop/include/boost/container/d...
On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Not quite - my container is single-ended.
I assume this is because you grow your block size as you extend the vector. Without looking at the implementation of deque, could you not use your approach when appending on the left side as well? Both sides of the deque would allocate geometrically increasing block sizes independently, which would maintain algorithmic complexity. Jeff Mehrdad
On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami@berkeley.edu>
wrote:
It's similar, but not quite. std::deque uses fixed-size blocks and
tends to be slow in my experience (at least in some implementations).
stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and similarly to) std::vector. It may be what std::deque should have been, but isn't currently.
Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?
https://github.com/boostorg/container/blob/develop/include/boost/container/d...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
I don't think it's possible without hurting the efficiency. Each block is represented by an (index, pointer) pair. Pushing to the front would require re-adjusting the indices in every bucket on every push to the front, and that would be very slow. On the other hand if I change the representation to, say, a (begin, end) pair, it would have repercussions. For example, subtracting iterators would take logarithmic time instead of constant time, as they no longer have global bucket indices to subtract. There are also possibly less significant but still nontrivial trade-offs I can think of. For example, worst-case space usage would become O(infinity) (like vector) instead of the current ~2n space bound (which is even slightly worse than a typical deque's n + n/16 or similar in the worst case). Furthermore, random-indexing could no longer be done in O(log log n) time. (Note: this last part is something I haven't yet implemented for stationary_vector, but it's trivial to implement right now due to the global index maintained for each block. This would no longer be possible without that information.) I think there are likely more trade-offs as well, but for ones I could think of were more than sufficient to rule it out as a drop-in replacement for any existing container in STL or Boost; that's why I ended up implementing a new container. Mehrdad On Tue, Jan 5, 2021 at 11:12 AM Jeff Hajewski via Boost < boost@lists.boost.org> wrote:
On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Not quite - my container is single-ended.
I assume this is because you grow your block size as you extend the vector. Without looking at the implementation of deque, could you not use your approach when appending on the left side as well? Both sides of the deque would allocate geometrically increasing block sizes independently, which would maintain algorithmic complexity.
Jeff
Mehrdad
On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami@berkeley.edu>
wrote:
It's similar, but not quite. std::deque uses fixed-size blocks and
tends to be slow in my experience (at least in some implementations).
stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and similarly to) std::vector. It may be what std::deque should have been, but isn't currently.
Ok, that sounds like your container offers the same basic guarantees
as a
std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?
https://github.com/boostorg/container/blob/develop/include/boost/container/d...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Edit: Actually it just occurred to me there might be a solution for the first issue: an additional "start offset" parameter that gets adjusted by push_front could potentially avoid the performance hit to iterator subtraction. I'm a bit tempted to try to implement it and see if it breaks any assumptions I have, but it might work. That said though, it still wouldn't substitute for deque, given that the space complexity difference implies some deque users would now need to worry about manually calling reserve & shrink_to_fit (and then deal with having elements get moved), which deque doesn't have any notion of. Mehrdad On Tue, Jan 5, 2021 at 11:52 AM Mehrdad Niknami <mniknami@berkeley.edu> wrote:
I don't think it's possible without hurting the efficiency.
Each block is represented by an (index, pointer) pair. Pushing to the front would require re-adjusting the indices in every bucket on every push to the front, and that would be very slow. On the other hand if I change the representation to, say, a (begin, end) pair, it would have repercussions. For example, subtracting iterators would take logarithmic time instead of constant time, as they no longer have global bucket indices to subtract.
There are also possibly less significant but still nontrivial trade-offs I can think of. For example, worst-case space usage would become O(infinity) (like vector) instead of the current ~2n space bound (which is even slightly worse than a typical deque's n + n/16 or similar in the worst case). Furthermore, random-indexing could no longer be done in O(log log n) time. (Note: this last part is something I haven't yet implemented for stationary_vector, but it's trivial to implement right now due to the global index maintained for each block. This would no longer be possible without that information.)
I think there are likely more trade-offs as well, but for ones I could think of were more than sufficient to rule it out as a drop-in replacement for any existing container in STL or Boost; that's why I ended up implementing a new container.
Mehrdad
On Tue, Jan 5, 2021 at 11:12 AM Jeff Hajewski via Boost < boost@lists.boost.org> wrote:
On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Not quite - my container is single-ended.
I assume this is because you grow your block size as you extend the vector. Without looking at the implementation of deque, could you not use your approach when appending on the left side as well? Both sides of the deque would allocate geometrically increasing block sizes independently, which would maintain algorithmic complexity.
Jeff
Mehrdad
On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <hans.dembinski@gmail.com
wrote:
On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami@berkeley.edu>
wrote:
It's similar, but not quite. std::deque uses fixed-size blocks and
tends to be slow in my experience (at least in some implementations).
stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and
similarly
to) std::vector.
It may be what std::deque should have been, but isn't currently.
Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?
https://github.com/boostorg/container/blob/develop/include/boost/container/d...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On 5. Jan 2021, at 23:25, Mehrdad Niknami via Boost <boost@lists.boost.org> wrote:
Edit: Actually it just occurred to me there might be a solution for the first issue: an additional "start offset" parameter that gets adjusted by push_front could potentially avoid the performance hit to iterator subtraction. I'm a bit tempted to try to implement it and see if it breaks any assumptions I have, but it might work.
That said though, it still wouldn't substitute for deque, given that the space complexity difference implies some deque users would now need to worry about manually calling reserve & shrink_to_fit (and then deal with having elements get moved), which deque doesn't have any notion of.
Ok, it sounds like it is sufficiently dissimilar from deque to be its own thing. It sounds like a useful addition to boost::container, would be great to hear what Ion Gaztanaga thinks. Best regards, Hans
Would you know if he's had a chance to take a look at this? Thanks, Mehrdad On Wed, Jan 6, 2021 at 2:47 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
On 5. Jan 2021, at 23:25, Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Edit: Actually it just occurred to me there might be a solution for the first issue: an additional "start offset" parameter that gets adjusted by push_front could potentially avoid the performance hit to iterator subtraction. I'm a bit tempted to try to implement it and see if it breaks any assumptions I have, but it might work.
That said though, it still wouldn't substitute for deque, given that the space complexity difference implies some deque users would now need to worry about manually calling reserve & shrink_to_fit (and then deal with having elements get moved), which deque doesn't have any notion of.
Ok, it sounds like it is sufficiently dissimilar from deque to be its own thing. It sounds like a useful addition to boost::container, would be great to hear what Ion Gaztanaga thinks.
Best regards, Hans
On 18. Jan 2021, at 02:44, Mehrdad Niknami <mniknami@berkeley.edu> wrote:
Would you know if he's had a chance to take a look at this?
Thanks, Mehrdad
On Wed, Jan 6, 2021 at 2:47 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
On 5. Jan 2021, at 23:25, Mehrdad Niknami via Boost <boost@lists.boost.org> wrote:
Edit: Actually it just occurred to me there might be a solution for the first issue: an additional "start offset" parameter that gets adjusted by push_front could potentially avoid the performance hit to iterator subtraction. I'm a bit tempted to try to implement it and see if it breaks any assumptions I have, but it might work.
That said though, it still wouldn't substitute for deque, given that the space complexity difference implies some deque users would now need to worry about manually calling reserve & shrink_to_fit (and then deal with having elements get moved), which deque doesn't have any notion of.
Ok, it sounds like it is sufficiently dissimilar from deque to be its own thing. It sounds like a useful addition to boost::container, would be great to hear what Ion Gaztanaga thinks.
Best regards, Hans
Please do not top post. We have a no top-post policy for the mailing list. I cannot help you with that. If he does not answer here, you could try to submit an issue to https://github.com/boostorg/container. Ion commits frequently to the repo, so I hope he sees that. Best regards, Hans
On Mon, Jan 18, 2021 at 12:32 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
Please do not top post. We have a no top-post policy for the mailing list.
I cannot help you with that. If he does not answer here, you could try to submit an issue to https://github.com/boostorg/container. Ion commits frequently to the repo, so I hope he sees that.
Best regards, Hans
Oh I see, okay thanks! Best, Mehrdad
On Mon, Jan 18, 2021 at 12:39 AM Mehrdad Niknami <mniknami@berkeley.edu> wrote:
On Mon, Jan 18, 2021 at 12:32 AM Hans Dembinski <hans.dembinski@gmail.com> wrote:
Please do not top post. We have a no top-post policy for the mailing list.
I cannot help you with that. If he does not answer here, you could try to submit an issue to https://github.com/boostorg/container. Ion commits frequently to the repo, so I hope he sees that.
Best regards, Hans
Oh I see, okay thanks!
Best, Mehrdad
Hi all, I just wanted to follow up on my stationary_vector proposal earlier. I do realize it's been a long time (I'm sorry about that)—I'll try to explain the current status below. For context—I was in touch with Ion last year as was suggested here (thank you). He was very helpful and suggested improvements I would need to make to prepare this for a Boost review, and I made some changes in that light. Unfortunately, things stalled at that point, as life got in the way—initially for me, then for him—and he doesn't believe he'll have the bandwidth to review major contributions to Boost.Container anytime soon. Therefore he suggested I reach out to you all here in the hopes that someone may be able to move the ball forward. Given I have more bandwidth in my life at the moment, I'd love to spend the extra time needed on this to get it into Boost ideally as soon as possible—I'd really love to make it available for people to use! I'm not really sure who else might be able to review/accept contributions to Boost.Container in particular, though, as I'm pretty new here. Would anybody be able to help review this contribution and guide me through the process toward getting it merged? Thank you, Mehrdad
niedz., 12 cze 2022 o 10:58 Mehrdad Niknami via Boost <boost@lists.boost.org> napisał(a):
On Mon, Jan 18, 2021 at 12:39 AM Mehrdad Niknami <mniknami@berkeley.edu> wrote:
On Mon, Jan 18, 2021 at 12:32 AM Hans Dembinski < hans.dembinski@gmail.com> wrote:
Please do not top post. We have a no top-post policy for the mailing list.
I cannot help you with that. If he does not answer here, you could try to submit an issue to https://github.com/boostorg/container. Ion commits frequently to the repo, so I hope he sees that.
Best regards, Hans
Oh I see, okay thanks!
Best, Mehrdad
Hi all,
I just wanted to follow up on my stationary_vector proposal earlier. I do realize it's been a long time (I'm sorry about that)—I'll try to explain the current status below.
For context—I was in touch with Ion last year as was suggested here (thank you). He was very helpful and suggested improvements I would need to make to prepare this for a Boost review, and I made some changes in that light. Unfortunately, things stalled at that point, as life got in the way—initially for me, then for him—and he doesn't believe he'll have the bandwidth to review major contributions to Boost.Container anytime soon. Therefore he suggested I reach out to you all here in the hopes that someone may be able to move the ball forward.
Given I have more bandwidth in my life at the moment, I'd love to spend the extra time needed on this to get it into Boost ideally as soon as possible—I'd really love to make it available for people to use! I'm not really sure who else might be able to review/accept contributions to Boost.Container in particular, though, as I'm pretty new here.
Would anybody be able to help review this contribution and guide me through the process toward getting it merged?
Hi Mehrdād, Thank you for writing this library, and sharing it. I can share some hints on how to get a library accepted into Boost. But I am not sure if the same rules apply when you want to add a component to an existing library. Before a library gets into Boost it has to undergo the Boost Review process. Here's the link to the instructions describing the submission process: https://www.boost.org/development/submissions.html Here's the page describing the Boost Review process: https://www.boost.org/community/reviews.html The best one can do in order to make one's library get into Boost is to make sure the library meets the Boost Review standards. The process usually takes time. I can offer some very initial feedback about the design/usefulness. The link provided in the initial mail in this post does not work. I found this one instead: https://github.com/mehrdadn/libvital/blob/master/doc/cpp/vital/container/sta... I understand that the library offers different trade-offs to STL containers which one might find sometimes useful. But I am not sure when that would be. I would expect the docs to tell me when I would prefer this container to others already present in the STL. The docs say, stationary_vector is "semantically, it is *almost* a drop-in replacement for std::vector, except [...]". This is a misleading statement. "Almost" says nothing more than that it is actually not a drop-in replacement for std::vector. THe basic guarantee that std::vector provides is that it stores a contiguous array of elements underneath and that I can access it and pass it to a C-style function that works on raw arrays: std::vector<char> vec {'a', 'b', 'c', 'd'}; c_function_that_takes_pointer_and_length(vec.data(), vec.size()); I don't think stationary_vector can offer that. For that reason, I am not sure if "vector" is a good name for the container. The docs also say, "Exception-safety is intended to be on par with that of std::vector (if not better). I have tried to ensure this, but it has undergone limited testing." This does not seem comforting. "Exception safety" cannot be equal or better than that of another library. It is not even clear what you mean by this. It is not libraries that offer exception safety, but functions that offer guarantees as to what state the objects are left in when a function that modified them reported an error. It also seems to be saying that the author does not know if the library functions are exception safe. The best course of action would be to *document* the exception safety of the functions in the library and provide automatic tests for demonstrating that these guarantees are satisfied. How to test this is described at: https://www.boost.org/community/exception_safety.html "*Testing* for single-threaded use is done against test suites for std::vector from standard libraries" -- how can they pass, given that stationary_vector doesn't guarantee a contiguous layout of elements? I hope that you will find this critique helpful. Regards, &rzej;
Hi Andrzej, Thank you for the feedback. Yes, I think the process is slightly different for adding to existing libraries. I believe Ion was interested in getting this reviewed & then merged—he just didn't have the bandwidth. Unfortunately I'm not sure what the process is at that point—is there anyone else with the authority to review & merge code into Boost.Container? I'm not sure whom to reach out to to be honest. Regarding your notes, I can elaborate a bit on some of the design and try to clarify some portions of it, though this may be easier to do in more depth directly with those reviewing the code: I understand that the library offers different trade-offs to STL containers
which one might find sometimes useful. But I am not sure when that would be. I would expect the docs to tell me when I would prefer this container to others already present in the STL.
I actually did write up a documentation on this—apologies for neglecting to commit it to the repo. You can now find this information here <https://github.com/mehrdadn/libvital/blob/master/doc/cpp/vital/container/stationary_vector.boost.md> . The docs say, stationary_vector is "semantically, it is *almost* a drop-in
replacement for std::vector, except [...]". This is a misleading statement. "Almost" says nothing more than that it is actually not a drop-in replacement for std::vector.
What "almost" means here is that the container interface is almost exactly the same as that of std::vector, with the exception of contiguity. There are numerous practical uses of std::vector that never convert it to a raw pointer or require contiguity, and this container can be used as a drop-in replacement in such cases. THe basic guarantee that std::vector provides is that it stores a
contiguous array of elements underneath and that I can access it and pass it to a C-style function that works on raw arrays:
std::vector<char> vec {'a', 'b', 'c', 'd'}; c_function_that_takes_pointer_and_length(vec.data(), vec.size());
I don't think stationary_vector can offer that. For that reason, I am not sure if "vector" is a good name for the container.
Boost.Container already has *stable_vector* <https://www.boost.org/doc/libs/1_79_0/doc/html/container/non_standard_containers.html> which is even more discontiguous than stationary_vector. Personally, I'm not aware of this having caused any confusion for users, but if this has happened, I am open to suggestions for better names. (I have been unable to think of any names that describe the container better thus far, unfortunately.) The docs also say, "Exception-safety is intended to be on par with that of
std::vector (if not better). I have tried to ensure this, but it has undergone limited testing." This does not seem comforting.
What I meant was, I am not aware of specific benchmarks for this purpose (hence the wording), but I have tried to test it to the extent that I can. If you are aware of any particular benchmarks I would be more than happy to profile the performance of the container on them. "Exception safety" cannot be equal or better than that of another library.
It is not even clear what you mean by this.
It can definitely be better—for example, this would occur if (for example) another library only provides a basic exception safety guarantee for some function, and this library provides a strong exception safety guarantee for that same function. It is not libraries that offer exception safety, but functions that offer
guarantees as to what state the objects are left in when a function that modified them reported an error. It also seems to be saying that the author does not know if the library functions are exception safe.
I am not unaware of them, though I can see how it may give that impression. I simply have not (yet) documented them. The best course of action would be to *document* the exception safety of
the functions in the library and provide automatic tests for demonstrating that these guarantees are satisfied. How to test this is described at: https://www.boost.org/community/exception_safety.html
Thank you for the link! I'd never seen that link before. Currently I have relied on the tests provided by various standard libraries (in the section quoted below). I will have to look into that implementation and see how adaptable it is to this container; hopefully I can integrate it. Regarding documentation: yes! I will definitely be happy to have all the details documented. "*Testing* for single-threaded use is done against test suites for
std::vector from standard libraries" -- how can they pass, given that stationary_vector doesn't guarantee a contiguous layout of elements?
Of course those tests are excluded. Only applicable tests are run. If you have any suggestions on whom I may be able to reach out to for the review process for Boost.Container, I'd appreciate it! Best, Mehrdad
On 6/13/22 08:51, Mehrdad Niknami via Boost wrote:
I actually did write up a documentation on this—apologies for neglecting to commit it to the repo. You can now find this information here <https://github.com/mehrdadn/libvital/blob/master/doc/cpp/vital/container/stationary_vector.boost.md>
It sounds similar to the std::hive proposal: https://wg21.link/P0447
On Mon, Jun 13, 2022 at 2:13 AM Bjorn Reese via Boost <boost@lists.boost.org> wrote:
It sounds similar to the std::hive proposal:
Interesting. At a quick glance, I do see some critical differences; e.g., it doesn't seem like std::hive is random-access, but stationary_vector is: The container is therefore considered unordered but sortable. Lastly,
because there is no way of predicting in advance where erasures ('skips') may occur during iteration, an O(1) time complexity [ ] operator is not necessarily possible (depending on implementation) and therefore, the container is bidirectional but not random-access.
Mehrdad
While I recognize the approach with geometrically allocated blocks this makes the stationary_vector unsuitable as a deque replacement. One of deques virtues is its ability to grow to a large size without running out of memory. With geometric growth, a stationary_vector will be unable to grow to more than half of available memory. On Tue, Jan 5, 2021 at 6:23 PM Hans Dembinski via Boost <boost@lists.boost.org> wrote:
On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami@berkeley.edu> wrote:
It's similar, but not quite. std::deque uses fixed-size blocks and tends to be slow in my experience (at least in some implementations). stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes). Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand. This allows it to perform much more competitively with (and similarly to) std::vector. It may be what std::deque should have been, but isn't currently.
Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?
https://github.com/boostorg/container/blob/develop/include/boost/container/d...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
On Tue, Jan 5, 2021 at 12:35 AM Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Hi all,
Happy new year! New mailing list member here.
I've developed an STL-style stationary_vector class that retains elements in-place when growing.
hello This looks very similar to stable_vector. https://www.boost.org/doc/libs/1_75_0/doc/html/boost/container/stable_vector...
Hi, This shares some similarities to stable_vector, but it has some critical differences. One is that elements are *not* fully stable; elements that *follow* the insertion point are still shifted forward. Another is that contiguous elements are *mostly* stored contiguously, in arrays that preserve the logical order. (The elements are *not* stored in nodes scattered in arbitrary order across memory and hence there is no per-element overhead, unlike in stable_vector.) This results in much better performance, closer to that of vector. Mehrdad On Mon, Jan 4, 2021 at 4:58 PM Barath Kannan via Boost < boost@lists.boost.org> wrote:
On Tue, Jan 5, 2021 at 12:35 AM Mehrdad Niknami via Boost < boost@lists.boost.org> wrote:
Hi all,
Happy new year! New mailing list member here.
I've developed an STL-style stationary_vector class that retains elements in-place when growing.
hello
This looks very similar to stable_vector.
https://www.boost.org/doc/libs/1_75_0/doc/html/boost/container/stable_vector...
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (7)
-
Andrzej Krzemienski -
Barath Kannan -
Bjorn Reese -
Hans Dembinski -
Jeff Hajewski -
Mehrdad Niknami -
Peter Koch Larsen