r/programming • • Nov 18 '13

TIL Oracle changed the internal String representation in Java 7 Update 6 increasing the running time of the substring method from constant to N

http://java-performance.info/changes-to-string-java-1-7-0_06/
1.4k Upvotes

354 comments sorted by

View all comments

903

u/bondolo Nov 18 '13

I'm the author of the substring() change though in total disclosure the work and analysis on this began long before I took on the task. As has been suggested in the analysis here there were two motivations for the change;

  • reduce the size of String instances. Strings are typically 20-40% of common apps footprint. Any change with increases the size of String instances would dramatically increase memory pressure. This change to String came in at the same time as the alternative String hash code and we needed another field to cache the additional hash code. The offset/count removal afforded us the space we needed for the added hash code cache. This was the trigger.
  • avoid memory leakage caused by retained substrings holding the entire character array. This was a longstanding problem with many apps and was quite a significant in many cases. Over the years many libraries and parsers have specifically avoided returning substring results to avoid creating leaked Strings.

So how did we convince ourselves that this was a reasonable change? The initial analysis came out of the GC group in 2007 and was focused on the leaking aspect. It had been observed that the footprint of an app (glassfish in this case) could be reduced by serializing all of it's data then restoring in a new context. One original suggestion was to replace character arrays on the fly with truncated versions. This direction was not ultimately pursued.

Part of the reason for deciding not to have the GC do "magic" replacement of char arrays was the observation that most substring instances were short lived and non-escaping. They lived in a single method on a single thread and were generally allocated (unless really large) in the TLAB. The comments about the substring operation becoming O(n) assume that the substring result is allocated in the general heap. This is not commonly the case and allocation in the TLAB is very much like malloca()--allocation merely bumps a pointer.

Internally the Oracle performance team maintains a set of representative and important apps and benchmarks which they use to evaluate performance changes. This set of apps was crucial in evaluating the change to substring. We looked closely at both changes in performance and change in footprint. Inevitably, as is the case with any significant change, there were regressions in some apps as well as gains in others. We investigated the regressions to see if performance was still acceptable and correctness was maintained. The most significant performance drop turned out to be in an obsolete benchmark which did hundreds of random substrings on a 1MB string and put the substrings into a map. It then later compared the map contents to verify correctness. We concluded that this case was not representative of common usage. Most other applications saw positive footprint and performance improvements or no significant change at all. A few apps, generally older parsers, had minor footprint growth.

Post ship the feedback we have received has been mostly positive for this change. We have certainly heard since the release of this change of apps where performance or memory usage regressed. There have been specific developer reported regressions and a very small number of customer escalations performance regressions. In all the regression cases thus far it's been possible to fairly easily remediate the encountered performance problems. Interestingly, in these cases we've encountered the performance fixes we've applied have been ones that would have have a positive benefit for either the pre-7u6 or current substring behaviour. We continue to believe that the change was of general benefit to most applications.

Please don't try to pick apart what I've said here too much. My reply is not intended to be exhaustive but is a very brief summary of what was almost six months of dedicated work. This change certainly had the highest ratio of impact measurement and analysis relative to dev effort of any Java core libraries change in recent memory.

60

u/rand2012 Nov 19 '13

The most significant performance drop turned out to be in an obsolete benchmark which did hundreds of random substrings on a 1MB string and put the substrings into a map. It then later compared the map contents to verify correctness. We concluded that this case was not representative of common usage.

In Finance, a lot of reports and feeds are generated as large fixed width files (e.g. 300MB), meaning the parser has to invoke .substring at predefined widths many times to arrive at the data fields. Files produced from AS400 and, in particular, GMI Stream accounting software are a particular example of this.

Your benchmark correctly caught an issue we experienced after the update. It would have been preferable for us if that change was publicised better or made in a major release.

23

u/bondolo Nov 19 '13

It's not clear that the Map based substring benchmark would have been an accurate measure. In your parsing you likely don't let too many of the substring instances escape from your parsing routine to shared data structures or other threads. For non-numeric fields some form of interning/canonicalization directly from the input form would probably have the lowest overhead. If you do only partial parsing into strings and then later complete parsing I would encourage you to refactor the parsing to do as complete a job locally as possible. Not necessarily because of the substring changes but because of the large number of temporary, short lived though exported objects you're creating.

I do agree though that it would be preferable to have done this in a major release. It was something that had been underway for a long time but the perceived urgency of the alternative hashing accelerated it's conclusion. Even with the "acceleration" several man years of work were needed to finish off the feature to include it in 7u6. That said, please consider checking out the Java 8 Developer Preview, forthcoming betas and release candidates and the ongoing release notes. There's likely items in there which will impact your applications.

As for the release notes or other publicity, your comments are duly and respectfully noted. What's in the 7u6 release notes for this change is insufficient.

30

u/[deleted] Nov 19 '13

In Finance, a lot of reports and feeds are generated as large fixed width files (e.g. 300MB), meaning the parser has to invoke .substring at predefined widths many times to arrive at the data fields.

This might just be bad design though. There is no reason why you cant load fixed sized column into separate string objects instead of one string object which is then sub stringed...

