llfio_v2_xxx::algorithm::trivial_vector< T > Class Template Reference

Provides a constant time capacity expanding move-only STL vector. Requires T to be trivially copyable. More...

#include "trivial_vector.hpp"

Inheritance diagram for llfio_v2_xxx::algorithm::trivial_vector< T >:

Public Types
using	value_type = T
	Value type.
using	pointer = value_type *
	Pointer type.
using	const_pointer = typename std::pointer_traits< pointer >::template rebind< const value_type >
	Const pointer type.
using	difference_type = typename std::pointer_traits< pointer >::difference_type
	Difference type.
using	size_type = typename std::make_unsigned< difference_type >::type
	Size type.
using	reference = value_type &
	Reference type.
using	const_reference = const value_type &
	Const reference type.
using	iterator = pointer
	Iterator type.
using	const_iterator = const_pointer
	Const iterator type.
using	reverse_iterator = std::reverse_iterator< iterator >
	Reverse iterator type.
using	const_reverse_iterator = std::reverse_iterator< const_iterator >
	Const reverse iterator type.

Public Member Functions
void	resize (size_type count)
	Resizes container, filling any new items with default constructed value_type
void	resize (size_type count, const value_type &v)
	Resizes container.
void	assign (size_type count, const value_type &v)
	Assigns.
void	assign (InputIt first, InputIt last)
	Assigns.
void	assign (std::initializer_list< value_type > il)
	Assigns.
reference	at (size_type i)
	Item index, bounds checked.
const_reference	at (size_type i) const
	Item index, bounds checked.
reference	operator[] (size_type i)
	Item index, unchecked.
const_reference	operator[] (size_type i) const
	Item index, unchecked.
reference	front ()
	First element.
const_reference	front () const
	First element.
reference	back ()
	Last element.
const_reference	back () const
	Last element.
pointer	data () noexcept
	Underlying array.
const_pointer	data () const noexcept
	Underlying array.
iterator	begin () noexcept
	Iterator to first item.
const_iterator	begin () const noexcept
	Iterator to first item.
const_iterator	cbegin () const noexcept
	Iterator to first item.
iterator	end () noexcept
	Iterator to after last item.
const_iterator	end () const noexcept
	Iterator to after last item.
const_iterator	cend () const noexcept
	Iterator to after last item.
reverse_iterator	rbegin () noexcept
	Iterator to last item.
const_reverse_iterator	rbegin () const noexcept
	Iterator to last item.
const_reverse_iterator	crbegin () const noexcept
	Iterator to last item.
reverse_iterator	rend () noexcept
	Iterator to before first item.
const_reverse_iterator	rend () const noexcept
	Iterator to before first item.
const_reverse_iterator	crend () const noexcept
	Iterator to before first item.
bool	empty () const noexcept
	If empty.
size_type	size () const noexcept
	Items in container.
size_type	max_size () const noexcept
	Maximum items in container.
void	reserve (size_type n)
	Increase capacity.
size_type	capacity () const noexcept
	Items can be stored until storage expanded.
void	shrink_to_fit ()
	Removes unused capacity.
void	clear () noexcept
	Clears container.
iterator	insert (const_iterator pos, const value_type &v)
	Inserts item.
iterator	insert (const_iterator pos, value_type &&v)
	Inserts item.
iterator	insert (const_iterator pos, size_type count, const value_type &v)
	Inserts items.
iterator	insert (const_iterator pos, InputIt first, InputIt last)
	Inserts items.
iterator	insert (const_iterator pos, std::initializer_list< value_type > il)
	Inserts items.
iterator	emplace (const_iterator pos, Args &&... args)
	Emplace item.
iterator	erase (const_iterator pos)
	Erases item.
iterator	erase (const_iterator first, const_iterator last)
	Erases items.
void	push_back (const value_type &v)
	Appends item.
void	push_back (value_type &&v)
	Appends item.
reference	emplace_back (Args &&... args)
	Appends item.
void	pop_back ()
	Removes last element.
void	swap (trivial_vector_impl &o) noexcept
	Swaps.

Detailed Description

template<class T>
class llfio_v2_xxx::algorithm::trivial_vector< T >

Provides a constant time capacity expanding move-only STL vector. Requires T to be trivially copyable.

As a hand waving estimate for whether this vector implementation may be useful to you, it usually roughly breaks even with std::vector on recent Intel CPUs at around the L2 cache boundary. So if your vector fits into the L2 cache, this implementation will be no better, but no worse. If your vector fits into the L1 cache, this implementation will be worse, often considerably so.

Note that no STL allocator support is provided as T must be trivially copyable (for which most STL's simply use memcpy() anyway instead of the allocator's construct), and an internal section_handle is used for the storage in order to implement the constant time capacity resizing.

