Optimizing variadic template pack subsequence matching 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;.