Re: Unicode implementation concept

comments interleaved below.

Mark
__________________________________
http://www.macchiato.com
► शिष्यादिच्छेत्पराजयम् ◄

----- Original Message ----- 
From: "Mark Evans" <[email protected]>
To: <[email protected]>
Sent: Sun, 2004 Jan 25 19:07
Subject: Re: Unicode implementation concept


>
>
> The number of programming languages that support string
> slicing is evidence enough of its utility.  I should not
> have to invent scenarios.  Examples include Python,
> Icon, JavaScript, SML, Perl, ad infinitum.

That is just a strawman. Of course slice (that is, extracting a substring) is a
crucial operation -- who said it wasn't?! The question at hand is whether slice
must use code point indices, or can use code unit indices. It is absolutely
clear, as I said before, that good, functional software can be written with
strings that use code unit indices, since we have done a large amount ourselves.

>
> Well, here is a scenario anyway.  Consider single
> character replacement.  This operation entails a
> performance hit using serial storage.  When a wide char
> is replaced by a normal char, a block copy is required
> to retain serial format, correct?  The proposed scheme
> obviates the need for such block moves.

Because the frequency of supplementary characters is so very low, the times that
an operation will replace a BMP by supplementary or vice versa will not, on
average, be at all significant. It is difficult to come up with any sort of
precise figure, but the frequency of supplementary characters as a percentage of
all text is going to be very, very low. Chinese characters up in that zone will
be the most common, but even they will be only some 0.0003% of Chinese text
(estimate; have asked expert for more info), and essentially 0% of anything
else.

Now of course, there may be individual documents that contain a higher
percentage of supplementaries. But those are going to be extremely rare. And
when working on performance it is the odds that count. E.g. if a particular
design decision means that you save 1 millisecs in 99% of the cases, but costs
50 millisecs in the remaining 1%, it is still worth doing. And the figures are
far more skewed in the case of supplementaries.

So whether or not it is really a disadvantage to use a block shift of memory for
a replacement depends entirely on the cost of that design -- and the frequency
it will be encountered -- vs the alternatives. And no alternatives are
cost-free. Your proposal would be faster for indexing code points (which, as
I've said, we very rarely if ever do, since we use code unit indices), but at
some cost at creating and maintaining additional data structure, plus looking up
in that data structure whenever a code point in a certain range is found. It is
also not clear how the code point is to be looked up. I presume it is to be
looked up by index, so that if I have a sequence of code points <0061, 10000,
0062, 10FFFF, 0063>, the string would look like:

array: <0061, D800, 0062, DBFF, 0063>
lookup: {{1 => DC00}, {3 => DCFF}}

What this would mean is that any manipulation of the string, if there is a
lookup table, would have to fix all the indices that come after the affected
area. For example, if I replace the first character (0061) by the string <0041,
0042>, the result would be:

array: <0041, 0042, D800, 0062, DBFF, 0063>
lookup: {{2 => DC00}, {4 => DCFF}}

If you were going to do this structure, it would be even better to have a single
sentinel value. A bit more storage (in the rare case), but saves a comparison on
every access to non-supplementary characters.

array: <0041, 0042, FFFF, 0062, FFFF, 0063>
lookup: {{2 => 10000}, {3 => 10FFFF}}

Another alternative is a dynamic one. Where there are more than than 2K
supplementaries in a string, use the above method, but for 2K or fewer, use D800
+ offset, with a flat array for lookup. That would get constant time for
character access, and no necessity to fix up the table unless supplementaries
were inserted or deleted

array: <0061, D800, 0062, D801, 0063>
lookup: [10000, 10FFFF]
...
array: <0041, 0042, D800, 0062, D801, 0063>
lookup: [10000, 10FFFF]

Now, all these sorts of design may be reasonable tradeoffs, given the rarity of
supplementaries, but one would want to do some performance analyses to be sure,
using a mix of operations and data that reflect real-life scenarios. This also
gets into the whole area of string design, which is more complex than one might
think, with different designs being better for different purposes. For dynamic
modification of largish strings, for example, a single-gap structure works very
well, not just a flat array anyway.

If you are going to primarily index by code points, and not code units, then one
of the above does look reasonable. What you appear to be missing, however, is
that it is not really necessary to index by code point. This is not to deny the
fact that it would be simpler in many cases. Anyway, that's as much time as I
can take on this topic.

>
> It was stipulated up front that I consider the
> designer's performance concerns overblown, but I wish to
> address them at the level that concerns him.  If his
> motivations are not clear I apologize.  Anyone still
> confused, please ignore this thread, but do not attempt
> to cut it short.  It looks to me like the list traffic
> is small anyway.
>
> I am interested in hearing from other people on the
> list.  Specifically, I would like to hear about test
> suites, test data, or test scenarios should I implement
> this concept.  If I do then I will report back with code
> in hand.
>
> Thanks again,
>
> Mark
> _______________________________________________
> icu mailing list
> [email protected]
> http://oss.software.ibm.com/developerworks/oss/mailman/listinfo/icu
>