2

When recursing over a parameter pack, given the choice, should I prefer to recurse via inheritance, or via a member field (composition)? Is this a cut-and-dried matter? What are the trade-offs?

One thing that I'm wondering, for example, is whether the composition-based form is generally considered to have better compilation speed, memory usage, or error reporting.

To illustrate, the following is an example of short-circuit or_ (disjunction) inspired by Jonathan Wakely's answer here.

Inheritance-based:

#include <type_traits>

// disjunction

template<typename... Conds>
struct or_ : std::false_type {};

template<typename Cond, typename... Conds>
struct or_<Cond, Conds...> 
  : std::conditional<Cond::value, std::true_type, or_<Conds...>>::type
{};

static_assert(or_<std::true_type, std::true_type, std::true_type>::value,"");
static_assert(or_<std::false_type, std::false_type, std::true_type>::value,"");
static_assert(or_<std::false_type, std::false_type, std::false_type>::value == false,"");

I understand that this version has the feature that or_<Ts...> will inherit from std::integral_constant. Please assume for the sake of my question that I don't care about whether or_ inherits from an integral_constant.

Composition-based:

template<typename... Conds>
struct or_ {
    static constexpr bool value = false;
};

template<typename Cond, typename... Conds>
struct or_<Cond, Conds...> {
    static constexpr bool value = std::conditional<Cond::value, std::true_type, or_<Conds...>>::type::value;
};

This form seems intuitively better to me, because the value is always located in the type itself, not in some superclass, but I'm not sure whether this is generally considered preferable.

P.S. I know that in C++17 I could often use fold expressions. But I'm aiming for C++11 compatibility.

Community
  • 1
  • 1
