Whats up @brunocodutra . You got a very nice library going here.

I was looking around and getting to know the library and techniques (since I'm a template noob :) ), so I decided to pick up metal::sort which is something I (should) understand and play with it.

I took a list of 1500 reversed unique types (char[1500], char[1499] ... ) and sorted it. I takes around 5.5 seconds to do that in my machine (GCC 6.3).

Just for fun, I implemented quick sort. Time went to 30 seconds (and can reach recursion limit - not nice).

Anyway, I was intrigued as to some implementation choices, for example:

        template<typename x, typename y>
        struct _sort_impl<list<x, y>> {
            template<template<typename...> class expr>
            using type = if_<expr<y, x>, list<y, x>, list<x, y>>;
        };

as opposed to:

        template<typename x, typename y, template<typename...> class expr>
        struct _sort_impl<list<x, y>, expr> {
            using type = if_<expr<y, x>, list<y, x>, list<x, y>>;
        };

Why is that? I imagined it could have something to do with performance, so I changed the code into the second version but the compilation time went down to 4.5 seconds.

The overall performance of Metal is particularly sensitive to core algorithms such as metal::join<>, which could see vast improvements if fast tracked linear recursed instead of tree-folded (edouarda/brigand#127).

Just including metal.hpp results in a few errors with VC++ 19.24. I created an empty project and changed none of the settings except for adding an additional include directory for metal.hpp. The file I tested this with is the one from https://raw.githubusercontent.com/brunocodutra/metal/standalone/metal.hpp. I also tried to include metal.hpp from the include directory of the source tree, which resulted in the same errors.

Source code:

#include <metal.hpp> int main() {}

Build log:

1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3113,1): error C3527: 'intmax_t' is not a valid operand for 'sizeof...'. Did you mean to use 'sizeof'? 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3113): message : see reference to alias template instantiation 'metal::join<caller<detail::if<std::integral_constantmetal::detail::int_,vs>::type,metal::list<x,y,t>...,metal::list...>::type...>' being compiled 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3114): message : see reference to class template instantiation 'metal::detail::_replace_if<metal::list<vals...>,metal::list<std::integral_constantmetal::detail::int_,vs...>,x,y,t...>' being compiled 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3113,1): error C2938: 'metal::join' : Failed to specialize alias template 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3121,1): error C3527: 'intmax_t' is not a valid operand for 'sizeof...'. Did you mean to use 'sizeof'? 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3121): message : see reference to alias template instantiation 'metal::join<caller<detail::if<std::integral_constantmetal::detail::int_,vs>::type,metal::list<>,metal::list...>::type...>' being compiled 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3122): message : see reference to class template instantiation 'metal::detail::_replace_if<metal::list<vals...>,metal::list<std::integral_constantmetal::detail::int_,vs...>,>' being compiled 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(3121,1): error C2938: 'metal::join' : Failed to specialize alias template 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(4142,1): error C3527: 'intmax_t' is not a valid operand for 'sizeof...'. Did you mean to use 'sizeof'? 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(4142): message : see reference to alias template instantiation 'metal::join<caller<detail::if<std::integral_constantmetal::detail::int_,vs>::type,metal::list...,metal::list<>>::type...>' being compiled 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(4143): message : see reference to class template instantiation 'metal::detail::_find_index<metal::list<std::integral_constantmetal::detail::int_,vs...>,metal::list<vals...>>' being compiled 1>C:\Users\Philipp\Documents\libs\metal-standalone\metal.hpp(4142,1): error C2938: 'metal::join' : Failed to specialize alias template 1>Done building project "TestProject.vcxproj" -- FAILED.

This PR is intended to share the work I have done related to the discussion in #84 . I'm working both in the suggestion from https://github.com/brunocodutra/metal/issues/84#issuecomment-458742205 and with the idea of creating an algorithm for large lists that fallback on the current algorithm (but adapted to be partial merge) when the lists are smaller.

Upon my testing this version does not impose significant perfomance drawbacks, while allowing the sort algorithm to work to list sizes going up to 5000 (which is what I tested).

I'm also opening the PR to have the CI to run this in different compilers.

