Java VM 1.6.0 Sorting Collections
in [Java Programming]
|
From: Lew on 10 Jun 2010 12:34 petek1976 wrote: > This prints about 0.58 seconds on average. How can I optimize this > reasonably? Note I am only timing the sort function. Using an array > instead of ArrayList is not an option. I tried Vector but it didn't > One would expect 'Vector' to be slightly slower than 'ArrayList'. > help. The equivalent C++ code (using vector) runs in about 0.37 > Java programs typically run at 50-105% of the speed of optimized C++ programs. What optimizations did you hand the JVM? One would expect that you at least specified "-server", yes? > seconds when built with optimization (g++ version 4.2.1 using -03 > optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7 > with 4 GB of ram. I also tried this example on Linux and saw no > difference. What is causing over 40% difference in speed? I must be > doing something wrong in my java [sic] code. > HotSpot takes something like 10,000 visits to the same code to compile to native code. Other optimizations may or may not take that many iterations. Run your loop 100,000 times or so without timing it, then repeat it under timing. This should prime the optimizer. Microbenchmarks are deceptive and usually not indicative of real-world performance. -- Lew
From: Tom Anderson on 10 Jun 2010 13:24 On Thu, 10 Jun 2010, Jim Janney wrote: > Jim Janney <jjanney(a)shell.xmission.com> writes: > >> You're copying the list to an array, sorting the array, and then >> copying the array back to the list. You might try coding up a simple >> quicksort that operates directly on the ArrayList to see what kind of >> times that gives you. > > The evil approach would be to use reflection to get the elementData > field in ArrayList, and call Arrays.sort directly on that. Your ideas are intriguing to me, and i wish to subscribe to your newsletter. tom -- They Set Up Us The Revolution - Now We Have Set Up It Them Back
From: Jim Janney on 10 Jun 2010 13:30 Lew <lew(a)lewscanon.com> writes: > petek1976 wrote: >> This prints about 0.58 seconds on average. How can I optimize this >> reasonably? Note I am only timing the sort function. Using an array >> instead of ArrayList is not an option. I tried Vector but it didn't >> > > One would expect 'Vector' to be slightly slower than 'ArrayList'. > >> help. The equivalent C++ code (using vector) runs in about 0.37 >> > > Java programs typically run at 50-105% of the speed of optimized C++ > programs. What optimizations did you hand the JVM? > > One would expect that you at least specified "-server", yes? > >> seconds when built with optimization (g++ version 4.2.1 using -03 >> optimization ). I am running on a MacBook Pro 2.66 GHz Intel Core i7 >> with 4 GB of ram. I also tried this example on Linux and saw no >> difference. What is causing over 40% difference in speed? I must be >> doing something wrong in my java [sic] code. >> > > HotSpot takes something like 10,000 visits to the same code to compile > to native code. Other optimizations may or may not take that many > iterations. > > Run your loop 100,000 times or so without timing it, then repeat it > under timing. This should prime the optimizer. > > Microbenchmarks are deceptive and usually not indicative of real-world > performance. Assuming n log(n) performance for the sorting algorithm, sorting a million-element list once gives you well over a million visits to the comparison code, and presumably to the inner loops of the sort. -- Jim Janney
From: Lew on 10 Jun 2010 13:49 Jim Janney wrote: > Assuming n log(n) performance for the sorting algorithm, sorting a > million-element list once gives you well over a million visits to the > comparison code, and presumably to the inner loops of the sort. > Good point, but if he doesn't have "-server" then it might not even do that optimization. -- Lew
From: Jim Janney on 10 Jun 2010 14:55
Tom Anderson <twic(a)urchin.earth.li> writes: > On Thu, 10 Jun 2010, Jim Janney wrote: > >> Jim Janney <jjanney(a)shell.xmission.com> writes: >> >>> You're copying the list to an array, sorting the array, and then >>> copying the array back to the list. You might try coding up a simple >>> quicksort that operates directly on the ArrayList to see what kind of >>> times that gives you. >> >> The evil approach would be to use reflection to get the elementData >> field in ArrayList, and call Arrays.sort directly on that. > > Your ideas are intriguing to me, and i wish to subscribe to your > newsletter. > "Why you should buy what you hate" http://online.wsj.com/article/SB10001424052748704025304575285000265955016.html -- Jim Janney |