Cache effects on benchmark
← Thread:Talk:K-NN algorithm benchmark/Cache effects on benchmark/reply (2)
Running them all at the same time could make sense, but I would suggest being if you do that, because the order that they get run in may matter. Even when running them one at a time in sequence, I've recall noticing that the order in which they are run could very slightly impact the apparent performance, I suspect due to caching, JIT, and/or garbage collection characteristics. It's been a while, but IIRC the System.gc() call I have in there between running different trees was to lessen that effect.
Cache performance is one of those things that's tricky with Robocode, because your robot is also sharing the CPU with another bot which could be doing who knows that with it's memory accesses. For that reason I wouldn't trust optimizations for better caching behavior to necessarily pan out in practice with bots. I may be wrong about that though.
One could put it in a reference bot yeah, though the tests would be far slower and less consistent, thus requiring a much greater number of test iterations to have a reliable result.
I wrote a quick benchmark and threw it in my main method. Some tweaks and improvements (putting the distance functions in methods, using a binary search for the results array) have given me big improvements at lower tree sizes:
Config: No JIT Warmup Tested on random data. Training and testing points shared across iterations. Searches interleaved. Num points: 20000 Num searches: 200 Dimensions: 12 Num Neighbours: 40 Accuracy: 100% Iteration: 1/3 This tree add avg: 3092 ns Reds tree add avg: 2216 ns This tree knn avg: 809965 ns Reds tree knn avg: 1380366 ns This tree knn max: 10844097 ns Reds tree knn max: 11005183 ns Accuracy: 100% Iteration: 2/3 This tree add avg: 1259 ns Reds tree add avg: 846 ns This tree knn avg: 643037 ns Reds tree knn avg: 1119268 ns This tree knn max: 979013 ns Reds tree knn max: 1787566 ns Accuracy: 100% Iteration: 3/3 This tree add avg: 1146 ns Reds tree add avg: 800 ns This tree knn avg: 641163 ns Reds tree knn avg: 1099657 ns This tree knn max: 1318587 ns Reds tree knn max: 1782212 ns
Note, I hacked the RedGen2 tree to not check for NaN in the distance functions so that they are on equal footing.
Ahh nice. Out of curiosity, any reason you're comparing against my 2nd gen tree? My 3rd gen tree was a bit faster at least in the tests I did.
I don't have it installed yet, and I thought I'll do a proper bench when I add my tree to the whole bench framework. Do you still have the code that does those nice charts tracking the trees through time? Is that what's in the KNN.jar? Yes it is! Great.
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 do not have permission to edit this page, for the following reasons:
You can view and copy the source of this page.
Return to Thread:Talk:K-NN algorithm benchmark/Cache effects on benchmark/reply (10).
