LLFIO v2.00
Loading...
Searching...
No Matches
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 >:
llfio_v2_xxx::algorithm::impl::trivial_vector_impl< true, T > llfio_v2_xxx::algorithm::impl::trivial_vector_impl< false, 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.
reference at (size_type i)
 Item index, bounds checked.
reference operator[] (size_type i)
 Item index, unchecked.
reference front ()
 First element.
reference back ()
 Last element.
pointer data () noexcept
 Underlying array.
iterator begin () noexcept
 Iterator to first item.
const_iterator cbegin () const noexcept
 Iterator to first item.
iterator end () 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 crbegin () const noexcept
 Iterator to last item.
reverse_iterator rend () 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 emplace (const_iterator pos, Args &&... args)
 Emplace item.
iterator erase (const_iterator pos)
 Erases item.
void push_back (const 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>
llfio_v2_xxx::algorithm::trivial_vector< T >::trivial_vector ( )
inlineconstexpr
713{} // NOLINT

Member Function Documentation

◆ assign()

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

Assigns.

233 {
234 clear();
235 insert(begin(), count, v);
236 }
void clear() noexcept
Definition trivial_vector.hpp:375
iterator begin() noexcept
Definition trivial_vector.hpp:282
iterator insert(const_iterator pos, const value_type &v)
Definition trivial_vector.hpp:382

◆ at()

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

Item index, bounds checked.

248 {
249 if(i >= size())
250 {
251 LLFIO_EXCEPTION_THROW(std::out_of_range("bounds exceeded")); // NOLINT
252 }
253 return _begin[i];
254 }
size_type size() const noexcept
Definition trivial_vector.hpp:309

◆ back()

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

Last element.

273{ return _end[-1]; }

◆ begin()

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

Iterator to first item.

282{ return iterator(_begin); }
pointer iterator
Iterator type.
Definition trivial_vector.hpp:584

◆ 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.

349{ 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.

286{ return const_iterator(_begin); }
const_pointer const_iterator
Const iterator type.
Definition trivial_vector.hpp:586

◆ cend()

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

Iterator to after last item.

292{ return const_iterator(_end); }

◆ clear()

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

Clears container.

376 {
377 // Trivially copyable means trivial destructor
378 _end = _begin;
379 }

◆ crbegin()

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

Iterator to last item.

298{ return const_reverse_iterator(end()); }
std::reverse_iterator< const_iterator > const_reverse_iterator
Const reverse iterator type.
Definition trivial_vector.hpp:590
iterator end() noexcept
Definition trivial_vector.hpp:288

◆ crend()

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

Iterator to before first item.

304{ return const_reverse_iterator(begin()); }

◆ data()

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

Underlying array.

277{ 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.

443 {
444 // reserve() may remap, which invalidates pos, so remember where it was
445 const auto offset = pos - _begin;
446 if(capacity() == size())
447 {
448 reserve(_scale_capacity(capacity()));
449 }
450 value_type *p = _begin + offset;
451 // Trivially copyable, so memmove
452 memmove(p + 1, p, (_end - p) * sizeof(value_type));
453 // BUT complex constructors may throw!
455 {
457 }
459 {
460 memmove(p, p + 1, (_end - p) * sizeof(value_type));
462 }
463 ++_end;
464 return iterator(p);
465 }
T value_type
Value type.
Definition trivial_vector.hpp:570
size_type capacity() const noexcept
Definition trivial_vector.hpp:349
void reserve(size_type n)
Definition trivial_vector.hpp:313

◆ emplace_back()

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

Appends item.

499 {
500 if(_end == _capacity)
501 {
502 reserve(_scale_capacity(capacity()));
503 }
504 new(_end) value_type(std::forward<Args>(args)...);
505 ++_end;
506 return *(_end - 1);
507 }

◆ empty()

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

If empty.

307{ return _end == _begin; }

◆ end()

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

Iterator to after last item.

288{ return iterator(_end); }

◆ erase()

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

Erases item.

469 {
470 // The iterator types are raw pointers, so there is no _v member to use
471 value_type *p = const_cast<value_type *>(pos);
472 // Trivially copyable
473 memmove(p, p + 1, ((_end - 1) - p) * sizeof(value_type));
474 --_end;
475 return iterator(p);
476 }

◆ front()

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

First element.

269{ return _begin[0]; }

◆ insert()

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

Inserts item.

382{ return emplace(pos, v); }
iterator emplace(const_iterator pos, Args &&... args)
Definition trivial_vector.hpp:442

◆ max_size()

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

Maximum items in container.

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

◆ operator[]()

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

Item index, unchecked.

265{ return _begin[i]; }

◆ pop_back()

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

Removes last element.

510 {
511 if(!empty())
512 {
513 --_end;
514 }
515 }
bool empty() const noexcept
Definition trivial_vector.hpp:307

◆ push_back()

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

Appends item.

488 {
489 if(_end == _capacity)
490 {
491 reserve(_scale_capacity(capacity()));
492 }
493 new(_end++) value_type(v);
494 }

◆ rbegin()

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

Iterator to last item.

294{ return reverse_iterator(end()); }
std::reverse_iterator< iterator > reverse_iterator
Reverse iterator type.
Definition trivial_vector.hpp:588

◆ rend()

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

Iterator to before first item.

300{ 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.

314 {
315 if(n > max_size())
316 {
317 LLFIO_EXCEPTION_THROW(std::length_error("Max size exceeded")); // NOLINT
318 }
320 size_type bytes = n * sizeof(value_type);
322 if(!_sh.is_valid())
323 {
324 _sh = section_handle::section(bytes).value();
325 _mh = map_handle::map(_sh, bytes).value();
326 }
327 else if(n > capacity())
328 {
329 // We can always grow a section even with maps open on it
330 _sh.truncate(bytes).value();
331 // Attempt to resize the map in place
332 if(!_mh.truncate(bytes, true))
333 {
334 // std::cerr << "truncate fail" << std::endl;
335 // If can't resize, close the map and reopen it into a new address
336 _mh.close().value();
337 _mh = map_handle::map(_sh, bytes).value();
338 }
339 }
340 else
341 {
342 return;
343 }
344 _begin = reinterpret_cast<pointer>(_mh.address());
345 _capacity = reinterpret_cast<pointer>(_mh.address() + bytes);
346 _end = _begin + current_size;
347 }
static result< map_handle > map(size_type bytes, bool zeroed=false, section_handle::flag _flag=section_handle::flag::readwrite) noexcept
Definition map_handle.hpp:634
static result< section_handle > section(file_handle &backing, extent_type maximum_size, flag _flag) noexcept
Create a memory section backed by a file.
T round_up_to_page_size(T i, size_t pagesize) noexcept
Round a value to its next highest page size multiple.
Definition utils.hpp:67
value_type * pointer
Pointer type.
Definition trivial_vector.hpp:572
typename std::make_unsigned< difference_type >::type size_type
Size type.
Definition trivial_vector.hpp:578
size_type max_size() const noexcept
Definition trivial_vector.hpp:311

◆ resize() [1/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.

519 {
520 if(count < size())
521 {
522 // Trivially copyable means trivial destructor
523 _end = _begin + count;
524 return;
525 }
526 if(count > capacity())
527 {
528 reserve(count);
529 }
530 // TODO(ned): Kinda assuming the compiler will do the right thing below, should really check that
531 while(count - size() >= 16)
532 {
533 new(_end++) value_type(v);
534 new(_end++) value_type(v);
535 new(_end++) value_type(v);
536 new(_end++) value_type(v);
537 new(_end++) value_type(v);
538 new(_end++) value_type(v);
539 new(_end++) value_type(v);
540 new(_end++) value_type(v);
541 new(_end++) value_type(v);
542 new(_end++) value_type(v);
543 new(_end++) value_type(v);
544 new(_end++) value_type(v);
545 new(_end++) value_type(v);
546 new(_end++) value_type(v);
547 new(_end++) value_type(v);
548 new(_end++) value_type(v);
549 }
550 while(count > size())
551 {
552 new(_end++) value_type(v);
553 }
554 }

◆ resize() [2/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.

602{ return resize(count, value_type{}); }
void resize(size_type count)
Resizes container, filling any new items with default constructed value_type.
Definition trivial_vector.hpp:602

◆ shrink_to_fit()

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

Removes unused capacity.

352 {
355 bytes = utils::round_up_to_page_size(bytes, _mh.page_size());
356 if(bytes / sizeof(value_type) == capacity())
357 {
358 return;
359 }
360 if(bytes == 0)
361 {
362 _mh.close().value();
363 _sh.close().value();
364 _begin = _end = _capacity = nullptr;
365 return;
366 }
367 _mh.close().value();
368 _sh.truncate(bytes).value();
369 _mh = map_handle::map(_sh, bytes).value();
370 _begin = reinterpret_cast<pointer>(_mh.address());
371 _capacity = reinterpret_cast<pointer>(_mh.address() + bytes);
372 _end = _begin + current_size;
373 }

◆ size()

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

Items in container.

309{ return _end - _begin; }

◆ swap()

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

Swaps.

557 {
558 using namespace std;
559 swap(_sh, o._sh);
560 swap(_mh, o._mh);
561 swap(_begin, o._begin);
562 swap(_end, o._end);
563 swap(_capacity, o._capacity);
564 }
void swap(trivial_vector_impl &o) noexcept
Definition trivial_vector.hpp:556

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