-1

I want to measure time of getting elements of ArrayList. I know that using ArrayList we can get any element in constant time. I tried to check this writing code, but it returns wrong result for first element.

My code:

private long getGetTime(int position) {
    long elapsedTime = 0;
    long start = System.nanoTime();


    list.get(position);

    long end = System.nanoTime();
    elapsedTime = end - start;

    return elapsedTime;
}
preapareStructure();
System.out.println("read 0, time: " + getGetTime(0));
System.out.println("read size/2, time: " + getGetTime(list.size()/2));
System.out.println("read size-1, time: " + getGetTime(list.size()-1));

And this returns something like this: 

read 0, time: 10243
read size/2, time: 843
read size-1, time: 843
akcza
  • 43
  • 1
  • 1
  • 6

1 Answers1

1

An ArrayList has a backing array which will be bought into the hardware cache the first time it is accessed. So the cache is now considered warmed up. All accesses following the first one will then be retrieved from the cache which will obviously be faster.

MS Srikkanth
  • 3,829
  • 3
  • 19
  • 33
  • Accept the answer if that helped you :) – MS Srikkanth Apr 24 '16 at 15:12
  • More importantly the code has to be loaded which take far long. As it is getting a value it just wrote it should be in cache already. – Peter Lawrey Apr 24 '16 at 16:44
  • @PeterLawrey - to be fair the timer starts only after the code is loaded. So the measurement is more of an indication of a memory access rather than code loading time. – MS Srikkanth Apr 24 '16 at 16:59
  • Getting a cache miss on an array you just wrote to is highly unlikely, esp a 10 micro-second delay from one. Whereas warming up the code is far more likely. I assume `ArrayList.get()` hasn't been loaded yet. – Peter Lawrey Apr 24 '16 at 17:02
  • Oh you meant the get() method. Sorry about the misunderstanding. And it is also entirely possible for an array read to still be left with a cache miss after an array write if the current thread got time sliced. In a small program like this it is highly unlikely but again the OP didn't show us the rest of his code. So am not sure entirely. – MS Srikkanth Apr 24 '16 at 17:08