Java Collections

ListBenchmark

ArrayList vs LinkedList.

Benchmark = add_first

void addFirst(Blackhole bh, List<Integer> list) {
  int index = 0;
  list.add(index, 42);
  bh.consume(list);
  list.remove(index);
}

• Count = 5
• Mode = avgt
• Score = ns/op

List	Size	Score	Error
array	10	166,541	4,148
linked	10	6,489	2,188
array	100	174,727	5,411
linked	100	6,242	0,113
array	1000	271,130	41,222
linked	1000	6,328	0,268
array	10000	1402,587	616,112
linked	10000	6,284	0,196
array	100000	14037,404	142,396
linked	100000	7,927	5,275
array	1000000	145173,967	1813,870
linked	1000000	10,419	4,249

Benchmark = add_middle

void addMiddle(Blackhole bh, List<Integer> list) {
  int index = list.size() / 2;
  list.add(index, 42);
  bh.consume(list);
  list.remove(index);
}

• Count = 5
• Mode = avgt
• Units = ns/op

List	Size	Score	Error
array	10	168,258	2,193
linked	10	14,050	1,026
array	100	176,150	27,045
linked	100	102,300	4,534
array	1000	216,975	41,597
linked	1000	1 143,048	22,466
array	10000	740,289	321,971
linked	10000	11 854,545	1 522,868
array	100000	6 834,025	1 803,712
linked	100000	116 610,383	3 183,270
array	1000000	72 438,658	666,111
linked	1000000	1 466 923,007	1 090 339,894

Benchmark = add_last

void addLast(Blackhole bh, List<Integer> list) {
  list.add(42);
  bh.consume(list);
  int index = list.size() - 1;
  list.remove(index);
}

• Count = 5
• Mode = avgt
• Units = ns/op

List	Size	Score	Error
array	10	4,488	0,100
linked	10	5,965	0,099
array	100	4,507	0,054
linked	100	5,980	0,193
array	1000	4,489	0,074
linked	1000	5,975	0,193
array	10000	4,502	0,101
linked	10000	6,013	0,338
array	100000	4,492	0,033
linked	100000	7,433	8,296
array	1000000	4,500	0,087
linked	1000000	9,954	5,723

Benchmark = for_each

void forEach(Blackhole bh, List<Integer> list) {
  for (Integer element : list) {
      bh.consume(element);
  }
}

• Count = 5
• Mode = avgt
• Units = ns/op

List	Size	Score	Error
array	10	13,613	0,153
linked	10	14,408	0,100
array	100	128,542	1,563
linked	100	122,940	2,957
array	1000	1 227,973	20,511
linked	1000	1 386,562	14,682
array	10000	12 685,227	2 243,539
linked	10000	14 209,001	5 365,963
array	100000	133 826,368	1 865,819
linked	100000	136 968,251	1 589,867
array	1000000	1 340 493,816	23 125,453
linked	1000000	2 407 031,829	1 993 203,241

Benchmark = for_each_by_index

void forEachByIndex(Blackhole bh, List<Integer> list) {
  for (int i = 0; i < list.size(); i++) {
  bh.consume(list.get(i));
  }
}

• Count = 5
• Mode = avgt
• Units = ns/op

List	Size	Score	Error
array	10	9,703	0,092
linked	10	23,531	0,421
array	100	100,149	2,096
linked	100	1 467,424	29,160
array	1000	952,353	17,025
linked	1000	268 960,881	4 275,529
array	10000	9 475,338	73,683
linked	10000	29 112 736,364	1 044 288,404
array	100000	86 505,863	2 189,136
linked	100000	2 890 075 800,000	23 147 072,181
array	1000000	773 493,703	26 630,359
linked	1000000	305 859 002 180,000	39 599 782 358,621

Benchmark = for_each_by_stream

void forEachByStream(Blackhole bh, List<Integer> list) {
  list.stream().forEach(bh::consume);
}

• Count = 5
• Mode = avgt
• Units = ns/op

List	Size	Score	Error
array	10	14,109	0,389
linked	10	20,047	0,413
array	100	43,807	0,908
linked	100	147,886	18,365
array	1000	338,732	21,480
linked	1000	1 220,351	57,839
array	10000	3 414,240	112,897
linked	10000	13 499,665	3 038,101
array	100000	43 963,571	5 358,098
linked	100000	126 405,650	59 323,272
array	1000000	732 486,958	30 655,566
linked	1000000	2 119 994,538	572 508,138