Reimplement the switchCases() hybrid implementation using array lookup

Summary

Reimplement the function Hybrid::switchCases(Range r,Index i,Function f) that calls the function f with an integral-constant that has the same value as the (possibly) runtime index i if the range is a static-range and with a runtime index if it is a dynamic-range.

Details

Instead of tail-recursion as in the old implementation it is implemented as kind-of an automatically generated lookup-table and thus does not need a recursion-break condition.

It is also hybrid in two senses:

1. if the range is static, call the function with an integral constant, otherwise with a runtime index
2. if the index is a runtime index, perform a lookup to call the function with the corresponding integral constant, otherwise if it is already an integral constant, pass it directly to the function.

Examples

Zero-based vectors that can be indexed by integral constants only:

auto t = Dune::makeTupleVector(std::string("1"), 2, 3.0f);
Hybrid::switchCases<decltype(t)::size()>(1, [&t](auto ii) { t[ii] = 20; });

Using different ranges with different access:

auto t = Dune::makeTupleVector(std::string("1"), 2, 3.0f);
auto v = std::vector<double>{1.0, 2.0, 3.0};
// StaticIntegralRange
Hybrid::switchCases(range(Hybrid::size(t)), 1, [&t](auto ii) { t[ii] = 20; });
// IntegralRange
Hybrid::switchCases(range(Hybrid::size(v)), 1, [&v](auto ii) { t[ii] = 20.0; });

Accessing a tuple by lookup or by direct index access:

auto t = Dune::makeTupleVector(std::string("1"), 2, 3.0f);
auto index_seq = std::make_index_sequence<decltype(t)::size()>{};
// search for index 1 in index sequence
Hybrid::switchCases(index_seq, 1, [&t](auto ii) { t[ii] = 20; });
// call function directly
Hybrid::switchCases(index_seq, index_constant<1>{}, [&t](auto ii) { t[ii] = 20; });

Notes

Since all the code in the dune core/staging modules that use Hybrid::switchCases essentially are restricted to simple index lookup, all can be replaced by the new implementation. The advantage is that we do not need to provide a fallback implementation in case the index is out of range. This is necessary for the old switchCases implementation in case a value should be returned.

added 1 commit

• d65c3726 - replace lambda by free function

Compare with previous version

added 1 commit

• 1d7035a5 - better test for withIndex index out of range

Compare with previous version

changed the description

added 1 commit

• 4210c78b - non-zero-based index sequences in withIndex

Compare with previous version

@carsten.graeser Do you think this utility function would be useful, especially in dune-functions, for implementing multi-type container algorithms and composite bases? In a first lookup, I could at least remove all the dummyElse functors. This makes the code already more readable. When just compiling directly swichCases and withIndex, I could measure a performance improvement (in the compile-time) of about about 40%. This is probably due to the reduced number of template instantiations.

@simon.praetorius I like the approach, but the MR does two things at once. First, it reimplements switchCase() in a way that is nicer and in some parts more complete, but leaves out some of its functionality. Second, it changes the name of the utility. I don't want to have to functions doing almost the same, being mostly part exchangeable, but having different names. Also it's not correct,that you need an else branch. AAll your examples should work with the current switchCase(). What does not work, in the current version but in yours) is to return a value without having an else branch.

I propose, to improve the implementation of switchCase using your approach and not to keep the old one conccurently. Later we can decide if we want to rename it and maybe deprecate the old name.

BTW: Since this is the work horse of Std::variant I also tested other implementations. One can often read that, if the cases are simply 0,...,n, this is best implemented using a classical switch ... case ... statement because compilers are tuned to optimize this (e.g. using bisection). However, my measurements did not reveal any difference to the current solution. Also you must hardwire an upper bound.

Maybe one should also benchmark the new implementation. Here the direct access and dispatch of a function pointer competes with inlining at the price of several (maybe log(n)) comparisons. I've no idea which is better. In fact I don't want to bother and think the compiler vendor should know best, i.e. this is IMHO missing in the STL.

For completeness: That's the patch I tried.

namespace Impl {

  template<class F1, class F2, class... Args>
  decltype(auto) callIf(Dune::Std::bool_constant<true>, F1&& f1, F2&&, Args&&... args)
  {
    return f1(std::forward<Args>(args)...);
  }

