Fast mapping of a
char to lowercase, uppercase, titlecase, or its simple case folding
in Rust using Unicode 15.0 data.
Motivation / When to Use
The Rust standard library supplies to_uppercase and to_lowercase methods on
char so you might be wondering why this crate was created or when to use it.
You should almost certainly use the standard library, unless:
- You need support for titlecase conversion or case folding according to the Unicode character database (UCD).
- You need lower level access to the mapping table data, compared to the iterator interface supplied by the standard library.
- You need faster performance than the standard library.
An additional motivation for creating this crate was to be able to version the UCD data used independent of the Rust version. This allows us to ensure all our Unicode related crates are all using the same UCD version.
Performance & Implementation Notes
ucd-generate is used to generate
tables.rs. A build script (
compiles this into a three level look up table. The look up time is constant as
it is just indexing into the arrays.
The multi-level approach maps a code point to a block, then to a position within a block, which is then the index of a record describing how to map that codepoint to lower, upper, and title case. This allows the data to be deduplicated, saving space, whilst also providing fast lookup. The code is parameterised over the block size, which must be a power of 2. The value in the build script is optimal for the data set.
This approach trades off some space for faster lookups. The tables take up
about 101KiB. Benchmarks (run with
cargo bench) show this approach to be
~5–10× faster than the binary search approach used in the Rust standard
It's possible there are further optimisations that could be made to eliminate some runs of repeated values in the first level array.
- Regenerate with
yeslogic-ucd-generate(see header of file).
#[allow(dead_code)]to each table to prevent warnings.
- Delete entries that map to themselves. E.g. in Vim: