Regarding PrioQueue
Because of how Java runs the JIT and GC in separate threads, I just tried a couple quick things:
If I force Java to run on only one core, I get this result:
- #1 Skilgannon's Cache-hit KDTree [0.0334] - #2 Rednaxela's kd-tree (3rd gen) [0.0343] - #3 Rednaxela's kd-tree (2nd gen) [0.0375] - #4 Voidious' Linear search [0.5844]
If I force Java to run on two cores, I get this result:
- #1 Rednaxela's kd-tree (3rd gen) [0.0280] - #2 Skilgannon's Cache-hit KDTree [0.0304] - #3 Rednaxela's kd-tree (2nd gen) [0.0341] - #4 Voidious' Linear search [0.4806]
Compared to allowing all 6 cores, only allowing 2 cores improved the linear search result (more dramatic than I expected!), but it hurt all of the kd-trees still.
Maybe that's why my linear search score is so much better than yours?
BTW, newest code is a little bit faster.
So, it turns out that if I use Oracle Java in Windows instead of OpenJDK on Linux, the performance is pretty different:
- #1 Skilgannon's Cache-hit KDTree [0.0275] - #2 Rednaxela's kd-tree (3rd gen) [0.0290] - #3 Rednaxela's kd-tree (2nd gen) [0.0309] - #4 Voidious' Linear search [0.5553]
The relative performance of things looks much more similar to what you saw, with a smaller difference between my 3rd and 2nd gen tree, with your one performing better.
Between OracleJava/Windows and OpenJDK/Linux, my 3rd gen tree and your cache-hit tree, swap places it seems.
java version "1.7.0_25" Java(TM) SE Runtime Environment (build 1.7.0_25-b17) Java HotSpot(TM) 64-Bit Server VM (build 23.25-b01, mixed mode)
(Also turns out the server JVM is much better suited for the kd-tree test than the client JVM. Edited this post to switch the results to those using the server JVM)
