Optimizing variadic template pack subsequence matching algorithm

Question

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
<
 List<int, char, int, int, char, int, double, int, char>
 ::IdxsOfSeq<int, char>,
 ListInt<0, 3, 7>
>());

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<bool, int> returns a ListInt<TStart> is the boolean
// is true, otherwise an empty ListInt<>
template<bool TAllTrue, int TStart> 
struct Matches;
template<int TStart> 
struct Matches<true, TStart> 
{ 
 using Type = ListInt<TStart>; 
};
template<int TStart> 
struct Matches<false, TStart> 
{ 
 using Type = ListInt<>; 
};
// GetMatch<TS, TM, TStart, TMIdxs>::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<typename TS, typename TM, int TStart, typename TMIdxs> 
struct GetMatch;
template<typename TS, typename TM, int TStart, SizeT... TMIdxs> 
struct GetMatch<TS, TM, TStart, IdxSeq<TMIdxs...>>
{
 using Type = typename Matches
 <
 // True if all the types inside AreAllTrue are std::true_type
 AreAllTrue
 <
 // Type checking with index sequence expansion
 std::is_same_t
 <
 typename TS::template At<TStart + TMIdxs>,
 typename TM::template At<TMIdxs>
 >...
 >{}(),
 TStart
 >::Type;
};
// Main helper template
// Finds every occurrence of the list TM inside TS and returns its index
template<typename TS, typename TM, typename TSIdxs, typename TMIdxs>
struct IdxsOfSeqHlpr;
template<typename TS, typename TM, SizeT... TSIdxs, typename TMIdxs> 
struct IdxsOfSeqHlpr<TS, TM, IdxSeq<TSIdxs...>, TMIdxs>
{
 // ConcatLists (obviously) concatenates the contents of the
 // lists passed as template parameters in a single list
 using Type = typename ConcatLists
 <
 ListInt<>, 
 typename GetMatch<TS, TM, TSIdxs, TMIdxs>::Type...
 >::Type;
};
// If the subsequence to match is empty, return an empty ListInt<>
template<typename TS, SizeT... TSIdxs, typename TMIdxs> 
struct IdxsOfSeqHlpr<TS, List<>, IdxSeq<TSIdxs...>, TMIdxs>
{
 using Type = ListInt<>;
};
// Main typedef
// 
template<typename TS, typename TM> 
using IdxsOfSeq = typename IdxsOfSeqHlpr
<
 // 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
 <
 getClampedMin(int(TS::size - TM::size + 1), 0)
 >, 
 // Index sequence of the subsequence to match
 std::make_index_sequence<TM::size>
>::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?

• Quuxplusone: Could you post a complete, compilable source file? I managed to get your code compiling, but the static-assert doesn't pass. Notice that a lot of your entities are just renamed versions of standard (C++14) entities, such as std::index_sequence (your IdxSeq) and even size_t (your SizeT). It would help me to understand the code if you would just use the standard entities directly, without renaming them.
• Quuxplusone: Here's a Wandbox link to a working version, which I wrote from scratch without particularly consulting the details of your version. I don't know any good way to "benchmark" the different versions with all kinds of big inputs, though; we need Louis Dionne in here! :)
• Quuxplusone: Here's an alternative approach, almost certainly worse: we could encode the list of all possible substrings into the representation of the list, so that the sentence X is a substring of Y translates into simply X is a member of Y::substrings.

Answer 1

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<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>;
static_assert(std::is_same<
 matches<T, typelist<int, char>>,
 intlist<0, 3, 7, 9, 12, 16, 18, 21, 25, 27, 30, 34>
 >::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<int, char, int, int, char, int, double, int, char>;

we want to turn it into something that looks like:

using X = typelist<typelist<int, char>,
 typelist<char, int>,
 typelist<int, int>,
 ...
 >;

And then pass that into a metafunction taking an appropriate typelist<Ts...> and std::index_sequence<Is...> do:

using type = concat<
 std::conditional_t<std::is_same<T, SUB>::value,
 typelist<std::integral_constant<std::size_t, Idx>>,
 typelist<>
 >...>;

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 <typename TL, int I>
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 <typename TL, int I>
struct skip_n_impl : skip_n_impl<tail<TL>, I-1> { };
template <typename TL>
struct skip_n_impl<TL, 0> {
 using type = TL;
};
template <typename TL, int I>
using skip_n = typename skip_n_impl<TL, I>::type;

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

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 <typename TL>
struct zip_impl;
template <typename TL, bool done>
struct zip_impl2;
template <typename TL>
struct zip_impl2<TL, true> {
 using type = typelist<>;
};
template <typename... Ts>
struct zip_impl2<typelist<Ts...>, false> {
 using type = concat<typelist<typelist<head<Ts>...>>,
 typename zip_impl<typelist<tail<Ts>...>>::type
 >;
};
template <typename... Ts>
struct zip_impl<typelist<Ts...>>
 : zip_impl2<typelist<Ts...>, any_of<is_empty<Ts>::value...>::value>
{ };
template <typename T>
using zip = typename zip_impl<T>::type;

This gives us the pieces to get back to take_by:

template <typename TL, int I, typename = std::make_index_sequence<I>>
struct take_by_impl;
template <typename TL, int I, std::size_t... Idx>
struct take_by_impl<TL, I, std::index_sequence<Idx...>>
{
 using iters = typelist<skip_n<TL, Idx>...>;
 using type = zip<iters>;
};
template <typename TL, int I>
using take_by = typename take_by_impl<TL, I>::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 <typename SRC, typename SUB>
struct matches_impl
{
 template <typename TL, typename = std::make_index_sequence<size<TL>::value>>
 struct impl;
 template <typename... T, std::size_t... Idx>
 struct impl<typelist<T...>, std::index_sequence<Idx...>>
 {
 using type = concat<
 std::conditional_t<std::is_same<T, SUB>::value,
 typelist<std::integral_constant<std::size_t, Idx>>,
 typelist<>
 >...>;
 };
 using type = typename impl<take_by<SRC, size<SUB>::value>>::type;
};
template <typename SRC, typename SUB>
using matches = typename matches_impl<SRC, SUB>::type;

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

intlist<0>,
typelist<>,
typelist<>,
intlist<3>,
typelist<>,
...

But concat will drop the empties, so when that gets combined, we get what we wanted - intlist<0, 3, 7>.