Presentation

Presentation.md

Getting a Benchmarking Library

Google Benchmark

• Similar interface to GTest
• Based off testing/base/benchmark
• New and shiny interface.

Example Usage:

static void BM_StringCreation(benchmark::State& state) {
  while (state.KeepRunning())
    std::string empty_string;
}
// Register the function as a benchmark
BENCHMARK(BM_StringCreation);

// Define another benchmark
static void BM_StringCopy(benchmark::State& state) {
  std::string x = "hello";
  while (state.KeepRunning())
    std::string copy(x);
}
BENCHMARK(BM_StringCopy);

BENCHMARK_MAIN();

Timings and Noise

bool State::KeepRunning() {
  struct rusage ru;
  getrusage(RUSAGE_SELF, &ru);
  double now = (static_cast<double>(ru.ru_utime.tv_sec) +
                static_cast<double>(ru.ru_utime.tv_usec) * 1e-6 +
                static_cast<double>(ru.ru_stime.tv_sec) +
                static_cast<double>(ru.ru_stime.tv_usec) * 1e-9);
  return (now - m_start < m_min_time);
    
}

bool State::KeepRunning() {
  return ++m_total_iterations < m_max_iterations;
}

void BM_empty(benchmark::State& st) {
  while (st.KeepRunning()) {
    for (int i=0; i < 10000; ++i) {}
  }  
}

Results for 100 repetitions over 50 seconds.

Test	Time(ns)	CPU(ns)	Iterations
Mean Before	56194	56816	8813
Stddev Before	1146	1133	171
Mean After	55454	55509	12344
Stddev After	670	635	N/A

• The old version becomes more unstable as the benchmark length decreases.

Linking two Standard libraries

Goal:

• Use one benchmark library for both libc++ and libstdc++
• No dependence on the standard library ABI

Solution:

1. PIMPL everywhere.
2. Only cross the library boundary when needed.
3. Only cross the library boundary with builtin types.
4. Don't use exceptions or RTTI.

Using std::string without naming std::string.

void SetLabel(const char* label);

template <class Tp>
void SetLabel(Tp const& str, typename Tp::basic_string* = nullptr) {
  SetLabel(str.c_str());  
}

DoNotOptimize(...)

Sample Code:

int Test() {
  int x = 0;
  for (int i=0; i < 64; ++i)
    x += i;
  return x;
}

Test():
  movl	$2016, %eax
  ret

Passing the data across the library boundary.

void UseCharPointer(const volatile char*);

template <class Tp>
inline __attribute__((__always_inline__))
void DoNotOptimize(Tp const& value) {
    UseCharPointer(&reinterpret_cast<char const volatile&>(value));
}
int Test() {
  int x = 0;
  for (int i=0; i < 64; ++i)
    DoNotOptimize(x += i);
  return x;
}

Test():
	pushq	%rbx
	xorl	%eax, %eax
	xorl	%ebx, %ebx
	subq	$16, %rsp
.L12:
	addl	%ebx, %eax
	movq	%rsp, %rdi
	addl	$1, %ebx
	movl	%eax, (%rsp)
	call	UseCharPointer(char const volatile*)
	cmpl	$64, %ebx
	movl	(%rsp), %eax
	jne	.L12
	addq	$16, %rsp
	popq	%rbx
	ret

Inline assembly solution:

template <class Tp>
inline __attribute__((__always_inline__)) 
void DoNotOptimize(Tp const& value) {
    asm volatile("" : "+rm" (const_cast<Tp&>(value)));
}

Test():
	xorl	%eax, %eax
	xorl	%edx, %edx
.L4:
	addl	%edx, %eax
	addl	$1, %edx
	cmpl	$64, %edx
	jne	.L4
	rep ret

Inline assembly on Clang:

template <class Tp>
inline __attribute__((__always_inline__))
void DoNotOptimize(Tp const& value) {
    asm volatile("" : "+m" (const_cast<Tp&>(value)));
}

Test():
	xorl	%edx, %edx
	xorl	%eax, %eax
	jmp	.L8
.L9:
	movl	-24(%rsp), %edx
.L8:
	addl	%eax, %edx
	movl	%edx, -24(%rsp)
	addl	$1, %eax
	cmpl	$64, %eax
	jne	.L9
	movl	-24(%rsp), %eax
	ret

Interface improvements

TODO

The Standard Library

• 90% headers and 10% compiled source. (Most source is locales)
• Benchmarks focus on containers and algorithms.

Containers:

