Cache effects on benchmark
Ah, looks like KNN.jar that's uploaded on the wiki isn't quite 100% up-to-date. A couple days after the KNN.jar uploaded to the wiki was last updated I made a few minor changes. See here for the latest source [1]
You got that just in time, your latest code is now in!
So on the vanilla Diamond-gun data benchmark it seems to be pretty much tied with your Gen2 and Gen3, changing places from run to run. This is what I saw mostly though, your Gen2 slightly above Gen3, and my cache-hit tree in the middle:
BEST RESULT: - #1 Rednaxela's kd-tree (2nd gen) [0.0317] - #2 Skilgannon's Cache-hit KDTree [0.0340] - #3 Rednaxela's kd-tree (3rd gen) [0.0356] - #4 Voidious' Linear search [0.4175]
So, I wrote some code which instantiates, does operations on, then destroys an array of 1k doubles and 1k ints, and makes it a dependency of a later println. This was the result:
RESULT << k-nearest neighbours search with Voidious' Linear search >> : Average searching time = 0.4198 miliseconds : Average worst searching time = 14.7468 miliseconds : Average adding time = 1.6292 microseconds : Accuracy = 100.0% RESULT << k-nearest neighbours search with Rednaxela's kd-tree (2nd gen) >> : Average searching time = 0.0333 miliseconds : Average worst searching time = 1.7135 miliseconds : Average adding time = 1.7662 microseconds : Accuracy = 100.0% RESULT << k-nearest neighbours search with Skilgannon's Cache-hit KDTree >> : Average searching time = 0.0312 miliseconds : Average worst searching time = 1.3695 miliseconds : Average adding time = 2.7642 microseconds : Accuracy = 100.0% RESULT << k-nearest neighbours search with Rednaxela's kd-tree (3rd gen) >> : Average searching time = 0.0317 miliseconds : Average worst searching time = 1.2998 miliseconds : Average adding time = 2.1558 microseconds : Accuracy = 100.0% BEST RESULT: - #1 Skilgannon's Cache-hit KDTree [0.0312] - #2 Rednaxela's kd-tree (3rd gen) [0.0317] - #3 Rednaxela's kd-tree (2nd gen) [0.0333] - #4 Voidious' Linear search [0.4198]
It now comes first every single time I run. So it seems my cache-hit design has paid off (slightly) =)
