xpcom/rust/gtest/bench-collections/Bench.cpp
author Chris Peterson <cpeterson@mozilla.com>
Sun, 24 Feb 2019 17:35:59 -0800
changeset 464363 5ff84e853d700af894616574f581551a88a93dc7
parent 448947 6f3709b3878117466168c40affa7bca0b60cf75b
permissions -rw-r--r--
Bug 1534878 - xpcom: Make some global functions static. r=erahm clang's -Wmissing-prototypes option identifies global functions that can be made static (because they're only called from one compilation unit) or removed (if they're never called). xpcom/base/Logging.cpp:85:13 [-Wmissing-prototypes] no previous prototype for function 'ToLogStr' xpcom/base/Logging.cpp:132:13 [-Wmissing-prototypes] no previous prototype for function 'ExpandPIDMarker' xpcom/base/LogModulePrefWatcher.cpp:37:6 [-Wmissing-prototypes] no previous prototype for function 'ResetExistingPrefs' xpcom/base/LogModulePrefWatcher.cpp:109:6 [-Wmissing-prototypes] no previous prototype for function 'LoadExistingPrefs' xpcom/base/nsCycleCollector.cpp:212:6 [-Wmissing-prototypes] no previous prototype for function 'SuspectUsingNurseryPurpleBuffer' xpcom/components/nsComponentManager.cpp:421:31 [-Wmissing-prototypes] no previous prototype for function 'begin' xpcom/components/nsComponentManager.cpp:427:31 [-Wmissing-prototypes] no previous prototype for function 'end' xpcom/ds/Dafsa.cpp:23:6 [-Wmissing-prototypes] no previous prototype for function 'GetNextOffset' xpcom/ds/Dafsa.cpp:55:6 [-Wmissing-prototypes] no previous prototype for function 'IsEOL' xpcom/ds/Dafsa.cpp:62:6 [-Wmissing-prototypes] no previous prototype for function 'IsMatch' xpcom/ds/Dafsa.cpp:70:6 [-Wmissing-prototypes] no previous prototype for function 'IsEndCharMatch' xpcom/ds/Dafsa.cpp:78:6 [-Wmissing-prototypes] no previous prototype for function 'GetReturnValue' xpcom/ds/Dafsa.cpp:91:5 [-Wmissing-prototypes] no previous prototype for function 'LookupString' xpcom/io/CocoaFileUtils.mm:195:13 [-Wmissing-prototypes] no previous prototype for function 'GetQuarantinePropKey' xpcom/io/CocoaFileUtils.mm:203:24 [-Wmissing-prototypes] no previous prototype for function 'CreateQuarantineDictionary' xpcom/rust/gtest/bench-collections/Bench.cpp:65:11 [-Wmissing-prototypes] no previous prototype for function 'MyRand' xpcom/rust/gtest/bench-collections/Bench.cpp:85:6 [-Wmissing-prototypes] no previous prototype for function 'Bench_Cpp_unordered_set' xpcom/rust/gtest/bench-collections/Bench.cpp:125:6 [-Wmissing-prototypes] no previous prototype for function 'Bench_Cpp_PLDHashTable' xpcom/rust/gtest/bench-collections/Bench.cpp:166:6 [-Wmissing-prototypes] no previous prototype for function 'Bench_Cpp_MozHashSet' xpcom/tests/gtest/TestAtoms.cpp:114:6 [-Wmissing-prototypes] no previous prototype for function 'isStaticAtom' xpcom/tests/gtest/TestCallTemplates.cpp:72:6 [-Wmissing-prototypes] no previous prototype for function 'JustTestingCompilation' xpcom/tests/gtest/TestCOMPtr.cpp:87:10 [-Wmissing-prototypes] no previous prototype for function 'CreateIFoo' xpcom/tests/gtest/TestCOMPtr.cpp:98:6 [-Wmissing-prototypes] no previous prototype for function 'set_a_IFoo' xpcom/tests/gtest/TestCOMPtr.cpp:105:16 [-Wmissing-prototypes] no previous prototype for function 'return_a_IFoo' xpcom/tests/gtest/TestCOMPtr.cpp:164:10 [-Wmissing-prototypes] no previous prototype for function 'CreateIBar' xpcom/tests/gtest/TestCOMPtr.cpp:175:6 [-Wmissing-prototypes] no previous prototype for function 'AnIFooPtrPtrContext' xpcom/tests/gtest/TestCOMPtr.cpp:177:6 [-Wmissing-prototypes] no previous prototype for function 'AVoidPtrPtrContext' xpcom/tests/gtest/TestCOMPtr.cpp:179:6 [-Wmissing-prototypes] no previous prototype for function 'AnISupportsPtrPtrContext' xpcom/tests/gtest/TestCOMPtr.cpp:263:6 [-Wmissing-prototypes] no previous prototype for function 'Comparison' xpcom/tests/gtest/TestCOMPtr.cpp:298:6 [-Wmissing-prototypes] no previous prototype for function 'DontAddRef' xpcom/tests/gtest/TestCRT.cpp:17:5 [-Wmissing-prototypes] no previous prototype for function 'sign' xpcom/tests/gtest/TestDeadlockDetector.cpp:62:6 [-Wmissing-prototypes] no previous prototype for function 'DisableCrashReporter' xpcom/tests/gtest/TestDeadlockDetector.cpp:74:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:95:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity2_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:159:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity4_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:182:5 [-Wmissing-prototypes] no previous prototype for function 'Sanity5_Child' xpcom/tests/gtest/TestDeadlockDetector.cpp:303:5 [-Wmissing-prototypes] no previous prototype for function 'ContentionNoDeadlock_Child' xpcom/tests/gtest/TestHashtables.cpp:88:6 [-Wmissing-prototypes] no previous prototype for function 'testTHashtable' xpcom/tests/gtest/TestHashtables.cpp:205:10 [-Wmissing-prototypes] no previous prototype for function 'CreateIFoo' xpcom/tests/gtest/TestMoveString.cpp:25:6 [-Wmissing-prototypes] no previous prototype for function 'SetAsOwned' xpcom/tests/gtest/TestMoveString.cpp:34:6 [-Wmissing-prototypes] no previous prototype for function 'ExpectTruncated' xpcom/tests/gtest/TestMoveString.cpp:40:6 [-Wmissing-prototypes] no previous prototype for function 'ExpectNew' xpcom/tests/gtest/TestMruCache.cpp:52:11 [-Wmissing-prototypes] no previous prototype for function 'MakeStringKey' xpcom/tests/gtest/TestMultiplexInputStream.cpp:106:34 [-Wmissing-prototypes] no previous prototype for function 'CreateStreamHelper' xpcom/tests/gtest/TestNonBlockingAsyncInputStream.cpp:62:10 [-Wmissing-prototypes] no previous prototype for function 'ReadSegmentsFunction' xpcom/tests/gtest/TestNsDeque.cpp:240:6 [-Wmissing-prototypes] no previous prototype for function 'CheckIfQueueEmpty' xpcom/tests/gtest/TestNsRefPtr.cpp:105:10 [-Wmissing-prototypes] no previous prototype for function 'CreateFoo' xpcom/tests/gtest/TestNsRefPtr.cpp:116:6 [-Wmissing-prototypes] no previous prototype for function 'set_a_Foo' xpcom/tests/gtest/TestNsRefPtr.cpp:123:13 [-Wmissing-prototypes] no previous prototype for function 'return_a_Foo' xpcom/tests/gtest/TestNsRefPtr.cpp:391:6 [-Wmissing-prototypes] no previous prototype for function 'AnFooPtrPtrContext' xpcom/tests/gtest/TestNsRefPtr.cpp:392:6 [-Wmissing-prototypes] no previous prototype for function 'AVoidPtrPtrContext' xpcom/tests/gtest/TestPLDHash.cpp:33:6 [-Wmissing-prototypes] no previous prototype for function 'TestCrashyOperation' xpcom/tests/gtest/TestPipes.cpp:98:10 [-Wmissing-prototypes] no previous prototype for function 'TestPipe' xpcom/tests/gtest/TestPipes.cpp:212:10 [-Wmissing-prototypes] no previous prototype for function 'TestShortWrites' xpcom/tests/gtest/TestPipes.cpp:354:6 [-Wmissing-prototypes] no previous prototype for function 'RunTests' xpcom/tests/gtest/TestPLDHash.cpp:90:6 [-Wmissing-prototypes] no previous prototype for function 'InitCapacityOk_InitialLengthTooBig' xpcom/tests/gtest/TestPLDHash.cpp:95:6 [-Wmissing-prototypes] no previous prototype for function 'InitCapacityOk_InitialEntryStoreTooBig' xpcom/tests/gtest/TestPLDHash.cpp:102:6 [-Wmissing-prototypes] no previous prototype for function 'InitCapacityOk_EntrySizeTooBig' xpcom/tests/gtest/TestSlicedInputStream.cpp:111:20 [-Wmissing-prototypes] no previous prototype for function 'CreateSeekableStreams' xpcom/tests/gtest/TestSlicedInputStream.cpp:125:20 [-Wmissing-prototypes] no previous prototype for function 'CreateNonSeekableStreams' xpcom/tests/gtest/TestStrings.cpp:471:6 [-Wmissing-prototypes] no previous prototype for function 'test_assign_helper' xpcom/tests/gtest/TestTArray.cpp:60:22 [-Wmissing-prototypes] no previous prototype for function 'DummyArray' xpcom/tests/gtest/TestTArray.cpp:72:22 [-Wmissing-prototypes] no previous prototype for function 'FakeHugeArray' xpcom/tests/gtest/TestThrottledEventQueue.cpp:96:6 [-Wmissing-prototypes] no previous prototype for function 'Enqueue' xpcom/threads/BlockingResourceBase.cpp:86:6 [-Wmissing-prototypes] no previous prototype for function 'PrintCycle' xpcom/threads/CPUUsageWatcher.cpp:41:10 [-Wmissing-prototypes] no previous prototype for function 'GetMicroseconds' xpcom/threads/CPUUsageWatcher.cpp:46:10 [-Wmissing-prototypes] no previous prototype for function 'GetMicroseconds' xpcom/threads/CPUUsageWatcher.cpp:51:40 [-Wmissing-prototypes] no previous prototype for function 'GetProcessCPUStats' xpcom/threads/CPUUsageWatcher.cpp:80:40 [-Wmissing-prototypes] no previous prototype for function 'GetGlobalCPUStats' xpcom/threads/nsTimerImpl.cpp:196:21 [-Wmissing-prototypes] no previous prototype for function 'GetTimerFiringsLog' Differential Revision: https://phabricator.services.mozilla.com/D23264

/* 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/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;
};

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); });