• 13 containers but only only 6 are really of interest.
• Sequence Containers: vector, deque, forward_list, list
• Associative Containers: set, multiset, map, multimap
• Unordered Containers: unordered_set, unordered_multiset, unordered_map, unordered_multimap

Algorithms:

• 85 in <algorithm>
• 5 in <numeric>
• Most algorithms are dispatched depending on the iterator type.
• Some algorithms have multiple signatures for taking extra parameters (ie predicates)
• This expands to a lot of different algorithm functions

Common Optimizations

Loop Unrolling

template <class InputIt, class ValueT>
InputIt find(InputIt first, InputIt last, ValueT const& value) {
  for (; first != last; ++first)
    if (*first == value)
      break;
  return first;
}

template <class RandIt, class ValueT>
RandIt find(RandIt first, RandIt last, ValueT const& value) {
  std::ptrdiff_t count = last - first;
  if (count == 0) return first;
  std::size_t n = (count + 3) / 4;
  switch (count % 4) {
  case 0:
    do {
      if (*first == value) return first;
      ++first;
    case 3:
      if (*first == value) return first;
      ++first;
    case 2:
      if (*first == value) return first;
      ++first;
    case 1:
      if (*first == value) return first;
      ++first;
    } while (--n > 0);
  }
  return last; 
}

Unroll	find int	find string
2:	0.01%	-10.00%
4:	4.00%	-8.00%
8:	37.40%	-8.00%
12:	41.00%	-2.00%
16:	43.00%	-3.00%

memcpy

template <class Alloc>
struct allocator_traits {

  template <class Iter, class Ptr>
  static void construct_range(Alloc& a, Iter begin1, Iter end1, Ptr begin2) {
    for (; begin1 != end1; ++begin1, ++begin2)
        construct(a, begin2, *begin1);
  }

  template <class Tp>
  static 
  typename enable_if<
      (is_same<Alloc, allocator<Tp>>::value 
        || !has_construct_method<Alloc>::value)
      && is_trivially_constructible<Tp>::value,
    void
  >::type
  construct_range(Alloc& a, Tp* begin1, Tp* end1, Tp* begin2) {
    std::ptrdiff_t dist = end1 - begin1;
    std::memcpy(begin2, begin1, dist * sizeof(Tp));
  }
};

• No improvement in optimized builds
• 75% improvement in debug builds.

memcmp

template <class InputIt1, class InputIt2>
bool equal_imp(InputIt1 first1, InputIt1 last1, InputIt2 first2, false_type) {
  for (; first1 != last1; ++first1, ++first2)
    if (!(*first1 == *first2))
      return false;
  return true;
}

template <class PtrIt1, class PtrIt2>
bool equal_imp(PtrIt1 first1, PtrIt1 last1, PtrIt2 first2, true_type) {
  using ValueT = typename iterator_traits<PtrIt1>::value_type;
  return !memcmp(first1, first2, sizeof(ValueT) * (last1 - first1)); 
}

template <class Iter1, class Iter2>
bool equal(Iter1 first1, Iter1 last1, Iter2 first2) {
  using ValueT1 = typename iterator_traits<Iter1>::value_type;
  using ValueT2 = typename iterator_traits<Iter2>::value_type;
  using CanMemCmp = integral_constant<bool,
    (is_pointer_v<ValueT1> || is_integral_v<ValueT2>)
    && is_pointer_v<Iter1> && is_pointer_v<Iter2>
    && is_same_v<ValueT1, ValueT2>>;
  return equal_imp(first1, last1, first2, CanMemCmp());
}

This gives a 75% speedup in optimized builds.

Improving performance

I have submitted or created patches for:

• vector::insert(Pos, Begin, End)
• unordered_*::insert(Value&&)
• find, find_if, find_if_not, any_of, all_of, none_of
• equal
• search
• find_end

There are known performance issues in:

• string::compare(const char*)
• map::map(map const&), set::set(set const&)

Results

• Google/Benchmark is now a feasible benchmarking library in the open source community.
  • More stable timings
  • A better interface to allow for more accurate timings.
  • Different output formats including JSON.
• LLVM
  • Patches are in the works to put the Benchmark library in LLVM.
  • I've Created a test format for LIT that allows benchmark regression testing and comparisons.
