1e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin/*
2e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * Copyright (C) 2012 Google Inc.
3e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin *
4e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License");
5e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * you may not use this file except in compliance with the License.
6e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * You may obtain a copy of the License at
7e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin *
8e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * http://www.apache.org/licenses/LICENSE-2.0
9e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin *
10e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * Unless required by applicable law or agreed to in writing, software
11e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * distributed under the License is distributed on an "AS IS" BASIS,
12e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * See the License for the specific language governing permissions and
14e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * limitations under the License.
15e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin */
16e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
17e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinpackage examples;
18e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
19e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport com.google.caliper.BeforeExperiment;
20e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport com.google.caliper.Benchmark;
21e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport com.google.caliper.Param;
22e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
23e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport java.util.ArrayList;
24e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport java.util.Iterator;
25e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport java.util.LinkedList;
26e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinimport java.util.List;
27e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
28e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin/**
29e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin * Measures performance of list operations.
30e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin */
31e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffinpublic class ListModificationBenchmark {
32e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
33e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  private enum Element {
34e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    INSTANCE,
35e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
36e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  private enum ListImpl {
37e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    Array {
38e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      @Override List<Element> create() {
39e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin        return new ArrayList<Element>();
40e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      }
41e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    },
42e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    Linked {
43e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      @Override List<Element> create() {
44e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin        return new LinkedList<Element>();
45e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      }
46e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    };
47e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
48e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    abstract List<Element> create();
49e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
50e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
51e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Param({"10", "100", "1000", "10000"})
52e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  private int size;
53e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
54e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Param({"Array", "Linked"})
55e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  private ListImpl implementation;
56e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
57e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  private List<Element> list;
58e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
59e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @BeforeExperiment void setUp() throws Exception {
60e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    list = implementation.create();
61e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    for (int i = 0; i < size; i++) {
62e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.add(Element.INSTANCE);
63e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    }
64e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
65e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
66e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Benchmark void populate(int reps) throws Exception {
67e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    for (int rep = 0; rep < reps; rep++) {
68e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      List<Element> list = implementation.create();
69e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      for (int i = 0; i < size; i++) {
70e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin        list.add(Element.INSTANCE);
71e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      }
72e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    }
73e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
74e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
75e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Benchmark void iteration(int reps) {
76e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    for (int rep = 0; rep < reps; rep++) {
77e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      Iterator<Element> iterator = list.iterator();
78e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      while (iterator.hasNext()) {
79e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin        iterator.next();
80e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      }
81e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    }
82e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
83e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
84e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Benchmark void headAddRemove(int reps) {
85e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    for (int rep = 0; rep < reps; rep++) {
86e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.add(0, Element.INSTANCE);
87e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.remove(0);
88e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    }
89e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
90e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
91e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Benchmark void middleAddRemove(int reps) {
92e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    int index = size / 2;
93e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    for (int rep = 0; rep < reps; rep++) {
94e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.add(index, Element.INSTANCE);
95e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.remove(index);
96e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    }
97e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
98e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin
99e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  @Benchmark void tailAddRemove(int reps) {
100e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    int index = size - 1;
101e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    for (int rep = 0; rep < reps; rep++) {
102e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.add(Element.INSTANCE);
103e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin      list.remove(index);
104e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin    }
105e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin  }
106e236301e5fc778bffe1748ed80d7936e6c807012Paul Duffin}
107