Hi there! A friend of mine found this on the net. I don't know if it's been posted before, and I don't know if all the tips are up to date, but it's good reading! Check out: http://www.glenmccl.com/ Hope you like it! //Kaspar
The site is not bad, but it's ancient! Use with caution. They use nothing later than JDK 1.1 and some performance discussion even takes JDK 1.0 as a benchmark - Java and especially JVMs have changed a lot since. While many techniques are still valid, the performance landscape has really changed and I wouldn't trust any of their data and comparisons. Also there's the odd instance of sloppy code. In their Search class here they manage to completely needlessly synchronize the method. Mmmm (Of course Java 1.1 collections render this discussion obsolete to some extent anyway). Some of their ideas are dangerous in most hands. - Peter
I'm not sure if I'd call the synchronization in the binary search "completely needless". Rather, if thread safety is a requirement, then additional synchronization is necessary - in fact, the code given does not go far enough. The fact that Vector is synchonized provides only partial protection from other threads - it prevents interruptions while one of the Vector methods is executing. But it does nothing to prevent interruptions elsewhere in the loop. What if another thread manages to call v.clear() while the search is running? The method will shortly throw an ArrayIndexOutOfBoundsException. More insidiously, if enough elements are inserted or deleted from the array so that the target object gets shifted outside the range [low, high] (while v.size() > high is still true) then the method will not throw any error, but the value returned will be incorrect. The value of mid will converge to either low or high - whichever is closer to the target - but will never go outside that range. In light of this, synchronizing the whole method seems to be a good idea - except that it is still insufficient. The problem is that the synchronization ends at the end of the method. So the the method returns the index of the found value, and now that caller knows this. What can the caller possibly do with the information? Access the element? Remove it? Insert a new element at this location? Since synchronization has just ended, there is no guarantee that when the next method is called, the target object will still be located at the index it was last found at. This may seem unlikely to be a problem on any given run - but it's the sort of bug that can lurk in a system for a long time, very hard to detect, but every so often causing mysterious failures which can't be easily replicated. This is really a fundamental problem with the method's API - there is simply no way that this method can be used in a thread-safe manner. Either the API should be redefined to include only larger-scoped tasks which can be meaningfully synchronized (e.g. find an index and insert a value there, or find an index and delete the value there), or synchronization should be dropped entirely and the method considered not thread-safe. Incomplete thread safety is worse than none at all. Sorry for the rant, which I admit has nothing really to do with performance. I just have bad memories of tracking down a bug along these lines once - I feel compelled to share.
"I'm not back." - Bill Harding, Twister
Joined: Jan 30, 2000
By the way "Nirvana" - please read our user name policy and re-register with a valid user name. Thanks. [This message has been edited by Jim Yingst (edited October 20, 2001).]
[This message has been edited by Nirvana C (edited October 21, 2001).] [This message has been edited by Nirvana C (edited October 21, 2001).]
Peter den Haan
Joined: Apr 20, 2000
Originally posted by Jim Yingst: I'm not sure if I'd call the synchronization in the binary search "completely needless".
The synchronized statement prevents multi-threaded execution of the Search() method which, given the total absence of state in the class, makes no sense whatsoever. Protection of the data structure being searched is a completely different matter. As you note, neither the "thread safety" of Vector nor any synchronization done within Search itself will help - it must be the responsibility of the caller, and the Search class should avoid the merest whiff of synchronization. One of he reasons that the Collections API is so much better than the Vector and Hashtable it supersedes. Don't apologise for the rant - it can't be repeated often enough. I see fine programmers stumble in the SCJD forum every day; don't even want to think about the production systems with threading problems. - Peter