search

microsoft / STL

MSVC's implementation of the C++ Standard Library.
Other
10.13k stars 1.5k forks source link

STL: Finish replacing tag dispatch with `if constexpr` #189

Open StephanTLavavej opened 5 years ago

StephanTLavavej commented 5 years ago

Tag dispatch is the STL's original metaprogramming technique: overload a helper function on a tag struct (e.g. input_iterator_tag versus forward_iterator_tag, or true_type versus false_type) and then call it with a tag object to select the appropriate overload. This has several downsides, though - it is somewhat verbose, it interferes with code organization, and it results in actual function calls in debug mode. (This is slower, more work to step through when debugging, and bloats object files.) C++17 if constexpr supersedes tag dispatch in almost every situation (see note below) and we're using it in new C++17-and-later code. We can use it in C++14 mode too (compilers support it unconditionally with a warning that we've suppressed).

We should finish overhauling the STL to use if constexpr.

Note: Tag dispatch works with delegating constructors, whereas if constexpr works only in function bodies. subrange's delegating constructors are a rare example of necessary tag dispatch: https://github.com/microsoft/STL/blob/f099e9c9f91187376e85385b135ac62ef933e54f/stl/inc/xutility#L3345-L3356

StephanTLavavej commented 4 years ago

In #491, I noticed that C++17 default_searcher is using tag dispatch when it could use if constexpr: https://github.com/microsoft/STL/blob/ff947563da6511270d8b7292e162f8549df8267f/stl/inc/functional#L1662-L1664

CaseyCarter commented 3 years ago

1433 brought _Lex_compare_memcmp_classify to our attention:

https://github.com/microsoft/STL/blob/60d9ed7ef4dcb7c3ec2d502bdb4b50123ae1c74b/stl/inc/xutility#L5303-L5319

This overload set could be if constexpr-ed to good effect, doubly so after #1433 adds more overloads to the set.

AlexGuteniev commented 3 years ago

I don't think it deserves separate issue, rather an expansion of this issue scope.

Some specializations can be replaced with if constexpr.

Compare internal _Invoke_ret dispached by SFINAE-selected partial specialization: https://github.com/microsoft/STL/blob/88332706f49d3297b200b5605ef174fc47d38d1a/stl/inc/functional#L658-L685

And standard invoke_r dispatched by if constexpr: https://github.com/microsoft/STL/blob/88332706f49d3297b200b5605ef174fc47d38d1a/stl/inc/functional#L33-L42

AlexGuteniev commented 2 years ago

https://github.com/microsoft/STL/issues/189#issuecomment-631298439:

In #491, I noticed that C++17 default_searcher is using tag dispatch when it could use if constexpr:

https://github.com/microsoft/STL/blob/ff947563da6511270d8b7292e162f8549df8267f/stl/inc/functional#L1662-L1664

This was addressed by #2219

https://github.com/microsoft/STL/issues/189#issuecomment-738499686:

1433 brought _Lex_compare_memcmp_classify to our attention:

https://github.com/microsoft/STL/blob/60d9ed7ef4dcb7c3ec2d502bdb4b50123ae1c74b/stl/inc/xutility#L5303-L5319

This overload set could be if constexpr-ed to good effect, doubly so after #1433 adds more overloads to the set.

This was addressed by #2158

AlexGuteniev commented 2 years ago

There's _Seed in <random>:

https://github.com/microsoft/STL/blob/86e22c3cf3238fa9aca10e47665f4c2b88b27206/stl/inc/random#L693-L702

StephanTLavavej commented 2 years ago

2479 updated basic_string_view and basic_string's find_first_of, with the remaining functions being:

2660 is updating these functions.

StephanTLavavej commented 2 years ago

Dispatching on iterator strength:

AlexGuteniev commented 8 months ago

There are candidates in <format> but not sure if it worth to untag dispatch them.

https://github.com/microsoft/STL/blob/bd3d740ae5de7255c720b8133c5d23aa131e0760/stl/inc/format#L1721-L1743