From 5aad635b78c8359adae9b2af015b67b7325c0e0b Mon Sep 17 00:00:00 2001
From: Evan Klitzke <evan@eklitzke.org>
Date: Mon, 26 Feb 2018 21:39:22 -0800
Subject: Use memset() to optimize prevector::resize()

Further optimize prevector::resize() (which is called by a number of
other prevector methods) to use memset to initialize memory when the
prevector contains trivial types.
---
 src/prevector.h | 31 +++++++++++++++++++++++++------
 1 file changed, 25 insertions(+), 6 deletions(-)

(limited to 'src/prevector.h')

diff --git a/src/prevector.h b/src/prevector.h
index 75d6abfb0e..103ead82cc 100644
--- a/src/prevector.h
+++ b/src/prevector.h
@@ -10,9 +10,12 @@
 #include <stdint.h>
 #include <string.h>
 
+#include <cstddef>
 #include <iterator>
 #include <type_traits>
 
+#include <compat.h>
+
 #pragma pack(push, 1)
 /** Implements a drop-in replacement for std::vector<T> which stores up to N
  *  elements directly (without heap allocation). The types Size and Diff are
@@ -194,8 +197,21 @@ private:
     T* item_ptr(difference_type pos) { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
     const T* item_ptr(difference_type pos) const { return is_direct() ? direct_ptr(pos) : indirect_ptr(pos); }
 
-    void fill(T* dst, size_type count, const T& value) {
-        for (size_type i = 0; i < count; ++i) {
+    void fill(T* dst, ptrdiff_t count) {
+        if (IS_TRIVIALLY_CONSTRUCTIBLE<T>::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<void*>(dst + i)) T();
+            }
+        }
+    }
+
+    void fill(T* dst, ptrdiff_t count, const T& value) {
+        for (auto i = 0; i < count; ++i) {
             new(static_cast<void*>(dst + i)) T(value);
         }
     }
@@ -310,16 +326,19 @@ public:
 
     void resize(size_type 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);
         }
-        for (T* p = item_ptr(0); cur_size < new_size; cur_size++) {
-            _size++;
-            new(static_cast<void*>(p + cur_size)) T();
-        }
+        ptrdiff_t increase = new_size - cur_size;
+        fill(item_ptr(cur_size), increase);
+        _size += increase;
     }
 
     void reserve(size_type new_capacity) {
-- 
cgit v1.2.3