How to (nano-)benchmark correctly

[henrixapp]

Hi,

I have written a tutorial on how to port a static implicit B+-Tree described in this algorithmica.org article to Google Highway. You can find the writeup in this repository:

https://github.com/henrixapp/static-btree-highway

I tried to benchmark the btree against std::lower_bound by using hwy::MeasureClosure for varying size of N inputs, N between 32 and 2^26.
The interface for this is size_t->size_t. To make it work with more datatypes (the btree also works with floats), I just generated 10k queries (in my datatype) and answered them in a for-loop and meassured the performance (a single element had not enough overhead to measure).
However, that gave me insane performance for N>2^21 on 64 bit values, jumping to a relative speed up of >80. (note the log-scale)

For 32-bit values the bump occurs for N>2^22.

When running under perf I could see that the std::lower_bound code would use 0.08 instructions per cycle, while the btree would use 0.6.

I tried using 5 or 10 different queues of queries, but that also resulted in these large speedups.

In the algorithmica.org article they mention to chain the queries, so that no query can be run without finishing the other.
So that brought me to this idea to prevent reordering of runs by calling hwy::Unpredictable1():

    size_t elems = queries[i].size();
    for (size_t j = 0; j < elems; j++) {
      last = instance.lower_bound(queries[i][j * hwy::Unpredictable1()]);
      Mask ^= last;
    }

The numbers look more realistic:

Nevertheless, there is still a bump around the L3 cache size of the processor and I am fearing that I only added some overhead in the form of a call to the clock ([in the implementation of Unpredictable1](https://github.com/google/highway/blob/master/hwy/nanobenchmark.cc#L240)).

So what would be the recommend way of measuring speed ups/benchmarking with nanobenchmark.h or should I be using googlebenchmark on bigger sized inputs?

Best
Henrik

[jan-wassenberg]

Hi, quick comment from on the road.
It is a good idea to use Unpredictable1 as the initial input, but as you say it has some overhead/cost, so maybe a better alternative is to have each iteration feed into the output (which you return from the function to measure) somehow. For example, you could have a sum initialized to Unpredictable1, and in each iteration add the lookup result, and use a cheap RNG/hash (also seeded with Unpredictable1) to generate the next input.

It is strange that perf increases with problem size. Generally you'd expect that SIMD gives a larger speedup when compute bound. When memory bound, it would not help much. This could indicate some overhead in the test, for example the use of Unpredictable1/the timer.

[henrixapp]

Hi Jan,

Thanks for the swift response!
Because the layers of the B+-tree are not always full, we should see some variation between different powers of 2.
I would also expect to see some difference around the cache sizes.

Following your idea, I changed the query generation to be like this:

  std::minstd_rand rng;
  std::uniform_real_distribution<double> dist;
//...
  size_t operator()(size_t i) {
    size_t Mask = 0;
    size_t last = hwy::Unpredictable1();
    rng.seed(last);
    DataType sum = hwy::Unpredictable1();
    for (size_t j = 0; j < queries; j++) {
      // rng.seed(last);
      sum = dist(rng);
      last = instance.lower_bound(sum);
      Mask ^= last;
    }
    mask = Mask;
    return Mask;
  }

When I give a direct dependency by adding rng.seed (as in the outcommented part), performance crashes:

If it is not part of the loop, the speed up is around 1-40

So I looked at the disassembly and noticed that when rng.seed is part of the loop, we get a bunch of initialization instructions inlined for the random seed (yellow):

Is it possible that these lines are responsible for a congestion or alike?

[jan-wassenberg]

Yeah, we don't want to re-seed every iteration.
One improvement would be to use our simple XorShift generator (example). I'd also skip the distribution and just use raw random bits if possible.
But more important is to seed just once, using Unpredictable1; from then on, the compiler is not able to predict what the output will be.

[henrixapp]

Thank you for your feedback, I will include it and run some tests.

I have a second question (can also open a separate issue, if needed), but this is visible in the screenshots above:
When wrapping a object derived from a class in a HWY_NAMESPACE (with HWY_BEFORE_NAMESPACE(); and HWY_AFTER_NAMESPACE guard), like lets say the BTree into a function as template parameter, calls into that object are silently not inlined (as demonstrated in the dissassembly-screenshot in the comment above).

When I explicitly mark them with HWY_INLINE they are correctly inlined and force the template function to be in a suitable HWY_NAMESPACE (with a compile-time error like error: inlining failed in call to 'always_inline' 'size_t henrixapp::static_btree::N_AVX2::ImplicitStaticBTree<ValueType>::lower_bound(ValueType) [with ValueType = int]': target specific option mismatch).

I could not find much documentation on this, so is the intended behavior that users manually need to specify which functions are intended to be inlined? Maybe it would be nice to emit a warning, if in a BEFORE/AFTER namespace block there are no HWY_INLINEs.

[jan-wassenberg]

Generally it's not a bad idea to manually mark your functions HWY_INLINE or HWY_NOINLINE for reasons of compile time/code size; we usually do.

From the perspective of our C++ library, I'm not aware of any way we can introspect on the inline attribute and raise warnings :)