commit b16b29a9fedbd703c3c4ff1fcc3ed3129daff8fb
author John Stiles <johnstiles@google.com> Mon Oct 05 09:56:42 2020 -0400
committer Skia Commit-Bot <skia-commit-bot@chromium.org> Mon Oct 05 14:40:14 2020 +0000
tree 8d5697d25d8be329944a4930a78b6cb076cae605
parent 750261f41af6fc636d64d4431cee2eae67d49d84

Create TinyUnorderedMap class for small-N data storage.

Our code relies on std::unordered_map for storage of unordered data.
Unfortunately, while unordered_map is algorithmically quite efficient,
in many real-world scenarios--particularly with small amounts of data--
a simple vector with linear search runs rings around it.

This CL doubles the performance of `nanobench -m sksl_large`:
http://screen/7uGYGLCaTtaHU4j

Change-Id: Ia2f6cedfac338876c2da57642e9b34addd85b683
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/322320
Commit-Queue: John Stiles <johnstiles@google.com>
Commit-Queue: Brian Osman <brianosman@google.com>
Auto-Submit: John Stiles <johnstiles@google.com>
Reviewed-by: Brian Osman <brianosman@google.com>

gn/sksl.gni

diff --git a/gn/sksl.gni b/gn/sksl.gni
index c1ba0c2..4f21e7c 100644
--- a/gn/sksl.gni
+++ b/gn/sksl.gni
@@ -45,6 +45,7 @@
   "$_src/sksl/SkSLString.cpp",
   "$_src/sksl/SkSLString.h",
   "$_src/sksl/SkSLStringStream.h",
+  "$_src/sksl/SkSLTinyUnorderedMap.h",
   "$_src/sksl/SkSLUtil.cpp",
   "$_src/sksl/SkSLUtil.h",
   "$_src/sksl/ir/SkSLBinaryExpression.h",

src/sksl/SkSLTinyUnorderedMap.h

diff --git a/src/sksl/SkSLTinyUnorderedMap.h b/src/sksl/SkSLTinyUnorderedMap.h
new file mode 100644
index 0000000..7bfc738
--- /dev/null
+++ b/src/sksl/SkSLTinyUnorderedMap.h
@@ -0,0 +1,66 @@
+/*
+ * Copyright 2020 Google LLC
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SKSL_TINYUNORDEREDMAP
+#define SKSL_TINYUNORDEREDMAP
+
+#include <algorithm>
+#include <iterator>
+#include <utility>
+#include <vector>
+
+namespace SkSL {
+
+/** The TinyUnorderedMap presents a minimal, unordered_map-like interface, but is backed by a normal
+    vector. No attempt is made to be clever during lookups or insertions. This is intended to be
+    used in cases where we have tiny amount of data (e.g. less than 50 elements); CPUs are really
+    good at scanning contiguous cachelines. */
+template <typename K, typename V>
+class TinyUnorderedMap {
+public:
+    using key_type = K;
+    using mapped_type = V;
+    using value_type = std::pair<const K, V>;
+    using iterator = typename std::vector<value_type>::iterator;
+    using const_iterator = typename std::vector<value_type>::const_iterator;
+
+    iterator begin() { return fData.begin(); }
+    const_iterator begin() const { return fData.begin(); }
+
+    iterator end() { return fData.end(); }
+    const_iterator end() const { return fData.end(); }
+
+    void clear() { fData.clear(); }
+    bool empty() { return fData.empty(); }
+    size_t size() { return fData.size(); }
+    void reserve(size_t amount) { fData.reserve(amount); }
+
+    iterator find(const K& key) {
+        return std::find_if(fData.begin(), fData.end(),
+                            [&](const value_type& a) { return a.first == key; });
+    }
+    const_iterator find(const K& key) const {
+        return std::find_if(fData.begin(), fData.end(),
+                            [&](const value_type& a) { return a.first == key; });
+    }
+
+    V& operator[](const K& key) {
+        auto iter = this->find(key);
+        if (iter != fData.end()) {
+            return iter->second;
+        }
+        fData.push_back(value_type{key, V{}});
+        return fData.back().second;
+    }
+
+private:
+    std::vector<value_type> fData;
+};
+
+}  // namespace SkSL
+
+#endif

src/sksl/ir/SkSLExpression.h

diff --git a/src/sksl/ir/SkSLExpression.h b/src/sksl/ir/SkSLExpression.h
index c425180..7921980 100644
--- a/src/sksl/ir/SkSLExpression.h
+++ b/src/sksl/ir/SkSLExpression.h
@@ -8,6 +8,7 @@
 #ifndef SKSL_EXPRESSION
 #define SKSL_EXPRESSION
 
+#include "src/sksl/SkSLTinyUnorderedMap.h"
 #include "src/sksl/ir/SkSLStatement.h"
 #include "src/sksl/ir/SkSLType.h"
 
@@ -19,7 +20,7 @@
 class IRGenerator;
 struct Variable;
 
-typedef std::unordered_map<const Variable*, std::unique_ptr<Expression>*> DefinitionMap;
+using DefinitionMap = TinyUnorderedMap<const Variable*, std::unique_ptr<Expression>*>;
 
 /**
  * Abstract supertype of all expressions.