Proposal for two new traits: `std::greedy_conjunction` and `std::greedy_disjunction `

[mateusz...@gmail.com]

Introduction

C++17 introduced besides the others two new structures in `<type_traits>` header: `std::conjuction` and `std::disjunction`. They are very useful in metaprogramming, but standard has in some way forced their implementation. 

In p0013r1 we can read:

The BaseCharacteristic of a specialization conjunction<B1, ..., BN> is the first type Bi in the list true_type, B1, ..., BN for which Bi::value == false, or if every Bi::value != false the BaseCharacteristic is BN. [Note: This means a specialization of conjunction does not necessarily have a BaseCharacteristic of either true_type or false_type. — end note]

Similar in the disjunction: 

The BaseCharacteristic of a specialization disjunction<B1, ..., BN> is the first type Bi in the list false_type, B1, ..., BN for which Bi::value != false, or if every Bi::value == false the BaseCharacteristic is BN. [Note: This means a specialization of disjunction does not necessarily have a BaseCharacteristic of either true_type or false_type. — end note]

I'd like to propose a two new structures in `<type_traits>`: `std::greedy_conjunction` and `std::greedy_disjunction`. Their results would very similar to the ones from `std::conjunciton` and `std::disjunction`, but their specification would give more flexibility to the standard library creators.

Motivation and Scope

With `std::conjuction` and `std::disjunction` restrictions in the standard, library creators are forced to make them in such (or similar) way:

template<class...> struct conjunction : std::true_type { };
template<class B1> struct conjunction<B1> : B1 { };
template<class B1, class... Bn>
struct conjunction<B1, Bn...>
    : std::conditional_t<bool(B1::value), conjunction<Bn...>, B1> {};
   
template<class...> struct disjunction : std::false_type { };
template<class B1> struct disjunction<B1> : B1 { };
template<class B1, class... Bn>
struct disjunction<B1, Bn...>
    : std::conditional_t<bool(B1::value), B1, disjunction<Bn...>>  { };

    

There are strong grounds to keep these implementations, e.g. short-circuiting, getting information on what type, recursion stopped etc. Although, because of these restrictions compilation time suffers in some cases.

Why new, very similar traits?

Abstract

