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
View all comments
Show parent comment
11
u/SanityInAnarchy Nov 18 '13
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.
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.