3 ms·
Algorithmic complexity should be considered part of an API, because it is not mere "internal implementation". It has observable effects from the outside. When a
by scott_s 11y ago
Algorithmic complexity should be considered part of an API, because it is not mere "internal implementation". It has observable effects from the outside. When a function in an API goes from O(1) to O(n), that should be considered a breaking change.
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 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 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.
- jaawn 11y agoThis is a fair argument to make, but to my knowledge, this is not currently true of the Java API. It probably would make sense for some future version of the Java API to include O notation as part of the contract, at least for certain elements such as String. Since the performance expectations of Java have increased dramatically, it really would be beneficial to maintain stable-or-better performance (edit: for all use cases) across versions.
- jaawn 11y agoI guess my point is that, regardless of your opinions of what the API contract should include, you have to work with the current contract and plan/design/develop accordingly to avoid issues with library implementation changes.
- scott_s 11y agoI think it's unreasonable to assume programmers can cope with an API that is free to change its algorithmic complexity, particularly when that API is part of the core library for a language. In other words, I do not fault the Java programmers who assumed that the algorithmic complexity would not change in a minor update. 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.
- jaawn 11y agoLike I said, this is a really good point, and it supports including algorithmic complexity as part of the Java API in the future, but unless I am mistaken, it currently is not formally included.
- mikeash 11y agoThe thing is, you end up depending on algorithmic complexity whether or not it's guaranteed. There's simply no way around it. If this API changed to an exponential or factorial running time, almost all users of it would be completely broken. Since the running time isn't guaranteed then it hasn't technically broken any API contract, but pretty much the only way not to be broken by this change is not to use the API. 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.
- jaawn 11y agoI think you're alluding to a generic, implicit promise of reasonable performance. I definitely think this is a valid assumption to make, so you are right to point it out. Any API function needs to have reasonable performance, or else there is no point in using it and it is not serving its purpose. It is very true that people write APIs to be used, and if their performance is unreasonably slow, they won't be used. This makes complete sense. 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.
- spiralpolitik 11y agosubstring() was always defined in the 6 and 7 JavaDoc as: "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.
- sanderjd 11y agoIt's true that they didn't violate the API documentation, but it's also true that (as your parent suggests) it probably would have been better if the API documentation had explicitly stated that `substring()` is O(1), such that this change would have been breaking. At the very least it would have made it more obvious, and at most it would have forced them to make a new method for the new behavior.
- x0x0 11y agoIn reality, performance often matters. Then there's no way to avoid needing to understand what the implementation does. The java6 implementation was a big, somewhat well-known gotcha. Read in mb of data in a String, substring a couple kb out, and tada! you're still holding all those mb. 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
- jaawn 11y agoor 3 - stop trusting the internal String implementation to be as efficient as possible, write a wrapper you can update with the best method for the current version, never look back :-)
- x0x0 11y agowhy not reimplement the entire standard library so you understand and control all the performance characteristics? This can be just like writing C in the 90s: start by writing a hashmap, a string, an arraylist or equivalent, etc. Because your code is sensitive to every common data structure you use.