2 * Copyright 2013 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // Andrei Alexandrescu (aalexandre)
20 * Vector type. Drop-in replacement for std::vector featuring
21 * significantly faster primitives, see e.g. benchmark results at
22 * https:*phabricator.fb.com/D235852.
24 * In order for a type to be used with fbvector, it must be
25 * relocatable, see Traits.h.
27 * For user-defined types you must specialize templates
28 * appropriately. Consult Traits.h for ways to do so and for a handy
29 * family of macros FOLLY_ASSUME_FBVECTOR_COMPATIBLE*.
31 * For more information and documentation see folly/docs/FBVector.md
34 #ifndef FOLLY_FBVECTOR_H_
35 #define FOLLY_FBVECTOR_H_
37 #include "folly/Foreach.h"
38 #include "folly/Malloc.h"
39 #include "folly/Traits.h"
45 #include <boost/type_traits.hpp>
46 #include <boost/operators.hpp>
47 #include <boost/utility/enable_if.hpp>
48 #include <type_traits>
52 * Forward declaration for use by FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2,
55 template <typename T, class Allocator = std::allocator<T> >
59 // You can define an fbvector of fbvectors.
60 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_2(folly::fbvector);
63 namespace fbvector_detail {
66 * isForwardIterator<T>::value yields true if T is a forward iterator
67 * or better, and false otherwise.
69 template <class It> struct isForwardIterator {
70 enum { value = boost::is_convertible<
71 typename std::iterator_traits<It>::iterator_category,
72 std::forward_iterator_tag>::value
77 * Destroys all elements in the range [b, e). If the type referred to
78 * by the iterators has a trivial destructor, does nothing.
81 void destroyRange(It b, It e) {
82 typedef typename boost::remove_reference<decltype(*b)>::type T;
83 if (boost::has_trivial_destructor<T>::value) return;
90 * Moves the "interesting" part of value to the uninitialized memory
91 * at address addr, and leaves value in a destroyable state.
95 typename boost::enable_if_c<
96 boost::has_trivial_assign<T>::value
98 uninitialized_destructive_move(T& value, T* addr) {
99 // Just assign the thing; this is most efficient
104 typename boost::enable_if_c<
105 !boost::has_trivial_assign<T>::value &&
106 boost::has_nothrow_constructor<T>::value
108 uninitialized_destructive_move(T& value, T* addr) {
109 // Cheap default constructor - move and reinitialize
110 memcpy(addr, &value, sizeof(T));
115 typename std::enable_if<
116 !boost::has_trivial_assign<T>::value &&
117 !boost::has_nothrow_constructor<T>::value
119 uninitialized_destructive_move(T& value, T* addr) {
120 // User defined move construction.
122 // TODO: we should probably prefer this over the above memcpy()
123 // version when the type has a user-defined move constructor. We
124 // don't right now because 4.6 doesn't implement
125 // std::is_move_constructible<> yet.
126 new (addr) T(std::move(value));
130 * Fills n objects of type T starting at address b with T's default
131 * value. If the operation throws, destroys all objects constructed so
132 * far and calls free(b).
135 void uninitializedFillDefaultOrFree(T * b, size_t n) {
136 if (boost::is_arithmetic<T>::value || boost::is_pointer<T>::value) {
137 if (n <= 16384 / sizeof(T)) {
138 memset(b, 0, n * sizeof(T));
142 } else if (boost::has_nothrow_constructor<T>::value) {
145 auto const e1 = b + (n & ~size_t(7));
146 for (; i != e1; i += 8) {
156 for (auto const e = b + n; i != e; ++i) {
160 // Conservative approach
163 for (auto const e = b + n; i != e; ++i) {
175 * Fills n objects of type T starting at address b with value. If the
176 * operation throws, destroys all objects constructed so far and calls
180 void uninitializedFillOrFree(T * b, size_t n, const T& value) {
181 auto const e = b + n;
182 if (boost::has_trivial_copy<T>::value) {
184 auto const e1 = b + (n & ~size_t(7));
185 for (; i != e1; i += 8) {
195 for (; i != e; ++i) {
199 // Conservative approach
202 for (; i != e; ++i) {
212 } // namespace fbvector_detail
215 * This is the std::vector replacement. For conformity, fbvector takes
216 * the same template parameters, but it doesn't use the
217 * allocator. Instead, it uses malloc, and when present, jemalloc's
220 template <class T, class Allocator>
221 class fbvector : private boost::totally_ordered<fbvector<T,Allocator> > {
222 bool isSane() const {
225 empty() == (size() == 0) &&
226 empty() == (begin() == end()) &&
227 size() <= max_size() &&
228 capacity() <= max_size() &&
229 size() <= capacity() &&
231 // Either we have no capacity or our pointers should make sense:
232 ((!b_ && !e_ && !z_) || (b_ != z_ && e_ <= z_));
237 explicit Invariant(const fbvector& s) : s_(s) {
246 explicit Invariant(const fbvector&) {}
248 Invariant& operator=(const Invariant&);
254 typedef T value_type;
255 typedef value_type& reference;
256 typedef const value_type& const_reference;
258 typedef const T* const_iterator;
259 typedef size_t size_type;
260 typedef ssize_t difference_type;
261 // typedef typename allocator_traits<Allocator>::pointer pointer;
262 // typedef typename allocator_traits<Allocator>::const_pointer const_pointer;
263 typedef Allocator allocator_type;
264 typedef typename Allocator::pointer pointer;
265 typedef typename Allocator::const_pointer const_pointer;
266 typedef std::reverse_iterator<iterator> reverse_iterator;
267 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
269 // 23.3.6.1 construct/copy/destroy:
270 fbvector() : b_(NULL), e_(NULL), z_(NULL) {}
272 explicit fbvector(const Allocator&) {
276 explicit fbvector(const size_type n) {
282 auto const nBytes = goodMallocSize(n * sizeof(T));
283 b_ = static_cast<T*>(checkedMalloc(nBytes));
284 fbvector_detail::uninitializedFillDefaultOrFree(b_, n);
286 z_ = b_ + nBytes / sizeof(T);
289 fbvector(const size_type n, const T& value) {
295 auto const nBytes = goodMallocSize(n * sizeof(T));
296 b_ = static_cast<T*>(checkedMalloc(nBytes));
297 fbvector_detail::uninitializedFillOrFree(b_, n, value);
299 z_ = b_ + nBytes / sizeof(T);
302 fbvector(const size_type n, const T& value, const Allocator&) {
303 new(this) fbvector(n, value);
306 template <class InputIteratorOrNum>
307 fbvector(InputIteratorOrNum first, InputIteratorOrNum last) {
312 template <class InputIterator>
313 fbvector(InputIterator first, InputIterator last,
315 new(this) fbvector(first, last);
318 fbvector(const fbvector& rhs) {
319 new(this) fbvector(rhs.begin(), rhs.end());
321 fbvector(const fbvector& rhs, const Allocator&) {
322 new(this) fbvector(rhs);
325 fbvector(fbvector&& o, const Allocator& = Allocator())
330 o.b_ = o.e_ = o.z_ = 0;
333 fbvector(std::initializer_list<T> il, const Allocator& = Allocator()) {
334 new(this) fbvector(il.begin(), il.end());
338 // fbvector only works with relocatable objects. We insert this
339 // static check inside the destructor because pretty much any
340 // instantiation of fbvector<T> will generate the destructor (and
341 // therefore refuse compilation if the assertion fails). To see
342 // how you can enable IsRelocatable for your type, refer to the
343 // definition of IsRelocatable in Traits.h.
344 BOOST_STATIC_ASSERT(IsRelocatable<T>::value);
346 fbvector_detail::destroyRange(b_, e_);
349 fbvector& operator=(const fbvector& rhs) {
350 assign(rhs.begin(), rhs.end());
354 fbvector& operator=(fbvector&& v) {
360 fbvector& operator=(std::initializer_list<T> il) {
361 assign(il.begin(), il.end());
365 bool operator==(const fbvector& rhs) const {
366 return size() == rhs.size() && std::equal(begin(), end(), rhs.begin());
369 bool operator<(const fbvector& rhs) const {
370 return std::lexicographical_compare(begin(), end(),
371 rhs.begin(), rhs.end());
375 template <class InputIterator>
376 void assignImpl(InputIterator first, InputIterator last, boost::false_type) {
378 if (fbvector_detail::isForwardIterator<InputIterator>::value) {
379 auto const oldSize = size();
380 auto const newSize = std::distance(first, last);
382 if (static_cast<difference_type>(oldSize) >= newSize) {
383 // No reallocation, nice
384 auto const newEnd = std::copy(first, last, b_);
385 fbvector_detail::destroyRange(newEnd, e_);
390 // Must reallocate - just do it on the side
391 auto const nBytes = goodMallocSize(newSize * sizeof(T));
392 auto const b = static_cast<T*>(checkedMalloc(nBytes));
393 std::uninitialized_copy(first, last, b);
394 this->fbvector::~fbvector();
397 z_ = b_ + nBytes / sizeof(T);
399 // Input iterator sucks
400 FOR_EACH (i, *this) {
402 fbvector_detail::destroyRange(i, e_);
409 FOR_EACH_RANGE (i, first, last) {
415 void assignImpl(const size_type newSize, const T value, boost::true_type) {
416 // Arithmetic type, forward back to unambiguous definition
417 assign(newSize, value);
421 // Classic ambiguity (and a lot of unnecessary complexity) in
422 // std::vector: assign(10, 20) for vector<int> means "assign 10
423 // elements all having the value 20" but is intercepted by the
424 // two-iterators overload assign(first, last). So we need to
425 // disambiguate here. There is no pretty solution. We use here
426 // overloading based on is_arithmetic. Method insert has the same
427 // issue (and the same solution in this implementation).
428 template <class InputIteratorOrNum>
429 void assign(InputIteratorOrNum first, InputIteratorOrNum last) {
430 assignImpl(first, last, boost::is_arithmetic<InputIteratorOrNum>());
433 void assign(const size_type newSize, const T& value) {
434 if (b_ <= &value && &value < e_) {
435 // Need to check for aliased assign, sigh
436 return assign(newSize, T(value));
439 auto const oldSize = size();
440 if (oldSize >= newSize) {
441 // No reallocation, nice
442 auto const newEnd = b_ + newSize;
443 fbvector_detail::destroyRange(newEnd, e_);
448 // Need to reallocate
449 if (reserve_in_place(newSize)) {
450 // Careful here, fill and uninitialized_fill may throw. The
451 // latter is transactional, so no need to worry about a
452 // buffer partially filled in case of exception.
453 std::fill(b_, e_, value);
454 auto const newEnd = b_ + newSize;
455 std::uninitialized_fill(e_, newEnd, value);
460 // Cannot expand or jemalloc not present at all; must just
461 // allocate a new chunk and discard the old one. This is
462 // tantamount with creating a new fbvector altogether. This won't
463 // recurse infinitely; the constructor implements its own.
464 fbvector temp(newSize, value);
468 void assign(std::initializer_list<T> il) {
469 assign(il.begin(), il.end());
472 allocator_type get_allocator() const {
474 return allocator_type();
481 const_iterator begin() const {
487 const_iterator end() const {
490 reverse_iterator rbegin() {
491 return reverse_iterator(end());
493 const_reverse_iterator rbegin() const {
494 return const_reverse_iterator(end());
496 reverse_iterator rend() {
497 return reverse_iterator(begin());
499 const_reverse_iterator rend() const {
500 return const_reverse_iterator(begin());
502 const_iterator cbegin() const {
505 const_iterator cend() const {
509 // 23.3.6.2 capacity:
510 size_type size() const {
514 size_type max_size() {
515 // good luck gettin' there
516 return ~size_type(0);
519 void resize(const size_type sz) {
520 auto const oldSize = size();
522 auto const newEnd = b_ + sz;
523 fbvector_detail::destroyRange(newEnd, e_);
528 auto newEnd = b_ + sz;
529 std::uninitialized_fill(e_, newEnd, T());
534 void resize(const size_type sz, const T& c) {
535 auto const oldSize = size();
537 auto const newEnd = b_ + sz;
538 fbvector_detail::destroyRange(newEnd, e_);
543 auto newEnd = b_ + sz;
544 std::uninitialized_fill(e_, newEnd, c);
549 size_type capacity() const {
557 bool reserve_in_place(const size_type n) {
558 auto const crtCapacity = capacity();
559 if (n <= crtCapacity) return true;
560 if (!rallocm) return false;
562 // using jemalloc's API. Don't forget that jemalloc can never grow
563 // in place blocks smaller than 4096 bytes.
564 auto const crtCapacityBytes = crtCapacity * sizeof(T);
565 if (crtCapacityBytes < jemallocMinInPlaceExpandable) return false;
567 auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
569 if (rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
574 // Managed to expand in place, reflect that in z_
576 z_ = b_ + newCapacityBytes / sizeof(T);
580 void reserve_with_move(const size_type n) {
581 // Here we can be sure we'll need to do a full reallocation
582 auto const crtCapacity = capacity();
583 assert(crtCapacity < n); // reserve_in_place should have taken
585 auto const newCapacityBytes = goodMallocSize(n * sizeof(T));
586 auto b = static_cast<T*>(checkedMalloc(newCapacityBytes));
587 auto const oldSize = size();
588 memcpy(b, b_, oldSize * sizeof(T));
589 // Done with the old chunk. Free but don't call destructors!
593 z_ = b_ + newCapacityBytes / sizeof(T);
594 // done with the old chunk
598 void reserve(const size_type n) {
599 if (reserve_in_place(n)) return;
600 reserve_with_move(n);
603 void shrink_to_fit() {
604 if (!rallocm) return;
606 // using jemalloc's API. Don't forget that jemalloc can never
607 // shrink in place blocks smaller than 4096 bytes.
609 auto const crtCapacityBytes = capacity() * sizeof(T);
610 auto const newCapacityBytes = goodMallocSize(size() * sizeof(T));
611 if (crtCapacityBytes >= jemallocMinInPlaceExpandable &&
612 rallocm(&p, NULL, newCapacityBytes, 0, ALLOCM_NO_MOVE)
615 z_ = b_ + newCapacityBytes / sizeof(T);
620 reference operator[](size_type n) {
624 const_reference operator[](size_type n) const {
628 const_reference at(size_type n) const {
630 throw std::out_of_range("fbvector: index is greater than size.");
634 reference at(size_type n) {
635 auto const& cThis = *this;
636 return const_cast<reference>(cThis.at(n));
642 const_reference front() const {
650 const_reference back() const {
655 // 23.3.6.3 data access
659 const T* data() const {
664 size_t computePushBackCapacity() const {
665 return empty() ? std::max(64 / sizeof(T), size_t(1))
666 : capacity() < jemallocMinInPlaceExpandable ? capacity() * 2
667 : (capacity() * 3) / 2;
671 // 23.3.6.4 modifiers:
672 template <class... Args>
673 void emplace_back(Args&&... args) {
675 if (!reserve_in_place(size() + 1)) {
676 reserve_with_move(computePushBackCapacity());
679 new (e_) T(std::forward<Args>(args)...);
683 void push_back(T x) {
685 if (!reserve_in_place(size() + 1)) {
686 reserve_with_move(computePushBackCapacity());
689 fbvector_detail::uninitialized_destructive_move(x, e_);
695 if (!rallocm) return false;
696 auto const capBytes = capacity() * sizeof(T);
697 if (capBytes < jemallocMinInPlaceExpandable) return false;
698 auto const newCapBytes = goodMallocSize(capBytes + sizeof(T));
700 if (rallocm(&bv, NULL, newCapBytes, 0, ALLOCM_NO_MOVE) != ALLOCM_SUCCESS) {
703 // Managed to expand in place
704 assert(bv == b_); // nothing moved
705 z_ = b_ + newCapBytes / sizeof(T);
706 assert(capacity() > capBytes / sizeof(T));
714 if (!boost::has_trivial_destructor<T>::value) {
718 // template <class... Args>
719 // iterator emplace(const_iterator position, Args&&... args);
721 iterator insert(const_iterator position, T x) {
722 size_t newSize; // intentionally uninitialized
723 if (e_ == z_ && !reserve_in_place(newSize = size() + 1)) {
724 // Can't reserve in place, make a copy
725 auto const offset = position - cbegin();
727 tmp.reserve(newSize);
728 memcpy(tmp.b_, b_, offset * sizeof(T));
729 fbvector_detail::uninitialized_destructive_move(
732 memcpy(tmp.b_ + offset + 1, b_ + offset, (size() - offset) * sizeof(T));
733 // Brutally reassign this to refer to tmp's guts
738 // get rid of tmp's guts
740 return begin() + offset;
742 // Here we have enough room
743 memmove(const_cast<T*>(&*position) + 1,
744 const_cast<T*>(&*position),
745 sizeof(T) * (e_ - position));
746 fbvector_detail::uninitialized_destructive_move(
748 const_cast<T*>(&*position));
750 return const_cast<iterator>(position);
753 iterator insert(const_iterator position, const size_type n, const T& x) {
755 if (b_ <= &x && &x < e_) {
756 // Ew, aliased insert
758 return insert(position, n, copy);
760 auto const m = position - b_;
764 memmove(const_cast<T*>(position) + n,
766 sizeof(T) * (e_ - position));
767 if (boost::has_trivial_copy<T>::value) {
768 std::uninitialized_fill(const_cast<T*>(position),
769 const_cast<T*>(position) + n,
773 std::uninitialized_fill(const_cast<T*>(position),
774 const_cast<T*>(position) + n,
777 // Oops, put things back where they were
778 memmove(const_cast<T*>(position),
780 sizeof(T) * (e_ - position));
785 return const_cast<iterator>(position);
789 template <class InputIterator>
790 iterator insertImpl(const_iterator position,
791 InputIterator first, InputIterator last,
794 if (fbvector_detail::isForwardIterator<InputIterator>::value) {
795 // Can compute distance
796 auto const n = std::distance(first, last);
798 auto const m = position - b_;
802 memmove(const_cast<T*>(position) + n,
804 sizeof(T) * (e_ - position));
806 std::uninitialized_copy(first, last,
807 const_cast<T*>(position));
809 // Oops, put things back where they were
810 memmove(const_cast<T*>(position),
812 sizeof(T) * (e_ - position));
816 return const_cast<iterator>(position);
818 // Cannot compute distance, crappy approach
820 fbvector result(cbegin(), position);
821 auto const offset = result.size();
822 FOR_EACH_RANGE (i, first, last) {
823 result.push_back(*i);
825 result.insert(result.end(), position, cend());
827 return begin() + offset;
831 iterator insertImpl(const_iterator position,
832 const size_type count, const T value, boost::true_type) {
833 // Forward back to unambiguous function
834 return insert(position, count, value);
838 template <class InputIteratorOrNum>
839 iterator insert(const_iterator position, InputIteratorOrNum first,
840 InputIteratorOrNum last) {
841 return insertImpl(position, first, last,
842 boost::is_arithmetic<InputIteratorOrNum>());
845 iterator insert(const_iterator position, std::initializer_list<T> il) {
846 return insert(position, il.begin(), il.end());
849 iterator erase(const_iterator position) {
850 if (position == e_) return e_;
851 auto p = const_cast<T*>(position);
853 memmove(p, p + 1, sizeof(T) * (e_ - p - 1));
858 iterator erase(const_iterator first, const_iterator last) {
859 assert(first <= last);
860 auto p1 = const_cast<T*>(first);
861 auto p2 = const_cast<T*>(last);
862 fbvector_detail::destroyRange(p1, p2);
863 memmove(p1, last, sizeof(T) * (e_ - last));
868 void swap(fbvector& rhs) {
869 std::swap(b_, rhs.b_);
870 std::swap(e_, rhs.e_);
871 std::swap(z_, rhs.z_);
875 fbvector_detail::destroyRange(b_, e_);
884 template <class T, class A>
885 bool operator!=(const fbvector<T, A>& lhs,
886 const fbvector<T, A>& rhs) {
887 return !(lhs == rhs);
890 template <class T, class A>
891 void swap(fbvector<T, A>& lhs, fbvector<T, A>& rhs) {
896 * Resizes *v to exactly n elements. May reallocate the vector to a
897 * smaller buffer if too much space will be left unused.
900 static void compactResize(folly::fbvector<T> * v, size_t size) {
901 auto const oldCap = v->capacity();
902 if (oldCap > size + 1024 && size < oldCap * 0.3) {
903 // Too much slack memory, reallocate a smaller buffer
904 auto const oldSize = v->size();
905 if (size <= oldSize) {
907 folly::fbvector<T>(v->begin(), v->begin() + size).swap(*v);
910 folly::fbvector<T> temp;
912 copy(v->begin(), v->end(), back_inserter(temp));
924 #endif // FOLLY_FBVECTOR_H_