Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

On 21/09/2017 19:38, Thorsten Ottosen via Boost wrote:

Dear users and members of Boost,

I'm proud to announce that the formal review of Benedek Thaler's Boost.DoubleEnded library starts today, September 21, and runs through September 30. This library is the result of Benedek's participation in Google Summer of Code 2015.

Hi, this is my review of Boost.DoubleEnded. ------------------------------------- ------------------------------------- What is your evaluation of the design? ------------------------------------- ------------------------------------- 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. ---------- devector -------- 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. 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. 2) Defaulting size_type to unsigned int is arbitrary and against existing practice. 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 find interesting the idea of expressing a different size_type to save space, but I am not sure if that should come from the allocator or from an option. 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). Strictly 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()); 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. 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, default_init_t) 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. 6) unsafe_push_back/front: I think they can be useful, many times we iterate until a known upper bound and capacity checks might be redundant in some code, just like we do with arrays. I suggest replacing “unsafe” with “unchecked” and “push” with “emplace” (which is much more general): “unchecked_emplace_back/front(Args&&….)”. 7) growth_policy: This is an option that could be interesting not only for devector but also for vector. However, I would prefer passing options as a single argument where options are combined, so that the class declaration is not modified each time a new option is added. Something like: template class devector; using myoptions = make_options_t; usinge mydevector = devector; a similar approach is used in Boost.Intrusive and will be added to Boost.Container. 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 and few times will be handled using the provided strong guarantees. On the other hand, most people will notice the big slowdown that will receive because their move constructors cannot be marked as noexcept (pimpl idiom, small buffer optimization, sentinel-node based lists, devector itself would be copied if small_buffer_size is used, etc.). I think “move_if_noexcept” was just added for backwards compatibility with C++03’s strong guarantee, but devector does not need to follow the same rule. I understand many (most?) people don’t agree here, but don’t think we should sacrifice devector performance just to support rare throwing cases. 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. 10) Default growth factor of 4. Sounds like overkill, 2 or 1.5 sounds more reasonable and in line with user expectations based on existing practice in STL and Boost. I’m not sure if shrinking should be part of the trait. ---------- Batch_deque -------- Many of the comments from devector are applicable here, so I will not repeat them here. 1) In general, I don’t see the need of batch_deque as a different container, because it’s basically a deque with some options (segment size and additional operations). Those could be added to boost::container::deque without breaking anythying. 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*. 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, which has the required operations, and also internal begin()/end() operations to obtain segment-local iterators (a la unordered containers). This could allow some optimized segment-based algorithms (see lafstern.org/matt/segmented.pdf, for more information) 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. ------------------------------------- ------------------------------------- What is your evaluation of the implementation? ------------------------------------- ------------------------------------- I think it’s solid. Tests look good. -------------------------- devector -------------------------- emplace_slow_path: The forced temporary creation should be avoided, it is overkill for containers of containers, devector 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 feature: http://www.boost.org/doc/libs/1_65_1/doc/html/container/Cpp11_conformance.ht... 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. emplace_slow_path: // construct at back + 1 from back (no guard) alloc_construct(end(), std::move(back())); // move back half right std::move_backward(position, end() - 1, end()); ++_back_index; This does not seem exception safe “++_back-index” should be done just after alloc_construct, same for front insertion. insert_range_slow_path_near_front/back: I see that construction + rotation is done, but I think this is not optimal, the implementation might be simplier, but more than necessary data movement is done. Range insert: A temporary temp_devector is used, which means copying data two times. The inline storage for 32 elements can blow the stack if T is something big (like static_vector) -------------------------- batch_deque -------------------------- 1) I like that deque_[const_]iterator is lightweight, I don’t know if iteration/access it’s more efficient than more traditional approaches. boost::container::deque iterators are really fat and should be improved to something similar to batch_deque iterator. On the other hand deque_segment_[const_]iterators are heavier than needed, and I think they could be just like vector iterators if used to iterate a single segment. The problem is that deque_segment_iterator works both as segment information class and as a local iterator. I think a similar approach to PolyCollection’s “segment_traversal_info” as segment information could work better, as it allows really lightweight local iterators that can speed up specialized segmented algorithms (local iterators could be just vector-like iterators inside a segment). 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. 3) I haven’t thoroughly reviewed all the code, but many devector comments are applicable: rotation, move_if_noexcept, etc. ------------------------------------- ------------------------------------- What is your evaluation of the documentation? ------------------------------------- ------------------------------------- Documentation is correct, but I expected more detail. If one of the goals of the library is efficiency, benchmarks should be there (maybe against Boost and Std vector and deque). ------------------------------------- ------------------------------------- What is your evaluation of the potential usefulness of the library? ------------------------------------- ------------------------------------- devector might be useful, I have doubts with batch_deque. Deque in general is not the most used STL container, so I don’t expect a lot of users, maybe for specialized cases. ------------------------------------- ------------------------------------- Did you try to use the library? With which compiler(s)? Did you have any problems? ------------------------------------- ------------------------------------- Just executed tests and examples and debugged to help code review. MSVC 2017 triggers quite a lot of warnings, mainly about constant conditional expressions. ------------------------------------- ------------------------------------- How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? ------------------------------------- ------------------------------------- Several hours analyzing the design and reading the code. An hour playing with the library with MSVC. ------------------------------------- ------------------------------------- Are you knowledgeable about the problem domain? ------------------------------------- ------------------------------------- I do think so. I’ve written a lot of containers for Boost and outside Boost. Deque is not my favorite container, though ;-) ------------------------------------- ------------------------------------- ¿Should we accept the library? ------------------------------------- ------------------------------------- I think the library (see my design comments) and the documentation still need improvements, but it's not the main issue. I’m reluctant to accept the library because I don’t see substantial benefits of batch_deque against deque (configurable segment size could be added to Boost.Container if that feature is considered useful), and I don’t know if the use cases where devector is supposed to shine needs a whole new library (we have no clear rules about how tiny a library can be, but in this case it would be a new container and reimplementation of another). Joaquín has proposed to merge this proposal to Boost.Container, but supported compilers and goals are quite different and a direct merge would be problematic as Boost.Container would loose coherency, common goals and minimum requirements between all containers. A middle solutions is to: 1) Start “porting” devector, after all issues have been agreed, (without small vector optimization, at least in the first version) to Boost.Container’s requirements (including some pre C++11 compilers) 2) Improve Boost.Container’s deque to support features (and maybe code) from batch_deque (configurable segment size, local iterators, etc.). That’s a lot of work, discards a lot of batch_queue code and I don’t know if Benedek would agree to help on this task after I spoke against this option when it was proposed and after doing so much work to write the library. Best, Ion