Regarding PrioQueue

Here's the CPU I'm using. That was with 8GB of DDR3 running at 1066MHz, but that's intentionally underclocked by a lot. If I clock my memory up to it's rated frequency of 1600MHz the result is as follows:

 - #1 Rednaxela's kd-tree (3rd gen) [0.0276]
 - #2 Skilgannon's Cache-hit KDTree [0.0288]
 - #3 Rednaxela's kd-tree (2nd gen) [0.0340]
 - #4 Voidious' Linear search [0.5593]

A little faster all around, but not much difference with memory clock rate it seems.

The AMD Phenom II I'm using has 6MB of L3 cache, 512kB of L2 cache per-core, completely seperate.

The Intel Core i5 you're using has 3MB of L3 cache, 256kB of L2 cache per-core, though it looks like supposedly intel has some method of allowing the two cores to access eachother's L2 cache.

Java version:

java version "1.7.0_40"
OpenJDK Runtime Environment (IcedTea 2.4.1) (ArchLinux build 7.u40_2.4.1-1-x86_64)
OpenJDK 64-Bit Server VM (build 24.0-b50, mixed mode)

I have my root partition running on an SSD with the /home partition running on a spinning disk, but I doubt the disk situation affects this benchmark at all in any case.