0

I am trying to time various algorithms for getting the intersection of two lists. On the O(n^2) algorithm I'm running into a peculiar problem where the algorithm takes more time for lists of size 2, 4, 8, and 16 than it does for lists of size 32 at which point the number begins growing as expected. The function runs a few thousand times on randomly generated lists but the times are determined by running 

startTime = Thread.getCurrentThreadCpuTime();
int intersections = intersectionAlgorithm(List1, List2); //O(n^2) algorithm
endTime = Thread.getCurrentThreadCpuTime();
runningTime = (endTime - startTime);

It's a minor issue but it repeats every time and is probably affecting the results elsewhere where it can't be noticed. I've tried running the program with different compile thresholds as well and that hasn't done me any help. How can I get an accurate timing of this function?

pashakondratyev
  • 9
  • 2
  • I'm guessing it's either one of two things: (1) You're using a collection that only needs to resize for 32 or more items, or (2) JIT statistics don't start working their magic until the JVM is "warmed up". You are probably seeing the pitfalls of small test cases. – duffymo Sep 17 '15 at 18:13
  • The collections aren't being created in the timed run and I've tried warming up by changing the compile threshold, as well as running the test 1000 times for the smaller lists. – pashakondratyev Sep 17 '15 at 18:25

0 Answers0