News for hackers. Stuff that matters.
Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @10:00AM (#9863970)
Based on all of the coding "best practices" books/blogs I've read, it is unwise to develop something which heavily depends on the internal implementation of the String class (or any library class). Many other commenters here are bemoaning the impacts the specific implementation of String will have on their existing applications. However, we should be designing based on the interface/contract presented, not specific implementation details of interfaces/libraries. Any optimization based on specific implementation details is "at your own risk."

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...

Re:Java 7 changed the structure of String by scott_s on Friday July 10, 2015 @10:55AM (#9864260)
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

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.

Re:Java 7 changed the structure of String by spiralpolitik on Friday July 10, 2015 @01:22PM (#9865362)
substring() 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.

Re:Java 7 changed the structure of String by x0x0 on Friday July 10, 2015 @03:01PM (#9866042)
In 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

Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @03:34PM (#9866249)
or 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 :-)
Re:Java 7 changed the structure of String by x0x0 on Friday July 10, 2015 @03:49PM (#9866317)
why 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.
Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @04:06PM (#9866420)
Because, most of the time, performance doesn't matter enough to justify it. Custom solutions are only necessary if you know performance is critical to your application's purpose, and that you need to squeeze as much out as possible. If that isn't the case, then you don't need to worry about the implementation details, because, in general, any performance changes won't matter.
Re:Java 7 changed the structure of String by sanderjd on Friday July 10, 2015 @01:41PM (#9865487)
It'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.
Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @11:02AM (#9864312)
This 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.
Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @11:06AM (#9864341)
I 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.
Re:Java 7 changed the structure of String by scott_s on Friday July 10, 2015 @11:18AM (#9864401)
I 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.

Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @11:36AM (#9864520)
Like 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.
Re:Java 7 changed the structure of String by mikeash on Friday July 10, 2015 @12:50PM (#9865112)
The 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.

Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @03:31PM (#9866229)
I 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.

Re:Java 7 changed the structure of String by mikeash on Friday July 10, 2015 @03:50PM (#9866325)
I have no opinion about this particular change, as I haven't looked into it much and I haven't done any Java in a while. I'm just pointing out that there is something of an implicit time complexity guarantee with any API, so the lack of an explicit API contract isn't enough to say that code which breaks due to a change is at fault.
Re:Java 7 changed the structure of String by bluecalm on Friday July 10, 2015 @10:33AM (#9864139)
>> However, we should be designing based on the interface/contract presented, not specific implementation details of interfaces/libraries. Any optimization based on specific implementation details is "at your own risk."

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.

Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @10:56AM (#9864274)
This is exactly the kind of "programming by coincidence" discussed at the link I provided.

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.

Re:Java 7 changed the structure of String by maxlybbert on Friday July 10, 2015 @12:23PM (#9864895)
> 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.

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.

Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @12:33PM (#9864984)
One method would be to have an informal heuristic you use when you're about to call a library: are the performance characteristics I need guaranteed by this library? If yes: proceed, if no: use a different solution or proceed with caution.

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."

Re:Java 7 changed the structure of String by maxlybbert on Friday July 10, 2015 @01:18PM (#9865326)
In this case, performance shouldn't have changed much -- at least in a big-O sense -- but memory use did. And the JDK guys have been swearing for years that the garbage collector handles that for you, so I'm not sure alarm bells would have gone off.

(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).

Re:Java 7 changed the structure of String by jaawn on Friday July 10, 2015 @03:21PM (#9866174)
I would usually choose option 2 or 3, but that is because usually small performance discrepancies are unimportant. If performance is paramount at the point in the code where the library is used, I would opt for (1) or a fourth option you omitted: find a library which has already implemented a performance-driven solution.

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.

Re:Java 7 changed the structure of String by flowerjeni on Monday July 13, 2015 @07:01AM (#9877332)
One method would be to have an informal heuristic you use when you're about to call a library: are the performance characteristics I need guaranteed by this library? If yes: proceed, if no: use a different solution or proceed with caution.http://www.trainingintambaram.in/dot-net-training-in-chennai...
Re:Java 7 changed the structure of String by dhirsatha101 on Monday July 13, 2015 @06:53AM (#9877317)
Thanks for sharing....its very informativehttp://www.trainingintambaram.in/perl-training-in-chennai.ht...