[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20260904234022.GC23438@brightrain.aerifal.cx>
Date: Fri, 4 Sep 2026 19:40:22 -0400
From: Rich Felker <dalias@...c.org>
To: Demi Marie Obenour <demiobenour@...il.com>
Cc: musl@...ts.openwall.com
Subject: Re: Collation implementation is functional
On Fri, Sep 04, 2026 at 05:07:59PM -0400, Rich Felker wrote:
> interleaving of multiple contractions. Something like this might be
> worth raising with the UCA folks, but probably needs a much deeper
> analysis to determine the real costs and whether this fully mitigates
> them.
Some analysis of 0F71^n 0F72^n:
Matching the k'th collation element requires n-k steps skipping over
0F71's, then k steps skipping over already-consumed 0F72's.
At all steps except going from the last 0F71 to the first 0F72, the
NFD iterator is an O(1) advancement. After the last 0F71 is seen, the
NFD iterator has to restart at the last starter to make sure there
were no earlier instances of the new ccc is missed. This takes n steps
to get back to the bounadary.
Thus, matching the k'th collation element takes 2n steps, and
repeating that n times for all n elements takes 2n² steps.
This is suboptimal; if we traded some moderate O(1) space and stored
NFD iterator instances for each ccc instead of skip counts, skipping
to the next ccc would be O(1) in time, and matching the k'th CE above
would be O(1)... if you don't count anything internal to the NFD
iterators.
What about with the NFD iterator internals? These restart scanning
from the beginning every time they reach a new ccc, which in general
is grossly inefficient, but hardly matters since all of the stepping
that's repeated here is within single ccc. The boundary crossing only
happens once for all n CEs. In general, it traverses the whole
non-starter sequence M times, where M is the number of ccc values that
appear in the sequence. This can be painful, but it means traversal
across n characters is still O(n), just with a big constant factor
(56).
I see ways we could do better if the input is already canonically
ordered, by increasing the NFD iterator state to keep a position
separately for each ccc and thus not have to scan from the start when
advancing to the next ccc. But in the general case where the input is
not canonically ordered, I don't think this actually helps.
What would the space cost of having per-ccc NFD iterators for
collation lookahead be?
On 64-bit, each one is 56 bytes; on 32-bit, 36. That comes out to 3k
or 2k, respectively. This would be painful in common cases where
they're useless, if we had to zero-fill them all, but if we kept
validity flags separate and only initialized them on use, it's very
cheap.
I think this is a worthwhile enhancement to pursue, but after the rest
of the project is done.
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.
