Modify

Ticket #6575 (closed Bugs: fixed)

Opened 2 years ago

Last modified 20 months ago

copy_remaining_to and copy_some_and_update don't use allocator_traits for construction

Reported by: Erik Jensen <Erik.Jensen@…> Owned by: igaztanaga
Milestone: To Be Determined Component: container
Version: Boost 1.49.0 Severity: Problem
Keywords: Cc:

Description

In advanced_insert_aux_emplace in advanced_insert_int.hpp, neither copy_remaining_to nor copy_some_and_update use allocator_traits for construction, even though the uninitialized versions do. This is problematic for allocators that need to alter the constructor's arguments list.

Thanks, Erik Jensen

Attachments

Change History

comment:1 Changed 2 years ago by igaztanaga

copy operations do not propagate the allocator because all the do is copy assignment, not copy construction. Allocators are propagated only in copy construction, as already built elements should be already constructed with the scoped allocator propagation model. That's consistent with the C++11 container implementations I've reviewed.

comment:2 Changed 2 years ago by Erik Jensen <Erik.Jensen@…>

Certainly copy assignment should not propagate the allocator. The problem with these two functions is that they construct a new object on the stack which they then move/copy into place. It is this initial construction that is the issue, not the subsequent move/copy.

The following is an attempt of mine to fix the issue (there may well be a better way, but my knowledge here is limited):

   virtual void copy_remaining_to(Iterator p)                                       \
   {                                                                                \
      if(!this->used_){                                                             \
         aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;    \
         value_type *vp = static_cast<value_type *>(static_cast<void *>(&v));       \
         alloc_traits::construct(a_, vp                                             \
            BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _));       \
         *p = boost::move(*vp);                                                     \
         this->used_ = true;                                                        \
      }                                                                             \
   }                                                                                \

I believe this is important for a few reasons. First, there are probably other uses for the allocator wanting to handle object construction than just propagating the allocator. Second, if construct is being used for allocator propagation, the allocator probably doesn't have a default constructor, leading to a build error with the current implementation. Finally, even if the allocator does have a default constructor, having a different allocator would probably force a potentially expensive copy from the temporary rather that a cheap move operation, defeating an important reason to use emplace.

Thanks,
Erik Jensen

comment:3 Changed 2 years ago by Erik Jensen <Erik.Jensen@…>

Err... forgot to destruct the temporary. It should have been this:

virtual void copy_remaining_to(Iterator p)                                       \
{                                                                                \
   if(!this->used_){                                                             \
      aligned_storage<sizeof(value_type), alignment_of<value_type>::value> v;    \
      value_type *vp = static_cast<value_type *>(static_cast<void *>(&v));       \
      alloc_traits::construct(a_, vp                                             \
         BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _));       \
      try {                                                                      \
         *p = boost::move(*vp);                                                  \
      } catch (...) {                                                            \
         alloc_traits::destroy(a_, vp);                                          \
         throw;                                                                  \
      }                                                                          \
      alloc_traits::destroy(a_, vp);                                             \
      this->used_ = true;                                                        \
   }                                                                             \
}                                                                                \

comment:4 Changed 2 years ago by igaztanaga

Both libc++ (clang) and libstdc++ (g++) implement the same approach as Boost.Container. The inserted element gets the container allocator as it is moved to an existing object built with with allocator_traits. I think the issue is not clear, and only happens in vector and deque (node-based containers allocates some memory and build the object directly there).

Instead of aligned storage, or a temporary, which might use some undefined stack space (we don't know how big T is), another alternative is to reserve additional capacity for two new elements at the end of the vector/deque before emplacing (instead of just one, it's really a negligible cost, as the vector capacity grows exponentially). Then built the object with allocator_traits in the end() + 1 position (with a rollback operation to destroy the element at the end of the scope, as it should be destroyed anyway after being moved to the right position).

This is not simple to do in Boost.Container as all [uninitialized]copy operations are hidden behind an abstract interface to avoid instantiating insertion bookeeing functions for each iterator type, but maybe we need some interface extension.

comment:5 Changed 2 years ago by igaztanaga

I think you've found a LWG issue here. We might end up calling two different functions if we call emplace_back(usually implemented via allocator_traits at the end of the buffer) or emplace(iterator, ...) (usually implemented via a temporary moved to the required position).

I think you're proposal is the correct one, construct the temporary via allocator_traits: the programmer does not receive any surprising error with non-default constructible allocators, performance is optimum and the constructor to be called is always well-known by the programmer. Thanks again for the report.

comment:6 Changed 2 years ago by Erik Jensen <Erik.Jensen@…>

For what it's worth, the STL implementation that ships with the Visual Studio 11 preview solves this problem by always doing an emplace_back, and then calling std::rotate if necessary to get everything into the correct spot. This way, it is always calling construct on an uninitialized memory location.

comment:7 Changed 20 months ago by igaztanaga

  • Status changed from new to closed
  • Resolution set to fixed

Fixed in Boost 1.50 using an aligned buffer.

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


E-mail address and user name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.