diff --git a/src/Makefile.bench.include b/src/Makefile.bench.include --- a/src/Makefile.bench.include +++ b/src/Makefile.bench.include @@ -26,7 +26,7 @@ bench/lockedpool.cpp \ bench/perf.cpp \ bench/perf.h \ - bench/prevector_destructor.cpp + bench/prevector.cpp nodist_bench_bench_bitcoin_SOURCES = $(GENERATED_TEST_FILES) diff --git a/src/bench/prevector.cpp b/src/bench/prevector.cpp new file mode 100644 --- /dev/null +++ b/src/bench/prevector.cpp @@ -0,0 +1,70 @@ +// Copyright (c) 2015-2017 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include +#include + +#include + +struct nontrivial_t { + int x; + nontrivial_t() : x(-1) {} +}; +static_assert(!IS_TRIVIALLY_CONSTRUCTIBLE::value, + "expected nontrivial_t to not be trivially constructible"); + +typedef unsigned char trivial_t; +static_assert(IS_TRIVIALLY_CONSTRUCTIBLE::value, + "expected trivial_t to be trivially constructible"); + +template static void PrevectorDestructor(benchmark::State &state) { + while (state.KeepRunning()) { + for (auto x = 0; x < 1000; ++x) { + prevector<28, T> t0; + prevector<28, T> t1; + t0.resize(28); + t1.resize(29); + } + } +} + +template static void PrevectorClear(benchmark::State &state) { + while (state.KeepRunning()) { + for (auto x = 0; x < 1000; ++x) { + prevector<28, T> t0; + prevector<28, T> t1; + t0.resize(28); + t0.clear(); + t1.resize(29); + t1.clear(); + } + } +} + +template void PrevectorResize(benchmark::State &state) { + while (state.KeepRunning()) { + prevector<28, T> t0; + prevector<28, T> t1; + for (auto x = 0; x < 1000; ++x) { + t0.resize(28); + t0.resize(0); + t1.resize(29); + t1.resize(0); + } + } +} + +#define PREVECTOR_TEST(name, nontrivops, trivops) \ + static void Prevector##name##Nontrivial(benchmark::State &state) { \ + Prevector##name(state); \ + } \ + BENCHMARK(Prevector##name##Nontrivial, nontrivops); \ + static void Prevector##name##Trivial(benchmark::State &state) { \ + Prevector##name(state); \ + } \ + BENCHMARK(Prevector##name##Trivial, trivops); + +PREVECTOR_TEST(Clear, 28300, 88600) +PREVECTOR_TEST(Destructor, 28800, 88900) +PREVECTOR_TEST(Resize, 28900, 90300) diff --git a/src/bench/prevector_destructor.cpp b/src/bench/prevector_destructor.cpp deleted file mode 100644 --- a/src/bench/prevector_destructor.cpp +++ /dev/null @@ -1,33 +0,0 @@ -// Copyright (c) 2015-2017 The Bitcoin Core developers -// Distributed under the MIT software license, see the accompanying -// file COPYING or http://www.opensource.org/licenses/mit-license.php. - -#include "bench.h" -#include "prevector.h" - -static void PrevectorDestructor(benchmark::State &state) { - while (state.KeepRunning()) { - for (auto x = 0; x < 1000; ++x) { - prevector<28, uint8_t> t0; - prevector<28, uint8_t> t1; - t0.resize(28); - t1.resize(29); - } - } -} - -static void PrevectorClear(benchmark::State &state) { - while (state.KeepRunning()) { - for (auto x = 0; x < 1000; ++x) { - prevector<28, uint8_t> t0; - prevector<28, uint8_t> t1; - t0.resize(28); - t0.clear(); - t1.resize(29); - t1.clear(); - } - } -} - -BENCHMARK(PrevectorDestructor, 5700); -BENCHMARK(PrevectorClear, 5600); diff --git a/src/compat.h b/src/compat.h --- a/src/compat.h +++ b/src/compat.h @@ -10,6 +10,16 @@ #include "config/bitcoin-config.h" #endif +#include + +// GCC 4.8 is missing some C++11 type_traits, +// https://www.gnu.org/software/gcc/gcc-5/changes.html +#if defined(__GNUC__) && __GNUC__ < 5 +#define IS_TRIVIALLY_CONSTRUCTIBLE std::is_trivial +#else +#define IS_TRIVIALLY_CONSTRUCTIBLE std::is_trivially_constructible +#endif + #ifdef WIN32 #ifdef _WIN32_WINNT #undef _WIN32_WINNT diff --git a/src/prevector.h b/src/prevector.h --- a/src/prevector.h +++ b/src/prevector.h @@ -10,9 +10,12 @@ #include #include +#include #include #include +#include + #pragma pack(push, 1) /** * Implements a drop-in replacement for std::vector which stores up to N @@ -296,16 +299,42 @@ return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); } + void fill(T *dst, ptrdiff_t count) { + if (IS_TRIVIALLY_CONSTRUCTIBLE::value) { + // The most common use of prevector is where T=unsigned char. For + // trivially constructible types, we can use memset() to avoid + // looping. + ::memset(dst, 0, count * sizeof(T)); + } else { + for (auto i = 0; i < count; ++i) { + new (static_cast(dst + i)) T(); + } + } + } + + void fill(T *dst, ptrdiff_t count, const T &value) { + for (auto i = 0; i < count; ++i) { + new (static_cast(dst + i)) T(value); + } + } + + template + void fill(T *dst, InputIterator first, InputIterator last) { + while (first != last) { + new (static_cast(dst)) T(*first); + ++dst; + ++first; + } + } + public: void assign(size_type n, const T &val) { clear(); if (capacity() < n) { change_capacity(n); } - while (size() < n) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(val); - } + _size += n; + fill(item_ptr(0), n, val); } template @@ -315,11 +344,8 @@ if (capacity() < n) { change_capacity(n); } - while (first != last) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(*first); - ++first; - } + _size += n; + fill(item_ptr(0), first, last); } prevector() : _size(0), _union{{}} {} @@ -328,31 +354,23 @@ explicit prevector(size_type n, const T &val) : prevector() { change_capacity(n); - while (size() < n) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(val); - } + _size += n; + fill(item_ptr(0), n, val); } template prevector(InputIterator first, InputIterator last) : prevector() { size_type n = last - first; change_capacity(n); - while (first != last) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(*first); - ++first; - } + _size += n; + fill(item_ptr(0), first, last); } prevector(const prevector &other) : prevector() { - change_capacity(other.size()); - const_iterator it = other.begin(); - while (it != other.end()) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(*it); - ++it; - } + size_type n = other.size(); + change_capacity(n); + _size += n; + fill(item_ptr(0), other.begin(), other.end()); } prevector(prevector &&other) : prevector() { @@ -363,14 +381,7 @@ if (&other == this) { return *this; } - resize(0); - change_capacity(other.size()); - const_iterator it = other.begin(); - while (it != other.end()) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(*it); - ++it; - } + assign(other.begin(), other.end()); return *this; } @@ -410,16 +421,20 @@ const T &operator[](size_type pos) const { return *item_ptr(pos); } void resize(size_type new_size) { - if (size() > new_size) { + size_type cur_size = size(); + if (cur_size == new_size) { + return; + } + if (cur_size > new_size) { erase(item_ptr(new_size), end()); + return; } if (new_size > capacity()) { change_capacity(new_size); } - while (size() < new_size) { - _size++; - new (static_cast(item_ptr(size() - 1))) T(); - } + ptrdiff_t increase = new_size - cur_size; + fill(item_ptr(cur_size), increase); + _size += increase; } void reserve(size_type new_capacity) { @@ -438,10 +453,11 @@ if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } - memmove(item_ptr(p + 1), item_ptr(p), (size() - p) * sizeof(T)); + T *ptr = item_ptr(p); + memmove(ptr + 1, ptr, (size() - p) * sizeof(T)); _size++; - new (static_cast(item_ptr(p))) T(value); - return iterator(item_ptr(p)); + new (static_cast(ptr)) T(value); + return iterator(ptr); } void insert(iterator pos, size_type count, const T &value) { @@ -450,11 +466,10 @@ if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } - memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T)); + T *ptr = item_ptr(p); + memmove(ptr + count, ptr, (size() - p) * sizeof(T)); _size += count; - for (size_type i = 0; i < count; i++) { - new (static_cast(item_ptr(p + i))) T(value); - } + fill(item_ptr(p), count, value); } template @@ -465,13 +480,10 @@ if (capacity() < new_size) { change_capacity(new_size + (new_size >> 1)); } - memmove(item_ptr(p + count), item_ptr(p), (size() - p) * sizeof(T)); + T *ptr = item_ptr(p); + memmove(ptr + count, ptr, (size() - p) * sizeof(T)); _size += count; - while (first != last) { - new (static_cast(item_ptr(p))) T(*first); - ++p; - ++first; - } + fill(ptr, first, last); } iterator erase(iterator pos) { return erase(pos, pos + 1); }