1

The program is simple. It creates ArrayList and LinkedList and fills it with numbers. Then it adds 0 in the centres of lists and measures the time spent.

The problem is that the spent time may be changed 100 times by manipulations, which should not effect the speed. For example, if you uncomment dummyWorkOnList(), the speed of adding in the center of arrayList will increase from 166 millis to 1 millis on my pc.

The same effect could be accomplished by commented out everything related to LinkedList.

And also I can't effect linkedList speed by doing dummy work on it or comment out arrayList (It can be change 2 times, but not 100 times).

Is it a data prefetch works this way?

public static void main(String[] args) throws InterruptedException {

    int size = 1000000;

    ArrayList<Integer> arrayList = new ArrayList<>(size);
    LinkedList<Integer> linkedList = new LinkedList<>();
    feelTheList(arrayList, size);
    feelTheList(linkedList, size);

    //dummyWorkOnList(arrayList);

    time("arrayList", () -> addInTheCenter(arrayList));
    time("linkedList", () -> addInTheCenter(linkedList));

}

static void dummyWorkOnList(List<Integer> list) {
    for (int i = 0; i < list.size(); i++) {
        int oldNum = list.get(i);
        list.set(i, 0);
        list.set(i, oldNum);
    }
}

static void feelTheList(List<Integer> list, int size) {
    for (int i = 0; i < size; i++) list.add(i);
}

static void addInTheCenter(List<Integer> list) {
    list.add(list.size() / 2 - 1, 0);
}


static void time(String mark, Runnable runnable) {
    long nanos = System.nanoTime();
    runnable.run();
    long duration = System.nanoTime() - nanos;

    int seconds = (int) (duration / 1000000000);
    int milliseconds = (int) (duration / 1000000) % 1000;
    int nanoseconds = (int) (duration % 1000000);

    System.out.printf("%s spent %d secs, %d millis, %d nanos\n",
            mark, seconds, milliseconds, nanoseconds);
}
Artur Dumchev
  • 1,252
  • 14
  • 17
  • 2
    Your benchmark is horribly flawed. I am going mark this as a duplicate of a question about writing benchmarks in Java. When you have rewritten your benchmarks using [JMH](http://openjdk.java.net/projects/code-tools/jmh/) feel free to post an updated question. – Boris the Spider Sep 25 '16 at 14:01
  • you are traversing and doing manipulation twice so it's basiclly O(n) so depend upon the speed it took 166 millis to traverse list + twice manipulation inculded without it just a single operation which is O(1), as @BoristheSpider , useless benchmark – Pavneet_Singh Sep 25 '16 at 14:06
  • @Pavneet, ok, I understand that it was a horrible benchmark. I have just used JMH and had stable results, but I am trying to understand different thing. Could you please hint me, was the reason of the changing speed in my first code in the fact, that arrayList's items were cached in process memory and that's why it worked faster? As you see, in my code above I just iterate over arrayList and set the same items in it. And by this senseless action, program adds elements faster in arrayList. – Artur Dumchev Sep 25 '16 at 16:37

0 Answers0