Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-04 09:45:40
Thanks for the detailed review. Some minor comments follow.
> The library presents two containers, devector and batch_deque. I find
> the first one as a relatively simple but interesting vector extension
> supporting front insertions. In the future it could maybe take advantage
> of the backwards memory expansion (taking the previously adjacent free
> memory segment so that new elements could be added to front without
> moving the rest of the elements) supported by Boost.Interprocess and the
> Boost.Containerâs modified DLMalloc.
> 1) From a design point of view, I would prefer not to include the small
> buffer optimization with the data structure, although reviewing code, it
> seems many parts are to be optimized.
Everything should be removed by the optimizer; if not, then that section
of code needs to be amended with a constant expression.
> It's like just having small_vector
> without having vector, most libraries have two classes for these two use
> cases. Different classes also ease that a type erasured base class can
> be defined independent from the static storage size (Boost.Container
> calls it small_vector_base, LLVM calls it SmallVectorBase)Â I think we
> should have a devector, and add small_devector and static_devector
> containers if there is demand.
Can they share some of the implementation, or are we left with a double
(or triple) implementation effort?
> 2) Defaulting size_type to unsigned int is arbitrary and against
> existing practice.
We didn't do that as an arbitrary decision.
> According to the usual STL rules, size_type shall
> come from the allocator, which knows what type can represent the number
> of elements that can be allocated.
I have no problems with STL rules, but it as you point out, even
Boost.Container deviates from several of those.
> 3) reserve_only_tag: I would rename it as âreserve_only_tâ (similarly to
> std::allocator_arg_t and Boost.Containerâs âdefault_init_tâ). The front
> and back capacity version should be enough as I thinkÂ devector should
> not show preference for back insertion (if a user wants only a back
> capacity, then it would use a vector and not a devector).
So you would prefer it to divide the buffer in two approximately equal
chucks? Or that one has to specify each chunk size explicitly each time
(so full symmetry, and the one-sided constructor gone)?
> speaking, capacity constructors are a bit redundant, but the same could
> be said about default constructing constructors:
> //it could be implemented as default constructor + resize
> explicit vector(size_type n, const Allocator & allocator = Allocator());
Yes, just like push_back is redundant when we have insert( iter, x ) :-)
> A reserve-only constructor plus an âunsafeâ emplacement could make a
> container similar to an array, where no redundant checks are done when
> filling the array. But I donât expect noticeable performance gains with
> this reserve-only constructor.
No, it is for convenience.
> 4) unsafe_uninitialized_tag: I donât like these non-safe constructors,
> which areÂ the cases?. With reserve-only constructors + unsafe emplace
> back a user can achieve nearly the same performance. For POD types (like
> the socket example mentioned in the documentation), I would suggest
> something like Boost.Containerâs âdefault_init_tâ. Instead of
> âunsafe_uninitialized_resize_frontâ I suggest resize_front(size_type,
I didn't know about these default_init_t when we started in 2015. They
have a good design IMO. But unfortunately they don't get rid of double
initialization for non-trivial types. So maybe both
resize_front( size_type, default_init_t )
resize_front( size_type, uninitialized_t )
would be an idea.
> 5) reserve() / resize(): I think they have no sensible meaning in the
> container (capacity() could be useful, depending on the reallocation
> strategy). We should not treat back insertion as the âdefaultâ
> insertion. IMHO the API of devector should be symmetrical.
Symmetry is good, but what about generic code?
> 8) Regarding "move_if_noexcept", Boost.Container does not use it as it
> consider a pessimized design for a situation (throwing moves) that will
> occur nearly never
> devector itself would be copied if
> small_buffer_size is used, etc.).
only when it stores elements with a non-noexcept move though.
> 9) Minor comment 2: IMHO I think iterators would be better as classes
> instead of pointers, a user can always use data() to make sure pointers
> are returned. Many times unwanted overload resolutions can happen if
> pointers are used, so I prefer the type safety offered by a class-based
> iterator. It can also offer checked iterators in the future.
I think you have a way to turn these into pointers again in
Boost.Container, By defining some preprocessor symbol, right? Having
pointers matters when interfacing with other types, because this is the
only case where the iterators are seen as contiguous.
I would much rather see that in debug mode the iterator type is a class
and in release mode it is a pointer compared to having extra
> 2) Segment_iterators: Raw pointers are stored in segment iterators. That
> means that those could not be placed in the memory that the allocator
> allocates, if the allocator does not defined ::pointer as T*.
There is definitely some work relating to allocators and such.
> Also, it seems strange that there is not segment_type/segment_info
> class. The iterator itself has members that return the address and the
> size of a segment. I think thatâs unexpected, the expected segment
> iterator would return a reference to a class (e.g. segment_type) that
> represents the segment,
I think we discussed that design at some point. Benedek, can you
remember why we went in the other direction?
> 3) stable_insert: I canât see the usefulness of this operation. A
> batch_deque is a sequence, but the user cares about the insertion point
> but does not care if additional elements are created somewhere? I fail
> to see a real use case.
A deque is a sequence, sure, but also a container with reference
stability. I'm curious, when you use Boost.Intrusive, where do store the
> emplace_slow_path: The forced temporary creation should be avoided, it
> is overkill for containers of containers, devector<static_vector> or
> containers with sentinel nodes. IMHO supporting references to already
> included elements is a bad feature of std::vector (a corner case
> supported in single element insertion, ignored for ranges, etc.)
> Boost.Container chose not to support it and no one has demanded that
Yeah, I remember heated discussion about this in past. I'm not a fan of
that feature of the STL containers.
> Reallocation strategy: First, I considered this strategyunnatural, but
> now I am not sure. For a push_front, if no free front capacity is found,
> but there is free back capacity, then all data is shifted to insert the
> element. If interleaved front and back insertions are performed, I donât
> know if this will lead to too many data movements. When memory is
> reallocated to make room for a front insertions, the free back capacity
> is unchanged and all new free capacity goes to front. This means that
> the last operation (front or back) determines where all the new capacity
> goes. I find a bit strange that N == front_back_capacity() does not mean
> that a reallocation will happen if we push_back N times, as repeated
> data movement will happen if front_free_capacity() is available.
> Another strategy is to treat both ends independently: if front insertion
> has no free space, it could always reallocate and make room at front, so
> further push_fronts donât provoke data movement. This would be similar
> to batch_deque, where memory is allocated if there is no free front
> capacityregardless of the free back capacityÂ (no data movement),f and
> free segment is recycled from back capacity to insert elements at front.
> Obviously, this approach consumes more memory. Yet another strategy
> would be distribute any new free capacity (after reallocation) between
> front and back, indepently from which operation (back or front) has
> provoked the allocation.
This is tricky. I think the best is to treat both ends independently.
If you start moving things around, you can break the O(1) amortized
guarantee by interleaving push_front/push_back.
> 2) The data structure o batch_deque is slightly bigger than the
> traditional one, just asking if itâs intended or it was developed like
> this to reuse code. Traditional deque (from SGI) used four elements (map
> pointer, map size, iterator to begin, iterator to end). Your
> implementation defines the map as a devector, which stores size and
> capacity for the map, but this allows youÂ handle the excess capacity of
> the map, Iâm not sure if it adds performance benefits.
Reuse & simplicity would be the answer. If the iterators are fat, I bet
you get the same size as as a batch_deque.
Having a secondary ad hoc data structure with amortized O(1) double
ended growth doesn't exactly make the code easier to reason about.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk