Re: [boost] double_ended - request formal review
On 15 July 2016 at 16:51, Benedek Thaler <thalerbenedek@gmail.com> wrote:
Dear Boost,
I'd like to request the review of the double_ended library.
Code: https://github.com/erenon/double_ended Documentation: http://erenon.hu/double_ended
The library contains two classes. Excerpt from the documentation:
* `devector` is a hybrid of the standard vector and deque containers, as well as the small_vector of Boost.Container. It offers cheap (amortized constant time) insertion at both the front and back ends, while also providing the regular features of std::vector, in particular the contiguous underlying memory. In contrast to the standard vector, however, devector offers greater control over its internals. Like small_vector, it can store elements internally without dynamically allocating memory.
Not related to your request per-se, but I think this occasion is as good as any to discuss the library. devector is an interesting variant of vector, but it gives the illusion that is could be used as a queue. However given the implementation, it seems elements removed from either end will never be reclaimed. I suggest documenting that limitation or having a threshold above which memory is actually freed.
On Thu, Jul 21, 2016 at 4:59 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
On 15 July 2016 at 16:51, Benedek Thaler <thalerbenedek@gmail.com> wrote:
devector is an interesting variant of vector, but it gives the illusion that is could be used as a queue. However given the implementation, it seems elements removed from either end will never be reclaimed.
I suggest documenting that limitation or having a threshold above which memory is actually freed.
Thanks for the feedback, Mathias. You are right. This implementation detail is a consequence of honoring reserve calls: devector<int> d; d.push_back(1); d.reserve_front(100); d.reserve_back(100); The reserve back has to keep the front capacity untouched or it breaks the promise of it. This also applies to a series of push_front/pop_backs, for example. I'll document this behavior. During the review, we'll see if we need more radical changes, e.g: changing the guarantees of reserve calls. Thanks, Benedek
On 7/24/2016 8:44 AM, Benedek Thaler wrote:
On Thu, Jul 21, 2016 at 4:59 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
On 15 July 2016 at 16:51, Benedek Thaler <thalerbenedek@gmail.com> wrote:
devector is an interesting variant of vector, but it gives the illusion that is could be used as a queue. However given the implementation, it seems elements removed from either end will never be reclaimed.
I suggest documenting that limitation or having a threshold above which memory is actually freed.
Thanks for the feedback, Mathias. You are right. This implementation detail is a consequence of honoring reserve calls:
devector<int> d; d.push_back(1); d.reserve_front(100); d.reserve_back(100);
The reserve back has to keep the front capacity untouched or it breaks the promise of it. This also applies to a series of push_front/pop_backs, for example.
I'll document this behavior. During the review, we'll see if we need more radical changes, e.g: changing the guarantees of reserve calls.
I haven't looked at the code but from your description it seems like there is an implicit connection between reserve_front and reserve_back. I would expect this to be explicit and there to be 3 reserve methods. reserve_front( size ) reserve_back( size ) reserve( front_size, back_size ) And that the implementation only maintain stability until a realloc occurs from any source (push/insert/reserve/whatever). If a realloc occurs it should be free to reposition the elements in the already allocated memory block by rotating them forward or back. It should also be free to change the available capacity at either end. If the user needs fine grained control they can use the reserve methods to control reallocation.
On 26-07-2016 18:14, Michael Marcin wrote:
I haven't looked at the code but from your description it seems like there is an implicit connection between reserve_front and reserve_back.
Rather, it is the opposite: they are independent. Calling one does not modify the promise of the other.
I would expect this to be explicit and there to be 3 reserve methods.
reserve_front( size ) reserve_back( size ) reserve( front_size, back_size )
And that the implementation only maintain stability until a realloc occurs from any source (push/insert/reserve/whatever).
Since devector strives to be close to vector, it has a reserve function taking one argument which does what vector does (important for generic code). I guess a two argument version would add a slight convenience, but not much.
If a realloc occurs it should be free to reposition the elements in the already allocated memory block by rotating them forward or back.
It should also be free to change the available capacity at either end.
Yeah, but the hard question is what is gained by that? What would a sound policy look like? There is the policy parameter which could do more things, but we need a really sound policy for moving things around implictly. I suspect that it will create confusing and lead to few if any benefits. The current implementation should be simple to understand and use. kind regards Thorsten
On 24 July 2016 at 14:44, Benedek Thaler <thalerbenedek@gmail.com> wrote:
Thanks for the feedback, Mathias. You are right. This implementation detail is a consequence of honoring reserve calls:
devector<int> d; d.push_back(1); d.reserve_front(100); d.reserve_back(100);
The reserve back has to keep the front capacity untouched or it breaks the promise of it. This also applies to a series of push_front/pop_backs, for example.
I think it's pretty serious. Consider: int n; devector<int> d; d.push_back(0); for(int i=0; i<n; ++i) { d.push_back(i); d.pop_front(); } You end up with ever growing memory consumption, despite the devector only containing one or two elements at all times.
On 26-07-2016 23:00, Mathias Gaunard wrote:
On 24 July 2016 at 14:44, Benedek Thaler <thalerbenedek@gmail.com> wrote:
Thanks for the feedback, Mathias. You are right. This implementation detail is a consequence of honoring reserve calls:
devector<int> d; d.push_back(1); d.reserve_front(100); d.reserve_back(100);
The reserve back has to keep the front capacity untouched or it breaks the promise of it. This also applies to a series of push_front/pop_backs, for example.
I think it's pretty serious. Consider:
int n;
devector<int> d; d.push_back(0);
for(int i=0; i<n; ++i) { d.push_back(i); d.pop_front(); }
You end up with ever growing memory consumption, despite the devector only containing one or two elements at all times.
Mathias, There are arguments for either behavior. devector is modelled after vector, and so it tries to do it like a vector does. And vector doesn't change the capacaity with pop_back(). It's not a circular queue either, and never can be because it promises that the [begin,end) range is one segment. Anyway, Benedek needs a review manager. I could do it, but I think it should not be me as I was his GSOC mentor. kind regards Thorsten
participants (4)
-
Benedek Thaler -
Mathias Gaunard -
Michael Marcin -
Thorsten Ottosen