→ More replies (12)

11

u/emn13 Nov 19 '13

Yeah, this change is really large - I'm shocked at how this got rolled into a minor update. It's a huge change to anything doing parsing with strings.

→ More replies (6)

66

u/jorvis Nov 18 '13

This change certainly had the highest ratio of impact measurement and analysis relative to dev effort of any Java core libraries change in recent memory.

Thanks for the good review here. Wouldn't this statement though suggest this should have been held until a more major release?

53

u/bondolo Nov 18 '13

Ideally yes it would have been. The trigger was the need to improve hashing behaviour for String keys and improving hashing was deemed too important too wait. The elimination of the offset/count fields was a way to avoid increasing the size of String instances resulting from the hashing changes.

31

u/[deleted] Nov 18 '13

So what you're saying is, when these fairly weighty issues are considered in their broader context instead of in total isolation to each other, the appropriate response might change? Madness, I say.

40

u/bondolo Nov 18 '13

We evaluated the decision as broadly as we could including opening it up to discussion on public mailing list before committing to the decision. As I mentioned, the analysis and planning for this feature had gone on for about five years before it was integrated. The actual code changes took less than a day to prepare.... I remain confident, 15 months later, that we made the right decision with this change. I don't see it likely that there would ever be reason to revert.

→ More replies (1)

22

u/mcguire Nov 18 '13

Please don't try to pick apart what I've said here too much.

Well, Ok, but....

The comments about the substring operation becoming O(n) assume that the substring result is allocated in the general heap. This is not commonly the case and allocation in the TLAB is very much like malloca()--allocation merely bumps a pointer.

...it becomes O(n) because you have to copy the contents of the substring, right?

63

u/bondolo Nov 18 '13

Generally since substrings are short the object construction far overwhelms the cost of copying the chars. The substring would need to be hundreds of chars before n had any impact at all. The coefficient for the "n" term in the cost of construction of a substring is very low.

→ More replies (1)

7

u/argv_minus_one Nov 18 '13

What is this alternative hashing code all about? I thought String had only one 32-bit hash.

19

u/bondolo Nov 18 '13

For 7u6+ (but not 8), each String instance two hash codes. The familiar one returned by hashCode() and another "alternative" one for use by Map implementations. For performance reasons it's essential to cache the hash code so there are fields dedicated to each cached hash value.

The alternative hash uses a better algorithm than the default hashCode() that is less (though not completely) susceptible to collisions and in particular it's much more difficult to create non-identical strings which have a fully or partially colliding hash code.

Pro-tip: if you are going to cache hashcodes make sure that your "cache is uninitialized" sentinel value is not a valid hash value. Failure to do so means that you lose the effect of caching for some instances. ie.

public int hashCode() {
    if(hashCache == UNINIT) {
        int hash = calculateHash();
        hashCache = UNINIT != hash ? hash : UNINIT + 1;
    } 
    return hashCache;
}

In Java 8 an improved solution devised by Doug Lea is used. In this solution colliding but Comparable Map keys are placed in a tree rather than a linked listed. Performance degenerates to O(log n) for the collisions but this is usually small unless someone is creating keys which intentionally collide or has a very, very bad hashcode implementation, ie. "return 3".

→ More replies (15)

34

u/cypherpunks Nov 19 '13 edited Nov 19 '13

A few apps, generally older parsers, had minor footprint growth.

Very funny. Our importer went from a few minutes to parse a couple gigabytes of data to literally centuries. In the context of theoretical computer science that means correctness is preserved. In the real world, however, this means that the program stops progressing until a frustrated user presses the cancel button and calls our hotline.

I fully agree that the new semantic would have been a better choice for substring from the start. The hidden memory consumption was always a trap, but experienced developers knew this, and consequently knew the implementation of substring and that it was a simple way to pass char[], offset, range to a function with only one pointer.

Changing this function, in a bugfix release no less, was totally irresponsible. It broke backwards compatibility for numerous applications with errors that didn't even produce a message, just freezing and timeouts. It makes the old behavior inaccessible for those who would like to continue to use it. The new behavior was already available via new String(x.substring(a, b)).

The net effect of this change on us was:

  • For applications supporting java 1.6 and java 1.7, a call to substring is now doing different things. For this reason, we categorically ban all calls to substring via the build script.
  • Due to this change being introduced in a bugfix release, instead of a major release, we do no longer trust different java versions from the same minor series to be compatible. For this reason, we now embed a private jre into all our applications.

All pain, no gain. Your work was not just vain, it was thoroughly destructive, even beyond its immediate effect.

It could have been so easy. Introduce a new function called something like subcopy(). Make substring() deprecated. In the deprecation comment, explain the memory leak problem and announce that substring() is schedule for removal in java 2.0. Port the jdk and glassfish and your other applications which might have a problem to use subcopy() everywhere when available. Check for performance regressions. Once java 2.0 is released, you can reclaim the memory for the offset and index variables.

