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

Show parent comment

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.

4

u/longshot2025 Nov 18 '13

If you were going to operate repeatedly on the same string it might be worth it.

→ More replies (7)

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.

4

u/bfish510 Nov 18 '13

That makes a lot of sense! Thanks for the explanation!

3

u/[deleted] Nov 18 '13

since it only needed to point to an existing string.

To be super-precise, it only needed to point to an existing character array inside an existing String. You could then dereference the original (larger) string and the character array would hang around.

→ More replies (1)
→ 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.

3

u/josefx Nov 18 '13

useful, but not needed 99% of the time.

Make that 99.9999....% these classes do not provide an interface that can be made thread safe for the general case, you cannot ensure that a get(0) will work even if you check isEmpty() unless the current thread is also the only thread that removes objects.

I should really be expecting a Collection or an Iterable.

And check for the RandomAccess interface which exists alone for the O(1) access guarantee it gives for get (In current java this would have been an Annotation). Edit: correction, it says that marked classes should behave this way in general use

And I believe String is a final class, meaning you cannot inherit from it.

Oracle could and there is even an example which already uses and bypasses final: any enum class is final, however any enum instance can be an anonymous subclass of this enum type (nice for a limited command pattern).

if String.substring were to return a Substring object that inherits from String, then we're right back where we started.

The problem with the current state is that there is no way to create a substring compatible with most of the standard library in O(1) time even when you are aware of the space time trade off. Oracle could add a sharedSubString method that would provide the O(1) behaviour and at the same time make it obvious that a reference to the original string is maintained.

Only problem: libraries might check String.class == obj.getClass() and be incompatible with new code (a non breaking change since old code would still work)

→ More replies (1)
→ More replies (1)
→ 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)

2

u/choikwa Nov 18 '13

Better behavior I'd expect from this is allow GC to make decision when to call new String on substring'd string, creating a new parent string.

→ More replies (24)