among state machine enhancements #302

I've been working on a new approach to implementing Snowball's substring...among.

This essentially encodes a state machine where each transition is either an O(1) multi-way dispatch on the next byte/character or a check that a particular string of bytes/characters follows (in UTF-8 it works in bytes; for fixed-width encodings it works in characters). This makes among O(1) in the number of strings rather than O(log(n)), and testing shows it's actually faster in practice for real-world among use. The size of the data tables is typically smaller than the old implementation on 64-bit machines, and roughly comparable on 32-bit machines. The generated C code is much more shared library friendly (the existing approach results in a lot of dynamic load time relocations).

This is now working well, and I just need to clean it up a bit and then merge it.

Once that's done, there are some further enhancements that could be made which I'm opening this ticket to keep track of. In no particular order:

• Look at this approach for other target languages. For some it might work better to generate nested switch statements instead of having a tiny interpreter for the state-machine (this might be interesting to try for C too).
• Find common subtrees in the state-machine and only store them once - e.g. in forwards mode, both of these end up allowing 'n' or 'ns': among ( 'ion' 'ions' 'ian' 'ians' ). This reduces the size of the data and so improves cache utilisation. Might need 2 passes, or some sort of interim data structure.
• Track a threshold to include in the limit check at each step so we can stop when the string is too short for a match to be possible from where we are. This would be added in the first limit check and mean we would not need the additional limit check in the substring case (because this threshold would be >= the segment size). See min_length_match in the code (which is calculated but currently not used).
• Currently N-way dispatch is done by a simple table with N entries, which is often fairly sparse (any bytes/characters which cause us not to match will be zero). We currently compactly encode cases where only one or two values can match, but we could potentially use some sort of cheap perfect hash (e.g. PEXT or similar operation) to reduce the number of entries we need to store in some other cases. (Note that this hash can conflate characters which take us to the same next state.)
• Or support N-way with a gap in the middle? Many of the long ranges have just one big gap (e.g. between ASCII latin letters and those with diacritics).
• Or support binary-chop for very sparse cases (it isn't O(1), but it could be limited to when there are < M non-zero entries to provide a complexity bound and/or its use could potentially be selected for rarely exercised cases based on profiling data)
• After a segment, the next transition can't be another segment - can we take advantage of that? Could encode segment+N-way with segment sometimes empty. Might work against common-subtree sometimes. Also a segment longer than 255 bytes/characters would probably need encoding as multiple consecutive segments... (Consecutive segments can occur if we can exactly match part way through - e.g. backwards among ( 'soyad' 'ad' ) has segment ad then segment soy.)
• Some groupings could be implemented by a symbol array lookup on an among N-way dispatch table (e.g. grouping of vowels vs an among transition which accepts a vowel). We could just opportunistically scan the generated among tables to find any data which is suitable - it doesn't actually have to be an N-way dispatch!
• Calls to among gating functions are now generated after the call to find_among()/find_among_b() - that means we could inline their code like we do for explicit calls. A C/C++ compiler should be able to inline them for us now (whereas it couldn't for the old among implementation), but this inlining would help languages which don't have an optimiser which inlines code for us. Even for C/C++, it could enable turning some global snowball integer or boolean variables into locals.
• gopast non-GROUPING could be encoded as an among table where the state machine can loop (it consumes a byte/character on each step so any looping is finite). Also goto and non-inverted cases, but that would require us to support the default (a) being a state transition and (b) advancing the cursor so it a bit more complex.
• Consecutive or composed amongs could be encoded together into a single table (including an among gating function which is an action-less among); similarly for grouping checks in such positions.
• Share identical tables between stemmers (e.g. stemmers which use only ASCII characters have identical tables for iso-8859-1 and UTF-8; some tables may even be the same across languages, though it seems none are currently). The groupings and string will also be the same for ASCII-only stemmers, so maybe this is really more about encoding variants...
• We could save explicitly storing string literals which are substrings of segments in among tables.