• libc++
  • 100+ benchmarks with good coverage of the containers and partial coverage of the algorithms.
  • 11 performance fixes have been completed.
  • Many more, previously unknown, performance problems have been identified.
  • libc++ now has a test format for comparing the performance of libc++ to libstdc++.
    • D7570 Fix PR12999 - unordered_set::insert calls operator new when no insert occurs
    • D8109 [libcxx] Optimize vectors uninitialized construction of trivial types from an iterator range.
    • Bug 19708 - libc++'s std::find is about 50% slower than the libstdc++'s
    • more to come...
  • Bug fixes to libc++ that blocked the MSAN-with-libc++ project. (only 14,000 failing builds to go!)
    • [libcxx] Properly convert the count arguments to the *_n algorithms before use.
    • D7444 [libcxx] Fix PR 22468 - std::function<void()> does not accept non-void-returning functions
    • [libc++] Fix PR20084 - std::is_function<void() const> failed.
    • D7569 [libc++] Try and prevent evaluation of is_default_constructible on tuples default constructor if it is not needed.
    • D7785 [libcxx] Allow declaration of map and multimap iterator with incomplete mapped type.

There is still a long way to go!

Micro benchmark improvements

BM_all_of/16k failed:
    cpu_time:   36.246%  FASTER (baseline=18757, current=13767, diff=4990)
    real_time:  36.241%  FASTER (baseline=18755, current=13766, diff=4989)
    iterations: 35.825%  FASTER (baseline=37292, current=50652, diff=13360)

BM_any_of/16k failed:
    cpu_time:   36.290%  FASTER (baseline=18759, current=13764, diff=4995)
    real_time:  36.310%  FASTER (baseline=18759, current=13762, diff=4997)
    iterations: 36.221%  FASTER (baseline=37304, current=50816, diff=13512)

BM_equal/16k failed:
    cpu_time:   3.996x   FASTER (baseline=28186, current=7054, diff=21132)
    real_time:  3.996x   FASTER (baseline=28186, current=7053, diff=21133)
    iterations: 3.976x   FASTER (baseline=24823, current=98697, diff=73874)

BM_equal_pred/16k failed:
    cpu_time:   50.349%  FASTER (baseline=28210, current=18763, diff=9447)
    real_time:  50.320%  FASTER (baseline=28206, current=18764, diff=9442)
    iterations: 49.982%  FASTER (baseline=24803, current=37200, diff=12397)

BM_find_end/16k/16 failed:
    cpu_time:   78.337%  FASTER (baseline=12612, current=7072, diff=5540)
    real_time:  78.334%  FASTER (baseline=12610, current=7071, diff=5539)
    iterations: 77.826%  FASTER (baseline=55546, current=98775, diff=43229)

BM_find_end/16k/16k failed:
    cpu_time:   77.757%  FASTER (baseline=12523, current=7045, diff=5478)
    real_time:  77.715%  FASTER (baseline=12520, current=7045, diff=5475)
    iterations: 77.663%  FASTER (baseline=55805, current=99145, diff=43340)

BM_for_each/16k failed:
    cpu_time:   25.934%  FASTER (baseline=2428, current=1928, diff=500)
    real_time:  25.934%  FASTER (baseline=2428, current=1928, diff=500)
    iterations: 1.698%   FASTER (baseline=356198, current=362246, diff=6048)

BM_none_of/16k failed:
    cpu_time:   36.226%  FASTER (baseline=18757, current=13769, diff=4988)
    real_time:  36.226%  FASTER (baseline=18757, current=13769, diff=4988)
    iterations: 36.062%  FASTER (baseline=37313, current=50769, diff=13456)

BM_search/16k/16 failed:
    cpu_time:   2.236x   FASTER (baseline=31528, current=14102, diff=17426)
    real_time:  2.235x   FASTER (baseline=31522, current=14101, diff=17421)
    iterations: 2.230x   FASTER (baseline=22177, current=49462, diff=27285)

BM_search/16k/16k failed:
    cpu_time:   58.702%  FASTER (baseline=9438, current=5947, diff=3491)
    real_time:  58.675%  FASTER (baseline=9438, current=5948, diff=3490)
    iterations: 58.850%  FASTER (baseline=74082, current=117679, diff=43597)

BM_search_single_length_pattern/16k/16 failed:
    cpu_time:   60.048%  FASTER (baseline=9398, current=5872, diff=3526)
    real_time:  60.058%  FASTER (baseline=9397, current=5871, diff=3526)
    iterations: 60.195%  FASTER (baseline=74432, current=119236, diff=44804)

BM_find<StrideGenerator<int>>/9.76562k failed:
    cpu_time:   59.794%  FASTER (baseline=5727, current=3584, diff=2143)
    real_time:  59.838%  FASTER (baseline=5727, current=3583, diff=2144)
    iterations: 59.977%  FASTER (baseline=121989, current=195154, diff=73165)