I tested some more approaches to nth_element. The compilation time is dominated by the comparison of elements with the pivot in order to create the partitions. The original version (v0) is slow on GCC 9 because GCC 9 dislikes the pack expansion of the form

join<if_<comp<vals, piv>, list<vals>, list<>>...>

An obvious alternative is v1, which is based on metal::partition. I think that we can make it SFINAE-friendly in analogy to metal::min_element. However, the current implementation of metal::partition uses metal::replace_if once for the lo partition and once more for the non-lo partition. As an optimization, v2 creates both partitions at once by using a custom 20-line partitioner. It is twice as fast on both Clang 9 and GCC 9. I suggest to choose v2.

Do you agree that the speedup of v2 over v1 is worth the extra code?

If yes: should we change metal::partition, or should metal::nth_element come with its own custom partitioner?

Would you accept a PR that adds aliases for ::value and ::type like the modern C++ standard library provides? E.g.

metal::same_v<t1, t2>

instead of:

metal::same<t1, t2>::value

If I'm not mistaken these would be implemented with variable templates:

namespace metal {
  template<typename... Ts>
  auto same_v = same<Ts...>::value;
}

Though I believe this requires C++14 so perhaps they would only be enabled if the compilation supports at least that standard.

If the same structure as that of the MPL is used, then people could really just rename from boost/mpl/... to boost/mpl2/... in their includes. Also, one advantage of a backwards compatible MPL is the fact that one does not have to relearn new stuff. The plain directory structure of the old MPL was easy to grok and I think will be expected by users of this library. Just my 0.2.

Users including metal in their projects using CMake's ExternalProject_Add, FetchContent or a git submodule with add_subdirectory might not want to build the docs, examples or tests. In fact, they might not even have the dependencies (doxygen for docs, boost for examples), which causes CMake to print a warning even though it doesn't cause build failures.

For such users metal now provides options METAL_BUILD_DOC, METAL_BUILD_TESTS and METAL_BUILD_EXAMPLES that are ON by default, but can be turned off by consumers.

template<class seq, template<class...> class expr> and friends are more concise than template<typename seq, template<typename...> class expr>. The keyword class can help to reduce the character count, which simplifies skimming through the code. In addition, it prevents some line breaks that are otherwise required by the column limit.

Do you intentionally prefer typename for aesthetic reasons? Are there any compiler-compatibility issues in that direction?

See #73.

Performance of Clang 8 and GCC 9 is similar (v5 refers to this version; v4 is based on metal::bind and metal::arg).

I suspect that the most expensive operation in this version is the recursive call of typename _min_element_worker<false>::template type. The recursion processes one element per step (no fast-tracking), and each call uses O(N) template arguments. It should be more efficient to cut the list into smaller pieces, calculate the minima of the pieces, and then calculate the minima of the minima. I guess you know the tree-based lookup of kvasir as explained in this blog post from Odin Holmes?

Maybe, this issue is placed wrong. It is an issue regarding the documentation. The type of true_/false_ in the documentation is described as boolean constant, but it is a number. The documentation for eg. containsmentions the return value correctly as number. But it forwards to true_/false_. So someone could assume, that contains_resultin following code snipped is of type bool: auto contains_result = metal::contains<list, element>::value

CMake's install target only installs metal.hpp and nothing else. The documentation uses the more specific headers everywhere (i.e. #include <metal/list/accumulate.hpp> to use metal::accumulate) which suggested to me that using these is also supported.

Continuation of https://github.com/brunocodutra/metal/pull/99#discussion_r331799458.

I copied the code of fold_left because I want to benchmark old and new versions. Preliminary results can be found in the section "Change of fold left" at https://ecrypa.github.io/metal-benchmark/.

Add a section to the documentation describing some of the techniques used under the hood. It should serve as a reference for contributors, as well as a gentle introduction to template metaprogramming for the uninitiated.

Generally, apply is synonymous with invoke. MPL library uses apply to invoke a metafunction or lambda. Boost.Hana's apply works just like std::invoke.

However, your apply unpacks the elements of a list and then invokes the lambda, which I found to be surprising. It seems like unpack would be a better name and would avoid the confusion.

It was suggested in #59 that it shouldn't be too difficult to support the Intel compiler, given that its compliance to the C++11 is similar to that of GCC 4.7.