Montag, 27. März 2017

The alias flaw - why kvasir::mpl is faster part 6 of n

In several previous posts I have mentioned that alias based metaprogramming is not quite as easy as it may seem and although most of the code shown so far would work as described on a few occasions I mentioned that steps would need to be taken to prevent the alias flaw. This is the post where we talk all about it.

The alias flaw occurs when an alias who's parameters contains a pack calls an alias who's parameters either do not contain a pack or has a larger number of fixed parameters than the calling alias:

in the case where Ts is a pack containing one argument this code would work, in all other cases it wouldn't. How to report errors on this and how well to analyze whether this is an error or not is a gray zone where different compilers will show different behavior. Since aliases are supposed to be transparent it is not feasible (or more specifically cheap) to analyze the full potentially long and complex chain of alias calls from every call site in the program in order to ensure that they don't break at some potentially deeply nested point because the packs have too many or too few parameters.

Our goal of using as many aliases a possible in order to speed up our TMP requires us to find a work around for this problem. My initial attempt was to track the number of parameters and add many different versions of each algorithms depending on that, as is usually the case when fighting exponential combinations with brute force it was quickly clear that it was a failure. Making a good library usually means being generic and being generic in this sense is to allow any number of parameters.

The work around which I came up with was to make the selection of the next alias to call depend on the number of arguments thus forcing the compiler to delay evaluation untill it actually knows the number of Ts and can then deduce that the next call is ok.

In the above example one can see that we are testing for Ts being larger than 10,000,000 so the condition will essentially always evaluate to true, therefore it is conceivable that it evaluates true and we still get an error.

This error is actually better than the error we would have gotten had we tested for Ts having size of 1 which in this case would be that void does not have a nested template. It is also important that we did not have to test for the exact number of Ts which we require because in a generic context one might not know how many are suitable. The goal is simply to delay evaluation so that the compiler must wait until it has a pack of Ts before it does its evaluation.

Although this pattern solves most of your problems we still have difficulties when we have a template<template...> class F, as in a template template parameter which may be an alias, and a pack which may not fit. In that case we can't use conditional because one cannot return a template template parameter. This can be easily fixed however by making a modified version of conditional called dcall (dependent call) who's nested alias takes a template template parameter F and a variadic pack and calls F with the pack in the true specialization of the enclosing struct and does nothing otherwise.

With these two examples one can tame the alias flaw for all relevant compilers and although it is a nuisance to the library implementer none of this complexity leaks into the public interface allowing the user to remain blissfully oblivious to how sausage in made.