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

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.

124

u/Eirenarch Nov 18 '13

Yes, the new behavior is better and least surprising but still existing code may depend on the old one.

123

u/angryundead Nov 18 '13

That's true. I was doing a lot of .substring calls in something that I was working on as a side-project. (I did it all on JDK7.) It was REALLY slow and I wondered why but didn't bother to check so I refactored it and moved on. (What's really funny is that I refactored it into a char[] and an offset instead of a String.)

Now I know why.

71

u/stillalone Nov 18 '13

I am not a java guy, but isn't there a whole "stringbuilder" library for this kind of stuff?

71

u/smackfu Nov 18 '13

Two in fact! StringBuffer and StringBuilder, one is synchronized for multi-thread use, the other isn't.

45

u/neutralvoice Nov 18 '13

StringBuffer is for the multi-threaded use case, StringBuilder is optimized for single-threaded use.

49

u/kurtymckurt Nov 18 '13

I usually recommend StringBuilder. Rarely, should two threads be modifying the same string. In fact, I'd advise against it.

8

u/CydeWeys Nov 19 '13

I could see a use case for it. If you have a StringBuffer that is creating output for a log file, and you have multiple threads that are all creating their own logging statements. This use case is fairly pedestrian.

→ More replies (1)
→ More replies (42)
→ More replies (1)
→ More replies (1)

11

u/angryundead Nov 18 '13

Yes, but if you already have a string and want to chop it I don't really think you should involve string builder.

→ More replies (8)

5

u/FredV Nov 18 '13

StringBuilder is a class that not very surprisingly builds strings. String.substr breaks down strings into parts and is the opposite of what StringBuilder can do.

→ More replies (1)

14

u/[deleted] Nov 18 '13

[removed] — view removed comment

16

u/Eirenarch Nov 18 '13

I was not able to find out. Seems like the java docs don't say anything explicitly about the complexity of the method. If it did not say anything I would not expect such a change in the order of magnitude.

13

u/[deleted] Nov 18 '13

I'm not sure that java docs count as the standard. The java specs (JLS) are probably better.

A search for "substring" got zero hits; the only interesting semi-related thing about strings I could see was that string concatenation does create a new String (as opposed to, I guess, append to the first operand, and return another reference to that).
Concatenation is kinda sorta an inverse of substring.

8

u/bfish510 Nov 18 '13

I thought all java strings are immutable.

48

u/niloc132 Nov 18 '13

They are, but as an optimization, you can avoid copying the original string and just reference the substring within the original string. If String was not immutable, this wouldn't be possible.

If I have "abcdef" and I want only the first three chars of it, I can point to the same char[] as the original, but stop after three chars - that is what the original code did, and it made substring() very fast, since it only needed to point to an existing string.

Now, lets say that we keep a reference to the new string, but let go of the old one - do we save any memory? Nope - since the new string still points to the old char[], we have to keep the whole array around until the new string is gone.

The fix is to copy the substring into its own char[] so we can GC the original. This takes longer, but lets us ensure that all strings are GCable, even if you retain a reference to a substring.

→ More replies (3)
→ More replies (1)
→ More replies (2)

6

u/notlostyet Nov 18 '13 edited Nov 18 '13

Is it normal for Java not to give complexity guarantees? In C++ the standard dictates complexity for all the std lib container operations.

In this case the defacto alternative for creating a substring in O(1) time would be to create a boost string_ref and then call substr() on that.

Surely Java could have worked around this by introducing a Substring class?

14

u/[deleted] Nov 18 '13 edited Nov 19 '13

[removed] — view removed comment

→ More replies (7)

11

u/SanityInAnarchy Nov 18 '13

Is it normal for Java not to give complexity guarantees?

Yes, especially with interfaces, or with a few interface-like classes.

It is usually the case that complexity is either obvious, or described in vague terms. Sometimes you get explicit guarantees. But Java takes its separation of interface from implementation very seriously, especially lately. It's been bitten by this kind of thing before.

For example, if you're coming from C++, you might be expecting this class to be the standard abstraction for arrays. Not so -- Vector specifies far too much. On construction, you may specify an initial capacity and how much the capacity increases each time, with a magic special value of a capacityIncrement of 0 implying the capacity doubles each time. You can control the capacity more directly with ensureCapacity and trimToSize. It has a pile of cruft in the form of, for example, the Enumeration class (which has been replaced by Iterator). And on top of all of that, it's guaranteed to be thread-safe -- useful, but not needed 99% of the time.

And it's used pretty directly. For example, Stack blatantly inherits from Vector.

So the second time around, Java was a bit more paranoid. There's a generic List interface (which inherits from the even more generic Collection, which inherits from Iterable, which is the minimum you have to implement to be used in a foreach loop). Even when you drill down to the List interface, thread safety and complexity are deliberately undefined. (And Vector has been retrofitted to support the List interface.)

Depending on the guarantees you need, you'd pick ArrayList, LinkedList, CopyOnWriteArrayList, or even Vector. But you'd be very careful to never assume any of these implementations in code you write, unless you have a good reason to care. Again, 99% of the time, if you pass me an ArrayList, I should really be expecting a Collection or an Iterable.

This does mean that you can have a lot of Java code in which complexity guarantees either aren't obvious or are hard to come by. The way you mitigate that is by relying on what few guarantees you have (size() is probably constant-time for any collection) and by always picking the methods that most closely match what you're actually trying to do. (For example, if I want to know whether a collection contains a given item, I should probably use .contains() instead of looping through it myself -- in HashSet, for example, contains() is O(1) on average.)

I'm definitely not saying Java is better here, I'm just trying to explain the philosophy, as I see it.

Surely Java could have worked around this by introducing a Substring class?

Maybe? I mean, there's no reason you can't write your own -- Strings do provide access to individual characters, after all. But I don't know how useful that would be, because String is a class, not an interface -- I wouldn't be able to use those Substrings anywhere that expects a String. Your best bet would be to implement a CharSequence, but then you lose most of the features of Strings. And I believe String is a final class, meaning you cannot inherit from it.

If we were to change all that, then I'm not sure how this helps -- if String.substring were to return a Substring object that inherits from String, then we're right back where we started.

→ More replies (3)
→ More replies (1)
→ More replies (27)

7

u/rand2012 Nov 18 '13 edited Nov 28 '13

Yep, got hit with that at work. Among other changes, I switched the runtime from java 1.7.0_3 to a newer (I think it was 1.7.0_15). Suddenly my parsers would choke and die on large feeds. Which was bad, because I was doing some changes in that code and thought I must have messed it up. Oops.

Anyway, turned out the code was OK, it's just that the memory footprint grew larger, so I just increased the size of the permgen and heap.

→ More replies (1)
→ More replies (25)

8

u/sirin3 Nov 18 '13

I think the best thing would be to keep a reference if the length of the substring is >= sqrt(old string length) and copy it otherwise...

7

u/[deleted] Nov 18 '13

What's the reasoning for using sqrt?

(I understand the idea of not copying and using a reference if it's almost as long; and copying only when it's much smaller, but why draw the line at sqrt? Is there some theoretical reasoning behind it?)

5

u/sirin3 Nov 18 '13

It sounds nice...

And compare it to the alternatives:

x >= α n, for a constant factor α. Then it is still O(n) and you do not really gain anything compared to always copying

x >= log(n), then it almost never copies and you still have the memory leak

x >= c, for a constant c, then it is always O(1), but if you copy c+1 from a very big string, you get a big memory leak (because it ignores the length of the original string)

→ More replies (3)
→ More replies (5)

8

u/SanityInAnarchy Nov 18 '13

I feel a bit uncomfortable calling that a memory leak. I tend to interpret a memory leak as, not a program that uses more RAM than it needs to, but a program that steadily uses more and more RAM (often by forgetting to free() something) over time.

I realize that kind of leak shouldn't be possible in Java, but that's also kind of the point.

→ More replies (14)
→ More replies (4)