Re: Unicode implementation concept

> Your idea is interesting and (I think) novel.

Thank you.  I'm sure someone, somewhere, has come up with
the same idea.  I've just not seen it discussed.

> It is not clear to me what problem you are trying to solve.

See previous message about language design issue.
The language designer wants to treat strings like arrays
and consequently your statement that

> code point indexing is rare

is wrong.  We are talking about slicing and dicing strings,
taking substrings, searching strings, etc.  In fact the
idea deliberately tackles what you called "strings that are
being modified heavily."  Fixed random-access indexing is
important for such tasks.

> The only positive feature of this 
> approach seems to be that code point indexing is efficient.

and random-access, and fixed-cost.  These are important
language performance considerations.

> - I would not underestimate the fact that you need to convert
>   a string each time you go into and out of
>   standard-string-type functions.

Nor overestimate.  See previous comments about serialization.
Not all strings will require this step.  For strings lacking
extra-wide chars, the array is already serialized in Unicode
format.  No conversion required.  Just pass the pointer out.

Remember the idea here is that the language uses this
hybrid format internally.  So for string manipulation
purposes all strings are already in this format and there
is never a need for serialization.

Remember too that serialization can be accomplished on the fly
for such things as streaming to disk or network.  You don't
need to serialize in memory for that.  Thus the performance
penalty for shipping extra-wide chars out the door is effectively
nil in these scenarios (e.g. UTF-8 going over the web).
Ditto for read-back:  just populate the data struct as the
bytes are read from disk or network.

> - Discontiguous storage makes it
>   + less efficient with CPU caches (access localization decreases)
>   + hard to deal with in C
>   + inefficient to read a multi-unit sequence

Disagree with all three points.  If the Unicode data as a whole
can fit in cache, so can the hybrid data struct.  Dealing with
arrays in C is vastly easier with random access and a simple bit
check for the necessity of table lookup.  Indeed that is largely
the motivation here.  Either the whole character is sitting in
the array, or the whole character is sitting in the table.  In
either case, the char is stored contiguously.

The entries in the table store full Unicode extra wide chars.
The table entries are not just "extra code unit" entries, but
full characters.  That is a small amount of memory duplication
with respect to the corresponding array entry, but worth it.

> - This looks like a lot of bookkeeping for
>   + small strings
>   + short-lived strings
>   + strings that are being modified heavily
>     (insert/replace/delete operations seem expensive)

The heavy modification cases are the ones that I think this
idea will help the most.  The small string cases are the ones
that it will hurt the least.  Overall then, it's not more
bookkeeping than having to constantly scan strings to find
character positions.

> You appear to propose a general mechanism for many character
> encoding forms, while I tried to argue 
> that most Unicode-savvy software uses UTF-16, which would not
> appear to benefit from such a scheme.

I agree that UTF-16 is the optimal encoding method.  It would
benefit from the features outlined above while incurring no
performance penalty for strings lacking extra wide chars.
(What is an empty lookup table, just a few bytes of storage,
no big deal.)

> - UTF-8: Text is either ASCII-heavy (so UTF-8 is quite efficient),
>   or it is not, and then your approach bogs down because
>   the lookup table is used all the time.

ASCII strings: no penalty, empty lookup table.
UTF-8 strings: more efficient lookup than serial storage;
               penalty only at serialization choke points.

> - UTF-16: Most texts are BMP-heavy or -exclusive, so UTF-16
>   is quite efficient.

Agreed, but this scheme does not penalize that efficiency,
and indeed enhances it in the presence of extra-wide chars.

>   A much simpler optimization is to store the index of
>   the first supplementary code point, so that code point
>   indexing is trivial below that threshold;
>   for most texts, the threshold will be the same as the string
>   length.
>   (I have done this in the ICU Punycode implementation.)

Rephrased,

It is advantageous to flag strings lacking extra wide chars
so they can be treated as normal arrays.

I agree, and this scheme encourages same.  Basically the "flag"
is an empty lookup table, in fact.

Thank you for the feedback!  To some extent these concepts
can only be proven in real-world implementation scenarios.
I am open to suggestions on that.

Best regards,
Mark