Java 7 changed the structure of String

http://www.javaspecialists.eu/archive/Issue230.html

by antoaravinth • 11 years ago

101 86 11 years ago

javaspecialists.eu

blueplanet• 11 years ago

Can someone explain to me why using a cached value for hashCode in an immutable string is a bad thing?

vbezhenar2• 11 years ago

It's certainly not a bad thing, why do you think it might be?

mnw21cam• 11 years ago

It can be a bad thing if all programmers assume that the caching works, and it doesn't. That's where the bit in the article mentions strings that produce a hash code of zero. Zero is used as a sentinel for "hash code not yet calculated", so for those particular strings the code is recalculated every single time.

abollaert• 11 years ago

I don't think he refers to the caching being a bad thing, but that it probably does not affect performance that much, since most Strings are likely to be small (and the number of times hashcode is called is also likely to be small).

There's also a catch : if the hashcode of the string is 0, the hashcode will be recalculated every time (since the code assumes it has not been cached yet).

moonchrome• 11 years ago

There's also a catch : if the hashcode of the string is 0, the hashcode will be recalculated every time (since the code assumes it has not been cached yet).

At least that part should be easy to fix by defining a hash function that returns numbers != 0 - even the article says they did it for JVM7 but it's gone in JVM8 - with no explanation ?

brandonbloom2• 11 years ago

Can just bit-or 1.

thescrewdriver• 11 years ago

The only negative was a small memory overhead.

nvarsj• 11 years ago

I assume it's because most of the standard Java collections (HashMap, HashSet) actually cache the hash codes themselves. So caching it again inside the object is a bit redundant.

However other data structures (notably the ones in guava), don't do this caching - which does hurt performance for any sort of heavy writes and/or complex object.

brandonbloom2• 11 years ago

This reminds me: Generic Persistent RRB vectors should be part of every standard library. There's a great master's thesis out there waiting to be written about a similar data structure for variable length encodings of elements (such as UTF-8 strings).

agumonkey• 11 years ago

Interesting, another Phil Bagwell paper http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf

ExpiredLink• 11 years ago

Java 7 quietly changed the structure of String. Instead of an offset and a count, the String now only contained a char[]. This had some harmful effects for those expecting substring() would always share the underlying char[].

In theory they could have implemented both. Substring optimization for small but not larger strings.

aembleton2• 11 years ago

That would been terrible and unexpected. The behaviour would differ based upon the length of the input String.

david-given• 11 years ago

It shouldn't. The behaviour is specified by the external interface, and if the internal implementation is changing the behaviour, then the implementation is broken.

For example, back when I was at a JVM company, we had two string implementations, one for ASCII strings and one for UCS-2 strings; the JVM uses a lot of ASCII strings, and frequently you could figure this out at code load time. Having an implementation based on an array of bytes saved quite a lot of space, and was completely transparent.

bsdetector• 11 years ago

The behavior would differ, but it would be the better behaviors for the length of the String.

For large strings, it would work exactly like it did before with fast views. And since the existing code already knew about memory sharing this wouldn't be a new problem for any code.

For small strings, it would now be faster and have smaller memory footprint. Existing programs would be faster and better performing.

I think the main reason this is a bad idea is that String is final. The way to do this properly is with two classes, SmallString and LargeString, and then using hotspot to optimize the program for how they are used. But that is not possible without changing the API.

jkot• 11 years ago

String on its own is inefficient class. There is extra pointer, int field... ASCII strings are not downgraded from char[] to byte[]... You get big performance bonus just by replacing String with raw byte[].

I wrote Map<String,String> which does this transparently, and it consumes about 5x less memory compared to HashMap<String,String>.

joajoa• 11 years ago

It's not that simple. See [1] and [2]

[1] https://bugs.openjdk.java.net/browse/JDK-8054307 [2] http://shipilev.net/blog/2015/black-magic-method-dispatch/

hyperpape• 11 years ago

It's been a little while since I read the method dispatch post...can you explain what you're driving at?

MichaelGG3• 11 years ago

Yeah I wish C# had a flag for this. UTF-16 is stupid, and in so, so many cases, it's just a pure loss with no benefits at all.

midko2• 11 years ago

The article is an example of using an anecdote ("During our course, the customer remarked that they had a real issue with this new Java 7 and 8 approach to substrings") and a skewed microbenchmark to extrapolate to general advice.

The substring change was done to address common real scenarios, as the author of the change described here: http://www.reddit.com/r/programming/comments/1qw73v/til_orac...

rsynnott2• 11 years ago

It does address common real scenarios. However, it also causes issues for other common real scenarios. For instance, say you have a CSV parser where you generally only look at a few columns. Under the old system, it wasn't crazy to implement this by, for each field, checking if any unescaping is necessary, and if not (generally the common case) doing a substring. This produces some garbage, of course, but manageable amounts. This approach abruptly gets _far_ slower under Java 7.

