Efficient unicode string implementation was: Re: Why No Supplemental
Characters In Character Literals?
This message is in MIME format. The first part should be readable text,
while the remaining parts are likely unreadable without MIME-aware tools.
--232016332-372783171-1296854682=:11442
Content-Type: TEXT/PLAIN; CHARSET=ISO-8859-15; format=flowed
Content-Transfer-Encoding: 8BIT
Content-ID: <alpine.DEB.1.10.1102042124571.11442@urchin.earth.li>
On Fri, 4 Feb 2011, Joshua Cranmer wrote:
"Arne Vajh?j" <arne@vajhoej.dk> wrote in message
But since codepoints above U+FFFF was added after the String class was
defined, then the options on how to handle it were pretty limited.
Extending to 24 bits is problematic because 24 bits opens you up to
unaligned memory access on most, if not all, platforms, so you'd have to
go fully up to 32 bits (this is what the codePoint methods in String et
al. do). But considering the sheer amount of Strings in memory, going to
32-bit memory storage for Strings now doubles the size of that data...
and can increase memory consumption in some cases by 30-40%.
This is something i ponder quite a lot.
It's essential that computers be able to represent characters from any
living human script. The astral planes include some such characters,
notably in the CJK extensions, without which it is impossible to write
some people's names correctly. The necessity of supporting more than 2**16
codepoints is simply beyond question.
The problem is how to do it efficiently.
Going to strings of 24- or 32-bit characters would indeed be prohibitive
in its effect in memory. But isn't 16-bit already an eye-watering waste?
Most characters currently sitting in RAM around the world are, i would
wager, in the ASCII range: the great majority of characters in almost any
text in a latin script will be ASCII, in that they won't have diacritics
[1] (and most text is still in latin script), and almost all characters in
non-natural-language text (HTML and XML markup, configuration files,
filesystem paths) will be ASCII. A sizeable fraction of non-latin text is
still encodable in one byte per character, using a national character set.
Forcing all users of programs written in Java (or any other platform which
uses UCS-2 encoding) to spend two bytes on each of those characters to
ease the lives of the minority of users who store a lot of CJK text seems
wildly regressive.
I am, however, at a loss to suggest a practical alternative!
A question to the house, then: has anyone ever invented a data structure
for strings which allows space-efficient storage for strings in different
scripts, but also allows time-efficient implementation of the common
string operations?
Upthread, Joshua mentions the idea of using UTF-8 strings, and cacheing
codepoint-to-bytepoint mappings. That's certainly an approach that would
work, although i worry about the performance effect of generating so many
writes, the difficulty of making it correct in multithreaded systems, and
the dependency on a good cache hit rate to make it pay off.
Anyone else?
For extra credit, give a representation which also makes it simple and
efficient to do normalisation, reversal, and "find the first occurrence of
this character, ignoring diacritics".
tom
[1] I would be interested to hear of a language (more properly, an
orthography) using latin script in which a majority of characters, or even
an unusually large fraction, do have diacritics. The pinyin romanisation
of Mandarin uses a lot of accents. Hawaiian uses quite a lot. Some ways of
writing ancient Greek use a lot of diacritics, for breathings and accents
and in verse, for long and short syllables.
--
Understand the world we're living in
--232016332-372783171-1296854682=:11442--