We also disable the copy constructor, as copying an entire backing file is expensive. Use the iterator based copy constructor if you really want to copy one of these.

The very first item stored reserves a capacity of utils::page_size()/sizeof(T) on POSIX and 65536/sizeof(T) on Windows. Capacity is doubled in byte terms thereafter (i.e. 8Kb, 16Kb and so on). As mentioned earlier, the capacity of the vector needs to become reasonably large before going to the kernel to resize the section_handle and remapping memory becomes faster than memcpy. For these reasons, this vector implementation is best suited to arrays of unknown in advance, but likely large, sizes.

Benchmarking notes for Skylake 3.1Ghz Intel Core i5 with 2133Mhz DDR3 RAM, L2 256Kb, L3 4Mb:

• OS X with clang 5.0 and libc++
  • push_back(): 32768,40,59 65536,36,76 131072,78,159 262144,166,198 524288,284,299 1048576,558,572 2097152,1074,1175 4194304,2201,2394 8388608,4520,5503 16777216,9339,9327 33554432,24853,17754 67108864,55876,40973 134217728,122577,86331 268435456,269004,178751 536870912,586466,330716
  • resize(): 8192,9,18 16384,14,20 32768,27,32 65536,66,43 131072,107,59 262144,222,131 524288,445,322 1048576,885,500 2097152,1785,1007 4194304,3623,2133 8388608,7334,4082 16777216,17096,8713 33554432,36890,18421 67108864,73593,40702
• Windows 10 with VS2017.5:
  • push_back(): 8192,17,70 16384,22,108 32768,36,117 65536,51,152 131072,174,209 262144,336,309 524288,661,471 1048576,1027,787 2097152,2513,1361 4194304,5948,2595 8388608,9919,4820 16777216,23789,9716 33554432,52997,19558 67108864,86468,39240 134217728,193013,76298 268435456,450059,149644 536870912,983442,318078
  • resize(): 8192,9,48 16384,17,44 32768,35,48 65536,62,72 131072,134,114 262144,132,168 524288,505,330 1048576,988,582 2097152,1501,1152 4194304,2972,2231 8388608,6122,4436 16777216,12483,8906 33554432,25203,17847 67108864,52005,53646 134217728,102942,86502 268435456,246367,177999 536870912,405524,294685

Constructor & Destructor Documentation

trivial_vector()

template<class T >

constexpr llfio_v2_xxx::algorithm::trivial_vector< T >::trivial_vector ( )

inlineconstexpr

{}  // NOLINT

Member Function Documentation

assign() [1/3]

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::assign ( InputIt  first, InputIt  last  )

inlineinherited

Assigns.

      {
        clear();
        insert(begin(), first, last);
      }

assign() [2/3]

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::assign ( size_type  count, const value_type &  v  )

inlineinherited

Assigns.

      {
        clear();
        insert(begin(), count, v);
      }

assign() [3/3]

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::assign ( std::initializer_list< value_type >  il )

inlineinherited

Assigns.

{ assign(il.begin(), il.end()); }

at() [1/2]

reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::at ( size_type  i )

inlineinherited

Item index, bounds checked.

      {
        if(i >= size())
        {
          LLFIO_EXCEPTION_THROW(std::out_of_range("bounds exceeded"));  // NOLINT
        }
        return _begin[i];
      }

at() [2/2]

const_reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::at ( size_type  i ) const

inlineinherited

Item index, bounds checked.

      {
        if(i >= size())
        {
          LLFIO_EXCEPTION_THROW(std::out_of_range("bounds exceeded"));  // NOLINT
        }
        return _begin[i];
      }

back() [1/2]

reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::back ( )

inlineinherited

Last element.

{ return _end[-1]; }

back() [2/2]

const_reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::back ( ) const

inlineinherited

Last element.

{ return _end[-1]; }

begin() [1/2]

const_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::begin ( ) const

inlinenoexceptinherited

Iterator to first item.

{ return const_iterator(_begin); }

begin() [2/2]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::begin ( )

inlinenoexceptinherited

Iterator to first item.

{ return iterator(_begin); }

capacity()

size_type llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::capacity ( ) const

inlinenoexceptinherited

Items can be stored until storage expanded.

{ return _capacity - _begin; }

cbegin()

const_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::cbegin ( ) const

inlinenoexceptinherited

Iterator to first item.

{ return const_iterator(_begin); }

cend()

const_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::cend ( ) const

inlinenoexceptinherited

Iterator to after last item.

{ return const_iterator(_end); }

clear()

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::clear ( )

inlinenoexceptinherited

Clears container.

      {
        // Trivially copyable means trivial destructor
        _end = _begin;
      }

crbegin()

const_reverse_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::crbegin ( ) const

inlinenoexceptinherited

Iterator to last item.

