from Hacker News

Fast character case conversion (or how to compress sparse arrays)

by donmcc on 10/13/21, 5:15 PM with 11 comments

  • by jhallenworld on 10/13/21, 7:10 PM

    I did a four-level radix tree for the Unicode character class and case conversion support in JOE (Joe's Own Editor, so that you can edit Unicode on non-Unicode systems): index sizes of 7 bits, 5, 5 and 4 plus ASCII has a fast-path table.

    The main difference is that it computes the tables at startup from the sorted Unicode intervals. So the construction code has to be fast. The same code is also used for user character classes in regular expressions.

    Anyway, it builds them in two passes. First pass it de-duplicates nodes, but only the previously constructed node is a candidate for de-duplication. This keeps the memory usage low during construction. De-duplicated nodes can still be modified during this construction, so they may be re-duplicated (there is a reference counter to determine when this happens).

    Second pass (after all data is loaded, no more changes allowed), it globally de-duplicates the leaf nodes using a hash table. Many of the leaf nodes are duplicates (and not just the all zero ones).

  • by willvarfar on 10/13/21, 6:09 PM

    My experience with this is to fast-path the common cases (ie ascii and vast swathes of emptiness) with hardcoded bounds comparisons, so the memory access is only done as a slow path when needed.

  • by edflsafoiewq on 10/13/21, 6:05 PM

  • by kaetemi on 10/14/21, 9:59 AM

    Wrote a case conversion that processes UTF-8 directly last year for Ryzom Core. The tables look like a mess, but it massively improved performance over the code that was replaced. Case changes seem to be called more often than I expected in the game. I do wonder if there's any cleaner and faster way.

    https://github.com/ryzom/ryzomcore/blob/core4/nel/src/misc/s...

  • by edflsafoiewq on 10/13/21, 7:03 PM

    quickjs has pretty cool case conversion too. It special cases ASCII, then does the rest with a binary search through some kinda run-length encoded table. There's more code but the table itself is only about 2K for both case directions.

    https://github.com/bellard/quickjs/blob/b5e62895c619d4ffc75c...

  • by dhsysusbsjsi on 10/13/21, 9:25 PM

    How do these benchmark? I’d like to know if the extra cost of the memory lookups is balanced by the smaller table and better cache locality.