Regarding PrioQueue

Jump to navigation Jump to search

Here's what I get:

BEST RESULT:
 - #1 Skilgannon's Cache-hit KDTree [0.0285]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0311]
 - #3 Rednaxela's kd-tree (2nd gen) [0.0326]
 - #4 Voidious' Linear search [0.4172]

Strange, it must have to do with cache sizes and RAM speeds. Here is my CPU. I have 6GB of DDR3-1333, and java -version gives me

java version "1.7.0"
Java(TM) SE Runtime Environment (build 1.7.0-b147)
Java HotSpot(TM) 64-Bit Server VM (build 21.0-b17, mixed mode)

I also have an SSD, if that changes anything. Anything stand out to you?

Skilgannon (talk)09:10, 18 July 2013

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.

Edit: I also find it very interesting that you get better performance numbers for the linear search, whereas I get better performance numbers for all of the trees except yours is about the same, plus the gap between my 3rd and 2nd gen tree is much larger for me than it is for you.

Edit: Since you uploaded a small update to your code this morning I tried that also. The change was small, going from 0.0288 changing to 0.0284.

Rednaxela (talk)13:53, 18 July 2013
 

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.

Rednaxela (talk)14:57, 18 July 2013

Maybe that's why my linear search score is so much better than yours?

BTW, newest code is a little bit faster.

Skilgannon (talk)15:39, 18 July 2013

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)

Rednaxela (talk)02:43, 19 July 2013

Client JVM is not designed for heavy processing, like how the rumble is.

MN (talk)22:51, 19 July 2013