Ross Bencina
  • 3,822
  • 1
  • 19
  • 33
  • It's a matter of taste, and personal preference. The end result is the same, and neither approach has any particular advantages over the other. – Sam Varshavchik Dec 23 '16 at 12:09
  • This is mostly opinion-based. The inheritance you instantly ignore has important benefits (simplifying tag dispatch, plus the several utilities provided by `integral_constant`). I suppose one could argue that someone might forget the `static` in the second form, especially if you write `const` rather than `constexpr`, which can lead to puzzling substitution failures in dependent contexts. – T.C. Dec 23 '16 at 12:15
  • In C++11 one can still use the trick that anticipates somehow fold expressions as a third approach. In C++14 you could do it using template variables and it's another different approach. Why are you interested only in the two in the question? – skypjack Dec 23 '16 at 12:50
  • @skypjack: could you point me to examples of the two other methods that you mentioned? I'm not sure whether I understand what you mean. – Ross Bencina Dec 23 '16 at 13:22
  • 1
    @RossBencina [Here](https://godbolt.org/g/FP0cWk) is an example of one of them. – skypjack Dec 23 '16 at 13:38
  • @skypjack: thanks. as for why I'm interested: the first method I listed was the cleanest/clearest/briefest that I'd seen, and the second I thought might be better/more efficient. others i'd seen were verbose or more difficult to understand. – Ross Bencina Dec 23 '16 at 13:45

5 Answers5

3

If we really don't care about short-circuiting, then there's always bool_pack:

template<bool...> struct bool_pack;

template<class... Ts>
using and_ = typename std::is_same<bool_pack<true, Ts::value...>,
                                   bool_pack<Ts::value..., true>>::type;

template<class T>
using not_ = std::integral_constant<bool, !T::value>;

template<class... Ts>
using or_ = not_<std::is_same<bool_pack<false, Ts::value...>, 
                              bool_pack<Ts::value..., false>>>; 
      // or not_<and_<not_<Ts>...>>
T.C.
  • 133,968
  • 17
  • 288
  • 421
2

Both forms would give similar effect. If you want to make the code better instead of choosing between those two you could try to avoid recursion... Your or_ code could be successfully replaced with the following:

#include <utility>
#include <type_traits>
#include <iostream>

template <std::size_t, class T>
struct indexed_condition;

template <std::size_t I>
struct indexed_condition<I, std::false_type> { };

template <class...>
struct voider {
    using type = void;
};

template <class... Conds>
struct helper: std::true_type {
};

template <std::size_t... Is, class... Conds>
struct helper<typename voider<decltype(indexed_condition<Is, Conds>())...>::type, std::index_sequence<Is...>, Conds...>: std::false_type {
};

template <class... Conds>
struct my_or: helper<void, std::make_index_sequence<sizeof...(Conds)>, Conds...> { };

int main() {
    std::cout << my_or<std::true_type, std::false_type, std::true_type>::value << std::endl;
    std::cout << my_or<std::false_type, std::false_type, std::false_type>::value << std::endl;
}

[live demo]

Output:

1
0

To be straight it won't affect run-time but the compilation-time efficiency.

One more thing - std::integer_sequence is c++14 construction, but can be implemented in c++11 as well see e.g. this implementation

W.F.
  • 13,888
  • 2
  • 34
  • 81
  • 1
    Virtual compile-time inheritance. Hah. – Yakk - Adam Nevraumont Dec 23 '16 at 13:05
  • Would you say that this is the preferred approach these days? Do you have any further pointers on why it compiles faster? – Ross Bencina Dec 23 '16 at 13:30
  • @RossBencina Well after Yakk's comment I started doubting it... if I find the way to do the same thing without virtual inheritance I'll edit my answer – W.F. Dec 23 '16 at 13:35
  • I'd still like to see benchmarks even for your new approach. I don't see the number of template instantiations being materially reduced by this; far from it. – T.C. Dec 23 '16 at 14:18
  • @T.C. Why do you think it shouldn't be efficient? I've successfully removed virtual inheritance... – W.F. Dec 23 '16 at 14:20
  • @T.C. But we reduced the number of parameters in existing instantiation... I believe it should be O(n*log n) (because of index_sequence), while with recursion it would be O(n^2), no? – W.F. Dec 23 '16 at 14:22
  • 1
    @t.c. recursive depth is massively reduced. And name length! As for virtual compile time inheritance, I find it funny not objectionable. – Yakk - Adam Nevraumont Dec 23 '16 at 14:37
  • @Yakk Less depth, but more breadth. Also loses short-circuiting (because I doubt that one usually uses this on `true_type`/`false_type` directly, so the potential cost of instantiating the template type arguments is also worth considering). Regardless, I'd like to see benchmarks for performance claims. – T.C. Dec 23 '16 at 14:41
  • @t.c. In the OP's case, it instantiates an `or` of length n, then n-1, then n-2, for a total length of O(n^2). That becomes a real pig. It does so recursively, which means it errors out around 1000 on most compilers. In C++14, some compilers use an intrinsic for index sequences, and others use a complex log-depth linear-total length generator. I would tweak this one to inherit from `true`/`false` instead of `T`, but I cannot imagine it being slower. – Yakk - Adam Nevraumont Dec 23 '16 at 15:00
  • @Yakk Sure, I can buy that (but even then it's interesting to look at how many template parameters are required to get actually a measurable improvement). But like I said, there's the cost of instantiating all the conditions, which is nonexistent when they are all `true_type`/`false_type` but in realistic cases may well be more costly (`is_constructible`, `is_convertible`, etc., which may trigger the instantiation of *even more stuff*). – T.C. Dec 23 '16 at 15:10
  • @T.C. I performed a very simple test (all true_type/all false_type) on gcc 6.1.1 and clang 3.6 for true_types to my surprise both implementation works similarly efficient, the noticeable boost is in case of false_types since passing circa 500 parameters... – W.F. Dec 23 '16 at 15:54
2

This is an attempt to make a slightly cleaner version of @W.F.'s answer.

template<std::size_t, class T, class=void>
struct detect_truthy : virtual std::false_type {};
template<std::size_t I, class T>
struct detect_truthy<I, T,
  typename std::enable_if<T::value>::type
> : virtual std::true_type {};

template<class...>struct pack {};

template<class Pack, class Is=void>
struct detect_truthies;
template<class...Ts>
struct detect_truthies<pack<Ts...>,void>:
  detect_truthies<pack<Ts...>, std::make_index_sequence<sizeof...(Ts)>>
{};
template<class...Ts, std::size_t...Is>
struct detect_truthies<pack<Ts...>,std::index_sequence<Is...>>:
  detect_truthy<Is, Ts>...
{};

std::true_type or_helper_f( std::true_type* );
std::false_type or_helper_f( ... );
std::false_type and_helper_f( std::false_type* );
std::true_type and_helper_f( ... );

template<class...Bools>
struct my_or:
  decltype( or_helper_f( (detect_truthies<pack<Bools...>>*)0 ) )
{};
template<class...Bools>
struct my_and:
  decltype( and_helper_f( (detect_truthies<pack<Bools...>>*)0 ) )
{};

live example.

It uses index_sequence and make_index_sequence, which is from C++14, but high quality C++11 versions can be used.

The point of this technique is that the only recursive/linear/binary template expansion occurs within index_sequence. Everywhere else we directly expand parameter packs.

As index_sequence can be written to be highly efficient at the cost of readability (for example, MSVC implements it as an intrinsic! Other compilers use a complex binary tree generator.), this focuses the high cost performance issues there.

In general, you want to isolate the spots where you do O(N^2) work at compile time. When you inherit linearly, you do O(N^2) work.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
1

There's a third option which is to use constexpr functions

static constexpr bool any_of(){
  return false;
}

template<class... T>
static constexpr bool any_of(bool b, T... rest){
  return b || any_of(rest...);
}


template<class... Cond>
using or_ = std::integral_constant<bool, any_of(Cond::value...)>;

int main(){
  static_assert(or_<std::true_type, std::true_type, std::true_type>::value,"");
  static_assert(or_<std::false_type, std::false_type, std::true_type>::value,"");
  static_assert(or_<std::false_type, std::false_type, std::false_type>::value == false,"");
}

The advantage of the inheritance method is that you can pass the _or class to any function that is overloaded with both a std::true_type and a std::false_type, which helps if you're playing with sfinae.

As far as compilation speed goes it's very hard to tell because it's completely compiler dependent (and the compiler guys are working on compilation speed for TMP so any good advice now might turn into bad advice without warning.

The main thing with compilation speed is to keep an eye on your algorithms. It's very hard to do conditional compilation in C++ 11/14 and compilers will evaluate both sides of a std::conditional. (They have to you can legally specialise std::conditional for one of the _or classes and the compiler can't prove you're a rational human being)

This means in both your cases the compiler will instantiate the or class for every partial list of cases. This probably isn't too bad, but sometimes you can suddenly turn an O(N) algorithm into an O(2^N) algorithm, which is when compilation times really start to hurt.

Tim
  • 693
  • 3
  • 11
  • See [comments to the question](https://godbolt.org/g/FP0cWk) for a shorter version. – skypjack Dec 23 '16 at 15:40
  • 1
    Note that the above code is already O(N^2) at compile time. `any_of` takes N arguments, then recurses taking N-1 arguments, etc. These sum to O(N^2). You can actually fix this with a binary tree based recursion, but it is messy. – Yakk - Adam Nevraumont Dec 23 '16 at 20:37
0

One more quite efficient in context of compilation time approach to or_:

#include <type_traits>
#include <utility>

template <class... Conds>
std::false_type or_impl(Conds... conds);
template <class... Conds>
std::true_type or_impl(...);

template <class, class T>
using typer = T;

template <class... Conds>
using or_ = decltype(or_impl<typer<Conds, std::false_type>...>(Conds{}...));

int main() {
    static_assert(or_<std::false_type, std::true_type, std::false_type>::value, "!");
    static_assert(!or_<std::false_type, std::false_type, std::false_type>::value, "!");
}

[live demo]

W.F.
  • 13,888
  • 2
  • 34
  • 81