76 lines
2.4 KiB
C++
76 lines
2.4 KiB
C++
//===- ImmutableSetBuildBM.cpp - Benchmark ImmutableSet construction ------===//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
//
|
|
// Benchmarks the mutating operations of ImmutableSet -- add and remove -- which
|
|
// exercise the ImutAVLFactory node bookkeeping (createNode / recoverNodes) that
|
|
// the iterator benchmark deliberately keeps out of its timed region. Run the
|
|
// binary before and after a change and compare the two reports (e.g. with
|
|
// llvm/utils/compare.py).
|
|
//
|
|
// * Build - build an N-element set from empty (N add calls).
|
|
// * BuildRemove - build an N-element set, then remove every element.
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "benchmark/benchmark.h"
|
|
#include "llvm/ADT/ImmutableSet.h"
|
|
#include <algorithm>
|
|
#include <numeric>
|
|
#include <random>
|
|
#include <vector>
|
|
|
|
using namespace llvm;
|
|
|
|
namespace {
|
|
|
|
// A shuffled [0, N) key sequence, so the tree is built in random order.
|
|
static std::vector<int> shuffledKeys(size_t N) {
|
|
std::vector<int> Vals(N);
|
|
std::iota(Vals.begin(), Vals.end(), 0);
|
|
std::mt19937 Rng(0xC0FFEE);
|
|
std::shuffle(Vals.begin(), Vals.end(), Rng);
|
|
return Vals;
|
|
}
|
|
|
|
static void BM_Build(benchmark::State &State) {
|
|
const size_t N = State.range(0);
|
|
std::vector<int> Vals = shuffledKeys(N);
|
|
for (auto _ : State) {
|
|
ImmutableSet<int>::Factory F(/*canonicalize=*/false);
|
|
ImmutableSet<int> S = F.getEmptySet();
|
|
for (int V : Vals)
|
|
S = F.add(S, V);
|
|
benchmark::DoNotOptimize(S.getRootWithoutRetain());
|
|
}
|
|
State.SetItemsProcessed(State.iterations() * N);
|
|
}
|
|
|
|
static void BM_BuildRemove(benchmark::State &State) {
|
|
const size_t N = State.range(0);
|
|
std::vector<int> Vals = shuffledKeys(N);
|
|
for (auto _ : State) {
|
|
ImmutableSet<int>::Factory F(/*canonicalize=*/false);
|
|
ImmutableSet<int> S = F.getEmptySet();
|
|
for (int V : Vals)
|
|
S = F.add(S, V);
|
|
for (int V : Vals)
|
|
S = F.remove(S, V);
|
|
benchmark::DoNotOptimize(S.getRootWithoutRetain());
|
|
}
|
|
State.SetItemsProcessed(State.iterations() * N * 2);
|
|
}
|
|
|
|
} // namespace
|
|
|
|
#define BUILD_SIZES Arg(256)->Arg(4096)->Arg(65536)
|
|
|
|
BENCHMARK(BM_Build)->Name("Build")->BUILD_SIZES;
|
|
BENCHMARK(BM_BuildRemove)->Name("BuildRemove")->BUILD_SIZES;
|
|
|
|
BENCHMARK_MAIN();
|