Bug 1477622 - Add microbenchmarks measuring hash table performance. r=froydnj
authorNicholas Nethercote <nnethercote@mozilla.com>
Tue, 24 Jul 2018 10:38:43 +1000
changeset 427921 1ea12424829ba27e9cc2bf2f22d688483f2c929a
parent 427920 6ea17dfcb278cbc22891a77d3e1baa82614c38ab
child 427922 e3f3506f327c421dcffc00266382669bbe2d101a
push id105586
push usernnethercote@mozilla.com
push dateTue, 24 Jul 2018 04:03:50 +0000
treeherdermozilla-inbound@1ea12424829b [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersfroydnj
bugs1477622
milestone63.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1477622 - Add microbenchmarks measuring hash table performance. r=froydnj
Cargo.lock
toolkit/library/gtest/rust/Cargo.toml
toolkit/library/gtest/rust/lib.rs
xpcom/rust/gtest/bench-collections/Bench.cpp
xpcom/rust/gtest/bench-collections/Cargo.toml
xpcom/rust/gtest/bench-collections/bench.rs
xpcom/rust/gtest/moz.build
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -136,16 +136,24 @@ name = "base64"
 version = "0.6.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "byteorder 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "safemem 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
+name = "bench-collections-gtest"
+version = "0.1.0"
+dependencies = [
+ "fnv 1.0.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "fxhash 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "binary-space-partition"
 version = "0.1.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "bincode"
 version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -815,16 +823,17 @@ dependencies = [
  "gkrust-shared 0.1.0",
  "stylo_tests 0.0.1",
 ]
 
 [[package]]
 name = "gkrust-gtest"
 version = "0.1.0"
 dependencies = [
+ "bench-collections-gtest 0.1.0",
  "gkrust-shared 0.1.0",
  "mp4parse-gtest 0.1.0",
  "nsstring-gtest 0.1.0",
  "xpcom-gtest 0.1.0",
 ]
 
 [[package]]
 name = "gkrust-shared"
--- a/toolkit/library/gtest/rust/Cargo.toml
+++ b/toolkit/library/gtest/rust/Cargo.toml
@@ -11,16 +11,17 @@ servo = ["gkrust-shared/servo"]
 quantum_render = ["gkrust-shared/quantum_render"]
 cubeb-remoting = ["gkrust-shared/cubeb-remoting"]
 cubeb_pulse_rust = ["gkrust-shared/cubeb_pulse_rust"]
 gecko_debug = ["gkrust-shared/gecko_debug"]
 simd-accel = ["gkrust-shared/simd-accel"]
 moz_memory = ["gkrust-shared/moz_memory"]
 
 [dependencies]
+bench-collections-gtest = { path = "../../../../xpcom/rust/gtest/bench-collections" }
 mp4parse-gtest = { path = "../../../../dom/media/gtest" }
 nsstring-gtest = { path = "../../../../xpcom/rust/gtest/nsstring" }
 xpcom-gtest = { path = "../../../../xpcom/rust/gtest/xpcom" }
 gkrust-shared = { path = "../../rust/shared" }
 
 [lib]
 path = "lib.rs"
 crate-type = ["staticlib"]
--- a/toolkit/library/gtest/rust/lib.rs
+++ b/toolkit/library/gtest/rust/lib.rs
@@ -1,8 +1,9 @@
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
+extern crate bench_collections_gtest;
 extern crate gkrust_shared;
 extern crate mp4parse_gtest;
 extern crate nsstring_gtest;
 extern crate xpcom_gtest;
new file mode 100644
--- /dev/null
+++ b/xpcom/rust/gtest/bench-collections/Bench.cpp
@@ -0,0 +1,313 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+// Overview
+// --------
+// This file measures the speed of various implementations of C++ and Rust
+// collections (hash tables, etc.) used within the codebase. There are a small
+// number of benchmarks for each collection type; each benchmark tests certain
+// operations (insertion, lookup, iteration, etc.) More benchmarks could easily
+// be envisioned, but this small number is enough to characterize the major
+// differences between implementations, while keeping the file size and
+// complexity low.
+//
+// Details
+// -------
+// The file uses `MOZ_GTEST_BENCH_F` so that results are integrated into
+// PerfHerder. It is also designed so that individual test benchmarks can be
+// run under a profiler.
+//
+// The C++ code uses `MOZ_RELEASE_ASSERT` extensively to check values and
+// ensure operations aren't optimized away by the compiler. The Rust code uses
+// `assert!()`. These should be roughly equivalent, but aren't guaranteed to be
+// the same. As a result, the intra-C++ comparisons should be reliable, and the
+// intra-Rust comparisons should be reliable, but the C++ vs. Rust comparisons
+// may be less reliable.
+//
+// Note that the Rust implementations run very slowly without --enable-release.
+//
+// Profiling
+// ---------
+// If you want to measure a particular implementation under a profiler such as
+// Callgrind, do something like this:
+//
+//   MOZ_RUN_GTEST=1 GTEST_FILTER='*BenchCollections*$IMPL*'
+//       valgrind --tool=callgrind --callgrind-out-file=clgout
+//       $OBJDIR/dist/bin/firefox -unittest
+//   callgrind_annotate --auto=yes clgout > clgann
+//
+// where $IMPL is part of an implementation name in a test (e.g. "PLDHash",
+// "JSHash") and $OBJDIR is an objdir containing a --enable-release build.
+//
+// Note that multiple processes are spawned, so `clgout` gets overwritten
+// multiple times, but the last process to write its profiling data to file is
+// the one of interest. (Alternatively, use --callgrind-out-file=clgout.%p to
+// get separate output files for each process, with a PID suffix.)
+
+#include "gtest/gtest.h"
+#include "gtest/MozGTestBench.h" // For MOZ_GTEST_BENCH
+#include "js/HashTable.h"
+#include "mozilla/AllocPolicy.h"
+#include "mozilla/HashFunctions.h"
+#include "mozilla/StaticMutex.h"
+#include "mozilla/TimeStamp.h"
+#include "PLDHashTable.h"
+#include <unordered_set>
+
+using namespace mozilla;
+
+// This function gives a pseudo-random sequence with the following properties:
+// - Deterministic and platform-independent.
+// - No duplicates in the first VALS_LEN results, which is useful for ensuring
+//   the tables get to a particular size, and also for guaranteeing lookups
+//   that fail.
+uintptr_t
+MyRand()
+{
+  static uintptr_t s = 0;
+  s = s * 1103515245 + 12345;
+  return s;
+}
+
+// Keep this in sync with Params in bench.rs.
+struct Params
+{
+  const char* mConfigName;
+  size_t mNumInserts;           // Insert this many unique keys
+  size_t mNumSuccessfulLookups; // Does mNumInserts lookups each time
+  size_t mNumFailingLookups;    // Does mNumInserts lookups each time
+  size_t mNumIterations;        // Iterates the full table each time
+  bool mRemoveInserts;          // Remove all entries at end?
+};
+
+// We don't use std::unordered_{set,map}, but it's an interesting thing to
+// benchmark against.
+//
+// Keep this in sync with all the other Bench_*() functions.
+void
+Bench_Cpp_unordered_set(const Params* aParams, void** aVals, size_t aLen)
+{
+  std::unordered_set<void*> hs;
+
+  for (size_t j = 0; j < aParams->mNumInserts; j++) {
+    hs.insert(aVals[j]);
+  }
+
+  for (size_t i = 0; i < aParams->mNumSuccessfulLookups; i++) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      MOZ_RELEASE_ASSERT(hs.find(aVals[j]) != hs.end());
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumFailingLookups; i++) {
+    for (size_t j = aParams->mNumInserts; j < aParams->mNumInserts*2; j++) {
+      MOZ_RELEASE_ASSERT(hs.find(aVals[j]) == hs.end());
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumIterations; i++) {
+    size_t n = 0;
+    for (const auto& elem : hs) {
+      (void)elem;
+      n++;
+    }
+    MOZ_RELEASE_ASSERT(aParams->mNumInserts == n);
+    MOZ_RELEASE_ASSERT(hs.size() == n);
+  }
+
+  if (aParams->mRemoveInserts) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      MOZ_RELEASE_ASSERT(hs.erase(aVals[j]) == 1);
+    }
+    MOZ_RELEASE_ASSERT(hs.size() == 0);
+  } else {
+    MOZ_RELEASE_ASSERT(hs.size() == aParams->mNumInserts);
+  }
+}
+
+// Keep this in sync with all the other Bench_*() functions.
+void
+Bench_Cpp_PLDHashTable(const Params* aParams, void** aVals, size_t aLen)
+{
+  PLDHashTable hs(PLDHashTable::StubOps(), sizeof(PLDHashEntryStub));
+
+  for (size_t j = 0; j < aParams->mNumInserts; j++) {
+    auto entry = static_cast<PLDHashEntryStub*>(hs.Add(aVals[j]));
+    MOZ_RELEASE_ASSERT(!entry->key);
+    entry->key = aVals[j];
+  }
+
+  for (size_t i = 0; i < aParams->mNumSuccessfulLookups; i++) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      MOZ_RELEASE_ASSERT(hs.Search(aVals[j]));
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumFailingLookups; i++) {
+    for (size_t j = aParams->mNumInserts; j < aParams->mNumInserts*2; j++) {
+      MOZ_RELEASE_ASSERT(!hs.Search(aVals[j]));
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumIterations; i++) {
+    size_t n = 0;
+    for (auto iter = hs.Iter(); !iter.Done(); iter.Next()) {
+      n++;
+    }
+    MOZ_RELEASE_ASSERT(aParams->mNumInserts == n);
+    MOZ_RELEASE_ASSERT(hs.EntryCount() == n);
+  }
+
+  if (aParams->mRemoveInserts) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      hs.Remove(aVals[j]);
+    }
+    MOZ_RELEASE_ASSERT(hs.EntryCount() == 0);
+  } else {
+    MOZ_RELEASE_ASSERT(hs.EntryCount() == aParams->mNumInserts);
+  }
+}
+
+// Keep this in sync with all the other Bench_*() functions.
+void
+Bench_Cpp_JSHashSet(const Params* aParams, void** aVals, size_t aLen)
+{
+  js::HashSet<void*, js::DefaultHasher<void*>, MallocAllocPolicy> hs;
+  MOZ_RELEASE_ASSERT(hs.init());
+
+  for (size_t j = 0; j < aParams->mNumInserts; j++) {
+    auto p = hs.lookupForAdd(aVals[j]);
+    MOZ_RELEASE_ASSERT(!p);
+    MOZ_RELEASE_ASSERT(hs.add(p, aVals[j]));
+  }
+
+  for (size_t i = 0; i < aParams->mNumSuccessfulLookups; i++) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      MOZ_RELEASE_ASSERT(hs.lookup(aVals[j]));
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumFailingLookups; i++) {
+    for (size_t j = aParams->mNumInserts; j < aParams->mNumInserts*2; j++) {
+      MOZ_RELEASE_ASSERT(!hs.lookup(aVals[j]));
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumIterations; i++) {
+    size_t n = 0;
+    for (auto range = hs.all(); !range.empty(); range.popFront()) {
+      n++;
+    }
+    MOZ_RELEASE_ASSERT(aParams->mNumInserts == n);
+    MOZ_RELEASE_ASSERT(hs.count() == n);
+  }
+
+  if (aParams->mRemoveInserts) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      hs.remove(aVals[j]);
+    }
+    MOZ_RELEASE_ASSERT(hs.count() == 0);
+  } else {
+    MOZ_RELEASE_ASSERT(hs.count() == aParams->mNumInserts);
+  }
+}
+
+extern "C" {
+void Bench_Rust_HashSet(const Params* params, void** aVals, size_t aLen);
+void Bench_Rust_FnvHashSet(const Params* params, void** aVals, size_t aLen);
+void Bench_Rust_FxHashSet(const Params* params, void** aVals, size_t aLen);
+}
+
+static const size_t VALS_LEN = 131072;
+
+// Each benchmark measures a different aspect of performance.
+// Note that no "Inserts" value can exceed VALS_LEN.
+// Also, if any failing lookups are done, Inserts must be <= VALS_LEN/2.
+const Params gParamsList[] = {
+  //                           Successful Failing              Remove
+  //                 Inserts   lookups    lookups  Iterations  inserts
+  { "succ_lookups",  1024,     5000,      0,       0,          false },
+  { "fail_lookups",  1024,     0,         5000,    0,          false },
+  { "insert_remove", VALS_LEN, 0,         0,       0,          true  },
+  { "iterate",       1024,     0,         0,       5000,       false },
+};
+
+class BenchCollections : public ::testing::Test
+{
+protected:
+  void SetUp() override
+  {
+    StaticMutexAutoLock lock(sValsMutex);
+
+    if (!sVals) {
+      sVals = (void**)malloc(VALS_LEN * sizeof(void*));
+      for (size_t i = 0; i < VALS_LEN; i++) {
+        // This leaves the high 32 bits zero on 64-bit platforms, but that
+        // should still be enough randomness to get typical behaviour.
+        sVals[i] = reinterpret_cast<void*>(uintptr_t(MyRand()));
+      }
+    }
+
+    printf("\n");
+    for (size_t i = 0; i < ArrayLength(gParamsList); i++) {
+      const Params* params = &gParamsList[i];
+      printf("%14s", params->mConfigName);
+    }
+    printf("%14s\n", "total");
+  }
+
+public:
+  void BenchImpl(void(*aBench)(const Params*, void**, size_t))
+  {
+    StaticMutexAutoLock lock(sValsMutex);
+
+    double total = 0;
+    for (size_t i = 0; i < ArrayLength(gParamsList); i++) {
+      const Params* params = &gParamsList[i];
+      TimeStamp t1 = TimeStamp::Now();
+      aBench(params, sVals, VALS_LEN);
+      TimeStamp t2 = TimeStamp::Now();
+      double t = (t2 - t1).ToMilliseconds();
+      printf("%11.1f ms", t);
+      total += t;
+    }
+    printf("%11.1f ms\n", total);
+  }
+
+private:
+  // Random values used in the benchmarks.
+  static void** sVals;
+
+  // A mutex that protects all benchmark operations, ensuring that two
+  // benchmarks never run concurrently.
+  static StaticMutex sValsMutex;
+};
+
+void** BenchCollections::sVals;
+StaticMutex BenchCollections::sValsMutex;
+
+MOZ_GTEST_BENCH_F(BenchCollections, unordered_set, [this] {
+  BenchImpl(Bench_Cpp_unordered_set);
+});
+
+MOZ_GTEST_BENCH_F(BenchCollections, PLDHash, [this] {
+  BenchImpl(Bench_Cpp_PLDHashTable);
+});
+
+MOZ_GTEST_BENCH_F(BenchCollections, JSHash, [this] {
+  BenchImpl(Bench_Cpp_JSHashSet);
+});
+
+MOZ_GTEST_BENCH_F(BenchCollections, RustHash, [this] {
+  BenchImpl(Bench_Rust_HashSet);
+});
+
+MOZ_GTEST_BENCH_F(BenchCollections, RustFnvHash, [this] {
+  BenchImpl(Bench_Rust_FnvHashSet);
+});
+
+MOZ_GTEST_BENCH_F(BenchCollections, RustFxHash, [this] {
+  BenchImpl(Bench_Rust_FxHashSet);
+});
+
new file mode 100644
--- /dev/null
+++ b/xpcom/rust/gtest/bench-collections/Cargo.toml
@@ -0,0 +1,12 @@
+[package]
+name = "bench-collections-gtest"
+version = "0.1.0"
+license = "MPL-2.0"
+description = "Benchmarks for various collections"
+
+[dependencies]
+fnv = "1.0"
+fxhash = "0.2.1"
+
+[lib]
+path = "bench.rs"
new file mode 100644
--- /dev/null
+++ b/xpcom/rust/gtest/bench-collections/bench.rs
@@ -0,0 +1,90 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#![allow(non_snake_case)]
+
+extern crate fnv;
+extern crate fxhash;
+
+use fnv::FnvHashSet;
+use fxhash::FxHashSet;
+use std::collections::HashSet;
+use std::os::raw::{c_char, c_void};
+use std::slice;
+
+/// Keep this in sync with Params in Bench.cpp.
+#[derive(Debug)]
+#[repr(C)]
+pub struct Params
+{
+  config_name: *const c_char,
+  num_inserts: usize,
+  num_successful_lookups: usize,
+  num_failing_lookups: usize,
+  num_iterations: usize,
+  remove_inserts: bool,
+}
+
+#[no_mangle]
+pub extern "C" fn Bench_Rust_HashSet(params: *const Params, vals: *const *const c_void,
+                                     len: usize) {
+    let hs: HashSet<_> = std::collections::HashSet::default();
+    Bench_Rust(hs, params, vals, len);
+}
+
+#[no_mangle]
+pub extern "C" fn Bench_Rust_FnvHashSet(params: *const Params, vals: *const *const c_void,
+                                        len: usize) {
+    let hs = FnvHashSet::default();
+    Bench_Rust(hs, params, vals, len);
+}
+
+#[no_mangle]
+pub extern "C" fn Bench_Rust_FxHashSet(params: *const Params, vals: *const *const c_void,
+                                       len: usize) {
+    let hs = FxHashSet::default();
+    Bench_Rust(hs, params, vals, len);
+}
+
+// Keep this in sync with all the other Bench_*() functions.
+fn Bench_Rust<H: std::hash::BuildHasher>(mut hs: HashSet<*const c_void, H>, params: *const Params,
+                                         vals: *const *const c_void, len: usize) {
+    let params = unsafe { &*params };
+    let vals = unsafe { slice::from_raw_parts(vals, len) };
+
+    for j in 0..params.num_inserts {
+        hs.insert(vals[j]);
+    }
+
+    for _i in 0..params.num_successful_lookups {
+        for j in 0..params.num_inserts {
+            assert!(hs.contains(&vals[j]));
+        }
+    }
+
+    for _i in 0..params.num_failing_lookups {
+        for j in params.num_inserts..params.num_inserts*2 {
+            assert!(!hs.contains(&vals[j]));
+        }
+    }
+
+    for _i in 0..params.num_iterations {
+      let mut n = 0;
+      for _ in hs.iter() {
+        n += 1;
+      }
+      assert!(params.num_inserts == n);
+      assert!(hs.len() == n);
+    }
+
+    if params.remove_inserts {
+        for j in 0..params.num_inserts {
+            assert!(hs.remove(&vals[j]));
+        }
+        assert!(hs.len() == 0);
+    } else {
+        assert!(hs.len() == params.num_inserts);
+    }
+}
+
--- a/xpcom/rust/gtest/moz.build
+++ b/xpcom/rust/gtest/moz.build
@@ -1,12 +1,13 @@
 # -*- Mode: python; indent-tabs-mode: nil; tab-width: 40 -*-
 # vim: set filetype=python:
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 UNIFIED_SOURCES += [
+    'bench-collections/Bench.cpp',
     'nsstring/Test.cpp',
     'xpcom/Test.cpp',
 ]
 
 FINAL_LIBRARY = 'xul-gtest'