{ return const_reverse_iterator(end()); }

crend()

const_reverse_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::crend ( ) const

inlinenoexceptinherited

Iterator to before first item.

{ return const_reverse_iterator(begin()); }

data() [1/2]

const_pointer llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::data ( ) const

inlinenoexceptinherited

Underlying array.

{ return _begin; }

data() [2/2]

pointer llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::data ( )

inlinenoexceptinherited

Underlying array.

{ return _begin; }

emplace()

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::emplace ( const_iterator  pos, Args &&...  args  )

inlineinherited

Emplace item.

      {
        if(capacity() == size())
        {
          reserve(_scale_capacity(capacity()));
        }
        // Trivially copyable, so memmove
        memmove(pos._v + 1, pos._v, (_end - pos._v) * sizeof(value_type));
        // BUT complex constructors may throw!
        LLFIO_EXCEPTION_TRY
        {
          new(pos._v) value_type(std::forward<Args>(args)...);
        }
        LLFIO_EXCEPTION_CATCH_ALL
        {
          memmove(pos._v, pos._v + 1, (_end - pos._v) * sizeof(value_type));
          LLFIO_EXCEPTION_RETHROW;
        }
        ++_end;
        return iterator(pos._v);
      }

emplace_back()

reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::emplace_back ( Args &&...  args )

inlineinherited

Appends item.

      {
        if(_end == _capacity)
        {
          reserve(_scale_capacity(capacity()));
        }
        new(_end) value_type(std::forward<Args>(args)...);
        ++_end;
        return *(_end - 1);
      }

empty()

bool llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::empty ( ) const

inlinenoexceptinherited

If empty.

{ return _end == _begin; }

end() [1/2]

const_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::end ( ) const

inlinenoexceptinherited

Iterator to after last item.

{ return const_iterator(_end); }

end() [2/2]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::end ( )

inlinenoexceptinherited

Iterator to after last item.

{ return iterator(_end); }

erase() [1/2]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::erase ( const_iterator  first, const_iterator  last  )

inlineinherited

Erases items.

      {
        // Trivially copyable
        memmove(first._v, last._v, (_end - last._v) * sizeof(value_type));
        _end -= last._v - first._v;
        return iterator(first._v);
      }

erase() [2/2]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::erase ( const_iterator  pos )

inlineinherited

Erases item.

      {
        // Trivially copyable
        memmove(pos._v, pos._v + 1, ((_end - 1) - pos._v) * sizeof(value_type));
        --_end;
        return iterator(pos._v);
      }

front() [1/2]

reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::front ( )

inlineinherited

First element.

{ return _begin[0]; }

front() [2/2]

const_reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::front ( ) const

inlineinherited

First element.

{ return _begin[0]; }

insert() [1/5]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::insert ( const_iterator  pos, const value_type &  v  )

inlineinherited

Inserts item.

{ return emplace(pos, v); }

insert() [2/5]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::insert ( const_iterator  pos, InputIt  first, InputIt  last  )

inlineinherited

Inserts items.

      {
        size_type count = std::distance(first, last);
        {
          size_type cap = capacity();
          while(size() + count < cap)
          {
            cap = _scale_capacity(cap);
          }
          reserve(cap);
        }
        // Trivially copyable, so memmove and we know copy construction can't fail
        memmove(pos._v + count, pos._v, (_end - pos._v) * sizeof(value_type));
        for(size_type n = 0; n < count; n++)
        {
          new(pos._v + n) value_type(*first++);
        }
        _end += count;
        return iterator(pos._v);
      }

insert() [3/5]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::insert ( const_iterator  pos, size_type  count, const value_type &  v  )

inlineinherited

Inserts items.

      {
        {
          size_type cap = capacity();
          while(size() + count < cap)
          {
            cap = _scale_capacity(cap);
          }
          reserve(cap);
        }
        // Trivially copyable, so memmove and we know copy construction can't fail
        memmove(pos._v + count, pos._v, (_end - pos._v) * sizeof(value_type));
        for(size_type n = 0; n < count; n++)
        {
          new(pos._v + n) value_type(v);
        }
        _end += count;
        return iterator(pos._v);
      }

insert() [4/5]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::insert ( const_iterator  pos, std::initializer_list< value_type >  il  )

inlineinherited

Inserts items.

{ return insert(pos, il.begin(), il.end()); }

insert() [5/5]

iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::insert ( const_iterator  pos, value_type &&  v  )

inlineinherited

Inserts item.

{ return emplace(pos, std::move(v)); }

max_size()

size_type llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::max_size ( ) const

inlinenoexceptinherited

Maximum items in container.

{ return static_cast<map_handle::size_type>(-1) / sizeof(T); }

operator[]() [1/2]

reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::operator[] ( size_type  i )

inlineinherited