container_insert_value<IntSet, Stride, ConstantGenerator<int, 42>>/1/16k failed:
    cpu_time:   2.499x   FASTER (baseline=2066891, current=826979, diff=1239912)
    real_time:  2.496x   FASTER (baseline=2061844, current=826108, diff=1235736)
    iterations: 2.457x   FASTER (baseline=348, current=855, diff=507)

container_copy_assignment<std::vector<int>, ConstantGenerator<int, 42>>/8k failed:
    cpu_time:   3.781x   FASTER (baseline=132128, current=34943, diff=97185)
    real_time:  3.783x   FASTER (baseline=131881, current=34860, diff=97021)
    iterations: 3.952x   FASTER (baseline=5028, current=19869, diff=14841)

container_copy_constructor<std::vector<int>, ConstantGenerator<int, 42>>/8k failed:
    cpu_time:   3.727x   FASTER (baseline=132426, current=35531, diff=96895)
    real_time:  3.721x   FASTER (baseline=132161, current=35514, diff=96647)
    iterations: 3.715x   FASTER (baseline=5400, current=20061, diff=14661)

container_range_constructor<std::vector<int>, ConstantGenerator<int, 42>>/8k failed:
    cpu_time:   3.521x   FASTER (baseline=133204, current=37829, diff=95375)
    real_time:  3.518x   FASTER (baseline=132970, current=37793, diff=95177)
    iterations: 2.632x   FASTER (baseline=5350, current=14080, diff=8730)

container_insert_range_end<IntVector, Stride, Stride>/256/256 failed:
    cpu_time:   42.892%  FASTER (baseline=5227, current=3658, diff=1569)
    real_time:  42.799%  FASTER (baseline=5225, current=3659, diff=1566)
    iterations: 2.573x   FASTER (baseline=110619, current=284630, diff=174011)

container_insert_range_end<IntVector, Stride, Stride>/256/256 failed:
    cpu_time:   63.207%  FASTER (baseline=4937, current=3025, diff=1912)
    real_time:  62.773%  FASTER (baseline=4919, current=3022, diff=1897)
    iterations: 2.576x   FASTER (baseline=123590, current=318311, diff=194721)

Macro Benchmarks

Goal:

• Programs that have a large C++11 code-base.
• Long execution times.
• Repeatable.

LNT:

• LNT is a compiler benchmark suite for clang
• Many single-source and multi-source tests
• built-in web interface to compare results.

Advice on template benchmarks.

1. Don't trust the compilers optimizer.
2. Verify benchmark assembly.
3. Place functions to be benchmarked across a compilation unit boundary.

gettimeofday (&tstart, NULL);
// We use 'dummy' to prevent clang from completely optimizing out the call to find().
volatile unsigned dummy = 0;
for (unsigned trial=0; trial<n_trials; ++trial) {
  UnorderedMapType::iterator it = um.find(N/2);
  dummy = it->first;
}
gettimeofday (&tstop, NULL);

// libstdc++
//
// N    map        unordered_map
// 2    2.06997    0.882264
// 4    2.53414    0.888939
// 8    3.19828    0.877453
// 16   3.83513    0.876052
// 32   3.82357    0.877334
// 64   4.38807    0.877624
// 128  4.94558    0.880401
// 256  5.52116    0.87198
// 512  6.20285    0.876554
// 1024 7.60791    0.916113

// libc++
//
// N    map        unordered_map
// 2    2.07317    2.03433
// 4    1.87946    18.2131
// 8    3.10882    18.229
// 16   3.80371    18.4432
// 32   3.80869    18.4188
// 64   4.44196    18.3647
// 128  8.17782    18.388
// 256  9.3574     18.4078
// 512  10.5781    18.3727
// 1024 11.6872    18.4273

template <class _Tp, class _Hash, class _Equal, class _Alloc>
template <class _Key>
typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
__hash_table<_Tp, _Hash, _Equal, _Alloc>::find(const _Key& __k)
{
    size_t __hash = hash_function()(__k);
    size_type __bc = bucket_count();
    if (__bc != 0)
    {
        size_t __chash = __constrain_hash(__hash, __bc);
        __node_pointer __nd = __bucket_list_[__chash];
        if (__nd != nullptr)
        {
            for (__nd = __nd->__next_;
                   __nd != nullptr
                   && __constrain_hash(__nd->__hash_, __bc) == __chash;
                   __nd = __nd->__next_)
            {
                if (key_eq()(__nd->__value_, __k))
                    return iterator(__nd);
            }
        }
    }
    return end();
}

Questions