Merge #12549: Make prevector::resize() and other prevector operations much faster

5aad635 Use memset() to optimize prevector::resize() (Evan Klitzke)
e46be25 Reduce redundant code of prevector and speed it up (Akio Nakamura)
f0e7aa7 Add new prevector benchmarks. (Evan Klitzke)

Pull request description:

  This branch optimizes various `prevector` operations, especially resizing vectors. While profiling the `loadblk` thread I noticed that a lot of time was being spent in `prevector::resize()` which led to this work. I have some data here indicating that it takes up **37%** of the time in `ReadBlockFromDisk()`: https://monad.io/readblockfromdisk.svg

  This branch improves things significantly. For trivial types, the new results for the prevector benchmark are:

   * `PrevectorClearTrivial` which tests `prevector::clear()` becomes 24.6x faster
   * `PrevectorDestructorTrivial` which tests `prevector::~prevector()` becomes 20.5x faster
   * `PrevectorResizeTrivial` which tests `prevector::resize()` becomes 20.3x faster

  Note that in practice it looks like the prevector is only used to contain `unsigned char` types, which is a trivial type. The benchmarks are testing a bit of an extreme case, but the changes here are motivated by the profiling data for `ReadBlockFromDisk()` I linked to above.

  The pull request here consists of a series of three commits:
   * The first adds new benchmarks but does not change the prevector code.
   * The second is from @AkioNak , and merges some prevector optimizations he submitted in #11988
   * The third optimizes `prevector::resize()` to use `memset()` when the prevector contains trivially constructible types

Tree-SHA512: 28f7cbb91a19f9f43b6a5942781d7eb2e3197389186b666f086b69df12bee37773140f765426d715bfb8ebff79cb27a5f1206d0325b54b4aa65598b50fb18368

1 files changed, 77 insertions, 0 deletions

diff --git a/src/bench/prevector.cpp b/src/bench/prevector.cpp
new file mode 100644
index 000000000..d0f28d1a3
--- /dev/null
+++ b/src/bench/prevector.cpp
@@ -0,0 +1,77 @@
+// 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 <compat.h>
+#include <prevector.h>
+
+#include <bench/bench.h>
+
+struct nontrivial_t {
+    int x;
+    nontrivial_t() :x(-1) {}
+};
+static_assert(!IS_TRIVIALLY_CONSTRUCTIBLE<nontrivial_t>::value,
+              "expected nontrivial_t to not be trivially constructible");
+
+typedef unsigned char trivial_t;
+static_assert(IS_TRIVIALLY_CONSTRUCTIBLE<trivial_t>::value,
+              "expected trivial_t to be trivially constructible");
+
+template <typename T>
+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 <typename T>
+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);
+            t0.clear();
+        }
+    }
+}
+
+template <typename T>
+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) { \
+        PrevectorResize<nontrivial_t>(state);                           \
+    }                                                                   \
+    BENCHMARK(Prevector ## name ## Nontrivial, nontrivops);             \
+    static void Prevector ## name ## Trivial(benchmark::State& state) { \
+        PrevectorResize<trivial_t>(state);                              \
+    }                                                                   \
+    BENCHMARK(Prevector ## name ## Trivial, trivops);
+
+PREVECTOR_TEST(Clear, 28300, 88600)
+PREVECTOR_TEST(Destructor, 28800, 88900)
+PREVECTOR_TEST(Resize, 28900, 90300)