Optimizing variadic template pack subsequence matching algorithm I'm building a small MPL module in one of my utility libraries for fun and learning experience. 

One of the problems I'm trying to solve is getting a list of all indices where a sequence of types appears inside another sequence of types.

Example:

static_assert(is_same
&lt;
    List&lt;int, char, int, int, char, int, double, int, char&gt;
        ::IdxsOfSeq&lt;int, char&gt;,
    ListInt&lt;0, 3, 7&gt;
&gt;());


The above code is valid and works as intended. However, finding out the indices of a subsequence in a long type sequence becomes very slow very fast.

Searching in a list with 20 or 30 elements can take up to 30 seconds of compilation time.

That would rarely be useful, but I'm also experimenting with compile-time strings implemented as character lists.

The current implementation of IdxsOfSeq basically uses std::index_sequence to perform a naive string matching algorithm over the type sequence.

The naive algorithm requires no preprocessing time, but the execution of the type matching requires a lot of computation time.

This is my current implementation of the string matching algorithm.

// Matches&lt;bool, int&gt; returns a ListInt&lt;TStart&gt; is the boolean
// is true, otherwise an empty ListInt&lt;&gt;
template&lt;bool TAllTrue, int TStart&gt; 
struct Matches;

template&lt;int TStart&gt; 
struct Matches&lt;true, TStart&gt; 
{ 
    using Type = ListInt&lt;TStart&gt;; 
};

template&lt;int TStart&gt; 
struct Matches&lt;false, TStart&gt;  
{ 
    using Type = ListInt&lt;&gt;; 
};



// GetMatch&lt;TS, TM, TStart, TMIdxs&gt;::Type checks if every type
// of TS (the source type sequence) starting from the index TStart
// matches every type in TM (the subsequence to find)
template&lt;typename TS, typename TM, int TStart, typename TMIdxs&gt; 
struct GetMatch;

template&lt;typename TS, typename TM, int TStart, SizeT... TMIdxs&gt; 
struct GetMatch&lt;TS, TM, TStart, IdxSeq&lt;TMIdxs...&gt;&gt;
{
    using Type = typename Matches
    &lt;
        // True if all the types inside AreAllTrue are std::true_type
        AreAllTrue
        &lt;
            // Type checking with index sequence expansion
            std::is_same_t
            &lt;
                typename TS::template At&lt;TStart + TMIdxs&gt;,
                typename TM::template At&lt;TMIdxs&gt;
            &gt;...
        &gt;{}(),
        TStart
    &gt;::Type;
};



// Main helper template
// Finds every occurrence of the list TM inside TS and returns its index
template&lt;typename TS, typename TM, typename TSIdxs, typename TMIdxs&gt;
struct IdxsOfSeqHlpr;

template&lt;typename TS, typename TM, SizeT... TSIdxs, typename TMIdxs&gt; 
struct IdxsOfSeqHlpr&lt;TS, TM, IdxSeq&lt;TSIdxs...&gt;, TMIdxs&gt;
{
    // ConcatLists (obviously) concatenates the contents of the
    // lists passed as template parameters in a single list
    using Type = typename ConcatLists
    &lt;
        ListInt&lt;&gt;, 
        typename GetMatch&lt;TS, TM, TSIdxs, TMIdxs&gt;::Type...
    &gt;::Type;
};

// If the subsequence to match is empty, return an empty ListInt&lt;&gt;
template&lt;typename TS, SizeT... TSIdxs, typename TMIdxs&gt; 
struct IdxsOfSeqHlpr&lt;TS, List&lt;&gt;, IdxSeq&lt;TSIdxs...&gt;, TMIdxs&gt;
{
    using Type = ListInt&lt;&gt;;
};



// Main typedef
// 
template&lt;typename TS, typename TM&gt; 
using IdxsOfSeq = typename IdxsOfSeqHlpr
&lt;
    // Source list
    TS, 

    // Subsequence to match
    TM, 

    // Index sequence of the source list
    // Starts from 0, ends at (source_list_size - matching_list_size + 1)
    std::make_index_sequence
    &lt;
        getClampedMin(int(TS::size - TM::size + 1), 0)
    &gt;, 

    // Index sequence of the subsequence to match
    std::make_index_sequence&lt;TM::size&gt;
&gt;::Type;


Is there any part of the algorithm that can easily be optimized? 

Or is it better to rewrite the solution from scratch, using another algorithm?
I'm going to throw out a fairly complicated solution here by breaking the problem into lots of smaller parts. The end result is that the compilation of the following:

using T = typelist&lt;int, char, int, int, char, int, double, int, char,
                   int, char, int, int, char, int, double, int, char,
                   int, char, int, int, char, int, double, int, char,
                   int, char, int, int, char, int, double, int, char&gt;;

static_assert(std::is_same&lt;
    matches&lt;T, typelist&lt;int, char&gt;&gt;,
    intlist&lt;0, 3, 7, 9, 12, 16, 18, 21, 25, 27, 30, 34&gt;
    &gt;::value, "!");


is still almost instantaneous.

The algorithm is actually going to come from an idea in Python's itertools. What we want to do is walk our typelist N at a time (where N is the match length), and just use std::is_same to compare. That is, taking the original problem's list:

