--- 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"
@@ -840,16 +848,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,284 @@
+/* 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/. */
+
+// This file benchmarks various implementations of C++ and Rust collections
+// (hash tables, etc.) used within the codebase. There are a small number of
+// scenarios for each implementation that test the main operations. More
+// scenarios could be envisioned, but this number is enough to characterize the
+// major differences between implementations.
+//
+// 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.
+//
+// If you want to run a test under a profiler such as Callgrind, do something
+// like this:
+//
+//   MOZ_RUN_GTEST=1 GTEST_FILTER='*BenchCollections*PLDHash*'
+//       valgrind --tool=callgrind --callgrind-out-file=clgout
+//       $OBJDIR/dist/bin/firefox -unittest
+//   callgrind_annotate --auto=yes clgout > clgann
+//
+// where OBJDIR is your objdir.
+//
+// Gtest spawns multiple processes, but the last one 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.)
+//
+// Note that the Rust implementations run very slowly without --enable-release.
+
+#include "gtest/gtest.h"
+#include "gtest/MozGTestBench.h" // For MOZ_GTEST_BENCH
+
+#include "mozilla/AllocPolicy.h"
+#include "mozilla/HashFunctions.h"
+#include "mozilla/StaticMutex.h"
+#include "mozilla/TimeStamp.h"
+
+#include "js/HashTable.h"
+
+#include "nsDataHashtable.h"
+
+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?
+};
+
+// 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(n == aParams->mNumInserts);
+    MOZ_RELEASE_ASSERT(n == hs.EntryCount());
+  }
+
+  if (aParams->mRemoveInserts) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      hs.Remove(aVals[j]);
+    }
+  }
+}
+
+// Keep this in sync with all the other Bench_*() functions.
+void
+Bench_Cpp_nsDataHashtable(const Params* aParams, void** aVals, size_t aLen)
+{
+  struct Empty {};
+  nsDataHashtable<nsPtrHashKey<void>, Empty> hs;
+
+  for (size_t j = 0; j < aParams->mNumInserts; j++) {
+    hs.Put(aVals[j], Empty {});
+  }
+
+  for (size_t i = 0; i < aParams->mNumSuccessfulLookups; i++) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      MOZ_RELEASE_ASSERT(hs.Get(aVals[j], nullptr));
+    }
+  }
+
+  for (size_t i = 0; i < aParams->mNumFailingLookups; i++) {
+    for (size_t j = aParams->mNumInserts; j < aParams->mNumInserts*2; j++) {
+      MOZ_RELEASE_ASSERT(!hs.Get(aVals[j], nullptr));
+    }
+  }
+
+  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(n == aParams->mNumInserts);
+    MOZ_RELEASE_ASSERT(n == hs.Count());
+  }
+
+  if (aParams->mRemoveInserts) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      MOZ_RELEASE_ASSERT(hs.Remove(aVals[j]));
+    }
+  }
+}
+
+// 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(n == aParams->mNumInserts);
+    MOZ_RELEASE_ASSERT(n == hs.count());
+  }
+
+  if (aParams->mRemoveInserts) {
+    for (size_t j = 0; j < aParams->mNumInserts; j++) {
+      hs.remove(aVals[j]);
+    }
+  }
+}
+
+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("%18s", params->mConfigName);
+    }
+    printf("\n");
+  }
+
+public:
+  void BenchImpl(void(*aBench)(const Params*, void**, size_t))
+  {
+    StaticMutexAutoLock lock(sValsMutex);
+
+    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();
+      printf("%15.1f ms", (t2 - t1).ToMilliseconds());
+    }
+    printf("\n");
+  }
+
+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, PLDHash, [this] {
+  BenchImpl(Bench_Cpp_PLDHashTable);
+});
+
+MOZ_GTEST_BENCH_F(BenchCollections, nsDataHash, [this] {
+  BenchImpl(Bench_Cpp_nsDataHashtable);
+});
+
+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,87 @@
+/* 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!(n == params.num_inserts);
+      assert!(n == hs.len());
+    }
+
+    if params.remove_inserts {
+        for j in 0..params.num_inserts {
+            assert!(hs.remove(&vals[j]));
+        }
+    }
+}
+

--- 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'