summaryrefslogtreecommitdiffstats
path: root/xpcom/rust/gtest/bench-collections
diff options
context:
space:
mode:
Diffstat (limited to 'xpcom/rust/gtest/bench-collections')
-rw-r--r--xpcom/rust/gtest/bench-collections/Bench.cpp297
-rw-r--r--xpcom/rust/gtest/bench-collections/Cargo.toml12
-rw-r--r--xpcom/rust/gtest/bench-collections/bench.rs101
3 files changed, 410 insertions, 0 deletions
diff --git a/xpcom/rust/gtest/bench-collections/Bench.cpp b/xpcom/rust/gtest/bench-collections/Bench.cpp
new file mode 100644
index 0000000000..41152470c7
--- /dev/null
+++ b/xpcom/rust/gtest/bench-collections/Bench.cpp
@@ -0,0 +1,297 @@
+/* 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",
+// "MozHash") 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 "mozilla/AllocPolicy.h"
+#include "mozilla/ArrayUtils.h"
+#include "mozilla/HashFunctions.h"
+#include "mozilla/HashTable.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.
+static 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.
+static 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.
+static 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.
+static void Bench_Cpp_MozHashSet(const Params* aParams, void** aVals,
+ size_t aLen) {
+ mozilla::HashSet<void*, mozilla::DefaultHasher<void*>, MallocAllocPolicy> hs;
+
+ for (size_t j = 0; j < aParams->mNumInserts; j++) {
+ MOZ_RELEASE_ASSERT(hs.put(aVals[j]));
+ }
+
+ for (size_t i = 0; i < aParams->mNumSuccessfulLookups; i++) {
+ for (size_t j = 0; j < aParams->mNumInserts; j++) {
+ MOZ_RELEASE_ASSERT(hs.has(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.has(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.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[] = {
+ // clang-format off
+ // 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 },
+ // clang-format on
+};
+
+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 MOZ_UNANNOTATED;
+};
+
+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, MozHash,
+ [this] { BenchImpl(Bench_Cpp_MozHashSet); });
+
+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); });
diff --git a/xpcom/rust/gtest/bench-collections/Cargo.toml b/xpcom/rust/gtest/bench-collections/Cargo.toml
new file mode 100644
index 0000000000..857d87cffd
--- /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"
diff --git a/xpcom/rust/gtest/bench-collections/bench.rs b/xpcom/rust/gtest/bench-collections/bench.rs
new file mode 100644
index 0000000000..1aba69f01f
--- /dev/null
+++ b/xpcom/rust/gtest/bench-collections/bench.rs
@@ -0,0 +1,101 @@
+/* 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.is_empty());
+ } else {
+ assert!(hs.len() == params.num_inserts);
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-30 00:03:35 +0000