using SRC = typelist&lt;int, char, int, int, char, int, double, int, char&gt;;


we want to turn it into something that looks like:

using X = typelist&lt;typelist&lt;int, char&gt;,
                   typelist&lt;char, int&gt;,
                   typelist&lt;int, int&gt;,
                   ...
                   &gt;;


And then pass that into a metafunction taking an appropriate typelist&lt;Ts...&gt; and std::index_sequence&lt;Is...&gt; do:

using type = concat&lt;
    std::conditional_t&lt;std::is_same&lt;T, SUB&gt;::value,
        typelist&lt;std::integral_constant&lt;std::size_t, Idx&gt;&gt;,
        typelist&lt;&gt;
        &gt;...&gt;;


That's the basic idea anyway. Plus, the smaller pieces are probably going to be useful in other contexts.



The Small Algorithms

These are very straightforward and I will omit them here for brevity: head, tail, size, concat (variadic!), any_of, and is_empty.

take_by

To generate the X typelist above, we need something like:

template &lt;typename TL, int I&gt;
using take_by = ???


The implementation of this is to make a typelist that is I copies of TL, each one dropping a steadily larger prefix off the top. Once we have that, we need to zip all the iterators together. So really, I need to start with the smaller pieces...

skip_n

Given a typelist, basically just call tail n times:

template &lt;typename TL, int I&gt;
struct skip_n_impl : skip_n_impl&lt;tail&lt;TL&gt;, I-1&gt; { };

template &lt;typename TL&gt;
struct skip_n_impl&lt;TL, 0&gt; {
    using type = TL;
};

template &lt;typename TL, int I&gt;
using skip_n = typename skip_n_impl&lt;TL, I&gt;::type;


There may be a better way to do this, but I'm not sure. So, skip_n&lt;typelist&lt;int, char, double&gt;, 2&gt; is typelist&lt;double&gt;. 

zip

This is the tricky part. Basically, we have a list of lists of types. If any of those typelists is empty, we're done. Otherwise, we concat all the heads with a recursive call against all the tails. We can't use std::conditional_t here due to eager evaluation of both parts, so I'm introducing two different impl types:

template &lt;typename TL&gt;
struct zip_impl;

template &lt;typename TL, bool done&gt;
struct zip_impl2;

template &lt;typename TL&gt;
struct zip_impl2&lt;TL, true&gt; {
    using type = typelist&lt;&gt;;
};

template &lt;typename... Ts&gt;
struct zip_impl2&lt;typelist&lt;Ts...&gt;, false&gt; {
    using type = concat&lt;typelist&lt;typelist&lt;head&lt;Ts&gt;...&gt;&gt;,
                        typename zip_impl&lt;typelist&lt;tail&lt;Ts&gt;...&gt;&gt;::type
                        &gt;;
};

template &lt;typename... Ts&gt;
struct zip_impl&lt;typelist&lt;Ts...&gt;&gt;
    : zip_impl2&lt;typelist&lt;Ts...&gt;, any_of&lt;is_empty&lt;Ts&gt;::value...&gt;::value&gt;
{ };

template &lt;typename T&gt;
using zip = typename zip_impl&lt;T&gt;::type;


This gives us the pieces to get back to take_by:

template &lt;typename TL, int I, typename = std::make_index_sequence&lt;I&gt;&gt;
struct take_by_impl;

template &lt;typename TL, int I, std::size_t... Idx&gt;
struct take_by_impl&lt;TL, I, std::index_sequence&lt;Idx...&gt;&gt;
{
    using iters = typelist&lt;skip_n&lt;TL, Idx&gt;...&gt;;
    using type = zip&lt;iters&gt;;
};

template &lt;typename TL, int I&gt;
using take_by = typename take_by_impl&lt;TL, I&gt;::type;


Hopefully that makes sense. First, we built up our "iterators" - which are all offset by one from each other. Then we just zip them up. Now we have the X, and all we need is:

**matches**:

template &lt;typename SRC, typename SUB&gt;
struct matches_impl
{
    template &lt;typename TL, typename = std::make_index_sequence&lt;size&lt;TL&gt;::value&gt;&gt;
    struct impl;

    template &lt;typename... T, std::size_t... Idx&gt;
    struct impl&lt;typelist&lt;T...&gt;, std::index_sequence&lt;Idx...&gt;&gt;
    {
        using type = concat&lt;
            std::conditional_t&lt;std::is_same&lt;T, SUB&gt;::value,
                typelist&lt;std::integral_constant&lt;std::size_t, Idx&gt;&gt;,
                typelist&lt;&gt;
                &gt;...&gt;;
    };

    using type = typename impl&lt;take_by&lt;SRC, size&lt;SUB&gt;::value&gt;&gt;::type;
};

template &lt;typename SRC, typename SUB&gt;
using matches = typename matches_impl&lt;SRC, SUB&gt;::type;


Basically, we end up creating a meta-list internally that would look like:

intlist&lt;0&gt;,
typelist&lt;&gt;,
typelist&lt;&gt;,
intlist&lt;3&gt;,
typelist&lt;&gt;,
...


But concat will drop the empties, so when that gets combined, we get what we wanted - intlist&lt;0, 3, 7&gt;.