SFINAE callability check, more algorithm categories, reducing allocations

Manu343726 commented 9 years ago

Stefan Löerwald sent me an email referencing some issues:

Hi Manuel,

I've come across your snail library and gave it a try. With gcc, I get compiler errors in the operator|(C&&, F). This is due to matches to this operator with non-callable F in some internal compiler headers.

To fix this, you may use SFINAE to check if F is actually a callable:

template <typename C, typename F>
using return_t = decltype(std::declval<F>()(std::declval<C>()));

template<typename C, typename F, typename = return_t<C, F>>
auto operator|(C&& container, F f)
{
    return std::move(f(std::forward<C>(container)));
}

Another note: Constructing a new container each time is a heavy operation which may be avoided in many circumstances. Did you think of a binary_mutable_inplace? I think there should be no issue with

template<>
struct algorithm_factory<snail::categories::binary_mutable_inplace>
{
    template<typename Algorithm>
    static auto make(Algorithm algorithm)
    {
        return [=](auto f)
        {
            return [=](auto&& container)
            {
                using std::begin;
                using std::end;
                using std::back_inserter;

                algorithm( begin(container), end(container),
                           begin(container), f);

                return std::move(container);
            };
        };
    }
};

and making

algorithm_category(std::transform, snail::categories::binary_mutable_inplace)

Of course this may not be directly applied to a filter!

For anything that supports erase, you may want to specialize the filter to. For reducing allocations I think (not 100% sure!) you can replace the return [=](const auto& container) by [=](auto&& container).

This reduces (in your example) the number of allocations from 10 to 4 (optimal would be one of course, but that's not possible with a generic back_inserter).

    template<>
    struct algorithm_factory<snail::categories::FILTER_STUFF>
    {
        template<typename Algorithm>
        static auto make(Algorithm algorithm)
        {
            return [=](auto f)
            {
                return [=](auto&& container)
                {
                    using std::begin;
                    using std::end;
                    auto new_end = algorithm( begin(container), end(container), begin(container), f);
                                        container.erase(new_end, end(container));
                    return std::move(container);
                };
            };
        }
    };

What do you think of these changes?

Best regards, Stefan

TL;DR

In brief, he points out some issues the library currently has:

The continuation does not check if the algorithm is applicable to the container: Even if this is a rare case, having a SFINAE check there is a good thing, making compilation-errors more clear than going down until the true application, through all the factories, lambdas, etc.
Besides that, I don't understand "With gcc, I get compiler errors in the operator|(C&&, F). This is due to matches to this operator with non-callable F in some internal compiler headers". The library is being tested on Travis CI with GCC compiler. Maybe he's using a previous version.
snail::categories::binary_mutable_inplace category to reduce unnecessary container allocations: Totally agree, adding more categories covering specific cases to improve performance is something I have to do. The current set of categories serves as a proof of concept, but it's too generic.
Using forwarding references in mutable algorithms to reduce allocations. I have to check this, I'm not sure too.

stefanloerwald commented 9 years ago

Regarding the "The continuation does not check if the algorithm is applicable to the container" issue:

The error using g++ is:

algorithm.hpp: In instantiation of ‘auto operator|(C&&, F) [with C = int; F = _MM_MANTISSA_NORM_ENUM]’: /usr/lib/gcc/x86_64-linux-gnu/4.9/include/avx512fintrin.h:8207:25: required from here algorithm.hpp:590:50: error: ‘f’ cannot be used as a function

This only applies for compiling with optimization (O1, O2, or O3)

Compiler information:

COLLECT_GCC=g++ COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.9/lto-wrapper Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu 4.9.1-16ubuntu6' --with-bugurl=file:///usr/share/doc/gcc-4.9/README.Bugs --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.9 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.9 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.9-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.9-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.9-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.9.1 (Ubuntu 4.9.1-16ubuntu6)

Manu343726 commented 9 years ago

Seems like we are overriding bitwise or by making the pipe operator an unconstrained template. I can add a is_function or is_callable as you suggested, but this is behavior correct? I'm not that sure. In theory function overloads are above templates in name lookup rules, so the correct bitwise operator should match first. This deserves a question in SO.

stefanloerwald commented 9 years ago

Regarding the new algorithm category for filter-like algorithms: With continuations we never actually want a new object. Stuff like copy_if works with copy_if(begin, end, begin2, f) and returns the "end2". Afaik any std algorithm that may work on two different ranges writing to the second one returns an iterator to the last element touched (Verification necessary!). If this is true, binary_mutable may be completely replaced by my proposed binary_mutable_inplace, right? It is important to consider containers that do not support erase.

stefanloerwald commented 9 years ago

The bug with gcc is certainly a nasty one. Even if it's a bug in gcc, I'd go with sfinae-enabling the method OR adding a nice and shiny static_assert.

pfultz2 commented 9 years ago

You can also use a trailing decltype, like this:

template<typename C, typename F>
auto operator|(C&& container, F f) -> decltype(f(std::forward<C>(container)))
{
    return f(std::forward<C>(container));
}

Also the std::move is not necessary.

Manu343726 / snail

SFINAE callability check, more algorithm categories, reducing allocations #3

TL;DR