  template<class F1, class F2, class... Args>
  decltype(auto) callIf(Dune::Std::bool_constant<false>, F1&&, F2&& f2, Args&&... args)
  {
    return f2(std::forward<Args>(args)...);
  }

  template<bool condition, class F1, class F2, class... Args>
  decltype(auto) callIf(F1&& f1, F2&& f2, Args&&... args)
  {
    return callIf(Dune::Std::bool_constant<condition>{}, f1, f2, std::forward<Args>(args)...);
  }

}

template<std::size_t caseCount, class Branches, class ElseBranch>
constexpr decltype(auto) switchCases(const Dune::index_constant<caseCount>&, const std::size_t& value, Branches&& branches, ElseBranch&& elseBranch)
{
  auto elseBranchIgnoreArgs = [&](auto&&...) -> decltype(auto) { return elseBranch(); };
  switch(value) {
    case  0: return Impl::callIf<( 0<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_0 );
    case  1: return Impl::callIf<( 1<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_1 );
    case  2: return Impl::callIf<( 2<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_2 );
    case  3: return Impl::callIf<( 3<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_3 );
    case  4: return Impl::callIf<( 4<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_4 );
    case  5: return Impl::callIf<( 5<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_5 );
    case  6: return Impl::callIf<( 6<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_6 );
    case  7: return Impl::callIf<( 7<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_7 );
    case  8: return Impl::callIf<( 8<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_8 );
    case  9: return Impl::callIf<( 9<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_9 );
    case 10: return Impl::callIf<(10<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_10);
    case 11: return Impl::callIf<(11<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_11);
    case 12: return Impl::callIf<(12<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_12);
    case 13: return Impl::callIf<(13<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_13);
    case 14: return Impl::callIf<(14<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_14);
    case 15: return Impl::callIf<(15<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_15);
    case 16: return Impl::callIf<(16<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_16);
    case 17: return Impl::callIf<(17<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_17);
    case 18: return Impl::callIf<(18<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_18);
    case 19: return Impl::callIf<(19<caseCount)>(branches, elseBranchIgnoreArgs, Dune::Indices::_19);
  }
  return elseBranch();
}

I just looked this up: In fact boost::mp11::mp_with_index also uses the switch ... case ... implementation. But not using the callIf<(i<caseCount)> ... trick, it has to specialize for n up to 16.

Yes, I also had a look at the implementation in boost. It is a bit more verbose than writing the array function-pointer lookup. But I remember that some years ago (maybe just 1 year), I had also re-implemented switchCases with a specialization on the range size and then classical switch-case statements and it was fast only in a very few cases, and only in one compiler not in the other. So, no direct experience that favours switch-case over recursive implementation.

The withIndex name was chosen, because I didn't want to directly replace switchCases. The latter is more general. But it could be discussed to remove one implementation. I searched for switchCases in the core and staging modules and there it was used with integer ranges only. So, everything could be replaced with the withIndex function and thus a renaming to switchCases would be fine.

changed the description

As far as I can see, switchCase does two thinks, that your implementation does not do: Supporting other ranges and an else branch (as an alternative to undefined behaviour). It seems to me that both could easily be implemented in your approach as well.

added 3 commits

• b7aa6b37 - renamed withIndex back to switchCases
• 276b7fbe - hybridutilities test and variant implementation adapted to new switchCases implementation
• 496deb88 - better error diagnostics in switchCases

Compare with previous version

I've tried to incorporate my changes into the switchCases implementation. This implementation got a bit more complex due to the elseBranch case that needs to be handled for all possible combinations of range and index type.

added 1 commit

• 4a63641a - corrected anyOf for IntegralRange

Compare with previous version

added 1 commit

• 75f0d4be - proper static_assert with message

Compare with previous version

changed title from Implement hybrid utility withIndex() as alternative to switchCases() to Reimplement the switchCases() hybrid implementation using array lookup

changed the description

added 733 commits

• 75f0d4be...eaa81ae8 - 732 commits from branch core:master
• 86877183 - Reimplement hybrid utility switchCases() using lookup-table

Compare with previous version

I have cleaned up the implementation. The old name withIndex is removed and replaced by switchCases. All the old "features" are implemented. @carsten.graeser Do you think it is worth merging, or do you want to try out first in other code contexts to see the possible error messages if "out-of-range" index or wrong argument or non-range passed?