vector::clear in libc++ for trivially destructible types

Question

Would vector<T, std::allocator<T>>::clear() be O(1) if T is trivially destructible?

gcc's implementation in bits/stl_vector.h calls std::_Destroy(bits/stl_construct.h). This implementation which optimizes for the case of T being trivially destructible through tag-dispatching on std::is_trivially_destructible<T>.

Looking through llvm's(3.5.0) implementation, vector::clear calls std::allocator<T>::destroy on every element, which in turn invokes the destructor.

 _LIBCPP_INLINE_VISIBILITY void destroy(pointer __p) {__p->~_Tp();}

Would this end up getting optimized out making vector::clear() O(1) in libc++ as well?

Answer 1

In general, a conforming implementation cannot implement std::vector::clear in O(1) for types with non-trivial destructors.

C++11 [container.requirements.general]/3 states:

For the components affected by this subclause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits<allocator_type>::construct function and destroyed using the allocator_traits<allocator_type>::destroy function (20.6.8.2).

Since clear must destroy size() elements, it necessarily needs to make O(N) calls to the destroy function of the associated allocator. The end result can, however, effectively take constant time if each of those calls takes zero time to complete (i.e., does nothing).

A quick look at the implementation of _Destroy in the current revision of libstdc++'s bits/stl_construct.h shows that it attempts to only perform this optimization when the default allocator is in use:

  /**
   * Destroy the object pointed to by a pointer type.
   */
  template<typename _Tp>
    inline void
    _Destroy(_Tp* __pointer)
    { __pointer->~_Tp(); }

  template<bool>
    struct _Destroy_aux
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator __first, _ForwardIterator __last)
      {
        for (; __first != __last; ++__first)
          std::_Destroy(std::__addressof(*__first));
      }
    };

  template<>
    struct _Destroy_aux<true>
    {
      template<typename _ForwardIterator>
        static void
        __destroy(_ForwardIterator, _ForwardIterator) { }
    };

  /**
   * Destroy a range of objects.  If the value_type of the object has
   * a trivial destructor, the compiler should optimize all of this
   * away, otherwise the objects' destructors must be invoked.
   */
  template<typename _ForwardIterator>
    inline void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last)
    {
      typedef typename iterator_traits<_ForwardIterator>::value_type
                       _Value_type;
      std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
        __destroy(__first, __last);
    }

  /**
   * Destroy a range of objects using the supplied allocator.  For
   * nondefault allocators we do not optimize away invocation of 
   * destroy() even if _Tp has a trivial destructor.
   */

  template<typename _ForwardIterator, typename _Allocator>
    void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
         _Allocator& __alloc)
    {
      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
      for (; __first != __last; ++__first)
        __traits::destroy(__alloc, std::__addressof(*__first));
    }

  template<typename _ForwardIterator, typename _Tp>
    inline void
    _Destroy(_ForwardIterator __first, _ForwardIterator __last,
         allocator<_Tp>&)
    {
      _Destroy(__first, __last);
    }

but unfortunately doesn't quite get it right since the standard allows specialization of templates in the std namespace that depend on user-defined types ([namespace.std]/1). For example, this program:

struct mytype {
    int value;

    mytype(int v) : value{v} {}

    operator int() const { return value; }
};

namespace std {
template <>
struct allocator<::mytype> {
    using value_type = mytype;

    allocator() = default;
    template <typename U>
    allocator(const allocator<U>&) {}

    mytype* allocate(std::size_t n) {
        auto result = ::operator new(n * sizeof(mytype));
        if (!result) throw bad_alloc();
        return static_cast<mytype*>(result);
    }

    void deallocate(mytype* ptr, std::size_t) noexcept {
        ::operator delete(ptr);
    }

    template <typename U, typename...Args>
    void construct(U* ptr, Args&&...args) {
        ::new ((void*)ptr) U(std::forward<Args>(args)...);
        std::cout << "constructed " << *ptr << '\n';
    }

    template <typename U>
    void destroy(U* ptr) noexcept {
        std::cout << "destroying " << *ptr << '\n';
        ptr->~U();
    }

    friend constexpr bool operator == (const allocator&, const allocator&) noexcept {
        return true;
    }
    friend constexpr bool operator != (const allocator&, const allocator&) noexcept {
        return false;
    }
};
} // namespace std

int main() {
    std::vector<mytype>{1,2,3};
}

should output:

constructed 1
constructed 2
constructed 3
destroying 3
destroying 2
destroying 1

(the order of element destruction is unspecified, so the "destroying" lines can be in any order but must all be present.) libstdc++ incorrectly "optimizes" out the calls to allocator<mytype>::construct and allocator<mytype>::destroy, but of course libc++ gets it right (DEMO).