Overload/SFINAE misses are hard to detect

[AntoinePrv]

When, by mistake, one overload is not selected, the code usually falls back to common via inheritance.
Tests are silently passing but the behavior is not what is intended.

xsimd/include/xsimd/types/xsimd_common_arch.hpp

Line 27 in c3a8d37

struct common

One recent example is in #1266

Possible solutions:

• Have some mode where (with a macro or something similar) one can disable all common fallbacks (or print a compile time warning).
  This enables power users to have a first diagnosis of their xsimd code without diving in assembly.
• HARD: Test for specific instructions in compile code.

[AntoinePrv]

I came up with a more generic idea to extend the macro solution above. The idea is to trace "provenance" of the path of batch through xsimd.

There are many way in which this could be done: compile or run time, only in tests activated by a macros, using modern C++ versions behind a macro etc.

One way is to modify batch like

template<typename T, typename A, typename P = User /* Provenance, unused outside of testing */>
class batch;

With all implicit conversions from batch<T, A, P1> to batch<T, A, P2> so that the current syntax still holds. Provenance could be a tag type, a tuple of tag types, or could be gated behind C++20 and us an NTTP std::array` of enums.

Then, in common, all functions would return batch<T, A, append_t<P, provenance::common>>. Other parts of the code that make no trivial dispatch could also append other things.

Finally in tests, we should be able to make assertions

auto x = xsimd::bitwise_rshift(a, b);
static_assert(xsimd::provenance_never_comon(x));

This could also be done at runtime, by adding an std::vector attribute (behind a macro).

To make this not intrusive, we would derive utilities so that assertions, appends etc. disappear without needing to wrap them in #ifdef every time. Also provide default so that we can start small (say only common) and not have to change the whole codebase.

[AntoinePrv]

Taking this opportunity to add another topic relevant to using overloads: forward declarations.

Today it is hard to reuse other functions (say neg, all...) inside the kernel because they may not be declared above.
It is even harder to know if the function should be used in a higher architecture (fictive example a function foo with require_arch<sse42> picks the sse2 implementation as the best candidate, itself needs to call bar, passes its input requires_arch to it, so even if foo is in sse2 it can call a better bar from sse42).

The obvious solution is forward declaration, but with all the SFINAE and overloads, it would be tedious to maintain.
In C++17 we should move to having simpler function signatures and use constexpr if.

[serge-sans-paille]

I've also been thinking of this, and I *think* we can also write a compiler-based check that checks, for each API-level call, if we end up calling common or specialized code. I'll try to write a prototype to illustrate the idea.

[AntoinePrv]

Actually I there is a much simpler solution when using C++17: leverage if constexpr for both the type and the arch dispatch (within a family). There could be only one implementation for say neg, with all requires_arch mechanisms gone:

template<typename T, typename A>
auto neg(batch<T, A>) {
    if constexpr(supports_v<sse4_2>) {
        if constexpr(std::is_same_v<T, float>) {
            // specific implementation
            return ...;
        } else if constexpr(std::is_signed_integral_v<T>) {
            // specific implementation
            return ...;
        }
    }
    if constexpr(supports_v<ssse3>) {
         if constexpr(std::is_signed_integral_v<T> && sizeof(T) <) {
            // specific implementation
            return ...;
        }
    }
    // common implementation
    return ...;
}

That way no need for provenance checks or looking at multiple files in parallel. If you are working on a specific function for the SSE family, the whole implementation is in front of you. Much easier for user to predict what happens. No need for provenance checks etc.

The downside might be long if chains. I'd argue that a long if chain at the top of the function is not worse than a long list of overloads (and slightly less code), and that nothing prevents this function to split some part into a detail namespace with very explicit names.

[DiamonDinoia]

I would keep the current requires_arch for now. When we move to c++20 we can use concepts. This c++17 transition requires a rewrite no? Do you think two rewrites c++17 and c++20 are worth the effort?

[AntoinePrv]

I think in this case if constexpr would be a better approach even in C++20 (which may be farther down the road). IMHO concepts are very similar to SFINAE and would suffer the same downsides when the selection of the function is implicit.

With if constexpr we can explicitly control the flow at every level of detail. For instance if you know that a given function should cover all types in sse42, you can add an explicit return at the end of that if constexpr(supports_v<sse4_2>) block and get a compiler error if you did not handle all types (instead of a silent common fallback).

For functions that are implemented in multiple steps, it's also simpler so share one or two steps/alias without exposing one-line functions in the global scope.

Last but not least, when I look at a function implementation (e.g. for sse4.2), I personally think it is simpler, as both a developer and a user, to see at once all other instructions in this family that it would end up using.

Note: Of course we should not change all the code base at once. We would change a few functions in a backward compatible way to see how it compares before we commit to anything.

[DiamonDinoia]

I wonder how this will interact with #1186.

[serge-sans-paille]

I trend to like the C++17 approach, but maybe only for "instruction set": sse instruction set, avx instruction set, neon instruction setc etc. Each instruction have extensions (or none!) which would be handled in a single file, as proposed by @AntoinePrv . That way the fallbacks are clear, and we still keep the per instruction set dispatch (I don't need to see the neon implementation when I build the sse one), but no longer rely on the extension dispatch.

This has to interact with #1186, I don't want to do two rewrite consecutively. But it turns out it interacts very gracefully: the SSE instruction set has the following extensions: sse2, ssse3, sse4.1, sse4.2... and avx, avx2, avx512 as they indeed provide extensions to SSE.

This instruction set model does change the way we represent architectures, but I like this idea as it also captures fma variants. And the wording looks quite clear to me. From an implementation point of view, we could write sse<sse2>, sse<avx>, sse<avx512f> etc, keep the inheritance relationship and use std::is_base_of to model the extension hierarchy. And all this is compatible with if constexpr cascade.

Does that look good to you?

[JohanMabille]

I like this idea, and we could process in two phases:

• first replaces all the architectures with the new design (which is more or less a mechanical task)
• start to refactor the functions one by one (we could even parallelize these tasks).

[AntoinePrv]

Yes, regarding #1186 I was also starting to think we should treat 128 bits versions of AVX2 and AVX512 as if they were just some follow-up to sse4.2 in the same familly.

[DiamonDinoia]

After some thought I think the if constexpr solution might be the best since makes things explicit and visible while concepts will be implicit like SFINAE.

We can do things like:

template<typename T>                                                                                                                                            
struct always_false : std::false_type {};                                                                                                                       
                                                                                                                                                                
template<typename T, typename A>                                                                                                                                
auto neg(batch<T, A> x) {                                                                                                                                       
    if constexpr (std::is_base_of_v<sse_family, A>) {                                                                                                           
        // entire SSE family (sse2 through 128-bit avx512) in one block                                                                                         
        if constexpr (std::is_base_of_v<sse4_2, A>)  { return /* ... */; }                                                                                      
        else if constexpr (std::is_base_of_v<sse2, A>) { return /* ... */; }                                                                                    
    }                                                                                                                                                           
    else if constexpr (std::is_base_of_v<neon_family, A>) {                                                                                                     
        // entire NEON family                                                                                                                                   
    }                                                 
    else {                                                                                                                                                      
        static_assert(always_false<A>::value, "neg: unhandled architecture family");
    }
}

You all convinced me.

[AntoinePrv]

@DiamonDinoia I think the consensus was to leave out if constexpr for family detection neon/sse/avx... (the outermost if in you example).
There is little need to see e.g. both neon and sse at once, and the room for error is low since the header inclusion is gated by incompatible macros / distinct inheritance chains.