A utility like this seems like it would belong in `itertools`, not `collections`. It should also ideally avoid fully realizing the sequence so it could work with iterators/generators as well; PySequence_Fast will force creation of a `list`/`tuple` of the whole sequence when in practice, a `deque` with a maxlen could be used to only maintain the necessary window into the "haystack".

It would also help to have a pure Python implementation (and until you have one, it's probably overkill to write the C accelerator) for other Python distributions, and to serve as a baseline for comparison to see if a C accelerator is justified.  Something like this might be a decent point of comparison:

def has_subsequence(it, searchseq, *, all=all, map=map, eq=operator.eq):
    searchseq = tuple(searchseq)
    if not searchseq:
        return True  # Empty sequence in everything
    window = collections.deque(itertools.islice(it, len(searchseq)-1), len(searchseq))
    for x in it:
        window.append(x)
        if all(map(eq, window, searchseq)):
            return True
    return False