During my pull request to folly (https://github.com/facebook/folly/pull/643) Jay Feldblum posted there a small benchmark script: https://gist.github.com/yfeldblum/ffae5374aaaa11b03f08919d25b1555b (big credits for poking my brain with the idea). I was surprised that, let's say, the naive implementation compiles faster that the standard one. 

I decided to benchmark this idea deeper:

-problem was to find in a types sequence if there is a type which T::value is equal to 0

-for every benchmark sequence has 1024 types inside

-tested sequences with two kinds of types: light and heavy to instantiate

-tested best and worse cases

-tested two new implementations: fold expression and bool-pack

-core benchmark was to measure the compilation time with given compiler (clang++-4.0/g++-6), case (best/worse), type (light/heavy), implementation (proposed/standard). Every compilation case was ran 500 times and average result was calculated.

Whole benchmarks code you can find in the gh repo: https://github.com/stryku/boolpack_vs_recursion

And here are the results (sorry for not posting it here, but table was too big and it was formatted in unreadable way):

https://raw.githubusercontent.com/stryku/boolpack_vs_recursion/master/output

As you can see, standard implementation is way better when we deal with the best case. It can compile 80x(!) faster than the proposed ones. Problem starts when the worse cases occurs. 

Standard library creators would be able to implement `greedy_conjunction` and `greedy_disjunction` in a way that they compiles up to around 6x faster than the standard one. Users would be able choose implementation which will suit best, based on what cases they are mostly expecting.

Specification

Since it's a pre-proposal I don't want to post fully described specification. I'm thinking about it in this way:

`std::greedy_conjunction` would be an alias or would derive from a type, which has a constexpr member `value` which can be converted to bool and is equal to:

-false if any bool(Tn::value0 == false

-true otherwise

`std::greedy_disjunction` would be an alias or would derive from a type, which has a constexpr member `value` which can be converted to bool and is equal to:

-false if all bool(Tn::value) == false

-true otherwise

Example implementations

bool-pack (this one seems to compile faster than fold expression):

template <bool... Bn>
struct __bools {};

template <typename... Tn>
struct greedy_disjunction: std::negation<std::is_same<__bools<bool(Tn::value)...>, __bools<(Tn::value && false)...>>> {};

template <typename... Tn>
struct greedy_conjunction: std::is_same<__bools<bool(Tn::value)...>, __bools<(Tn::value || true)...>> {};

fold expression:

template <typename... Tn>
struct greedy_disjunction : std::bool_constant<(false || ... || bool(Tn::value))> {};

template <typename... Tn>
struct greedy_conjunction : std::bool_constant<(true && ... && bool(Tn::value))> {};

Wordings:

There is couple of questions

I asked them to myself a lot, during this pre-proposal.

-Is it in the C++ standard scope to care about how things will be implemented in standard library, even if the implementations will be not efficient on compile-time level?

-Should the standard be changed because of standard library compilation time?

And here's my conclusion (and reason why I'm writing this post).

C++ standard purpose is not to specify a theoretical language. It's created to be used by a lot of people in the real world. Giving a choice to user between implementations which differs in a compile-time efficiency is same thing as to give a choice between containers e.g. `std::vector` and `std::list`. In some cases one implementation is better, in others the other one.

And of course the name

I thought about `strict_*` (like it's in Facebook/folly lib) instead of `greedy_*`, but I'm sure that if this proposal is a thing community will propose better names.

What do you think?

Mateusz (stryku) Janek

[Michał Dominiak]

You can already write your "greedy" things by just... deriving from bool_constant directly (exactly like in your last snippet). You couldn't do what the two traits are doing directly, and that's I believe is the only justification of their existence. Your thing doesn't seem to be very useful.

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposal...@isocpp.org.
To post to this group, send email to std-pr...@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/a79ce0b4-ca2d-4c37-b49e-cb707689a0e2%40isocpp.org.

[mateusz...@gmail.com]

These traits are as useful as current conjunction and disjunction are - they compute the same result, but additionally give user a choice about compilation time and IMO that's a useful addition.

[mateusz...@gmail.com]

Hello again,

I am wondering if lack of response in this thread means that my idea has been already rejected? If yes then could anyone explain why?

I might be wrong but this is why I'm not convicted by the current arguments:

>You can already write your "greedy" things by just... deriving from bool_constant directly (exactly like in your last snippet).

I assume that your point is that it's easy to implement by the user on his own. I'm not convicted because there is a lot of stuff in the standard library that are easy to implement, e.g. std::negation

>Your thing doesn't seem to be very useful.

Not sure if I follow. If they are not useful => std::conjunction and disjunction are not as well (:

As you can see they compute almost same result as std::conjunction and disjunction, plus they give a choice to the user about the compilation time.

The only thing that concerns me here is if it's in the standard library scope to care about the compilation time.

Thanks in advance,

Mateusz Janek

[Michał Dominiak]

What I meant is that you don't really need a specific trait.

You can't obtain the result of std::{con,dis}junction directly, without using a layer of abstraction for the laziness.

You can, however, obtain the result of the greedy operation directly - by just &&ing or ||ing the values of the traits you'd pass to this trait. Evaluation in templates is already eager that way, and it's no problem to && or || them together even in generic contexts, especially since we have fold expressions now.

The reason for the traits that we have is laziness. If you don't need laziness, you don't need the trait.

To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/81a6a1fa-a331-483e-8f4d-4184c661b106%40isocpp.org.

[shmitti...@gmail.com]

Got it. Thank you!

[mateusz...@gmail.com]

Sorry, didn't realize that I was on wrong account.