Date: Wed, 7 Mar 2018 10:44:20 -0500 From: Rich Felker <dalias@...c.org> To: musl@...ts.openwall.com Subject: Re: Efficient case mapping On Tue, Mar 06, 2018 at 03:27:41PM -0500, Rich Felker wrote: > Replacing the compact but slow linear-search-based case mapping tables > with something comparably compact but fast has been on the hidden > roadmap for a while now, and I think I have a good solution: > > Analysis of Unicode blocks (256-char) shows that most blocks have > either no case mappings at all, or just a single common delta between > lower and upper case for the whole block. There are about 11 blocks > that break this rule and have more. The most unique deltas with > nontrivial frequency (same delta used by more than a single-digit > number of characters) in any block is 3, appearing only in block 04. > > As such, a single-direction case mapping can be achieved as follows. > Use two multi-level bit tables (same format as ctype bits) to assign a > 2-bit number to each codepoint, and 2 integer deltas (the two most > common) to each block. The meanings are: > > 00 - no case mapping > 01 - map via block's first delta > 10 - map via block's second delta > 11 - exception; binary search tiny table of exceptions > > Obviously this can be extended to two directions via a second pair of > tables, but I think we can do better, just 3 bits total: > > 000 - no case mappings > 001 - is lowercase; map to uppercase via block's first toupper delta > 010 - is uppercase; map to lowercase via block's first tolower delta > 011 - exception; binary search tiny table of exceptions > 100 - is lowercase; map to uppercase via block's second toupper delta > 101 - is lowercase; map to uppercase via block's third toupper delta > 110 - is uppercase; map to lowercase via block's second tolower delta > 111 - is uppercase; map to lowercase via block's third tolower delta > > Most blocks will use no bits at all (no case mappings). A few blocks > that only contain lowercase with a single delta will use just one bit. > Many blocks with case mappings will use 2 bits (only one frequent > delta for each direction). The remaining few will use 3 bits, and now > they can code not just 2 but 3 frequent deltas in each direction, > getting rid of a lot of exceptions. > > Some quick size estimates (hope I didn't mess this up): > > 11 complex blocks -- 11 blocks * 256/8 bytes * 3 bits > 7 simple blocks -- 7 blocks * 256/8 bytes * 1 bit > Top-level tables -- 512 blocks * 1 byte * 3 tables > Exceptions -- ~96 pairs * 4 bytes * 2 sortings > > Looks like it comes to about 3k total. Note that this was a significant underestimate. Of course it omitted any accounting for storage of per-block deltas (up to 6 of them for each block) like my first total for the improved scheme, but there seem to be other significant errors too. The counts for "complex" and "simple" blocks were based on just one direction of case mapping, upper to lower. Once you bring in both directions, very little is simple and the number of blocks increases quite a bit. > Further optimizing: We're not using all the data we already have. Only > alphabetic characters can have case mappings, and we already have an > iswalpha table; the above tables are highly correlated with it. > > If we short-circuit out the whole operation with iswalpha, then the > "000 - no case mappings" value is no longer common. Instead, "zero is > one of the common deltas" can be included or not on a per-block basis. An interesting find after implementing this (and reporting the results, which had a minor bug, in the previous reply to the quoted email): ahort-circuiting with iswalpha barely helps at all. There are only two blocks 04 and 24, that have fewer rules after folding the nonalphabetic characters into another rule as "dontcare". Of those, 04 has loads of exceptional cases and saving a rule has minor benefit. Only 24 actually goes from needing 2 bits down to needing only 1 bit. So the "further optimizing" really has only marginal benefit, saving about 72 bytes of table at the (size and time) expense of a call to iswalpha. Arguably a better optimization might be to optimize iswalpha (3.8k) as iswlower||iswupper||small_table_of_caseless_alpha. What this really comes down to is that having a multi-level bit table per-property for character properties is always going to be locally cheaper (for static linking when you just want one property) than a table mapping characters to a bit vector representing all their properties and just picking out the property you want, but if you have a variable-width table like what I'm doing with case mappings, where the width (and thus number/set of possible output combinations) varies per block, it may be more efficient to combine all properties in to a single variable-width-bit-vector table (mainly/especially if the properties are correlated). If so, it may make sense to make such a change eventually -- to have a single musl-internal character properties lookup function that returns a bit vector representing: - wcwidth: -1, 0, 1, or 2 - type: lower[delta], upper[delta], casing-exception, nocase-alpha, punct, control, or space Then iswalpha would be represented as reading the table and masking for lower||upper||casing-exception||nocase-alpha, etc. The key to how this is different, and much more efficient, than glibc and other implementations is the multilevel aspect of the table and the variable-width of the encoding, whereby blocks with only a few possible outputs only need 1 or 2 bits. At 128 blocks needing 3 bits on average (a number I made up, assuming over half of the 512 blocks are CJK or unassigned and some others are simpler) this would be 13k of tables, which is comparable to the current size of the character type data (iswalpha+iswpunct+wcwidth) without any case mappings. So it looks like a minor win at best, but maybe something to keep in mind for the future. Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.