I can see why they made the change, but it absolutely did cause problems for real-world use-cases.

midko2• 11 years ago

The way the change was distributed (in a bugfix release) and (mis)communicated was completely wrong, I definitely agree with that. As for the parsing example, yes, that's one way to implement this but definitely not the only right one -- if you care only about a couple of fields from a massive string, it depends on your application domain whether you can tolerate the additional memory bloat. What I like about the current behaviour is that the method is less surprising and more GC friendly

strictfp3• 11 years ago

Stop being so dismissive of this being a problem. I've had lots of problems with runaway allocation rates in parsers due to this issue. They could at least have introduced an alternative method which returns a view into the original String IMO. Not everyone is silly enough to not read the doc and get confused when memory blows up.

the84722• 11 years ago

and get confused when memory blows up

this is fairly easy to spot with a profiler though

strictfp3• 11 years ago

Yes that is what I mean. Is it really more common that people do substring and expect the rest to be thrown away than the other way around? I would like to argue that this is an optimization aimed at sloppy code while it's penalizing well-written code.

jeb_douche• 11 years ago

And there is a good chance it will change again to have compact String in OpenJDK 9, see http://openjdk.java.net/jeps/254

stevoski3• 11 years ago

I'm dubious as to whether this change will occur. It's been tried before, and given up due to complexity.

I think it is an excellent idea, but in practice too awkward to implement seamlessly.

ptx• 11 years ago

Python 3.3 did it: https://www.python.org/dev/peps/pep-0393/

aembleton2• 11 years ago

This looks like a good idea. Most Strings could be encoded with one byte per char.

MichaelGG3• 11 years ago

Why does he say SubbableString example is not threadsafe? The private fields are only written during object creation.

rlmw• 11 years ago

Because he takes a reference to a char[] in the constructor without copying it. char[]s are mutable so this means that the internal state of his String can be mutated by something else without any synchronisation guarantees.

MichaelGG3• 11 years ago

But that's nothing to do with thread saftey - even with a single thread if the char[] changes then stuff blows up right?

mcherm• 11 years ago

I would not have objected to releasing this change in Java 1.7. But releasing it in a BUG FIX RELEASE causes me to lose confidence in the maintainers of the JVM. One of the reasons that large companies like mine build in Java is because of Sun's long history of extremely careful attention to backward compatibility. Oracle is no Sun.

easytiger• 11 years ago

100% right. Sun were psychotically obsessed with maintaining a completely stable and reliable and predictable platform for both the JVM & Solaris. This went out the window with Oracle for the sake of "innovation". The number of major incidents caused by cavalier changes in 1.6 & 1.7 is ridiculous. Youd be hard pushed to even find anything worse than a documentation formatting bug in 1.5.

jerven• 11 years ago

I don't think that is fair 1.5 introduced the enum keyword. That was not a fun change in a codebase I worked on. Java 6 and later are more sticklers in what is allowed by the api contacts and not breaking those than in the sun days.

toyg• 11 years ago

Tbh, though, it's a "damned if you do" scenario: pre-acquisition, all talk was about the glacial pace of evolution in the Java world and how things were just not progressing. Oracle started releasing hard and fast, and now people complain it's too much and too buggy. Can't please everyone...

stevoski3• 11 years ago

I've been programming in Java since Java 1.1.8 and I hazily recall several regression problems under Sun's stewardship. My gut feeling is that the rate of regressions in Java updates has remained steady.

If the rate has increased significantly under Oracle's stewardship, this is something I'd like to write about in my Java newsletter.

Do you have some statistics to demonstrate that regressions have become substantially worse since Oracle took over Java? I'd happily acknowledge you as a source!

grandinj• 11 years ago

You must be kidding. Up until 1.6 I had regressions on even the minor releases. Since oracle took over I update without even thinking about it. And I've been delivering desktop apps since 1.1.8

stygiansonic2• 11 years ago

Here is an explanation of the change to `substring()`[0] and why it was done. The change was done in Java 7u6.

In short, the previous way of keeping the same underlying character array and just updating the {offset, count} indexes has a drawback in that if the original string is large, it is prevented from being GC'd if one keeps a reference to even a single substring generated from it.

So, it's a trade-off between the original and new behaviour; the original way more or less caps the memory usage at the size of the original string, but at the expense of not being able to GC it if even a single substring exists, while the new way increases memory usage for each substring generated but does not prevent any of the strings from being GC'd.

This is why the article's code example yields such a huge difference in memory usage in Java 6 vs Java 7; it is effectively a sort of "anti-pattern" when used against the new `substring()` method. (i.e. iterating through a large string and generating lots of sub-strings)

The article I linked to, which came out in late 2012, basically had the same advice:

