For the record, C++'s standard library has algorithmic complexity as a part of the API. See the analogous std::basic_string::substr: http://en.cppreference.com/w/cpp/string/basic_string/substr
I've been bitten by std::list::size in pre C++11 code, as it was allowed to be O(n). But they were clear about it, the fault was mine. Now, it is guaranteed to be O(1): http://en.cppreference.com/w/cpp/container/list/size
I think it's likely that the change to String.substring was actually a good one. But I also agree with others that it was rolled out poorly, and should probably not have been in a fixpack release, as from how I see it, they changed the API.
"Returns a new string that is a substring of this string..."
Both implementations satisfy the API description so the API didn't change, the implementation did.
Optimizing your code based on the internals of a supposedly opaque data structure is a bad practice and if you get burned you only have yourself to blame.
You inescapably either:
1 - substring introduces a new string, creating lots of garbage since it's an incredibly common operation,
or
2 - substring saves garbage in many cases by having substring return sub-chunks of the full char array, but you will be unable to gc the full string as long as any substring remains reachable
The end-game for what you're suggesting is that all Java developers who care about performance, and do heavy string manipulation in their performance critical code, should re-implement the String class. I do not find that realistic.
That means that if there's no explicit running time guarantee given, your alternatives are to either not use that API at all, or depend on the running time you can observe or guess at.
Since people write APIs to be used, the former is obviously not what's intended. So it's pretty reasonable to consider any API without an explicit running time guarantee to have an implicit one along the lines of "this won't get vastly worse" because your only other choice is not to use it at all.
If your argument is that the String implementation change constitutes "unreasonably poor performance," as in...for most normal use cases, then that makes sense. I disagree with it, but it makes sense to argue that if you think that is what's happening. That goes beyond the implementation vs. contract discussion, and maybe that is the real issue many people have. Maybe some feel like the performance hit will affect so many use cases that are common for String, that it is an unreasonable performance change.
That's a bit naive. Let's say you want to code something which heavily depends on a String class. You test the standard one, it's fast enough. You decide you don't need to roll your own because of it.
Then it changes and it's no longer fast and changing it at this point might be a big pain. I mean, it's hard to predict that fundamental class in a language is going to change its performance characteristics.
If you are designing something that makes heavy use of String and String operations, and you know it needs to be as optimized as possible, you should consider whether or not you need a custom String solution as part of the design process. Of course there is a hypothetical scenario where a developer might run into this even when "doing everything right", but generally it can be avoided by being aware of these potential interactions and "program deliberately."
I am not saying there will never be times when you need to "just make it work" and reasonably can't account for everything like this. The real world does not always provide the opportunity to do everything "the right way." My point is just that, when you run into this issue, it should be understood that any issues caused by implementation changes aren't really the fault of the maintainers if they haven't broken the contract/interface, and it performs well under the use cases it is designed for.
And how do you do that? By writing a test case and seeing what the standard string does. Clearly, we expect things to change over time, so Oracle didn't necessarily do something underhanded here. But Oracle did change the behavior of String enough that people need to hear about it, and perhaps reconsider whether the standard string still does what they need to do.
So, if you are implementing something that deals with a large input string, and creates a large number of substrings, you know there could potentially be a performance impact depending on the way the implementation works with substrings. The API makes no performance or memory guarantees about substrings. If your application has strict performance requirements, you know you either need to find another solution, or "proceed with caution."
(We'll ignore the fact that every article I see about high performance Java talks about using memory buffers or some kind of "off heap" scheme specifically to get around the garbage collector).
I need a random number. I see that Java has a class for this ( http://docs.oracle.com/javase/8/docs/api/java/util/Random.ht... ). It doesn't guarantee anything about performance. It doesn't even really guarantee anything about the algorithm it will use in the future, but does say that it currently uses a linear congruential algorithm. Should I (1) write my own random number generator? (2) "proceed with caution"? or (3) write a test case, see if the thing is fast enough for what I want, and pay attention to any changes to java.util.Random in future releases? Personally, I generally pick (3).
It is similar to sorting implementations. If you have a small list of items in a collection, you might not care about how fast they can be sorted as long as it is "reasonably fast," so you can just use a built-in sort() function. If you know your collection will likely be larger than most, or you need them sorted as fast as possible, you might choose to implement your own sorting function, or use a different library which specifies a given performance level.
You could just use this hypothetical, built-in sort() for now, and deal with it later if any issues arise, or you could plan ahead if it is important and future proof the code now. The former would be "proceeding with caution" while the latter would be the more maintainable, "best practices" approach when you know performance is higher priority than normal.
If you "proceed with caution" you might run into a situation where the maintainers switch from insertion sort to heap sort, because in many (most?) use cases, heap sort is faster. However, your collection is often already sorted or mostly sorted, which is a case where heap sort performs much worse than insertion sort. Now your specific application has worse performance, but other applications have improved performance. If your collection needs to be sorted at a specific performance level, it is better (but not required) for you to implement a custom sort function, or use a library that is designed for your use case. This way you can have appropriate control over the performance.
If changes to the implementation of String could cause issues for you, you really should be using a custom solution anyway. A quick and dirty option would be to write a wrapper class which uses all of your preferred String hacks in a central location, and using that in place of String throughout your code. When String's implementation changes, you can update your hacks all in one place.
Here is some relevant advice from The Pragmatic Programmer: https://pragprog.com/the-pragmatic-programmer/extracts/coinc...