Boost C++ Libraries: Ticket #6575: copy_remaining_to and copy_some_and_update don't use allocator_traits for construction

Ion Gaztañaga — Sat, 18 Feb 2012 08:41:35 GMT

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.

Sun, 19 Feb 2012 02:57:30 GMT

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

Sun, 19 Feb 2012 03:09:07 GMT

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;                                                        \
   }                                                                             \
}                                                                                \

Ion Gaztañaga — Sun, 19 Feb 2012 15:59:38 GMT

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.

Ion Gaztañaga — Mon, 20 Feb 2012 12:33:15 GMT

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.

Fri, 24 Feb 2012 03:27:49 GMT

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.

status changed; resolution set

Ion Gaztañaga — Fri, 24 Aug 2012 21:43:07 GMT

status new → closed
resolution → fixed

Fixed in Boost 1.50 using an aligned buffer.