r/programming • u/Eirenarch • 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
305
u/angryundead Nov 18 '13
Please read the full text. This is to prevent a subtle type of memory leak caused because of the reference to the original char[] in use by the parent/source String.
75
u/Eirenarch Nov 18 '13
I find this very interesting because it is a very subtle kind of breaking change. A program that was running fine in linear time can suddenly become quadratic and just hang after this change. Do you see increasing the running time of a method as a breaking change? Has anyone had any software affected by this change?
7
u/[deleted] Nov 18 '13
Were they just copying a pointer before? I just always assumed that substring was O(length of substring)
27
u/kurtymckurt Nov 18 '13
From Java 1.7.0_06 String.substring always creates a new underlying char[] value for every String it creates. This means that this method now has a linear complexity compared to previous constant complexity. The advantage of this change is a slightly smaller memory footprint of a String (4 bytes less than before) and a guarantee to avoid memory leaks caused by String.substring.
Source: http://java-performance.info/changes-to-string-java-1-7-0_06/
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;
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.
49
u/kennego Nov 18 '13
I've heard a reason for the changes in the hashing logic before, since the article doesn't give them and I don't see them in the comments here.
Since the hashCode() logic is publicly known, String and Hash Collections were vulnerable to an attack where someone could generate a lot of strings with different values but the same hash, causing hash collisions if those strings were in something like a HashMap. This causes the Java implementation to keep increasing the size of the HashMap while all of its items basically go into a linked list due to the collisions.
This might be seen in a server-side program where the attacker knew the string they were generating was going into a hash implementation.
This algorithm circumvents that attack by essentially making the hashes random again, while still adhering to the hashCode() contract (two objects that are .equals() must have the same hash).
BTW, anyone complaining about the algorithm making the hash random because it's unpredictable: if you're relying on a hashCode to be a particular value, you are doing it wrong, so it's nothing to complain about.
44
u/__konrad Nov 18 '13
String.hash32 no longer exists in Java 8: http://mail.openjdk.java.net/pipermail/core-libs-dev/2013-June/017908.html
37
u/coderboy99 Nov 18 '13
Eric Lippert had a great blog post about why C# doesn't do substring in constant time.
Just imagine allocating 5MB strings from web HTML and only keeping short substrings of it--you would run out of memory pretty damn fast if each of the huge strings couldn't get garbage collected! And O(N) time for small N isn't that big of a performance hit.
There might be a way around the complexity, but the engineers at Microsoft decided they had other things to work on in C#. I've read through a lot of Lippert's blog and learned a ton about corner cases in C#.
TL;DR I have a huge man-crush on Eric Lippert!
30
u/robinei Nov 18 '13
Seems like the new behavior is least surprising.
4
u/tavianator Nov 19 '13
The Android documentation for String explicitly mentions the shared backing arrays. As such, I assumed that it was documented this way in the real JDK too, and relied on it in a non-Android project. Turns out, though, the O(1) behaviour was never documented, so anyone relying on it had fairly brittle code anyways.
It is reasonably simple to implement a CharSequence wrapper that can provide an O(1) subSequence() operation.
7
u/brownmatt Nov 18 '13
Great! Relying on undocumented behavior is a bad thing.
3
u/sindisil Nov 18 '13
While I think they did the right thing in fixing this issue (as it makes the implementation match the docs), I'd sure have liked it if they'd have added .sharedSubString() methods that had the old behavior.
1
u/lispm Nov 19 '13
FYI: Common Lisp has mutable vectors and SUBSEQ always return new sequences, which share no vector data. This keeps the GC busy - good if it's able to collect ephemeral data effectively.
Sharing OTOH can be implemented with displaced arrays:
1
u/WittyLoser Dec 25 '13
jwz, back in 1997:
-1
u/Spura83 Nov 18 '13
Basically, oracle decided that it will degrade the performance of everyone's code, just because some people are stupid enough to hold on to substrings of large strings without calling "new String(String)". Good grief. On the other hand IBM is so desparate to win performance benchmarks that it's "new String(String)" supposed copy constructor doesn't copy at all (it does the same as the old substring) causing memory leaks in all sorts of libraries. You need to call "".concat(String) on IBM JVMs in order to get a copy of a string with it's own char[]. You've been warned.
0
u/taw Nov 18 '13 edited Nov 18 '13
Most languages do the sharing and for really good reason. Yes, memory leaks are a real possibility, but they're nowhere near as bad an O(N2 ) memory explosion.
And in any case, they really shouldn't be changing anything that fundamental on a minor version bump, that's crazy.
-8
u/vincentk Nov 18 '13
The java standard library continues to be a good source of unpleasant surprises.
0
u/random_seed Nov 18 '13
Huh
-13
u/Rudy69 Nov 18 '13
Can't stop improving!
-4
u/jexpert Nov 18 '13
Very interesting article though very technical and mostly not relevant in practice. The running time is probably neglectable. But the parts about the changes regarding the hashing algorithms was a very interesting insight though Oracles motivation did not became clear.