How to benchmark a compile-time action?

[prestokeys]

I've written the following binary search of a sorted template pack of integers.
std::cout << BinarySearch<65, 1,5,7,8,11,12,18,25,32,65,111,150>::value << std::endl;
returns the compile-time constant 9 because 65 is in position 9 of the template arguments 1,5,7,8,11,12,18,25,32,65,111,150 (position 0 being the first position). It is done through a binary search, and I want to know if this is truly faster than a simple linear search. But this is done during compile time, so how to time it? Or perhaps someone can tell me just by looking that it is NOT faster than simply unpacking the pack?

Note that the goal is to get the correct position as a compile-time constant, so using a std::map with the integers is not a solution.

#include <iostream>
#include <type_traits>

const int NOT_FOUND = -1;
template <bool, int, template <int, int> class Compare, int, int, int, int...> struct B3;
template <bool, int, template <int, int> class Compare, int, int, int, int...> struct B4;

template <int Key, template <int, int> class Compare, int Position, int ValueAtPosition, int LowerBound, int UpperBound, int... Rest>
struct B2 : std::conditional< Compare<Key, ValueAtPosition>::value,
	B3< Compare<UpperBound, LowerBound>::value, Key, Compare, Position, LowerBound, UpperBound, Rest...>,
	B4< Compare<UpperBound, LowerBound>::value, Key, Compare, Position, LowerBound, UpperBound, Rest...>
>::type {};

template <int Key, template <int, int> class Compare, int Position, int ValueAtPosition, int LowerBound, int UpperBound, int... Rest>
struct B1 : std::conditional<ValueAtPosition == Key,
	std::integral_constant<int, Position>,
	std::integral_constant<int, B2<Key, Compare, Position, ValueAtPosition, LowerBound, UpperBound, Rest...>::value>
>::type {};

template <int Key, template <int, int> class Compare, int LowerBound, int UpperBound, int... Rest>
struct B0 {
	static int constexpr array[] = {Rest...};
	static constexpr int position = (LowerBound + UpperBound) / 2,  value_at_position = array[position];
	static constexpr int value = B1<Key, Compare, position, value_at_position, LowerBound, UpperBound, Rest...>::value;
};

template <int Key, template <int, int> class Compare, int Position, int LowerBound, int UpperBound, int... Rest>
struct B3<true, Key, Compare, Position, LowerBound, UpperBound, Rest...> : std::integral_constant<int, NOT_FOUND> {};

template <int Key, template <int, int> class Compare, int Position, int LowerBound, int UpperBound, int... Rest>
struct B3<false, Key, Compare, Position, LowerBound, UpperBound, Rest...> :
	std::integral_constant<int, B0<Key, Compare, LowerBound, Position - 1, Rest...>::value> {};

template <int Key, template <int, int> class Compare, int Position, int LowerBound, int UpperBound, int... Rest>
struct B4<true, Key, Compare, Position, LowerBound, UpperBound, Rest...> : std::integral_constant<int, NOT_FOUND> {};

template <int Key, template <int, int> class Compare, int Position, int LowerBound, int UpperBound, int... Rest>
struct B4<false, Key, Compare, Position, LowerBound, UpperBound, Rest...> :
	std::integral_constant<int, B0<Key, Compare, Position + 1, UpperBound, Rest...>::value> {};

template <int X, int Y>
struct Less : std::conditional<(X < Y), std::true_type, std::false_type>::type {};

template <int Key, int... Rest>
using BinarySearch = B0<Key, Less, 0, sizeof...(Rest) - 1, Rest...>;

template <int Key, template <int, int> class Compare, int... Rest>
using BinarySearchCustomCompare = B0<Key, Compare, 0, sizeof...(Rest) - 1, Rest...>;

// Testing ------------------------------------------------------
template <int X, int Y>
struct Greater : std::conditional<(X > Y), std::true_type, std::false_type>::type {};

int main() {
	std::cout << BinarySearch<65,  1,5,7,8,11,12,18,25,32,65,111,150>::value << std::endl;  // 9
	std::cout << BinarySearchCustomCompare<65, Greater, 200,195,120,111,98,76,65,45,32,25,10,8,3,2>::value << std::endl;  // 6
}

[philipjfry]

The algorithmic complexity of binary search is O(log n), and of linear search is O(n), so except in corner case when n == 1 and n==2, binary search will be faster than linear search.

In your code too, your binary search will remain faster than the linear search equivalent. Because, it will result in creation of fewer templates. Thats my impression, unless the compiler uses some heuristic or optimization to turn a linear search template into binary search template, which is always possible, but unlikely imo.

[prestokeys]

But what about instantiation of the constexpr array[] = {Rest...} ? That takes up time too, right? So there are fewer steps, but each step requires that type instantiation. And also the look-up array[position], though that is O(1), it still takes up time. These are what's confusing me.

Here's a linear search, by the way. But I don't know how to compare the two's compile time performance.

#include <iostream>

const int NOT_FOUND = -1;
template <int, int, int...> struct LinearSearchHelper;

template <int N, int Key, int... Rest>
struct LinearSearchHelper<N, Key, Key, Rest...> : std::integral_constant<int, N> {};

template <int N, int Key, int First, int... Rest>
struct LinearSearchHelper<N, Key, First, Rest...> : LinearSearchHelper<N+1, Key, Rest...> {};

template <int N, int Key>
struct LinearSearchHelper<N, Key> : std::integral_constant<int, NOT_FOUND> {};

template <int Key, int... Rest>
using LinearSearch = LinearSearchHelper<0, Key, Rest...>;

int main() {
	std::cout << LinearSearch<65,  1,5,7,8,11,12,18,25,32,65,111,150>::value << std::endl;
}  // 9 

[prestokeys]

Another question I have is suppose I want to write a meta binary search with types instead of int (with, for example, a comparator that compares according to type size). Do I have to rewrite all of the above but replace int with typename? How to write this just once to cover int, typenames, std::size_t, etc...?

Also, you may have noticed that my code has a mix of std::conditional usage and true/false partial specialization. I couldn't think of how to use std::conditional throughout because of the cyclic dependency of the structs (B0 on B1, B1 on B2, B2 on B3 and B4, B3 and B4 on B0).