Add efficient findCharIndex

findCharIndex :: Char -> Text -> Maybe Int

When having look at #369, it looks like having access to this primitive, with a fast C implementation that uses the known size of each char in utf-8 might be able to make isSubsequenceOf quite fast, particularly when the haystack is quite large and the needle chars are spread far apart.

int findCharIndex(const char * haystack, int length, int target) {
    char * offset;
    if (target < 128) {
        offset = memchr(haystack, length target);
    } else {
        // Implementation left as an exercise to the reader, but it would look for
        // utf-8 encoded bytes for the Char.
        offset = efficientlyFindUTF8Codepoint(haystack, length, target);
    }
    if (offset == NULL) return -1;
    return (int)(offset - haystack);
}

Having this also means we could add the rule

{-# RULES "findIndex Char" findIndex (c ==) = findCharIndex c #-}
{-# RULES "findIndex Char2" findIndex (== c) = findCharIndex c #-}

[Bodigrim]

Yeah, sounds like a good idea.

Thinking about this a bit more, I think there's probably an efficient vectorised algorithm for each of the 2, 3 and 4 byte sequences... now I need to go and teach my self how to write those...

#c on libera.chat mentioned that there is a nonstandard function memmem which appears to be available on linux, macOS and FreeBSD, but not Windows.

Also, implementing this using memchr would be relatively easy, since knowing that the haystack is valid utf-8, and knowing that the first byte determines the length of the match, we could do something like

...
if(charLen == 3) {
  for(...) {
     char * offset = memchr(haystack, length, (int)charAsUtf8[0]);
     if(offset == NULL) return -1;
     if(offset[1] == charAsUtf8[1] && offset[2] == charAsUtf8[2]) return offset;
    haystack += 3; 
    length -= 3;
  }
} else if (charLen == 4) {
  ...
}
...

Edit: Looks like this pretty much exactly what FreeBSD does: https://github.com/freebsd/freebsd-src/blob/main/lib/libc/string/memmem.c