Item index, unchecked.

{ return _begin[i]; }

operator[]() [2/2]

const_reference llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::operator[] ( size_type  i ) const

inlineinherited

Item index, unchecked.

{ return _begin[i]; }

pop_back()

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::pop_back ( )

inlineinherited

Removes last element.

      {
        if(!empty())
        {
          --_end;
        }
      }

push_back() [1/2]

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::push_back ( const value_type &  v )

inlineinherited

Appends item.

      {
        if(_end == _capacity)
        {
          reserve(_scale_capacity(capacity()));
        }
        new(_end++) value_type(v);
      }

push_back() [2/2]

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::push_back ( value_type &&  v )

inlineinherited

Appends item.

{ push_back(v); }

rbegin() [1/2]

const_reverse_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::rbegin ( ) const

inlinenoexceptinherited

Iterator to last item.

{ return const_reverse_iterator(end()); }

rbegin() [2/2]

reverse_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::rbegin ( )

inlinenoexceptinherited

Iterator to last item.

{ return reverse_iterator(end()); }

rend() [1/2]

const_reverse_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::rend ( ) const

inlinenoexceptinherited

Iterator to before first item.

{ return const_reverse_iterator(begin()); }

rend() [2/2]

reverse_iterator llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::rend ( )

inlinenoexceptinherited

Iterator to before first item.

{ return reverse_iterator(begin()); }

reserve()

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::reserve ( size_type  n )

inlineinherited

Increase capacity.

      {
        if(n > max_size())
        {
          LLFIO_EXCEPTION_THROW(std::length_error("Max size exceeded"));  // NOLINT
        }
        size_type current_size = size();
        size_type bytes = n * sizeof(value_type);
        bytes = utils::round_up_to_page_size(bytes, utils::page_size());
        if(!_sh.is_valid())
        {
          _sh = section_handle::section(bytes).value();
          _mh = map_handle::map(_sh, bytes).value();
        }
        else if(n > capacity())
        {
          // We can always grow a section even with maps open on it
          _sh.truncate(bytes).value();
          // Attempt to resize the map in place
          if(!_mh.truncate(bytes, true))
          {
            // std::cerr << "truncate fail" << std::endl;
            // If can't resize, close the map and reopen it into a new address
            _mh.close().value();
            _mh = map_handle::map(_sh, bytes).value();
          }
        }
        else
        {
          return;
        }
        _begin = reinterpret_cast<pointer>(_mh.address());
        _capacity = reinterpret_cast<pointer>(_mh.address() + bytes);
        _end = _begin + current_size;
      }

resize() [1/2]

template<class T >

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< true, T >::resize ( size_type  count )

inlineinherited

Resizes container, filling any new items with default constructed value_type

{ return resize(count, value_type{}); }

resize() [2/2]

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::resize ( size_type  count, const value_type &  v  )

inlineinherited

Resizes container.

      {
        if(count < size())
        {
          // Trivially copyable means trivial destructor
          _end = _begin + count;
          return;
        }
        if(count > capacity())
        {
          reserve(count);
        }
        // TODO(ned): Kinda assuming the compiler will do the right thing below, should really check that
        while(count - size() >= 16)
        {
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
          new(_end++) value_type(v);
        }
        while(count > size())
        {
          new(_end++) value_type(v);
        }
      }

shrink_to_fit()

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::shrink_to_fit ( )

inlineinherited

Removes unused capacity.

      {
        size_type current_size = size();
        size_type bytes = current_size * sizeof(value_type);
        bytes = utils::round_up_to_page_size(bytes, _mh.page_size());
        if(bytes / sizeof(value_type) == capacity())
        {
          return;
        }
        if(bytes == 0)
        {
          _mh.close().value();
          _sh.close().value();
          _begin = _end = _capacity = nullptr;
          return;
        }
        _mh.close().value();
        _sh.truncate(bytes).value();
        _mh = map_handle::map(_sh, bytes).value();
        _begin = reinterpret_cast<pointer>(_mh.address());
        _capacity = reinterpret_cast<pointer>(_mh.address() + bytes);
        _end = _begin + current_size;
      }

size()

size_type llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::size ( ) const

inlinenoexceptinherited

Items in container.

{ return _end - _begin; }

swap()

void llfio_v2_xxx::algorithm::impl::trivial_vector_impl< has_default_construction, T >::swap ( trivial_vector_impl< false, T > &  o )

inlinenoexceptinherited

Swaps.

      {
        using namespace std;
        swap(_sh, o._sh);
        swap(_mh, o._mh);
        swap(_begin, o._begin);
        swap(_end, o._end);
        swap(_capacity, o._capacity);
      }

---

The documentation for this class was generated from the following file:

• include/llfio/v2.0/algorithm/trivial_vector.hpp