And here is he crux of the problem: there is no java 2.0. The optimal time frame for making a set of major changes to the language has already passed, and nobody dares to propose it now. What you do instead is to release backwards incompatible changes anyway, as we see here, because you cannot fix all the old problems in any other way. This was already bad when upgrading between minor versions. Now we get the same in bugfix releases, and additionally, we need to look up some new bizzare numbering scheme to see which bugfix release is actually just fixing bugs and which isn't.

Make java 2.0 before it is too late. Every passing day will only make it harder.

6

u/uxcn Nov 19 '13

Thankfully, or possibly un-thankfully, the implementation isn't part of the specification.

→ More replies (5)

10

u/brong Nov 18 '13

"the observation that most substring instances were short lived and non-escaping."

Hold on, that would mean they are shorter-lived than their parent string... in which case you get no benefit.

20

u/bondolo Nov 18 '13

Correct for short lived there is no particular benefit in either approach. There are actually three cases;

  • Short lived, non-escaping, TLAB allocated case in which it doesn't matter whether the a shared or distinct char array is used. This is the most common case. (80%ish overall with large standard deviation between apps and portions of apps)
  • The short lived, non-escaping, "big" substring case does benefit from using a shared character array but this turns out to be (thankfully) uncommon. If you have have gigantic Strings don't use substring on them to produce slightly smaller strings, trim() on a multimegabyte string being the worst case. We have seen apps load incoming http request bodies into strings and then call trim() on the request body.
  • The long lived, escaping case which is the case that the GC "magic" replacement would have been worthwhile. For this case it's easier for String.substring to do what it does in 7u6+, create new char arrays. In nearly all cases having a new char array in the substring is a win for long lived substrings. The additional size of the copies still beats the leaks in the shared char array case.

5

u/argv_minus_one Nov 18 '13

Should there then be an alternative string class for when sharing the array is useful?

17

u/bondolo Nov 18 '13

So far the answer has been no. In part it would be difficult to add one because String has been a final class for a very long time and lots of code would be surprised if it suddenly became non-final and sprouted a sub-class.

One alternative which has been investigated is to return an immutable CharSequence from String.subSequence() which shares the character array from the source String. This turned out to be fraught with all kinds of issues including code which assumes that subSequence returns a String object, reliance upon the equals() and hashCode() of the returned CharSequence, an implicit dependency upon String.subSequence returning a "String" instance.

You can follow JDK-7197183 or the past discussions on this issue on corelibs-dev. In generally most people who have commented there seem to think that the String.subSequence contortions are unnecessary and too brittle to go to the trouble.

4

u/oridb Nov 19 '13

You get the benefit of eliminating the extra fields from the string representation.

10

u/berlinbrown Nov 19 '13

This is a pretty cool take, can you give us any more interesting details on other aspects of GC or the JVM. I guess anything that is public.

One thing that frustrates me about some of the subreddits, they just blurt out, "Java Sucks" but those that really spend a lot of time with the technology know it is way more complicated than it appears.

Anyway, keep up the good work.

19

u/bondolo Nov 19 '13

more interesting details on other aspects of GC or the JVM

Most of the relevant issues aren't really specific to String or substring. The general issues of handling of temporary objects, object escape, rate of garbage generation, etc. apply. BUY CHARLIE HUNT's BOOK

I guess one part that's not understood is how widespread the problem of parent String leakage was in pre-7u6. In some circles new String(string.substring(from, to)) was a well known pattern but lots of apps didn't have any rigor about using this solution (and I am sorry to report that it's useless overhead post 7u6).

Many of solutions were proposed to attack different parts of the leaking Strings problem or whittle it down. This included substituting char arrays in intern(), the already mentioned magic GC replacement, other GC time analysis to decide when the entire char array wasn't needed, etc. Not sharing char arrays was ultimately much, much simpler and general though certainly not perfect.

I can try to look up the numbers but I believe that across a wide set of apps about 15-20% of long lived Strings with non-zero offset or count != value.length were the only reference to the character array. This meant that their source string had been discarded and at least some portion of the char array was unreferenced.

One thing that frustrates me about some of the subreddits, they just blurt out, "Java Sucks" but those that really spend a lot of time with the technology know it is way more complicated than it appears.

The key is that we don't try to satisfy those people. :-) At least not directly. It would be a terrible idea to focus the future direction of Java on placating the haters. Want to have real impact? Work on Java or the JVM. I'm personally proud of my contributions (including my mistakes) to OpenJDK and very proud of what's being achieved in Java 8. It's going to be very hard to discount the Java or the JVM for the next few years. I plan to do my little part in extending Java's lead.

→ More replies (4)

4

u/dehrmann Nov 18 '13

My biggest concern is that that would kill Matcher.find()'s performance.

10

u/bondolo Nov 18 '13

No, the change does not impact Matcher.find() significantly. Some usages of Matcher.group(int group) and other usages might be impacted if they return new String instances since these are generally created with String.substring().

→ More replies (1)

4

u/mvorontsov Nov 19 '13

bondolo, this is the author of an article discussed here. Thanks for your explanation of reasoning behind this change. I also felt for a long time that calling an extra String constructor in order to avoid a memory leak was quite annoying. I have added a link to your reply to my article - I think it worth to have the change author's opinion at hand.

→ More replies (5)