Re: Improve the performance of Unicode Normalization Forms.

On 22/12/2025 17:44, Alexander Borisov wrote:
> The branching kept bothering me. The algorithm consisted of a function
> with branches (essentially a binary search with offsets) and a table of
> indexes. I really wanted to get rid of the branches. And then it dawned
> on me that instead of building branches with offsets, I could create
> another table that would contain these offsets.
> The "inspiration" came from my patch Optimization of the is_normalized()
> function [0].
>
> Actually, I changed the GenerateSparseArray algorithm, which now
> generates a table with offsets instead of a function with branches.
> In other words, we now have two tables:
> 1. A table with offsets, indicating what offset is needed to obtain the
>    desired index from the index table.
> 2. A table with indexes. The data is divided into fixed ranges.

Sounds like you re-invented the radix tree :-). Nothing wrong with that;
a radix tree sounds like a good data structure for this.

> > The GenerateSparseArray adds comments like "/* U+1234 */" to each
> > element. That's nice but it implies that the elements are unicode code
> > points. GenerateSparseArray could be used for many other things. Let's
> > use "/* 0x1234 */" instead, or make it somehow configurable.
> >
> > The generated file is very large, over 1 MB. I guess it doesn't matter
> > all that much, but perhaps we should generate a little more compact
> > code. Maybe we don't need the "/* U+1234 */" comment on every line, but
> > only one comment for each range, for example.
>
> I have many places where I need to generate C tables. To make my life
> easier, and perhaps the lives of others, I added a small module for
> generating "pretty" tables. ./src/tools/PrettyLine.pm
> After applying it, the size of the generated header file was reduced
> to ~300KB.

I think a fixed number of values per line would look nicer than trying
to pack as much possible on each line.

(This isn't too important of course, this is just about making the
generated code look prettier.)

Thanks, I'll try to find time to take a closer look.

- Heikki