JEP254: proposal to represent Java Strings as ISO-8859-1 (openjdk.java.net)
According to the proposed Java enhancement "most strings" fall in the Latin-1 character set. Instead of storing all character arrays as 16-bit elements (in UTF-16) the proposal is to have a boolean flag to indicate if the string is in UTF-16 or Latin-1/ISO-8859-1 encoding, thus saving memory overall.
54 comments
[ 1.2 ms ] story [ 114 ms ] threadOne language whose name escapes me took an approach where the internal representation is always unicode codepoints, and Strings have methods for projecting those .toUTF8() or whatever to interact with the outside world - I liked that a lot due to its simplicity, anyone knows which language that was?
if Java had a non-broken string API, even with the current UCS-2 based solution they couldn't do constant-time character lookups.
And even if Java went the extra mile of using characters big enough to encode every code point of a string, constant lookup would still not be possible because users are often interested graphemes, not characters.
Do you know of an example of a well-designed String API? I'd be interested in what trade-offs other language designers made (newer ones, like Rust/Swift/Go/?).
A simple string append can, for instance, require up to 5x the memory consumed by the string.
Worse, this problem will only show up if someone ever enters in a high enough code point. Better hope any user-defined data never gets turned into part of a large string at any point, or you have a potential memory problem down the line.
There are numerous alternatives for encoding sequences of Unicode code points, each with its own pros and cons. UTF-8, UTF-16, UTF-32, and various compression schemes emphasize backward compatibility, or space savings, or rapid, random access of characters, or whatever. Different designs optimized for different benefits, with different associated costs. The UCS character sequence is the universal thing, but how it is represented should be optimized for the application.
It sounds as though this proposal is only about minimizing the number of bytes needed to represent a sequence of UCS characters, but ISO 8859-1 was never designed as a minimal-space representation of UCS characters. Its design reflects entirely different goals. If all you care about is an internal (not externally visible) representation that minimizes string size, you should do a proper statistical analysis first. You will find, for example, that the curly quotes and dashes that are nearly ubiquitous in serious English text and the Euro character so fundamental to international economics are far more commonly included in Java strings than are most control characters. Yet control characters are a part of ISO 8859-1, and those vastly more useful characters are not. Why, if your goal is to optimize for space, would you privilege so many obscure control characters in your default, internal representation, yet force a switch to a different encoding for any string on a blog containing an m-dash or on an e-commerce site containing a Euro sign?
Instead, if it's all about space, and it is an internal, hidden representation, you do a proper statistical analysis of exactly what it is you most need to represent, and either assign bytes in inverse proportion to commonness, or you use a proper information-theoretic compression "encoding" scheme based on the results of your analysis and your weighted goals. Or you stick with the existing, standard, run-anywhere representation Java has used since the beginning.
Either way, switching to ISO 8859-1 for this makes no sense.
The same is not true of Java.
That said, all conforming HTML documents must now use UTF-8.
unfortunately, Java treats text as data encoded in UCS-2 which uses a maximum of two bytes to represent a character and all the Java string APIs assume the UCS-2 encoding.
The problem with UCS-2 is that it doesn't allow to encode characters outside of the Unicode BMP.
In order to solve this, Java actually uses UTF-16 encoding to encode characters outside of the BMP, but none of the APIs actually know about this and still assume UCS-2.
This leads to the API being wrong about character lengths and to regular expressions wrongly matching certain strings and sometimes destroying data when you apply them to replace substrings.
Case in point is this little test class here: https://gist.github.com/5745601abbfbf7068fcd
which prints 2 on the console. I've also given a talk about this at a swiss JS conference in 2012: http://pilif.me/unicode.pdf - JS has/had the same issues as Java in that regard.
The only well-known contemporary languages that get this (somewhat) right are Perl (since forever), Python 3, Ruby 1.9 and Swift, though ES6 is in process of getting up to speed too.
Python 3 and Swift have the issue of being totally tied to unicode, so if the politics and issues around Han Unification matter to you then those two are actually also not usable for you.
And Perl.
Not entirely true. There are codePoint*, indexOf(int ch), and various other methods on String which do work correctly in code points. Unfortunately old methods can't be changed without affecting compatibility.
and Ceylon.
I don't know how Perl, Ruby and Python handle this, but with Unicode, I don't think we can get better than 'somewhat right'.
For example, Swift removes some invariants on string operations that many people take for granted, such as:
I also am not sure whether s==t and u==v implies s+u==t+v.If a language supports a string type and related functions that equate "character" with a grapheme they'll deliver your first two invariants.
With an appropriate approach to byte representations your third invariant can also be maintained.
That means:
All three strings have 1 Swift Character in them; the first is not a prefix of the last.And yes, you can normalize byte representations, but then you have to give up round-tripping through strings.
I maintain convinced that there is no way to do Unicode strings without drawbacks.
Based on direct cut/paste and inspection, the grave accent (in the "`" string above and here in these parens too) is codepoint 96. This is a non-combining (standalone) grave accent that is meant to be its own grapheme. Appending it to another grapheme such as "e" should not combine. The result should be an "e" followed by a visually separate grave character. The string should contain two separate graphemes and have a length of 2.
I can't tell if the confusion/complexity in this case is due to some cut/paste/storage/browser bug, or Swift's handling of the special case (called "degenerate" in the Unicode standard) of an isolated combining character that hasn't yet been combined, or something else.
So I read some of the Swift docs to see if that revealed anything.
The Swift docs I read used the example of appending a combining grave accent (ie codepoint 768, which is NOT the same as the codepoint 96 stored in "`", but rather something more akin to "̀"), stored as a Character value, to an "e" string, stored as a String value. After appending a Character that is a combining character, the length of the new String is the same as the old one. And that's appropriate.
I presume that the Swiftian character count concept, which is applicable to Swift Strings, and which is returned by .count, is inapplicable to Swift's Character values.
Presumably, when a Swift Character value needs to be displayed, Swift generates a String that contains it and displays that. Further, perhaps, if the Character value is a combining character, Swift automatically prepends an appropriate base character (a space, value 32, or NBSP, or dotted circle, or some such) to ensure it becomes its own grapheme.
Part of the confusion may stem from the decision in Swift to use "..." quotemarks for literals of both types. It seems you have to explicitly tell Swift that a "..." literal is a Character, not a String, if you want a Character. At first blush I like the sound of that.
Alternatively, they've screwed something up.
Those issues do matter to me, yet Unicode-based languages like Python 3 and Swift are not only usable, they are best general approach (among actually existing technologies, not among all theoretically possible approaches). I've been building Asian (CJK) infosystems since the 1980s, and there are far fewer problems with Unicode-based approaches than with the encoding soup we had before.
ISO 8859-1 has an important property: it maps directly to the first 256 Unicode codepoints (by construction, since Unicode was designed so that property was true). This means that converting from ISO 8859-1 to UCS-2 or UTF-16 is a simple zero-extension. That has direct performance benefits when doing any operation which mixes ISO 8859-1 and UCS-2 or UTF-16, which will happen often if the internal representation for String can use either. For instance, searching for an ASCII substring within a long UTF-16 string (ASCII maps directly to the first 128 ISO 8859-1 values, another important property).
Yes, it's not the most minimal representation, but since Strings are so common in Java, performance is important. And a lot of Strings use only the first 256 codepoints. It's mentioned in the linked article: "Data gathered from many different applications indicates that strings are a major component of heap usage and, moreover, that most String objects contain only Latin-1 characters."
Personally, I'd be astonished if JVMs didn't already do this: way back when when I was working for a company that did embedded JVMs, it was one of the first optimisations we did. When class files were loaded, we'd look at each string, and if they were ISO-8859-1 we'd use a byte-based representation rather than a word-based one. (Programmatically created strings were always words, of course.)
Even in an environment where most of our customers were Asian the savings were huge. Java uses a lot of identifier strings.
Memory is dirt cheap these days anyway, why now? And if you have mounds of text, compress it.
The smaller the strings, the more strings you can allocate before triggering a garbage collection. Also, the smaller the objects, the less copying is needed when promoting survivors.
You store a string as a self-balancing tree, preferably one that supports constant-time appends and prepends.(For example, a skew-binary random access list or a finger tree.) Each node of the tree has an encoding enum, an array (+ length of said array), and the length including children (alternatively, the length of the left child). A node's characters are all the same length given by the encoding of the node, and a node stores characters by grapheme clusters.
This allows efficient string building, among other things. About the only problems are that lookup/replacement in the middle of strings is now O(log n), and the constant factor.
So, for example, if you have the string "This is a t̴̟̟͙̞̑ͩ͌͝est", it'd (probably) be stored in three nodes: one that stores "This is a t" with an encoding of one byte per character, a direct lookup into the first 256 unicode characters, one that stores "̴̴̟̟͙̞̟̟͙̞̑ͩ͌̑ͩ͌͝͝e", with an encoding of, what, 20 bytes per character, utf8 within a character, and one that stores "st", same as the start.
Unfortunately, Java has too much overhead to make this practical.
But I agree with you on the performance side. My impression is that a lot of Java applications are simple data pumps. They read data from a database and send it to a client. It's hard to see how this JEP helps in that case:
- read bytes from the network (probably UTF-8)
- convert bytes to Java Strings
- compress Java String (ASCII, Latin-1, UTF-8) new
- "render" String to Writer (HTML, XML, JSON, ...)
- decompress Java String for Writer new
- encode to again UTF-8 for OutputStream/browser
In this case this would increase allocation rates and increase CPU load for a potentially smaller old gen.
The only real way to optimize this would be to redesign the String class to be encoding aware and update the Writer classes accordingly. This is unlikely to happen and would hurt other use cases.
Edit: "There are no plans to add any new public APIs or other interfaces.". :(
Presumably if you use one of the byte[] constructors and the encoding is already in the compression format or something compatible then yes.
Whether you'll be able to do that depends on very much on how you implemented your IO. We're still seeing way to many String#substring in our traces after it become slow in 1.7.0_06. Some of them can be fixed easily, others not so much.