On 23-09-14 22:15, Andi Kleen wrote:
>> A big part of the table does decompositions for Korean: eliminating
>> the Hangul decompositions removes 156320 bytes, leaving 89936 bytes.
>
> Are there regular ranges or other redundancies in the Korean encoding
> that could be used to compress paths?
Yes, though at the expense of more complicated code and interfaces. in
particular, lookups that want a normalized string would need to provide a
10-byte buffer to store it in.
> Doing some basic research other people already answered this:
>
> Please use the ICU or google tables referenced below. Apparently
> smaller is possible too, but 40-50k seems more reasonable.
Riffing off the http://macchiato.com/unicode/normalization_footprint.htm
link you provided, looking at the NFKD case. For Unicode 3.0.0 that link
gives 3483 NFKD normalizations (exlcuding Hangul), and gives 26,918 bytes as
the size of a simple lookup table (key/offset pairs, with the offset
pointing into a string table).
In Unicode 7.0.0 I count 5721 NFKD normalizations (again excluding Hangul).
As NUL-terminated UTF-8 strings these take 23390 bytes. Using a
key-offset table I need 3 bytes for the key (code points are 21 bits) and 2
bytes for an offset. Total is 5721 * (3 + 2) + 23390 = 51995 bytes. Stealing
4 bits from the key field and 1 from the offset to store the size of the
normalized string I can remove the NUL bytes from the string table and
reduce total size to 46274 bytes.
The trie implementation used here would use 66283 bytes to store the same
information, but it also provides unicode version and canonical combining
class for all codepoints. There are 10268 leaves in this case, with the size
of each leaf being 1 byte for version, one for ccc, plus the size of the
decomposition, if any. So a quick estimate on the space used just for the
NFKD data is some 45747 bytes.
I'm pretty certain that a trie that only stores the NFKD would be smaller
than 45747 bytes as it would need fewer internal nodes, but didn't do the
experiment. But as you can see, for just the NFKD part and excluding Hangul,
the size of the trie is within the ballpark of the numbers you gave.
Case folding adds a partial trie that forwards to the "main" trie for parts
that are identical. This adds 2672 extra leaves and 20171 extra bytes. The
data for the normalization corrections adds another 3328 bytes. With a bit
of rounding, total size comes to 89840 bytes.
> I'm just gonna make the claim that whatever performance you
> get from a larger table is dwarfed by the cache miss overhead.
That's possible, though it seems plausible you'd only suffer from this doing
actual Hangul decomposition: all the data related to this (trie nodes, trie
leaves, and strings) sits in one contiguous block in memory.
Olaf
--
Olaf Weber SGI Phone: +31(0)30-6696796
Veldzigt 2b Fax: +31(0)30-6696799
Technical Lead 3454 PW de Meern Vnet: 955-6796
Storage Software The Netherlands Email: olaf at sgi.com