"If you are writing parsers and such, you can not rely any more on the implicit caching provided by String. You will need to implement a similar mechanism based on buffering and a custom implementation of CharSequence"

0. http://www.javaadvent.com/2012/12/changes-to-stringsubstring...

TheLoneWolfling• 11 years ago

The thing I mind is that there is now no way to get the old behavior. String is a final class, so you cannot override it and add a field, even. You can roll your own - if there is no code you do not control that takes a string. (And if you don't mind having to write your own string class!)

And it being done in a "bugfix" release? That's unacceptable.

stygiansonic2• 11 years ago

I agree - echoing the sentiments of another commentator here, I feel like one of the tenets of Java is backwards compatibility. While the change doesn't affect functionality, it can turn code that previously had a space complexity of O(1) into one that is O(n). This is probably a Bad Thing.

Conversely, for people new or somewhat-new to the language, the change probably makes sense from a principle of least surprise. From the start, you're taught that Strings are immutable objects, so you probably understand that `.substring()` produces a new instance object. Not having the original memory freed when you remove all references to the original string would likely be puzzling at first.

In this respect, the Java/Oracle folks likely decided that optimizing for the "parsing/tokenization" use case (where you make lots of substrings from a large original string and thus it makes sense to use the same underlying character array) was more novel and less frequent than the use case of "just pulling a small substring from a much larger one and then discarding the large one."

the84722• 11 years ago

You can roll your own - if there is no code you do not control that takes a string.

You can roll your own for the standard String too, through the bootstrap class loader.

Although I don't know how many assumptions about the internals of the string class are baked into the JVM. But I think you could replace substring() relatively safely.

tuckermi• 11 years ago

Given the pain that would be associated with rolling your own, why not make the case that a new method be added to the String interface that provides the old behavior? Legacy applications still need to change, but it would be a relatively straight-forward mechanical replacment.

stevoski3• 11 years ago

I recently started to write an article describing how java.lang.String was one of the classes that the Java creators got mostly right in Java 1.0. This contrasts to other Java 1.0 classes such as java.util.Date, which, as the usage of Java spread, and some good practices emerged, revealed itself to be poorly implemented.

I wanted to show in my article how one of String's strengths is that String efficiently shares memory with substrings. But then when I looked into Java 8's String source code, I was surprised to find that this was not the case. It seemed I had been working with false assumptions for years.

Now, thanks to Heinz's article (OP), I discover that this was a change in the String class.

Long ago, a man who had been programming for 30 years told me about his theory of the half-life of programming knowledge being roughly 18 months. Today, Java has made me believe his theory a little bit more.

ygra• 11 years ago

Today, Java has made me believe his theory a little bit more.

I think Java is sort of an exceptional case here in that the language stays relatively stable and evolves very little over time. Also they tend to not change internal details of the standard library without reason, so even lots of things programmers shouldn't rely on, such as behaviour of substring() will stay unchanged for quite long.

Now JavaScript on the other hand probably has programmign language and framework knowledge half life of considerably less than 18 months ...

nkassis• 11 years ago

JS now is moving fast but for the longest time it was stuck in stasis with various incompatible implementations floating around. And almost any knowledge on it was probably invalid in one of those implementations.

alblue2• 11 years ago

The date API in Java (before 8 anyway) was hideous. Here's what was wrong with it:

http://stackoverflow.com/questions/1969442/whats-wrong-with-...

jaawn11• 11 years ago

Based on all of the coding "best practices" books/blogs I've read, it is unwise to develop something which heavily depends on the internal implementation of the String class (or any library class). Many other commenters here are bemoaning the impacts the specific implementation of String will have on their existing applications. However, we should be designing based on the interface/contract presented, not specific implementation details of interfaces/libraries. Any optimization based on specific implementation details is "at your own risk."

If changes to the implementation of String could cause issues for you, you really should be using a custom solution anyway. A quick and dirty option would be to write a wrapper class which uses all of your preferred String hacks in a central location, and using that in place of String throughout your code. When String's implementation changes, you can update your hacks all in one place.

Here is some relevant advice from The Pragmatic Programmer: https://pragprog.com/the-pragmatic-programmer/extracts/coinc...

bluecalm• 11 years ago

> However, we should be designing based on the interface/contract presented, not specific implementation details of interfaces/libraries. Any optimization based on specific implementation details is "at your own risk."

That's a bit naive. Let's say you want to code something which heavily depends on a String class. You test the standard one, it's fast enough. You decide you don't need to roll your own because of it.

Then it changes and it's no longer fast and changing it at this point might be a big pain. I mean, it's hard to predict that fundamental class in a language is going to change its performance characteristics.

jaawn11• 11 years ago

This is exactly the kind of "programming by coincidence" discussed at the link I provided.

If you are designing something that makes heavy use of String and String operations, and you know it needs to be as optimized as possible, you should consider whether or not you need a custom String solution as part of the design process. Of course there is a hypothetical scenario where a developer might run into this even when "doing everything right", but generally it can be avoided by being aware of these potential interactions and "program deliberately."

I am not saying there will never be times when you need to "just make it work" and reasonably can't account for everything like this. The real world does not always provide the opportunity to do everything "the right way." My point is just that, when you run into this issue, it should be understood that any issues caused by implementation changes aren't really the fault of the maintainers if they haven't broken the contract/interface, and it performs well under the use cases it is designed for.

scott_s2• 11 years ago

Algorithmic complexity should be considered part of an API, because it is not mere "internal implementation". It has observable effects from the outside. When a function in an API goes from O(1) to O(n), that should be considered a breaking change.

For the record, C++'s standard library has algorithmic complexity as a part of the API. See the analogous std::basic_string::substr: http://en.cppreference.com/w/cpp/string/basic_string/substr

I've been bitten by std::list::size in pre C++11 code, as it was allowed to be O(n). But they were clear about it, the fault was mine. Now, it is guaranteed to be O(1): http://en.cppreference.com/w/cpp/container/list/size

I think it's likely that the change to String.substring was actually a good one. But I also agree with others that it was rolled out poorly, and should probably not have been in a fixpack release, as from how I see it, they changed the API.

jaawn11• 11 years ago

This is a fair argument to make, but to my knowledge, this is not currently true of the Java API. It probably would make sense for some future version of the Java API to include O notation as part of the contract, at least for certain elements such as String. Since the performance expectations of Java have increased dramatically, it really would be beneficial to maintain stable-or-better performance (edit: for all use cases) across versions.

jaawn11• 11 years ago

I guess my point is that, regardless of your opinions of what the API contract should include, you have to work with the current contract and plan/design/develop accordingly to avoid issues with library implementation changes.

spiralpolitik• 11 years ago

substring() was always defined in the 6 and 7 JavaDoc as:

"Returns a new string that is a substring of this string..."

Both implementations satisfy the API description so the API didn't change, the implementation did.

Optimizing your code based on the internals of a supposedly opaque data structure is a bad practice and if you get burned you only have yourself to blame.

dhirsatha101• 11 years ago

Thanks for sharing....its very informativehttp://www.trainingintambaram.in/perl-training-in-chennai.ht...

flowerjeni• 11 years ago

One method would be to have an informal heuristic you use when you're about to call a library: are the performance characteristics I need guaranteed by this library? If yes: proceed, if no: use a different solution or proceed with caution.http://www.trainingintambaram.in/dot-net-training-in-chennai...

epmatsw• 11 years ago

The author of the change participated in a Reddit thread discussing it when the update came out. Thought he made a pretty good case for it.

https://reddit.com/r/programming/comments/1qw73v/til_oracle_...

e40• 11 years ago

I don't know, this

https://www.reddit.com/r/programming/comments/1qw73v/til_ora...

seems to bring up persuasive arguments on the other side.

threeseed• 11 years ago

His suggestion is pretty ludicrous though.

You can't just deprecate substring() which is a function that is used in what 90% of the millions of Java applications around the world. All because life is difficult for a tiny few edge cases (and for which workarounds exist i.e. checking Java version numbers). Sure it wasn't great that it was done during a bug fix but we need to be mindful that Java releases do span multiple years.

pron• 11 years ago

OTOH, Java 8u20 added string deduplication in the GC: https://blog.codecentric.de/en/2014/08/string-deduplication-...

bcg1• 11 years ago

Can't understand why people in this thread seem so ticked about this.

The author's observation is interesting and useful to know, but this is an edge case that is easily fixable and actually kind of the fault of user code, not the implementation or the spec.

Its not so simple to just say "I can't believe they changed the performance of xyz"... the author's article is about just one usage pattern, and there is no evidence presented to show it is very common compared to others. Developers needing specific behavior for this pattern could easily have used java.nio.CharBuffer which makes allocation/copying/access to the underlying array/etc explicit, and just happens to implement CharSequence. No reimplementation of String necessary.

In general, Java is not C or C++, and has never been billed as a platform where you could rely on the internal representation of anything unless it is specified as such. Even the same bytecode running on the same platform on the same machine can run differently if the hotspot compiler says Make It So. That of course assumes you are even using Oracle's JVM or OpenJDK... there are in fact other implementations of both the JVM and the standard library that are free to implement things however they want.

Even within the Oracle/OpenJDK sphere - there are 4 different garbage collectors which all could affect this pattern differently. There is even a new String dedup feature that would have an impact on the internal behavior of Strings:

https://blog.codecentric.de/en/2014/08/string-deduplication-...

tl;dr - don't assume and pick the right tool for the job

hobarrera• 11 years ago

Obligatory: https://xkcd.com/1172/

Java 7 changed the structure of String

Related Stories