Hello, community! In the attachments, you may find a text file summarizing the JMH benchmark of my IndexedLinkedList vs. ExtendedTreeList [1]. It turned out that my list implementation easily outperforms [1].
What do you think? Should I do a PR? References: [1] https://github.com/coderodde/IndexedLinkedList/blob/main/src/main/java/io/github/coderodde/util/ExtendedTreeList.java PS. ExtendedTreeList is a subclass of TreeList that implements some essential missing methods such as subList(..., ...).clear() and so on.
Benchmark (batchSize) (impl) (size) Mode Cnt Score Error Units JMHBenchmark.append 10 IndexedLinkedList 1000 avgt 5 64,915 ± 6,143 ns/op JMHBenchmark.append 10 IndexedLinkedList 10000 avgt 5 279,072 ± 284,605 ns/op JMHBenchmark.append 10 IndexedLinkedList 100000 avgt 5 487,008 ± 207,730 ns/op JMHBenchmark.append 10 ExtendedTreeList 1000 avgt 5 291,501 ± 205,052 ns/op JMHBenchmark.append 10 ExtendedTreeList 10000 avgt 5 866,173 ± 105,774 ns/op JMHBenchmark.append 10 ExtendedTreeList 100000 avgt 5 2880,122 ± 4612,962 ns/op JMHBenchmark.append 100 IndexedLinkedList 1000 avgt 5 67,155 ± 8,217 ns/op JMHBenchmark.append 100 IndexedLinkedList 10000 avgt 5 287,409 ± 319,976 ns/op JMHBenchmark.append 100 IndexedLinkedList 100000 avgt 5 476,247 ± 376,471 ns/op JMHBenchmark.append 100 ExtendedTreeList 1000 avgt 5 315,245 ± 260,032 ns/op JMHBenchmark.append 100 ExtendedTreeList 10000 avgt 5 861,418 ± 436,281 ns/op JMHBenchmark.append 100 ExtendedTreeList 100000 avgt 5 2771,020 ± 6279,912 ns/op JMHBenchmark.appendCollection 10 IndexedLinkedList 1000 avgt 5 141,500 ± 10,995 ns/op JMHBenchmark.appendCollection 10 IndexedLinkedList 10000 avgt 5 561,708 ± 739,892 ns/op JMHBenchmark.appendCollection 10 IndexedLinkedList 100000 avgt 5 615,461 ± 565,454 ns/op JMHBenchmark.appendCollection 10 ExtendedTreeList 1000 avgt 5 842,405 ± 484,109 ns/op JMHBenchmark.appendCollection 10 ExtendedTreeList 10000 avgt 5 2672,787 ± 1163,112 ns/op JMHBenchmark.appendCollection 10 ExtendedTreeList 100000 avgt 5 15077,101 ± 23355,881 ns/op JMHBenchmark.appendCollection 100 IndexedLinkedList 1000 avgt 5 983,205 ± 95,252 ns/op JMHBenchmark.appendCollection 100 IndexedLinkedList 10000 avgt 5 1120,761 ± 311,354 ns/op JMHBenchmark.appendCollection 100 IndexedLinkedList 100000 avgt 5 1406,768 ± 693,224 ns/op JMHBenchmark.appendCollection 100 ExtendedTreeList 1000 avgt 5 2460,425 ± 542,012 ns/op JMHBenchmark.appendCollection 100 ExtendedTreeList 10000 avgt 5 4689,977 ± 1301,675 ns/op JMHBenchmark.appendCollection 100 ExtendedTreeList 100000 avgt 5 16343,768 ± 22142,536 ns/op JMHBenchmark.insertCollectionMiddle 10 IndexedLinkedList 1000 avgt 5 250,523 ± 11,304 ns/op JMHBenchmark.insertCollectionMiddle 10 IndexedLinkedList 10000 avgt 5 1061,421 ± 469,517 ns/op JMHBenchmark.insertCollectionMiddle 10 IndexedLinkedList 100000 avgt 5 4577,651 ± 701,934 ns/op JMHBenchmark.insertCollectionMiddle 10 ExtendedTreeList 1000 avgt 5 2316,450 ± 258,595 ns/op JMHBenchmark.insertCollectionMiddle 10 ExtendedTreeList 10000 avgt 5 5083,625 ± 592,791 ns/op JMHBenchmark.insertCollectionMiddle 10 ExtendedTreeList 100000 avgt 5 16081,564 ± 15040,489 ns/op JMHBenchmark.insertCollectionMiddle 100 IndexedLinkedList 1000 avgt 5 1265,761 ± 125,001 ns/op JMHBenchmark.insertCollectionMiddle 100 IndexedLinkedList 10000 avgt 5 1668,641 ± 358,181 ns/op JMHBenchmark.insertCollectionMiddle 100 IndexedLinkedList 100000 avgt 5 5300,504 ± 482,673 ns/op JMHBenchmark.insertCollectionMiddle 100 ExtendedTreeList 1000 avgt 5 18522,967 ± 1248,021 ns/op JMHBenchmark.insertCollectionMiddle 100 ExtendedTreeList 10000 avgt 5 26590,772 ± 3384,152 ns/op JMHBenchmark.insertCollectionMiddle 100 ExtendedTreeList 100000 avgt 5 43263,878 ± 11512,113 ns/op JMHBenchmark.insertMiddle 10 IndexedLinkedList 1000 avgt 5 186,700 ± 25,527 ns/op JMHBenchmark.insertMiddle 10 IndexedLinkedList 10000 avgt 5 1025,135 ± 408,541 ns/op JMHBenchmark.insertMiddle 10 IndexedLinkedList 100000 avgt 5 4721,745 ± 1479,694 ns/op JMHBenchmark.insertMiddle 10 ExtendedTreeList 1000 avgt 5 773,963 ± 296,235 ns/op JMHBenchmark.insertMiddle 10 ExtendedTreeList 10000 avgt 5 2444,344 ± 901,709 ns/op JMHBenchmark.insertMiddle 10 ExtendedTreeList 100000 avgt 5 7389,522 ± 7972,389 ns/op JMHBenchmark.insertMiddle 100 IndexedLinkedList 1000 avgt 5 176,053 ± 9,348 ns/op JMHBenchmark.insertMiddle 100 IndexedLinkedList 10000 avgt 5 1166,690 ± 979,258 ns/op JMHBenchmark.insertMiddle 100 IndexedLinkedList 100000 avgt 5 5014,233 ± 2873,290 ns/op JMHBenchmark.insertMiddle 100 ExtendedTreeList 1000 avgt 5 578,431 ± 594,113 ns/op JMHBenchmark.insertMiddle 100 ExtendedTreeList 10000 avgt 5 2263,821 ± 753,650 ns/op JMHBenchmark.insertMiddle 100 ExtendedTreeList 100000 avgt 5 7850,731 ± 8674,814 ns/op JMHBenchmark.popBack 10 IndexedLinkedList 1000 avgt 5 175,117 ± 6,589 ns/op JMHBenchmark.popBack 10 IndexedLinkedList 10000 avgt 5 904,957 ± 346,372 ns/op JMHBenchmark.popBack 10 IndexedLinkedList 100000 avgt 5 1912,568 ± 1899,566 ns/op JMHBenchmark.popBack 10 ExtendedTreeList 1000 avgt 5 504,600 ± 658,946 ns/op JMHBenchmark.popBack 10 ExtendedTreeList 10000 avgt 5 2170,747 ± 3098,729 ns/op JMHBenchmark.popBack 10 ExtendedTreeList 100000 avgt 5 24292,381 ± 37328,087 ns/op JMHBenchmark.popBack 100 IndexedLinkedList 1000 avgt 5 181,243 ± 46,263 ns/op JMHBenchmark.popBack 100 IndexedLinkedList 10000 avgt 5 1103,716 ± 355,925 ns/op JMHBenchmark.popBack 100 IndexedLinkedList 100000 avgt 5 3028,288 ± 3924,836 ns/op JMHBenchmark.popBack 100 ExtendedTreeList 1000 avgt 5 472,842 ± 716,904 ns/op JMHBenchmark.popBack 100 ExtendedTreeList 10000 avgt 5 2046,884 ± 624,399 ns/op JMHBenchmark.popBack 100 ExtendedTreeList 100000 avgt 5 15952,385 ± 19123,110 ns/op JMHBenchmark.popFront 10 IndexedLinkedList 1000 avgt 5 145,952 ± 28,667 ns/op JMHBenchmark.popFront 10 IndexedLinkedList 10000 avgt 5 797,268 ± 381,810 ns/op JMHBenchmark.popFront 10 IndexedLinkedList 100000 avgt 5 4528,938 ± 780,726 ns/op JMHBenchmark.popFront 10 ExtendedTreeList 1000 avgt 5 499,200 ± 403,122 ns/op JMHBenchmark.popFront 10 ExtendedTreeList 10000 avgt 5 2700,327 ± 393,460 ns/op JMHBenchmark.popFront 10 ExtendedTreeList 100000 avgt 5 9761,271 ± 17069,245 ns/op JMHBenchmark.popFront 100 IndexedLinkedList 1000 avgt 5 132,961 ± 15,294 ns/op JMHBenchmark.popFront 100 IndexedLinkedList 10000 avgt 5 1146,928 ± 341,277 ns/op JMHBenchmark.popFront 100 IndexedLinkedList 100000 avgt 5 5064,484 ± 2868,024 ns/op JMHBenchmark.popFront 100 ExtendedTreeList 1000 avgt 5 477,664 ± 270,456 ns/op JMHBenchmark.popFront 100 ExtendedTreeList 10000 avgt 5 2739,101 ± 883,310 ns/op JMHBenchmark.popFront 100 ExtendedTreeList 100000 avgt 5 11638,890 ± 26097,166 ns/op JMHBenchmark.popRandom 10 IndexedLinkedList 1000 avgt 5 265,022 ± 36,573 ns/op JMHBenchmark.popRandom 10 IndexedLinkedList 10000 avgt 5 761,867 ± 250,162 ns/op JMHBenchmark.popRandom 10 IndexedLinkedList 100000 avgt 5 3916,704 ± 1320,950 ns/op JMHBenchmark.popRandom 10 ExtendedTreeList 1000 avgt 5 701,184 ± 185,988 ns/op JMHBenchmark.popRandom 10 ExtendedTreeList 10000 avgt 5 3060,373 ± 1734,822 ns/op JMHBenchmark.popRandom 10 ExtendedTreeList 100000 avgt 5 16123,595 ± 27665,152 ns/op JMHBenchmark.popRandom 100 IndexedLinkedList 1000 avgt 5 243,823 ± 11,005 ns/op JMHBenchmark.popRandom 100 IndexedLinkedList 10000 avgt 5 738,733 ± 298,184 ns/op JMHBenchmark.popRandom 100 IndexedLinkedList 100000 avgt 5 3713,617 ± 1367,575 ns/op JMHBenchmark.popRandom 100 ExtendedTreeList 1000 avgt 5 758,344 ± 611,526 ns/op JMHBenchmark.popRandom 100 ExtendedTreeList 10000 avgt 5 3223,332 ± 3038,879 ns/op JMHBenchmark.popRandom 100 ExtendedTreeList 100000 avgt 5 15784,077 ± 20702,279 ns/op JMHBenchmark.prepend 10 IndexedLinkedList 1000 avgt 5 105,050 ± 7,953 ns/op JMHBenchmark.prepend 10 IndexedLinkedList 10000 avgt 5 1057,347 ± 460,614 ns/op JMHBenchmark.prepend 10 IndexedLinkedList 100000 avgt 5 4826,894 ± 1124,418 ns/op JMHBenchmark.prepend 10 ExtendedTreeList 1000 avgt 5 418,501 ± 205,158 ns/op JMHBenchmark.prepend 10 ExtendedTreeList 10000 avgt 5 2683,429 ± 771,538 ns/op JMHBenchmark.prepend 10 ExtendedTreeList 100000 avgt 5 7338,571 ± 9039,416 ns/op JMHBenchmark.prepend 100 IndexedLinkedList 1000 avgt 5 104,339 ± 3,294 ns/op JMHBenchmark.prepend 100 IndexedLinkedList 10000 avgt 5 1034,958 ± 387,422 ns/op JMHBenchmark.prepend 100 IndexedLinkedList 100000 avgt 5 4590,057 ± 1512,345 ns/op JMHBenchmark.prepend 100 ExtendedTreeList 1000 avgt 5 527,600 ± 605,331 ns/op JMHBenchmark.prepend 100 ExtendedTreeList 10000 avgt 5 2672,238 ± 472,297 ns/op JMHBenchmark.prepend 100 ExtendedTreeList 100000 avgt 5 6611,444 ± 10855,412 ns/op JMHBenchmark.prependCollection 10 IndexedLinkedList 1000 avgt 5 184,307 ± 14,441 ns/op JMHBenchmark.prependCollection 10 IndexedLinkedList 10000 avgt 5 1512,808 ± 358,081 ns/op JMHBenchmark.prependCollection 10 IndexedLinkedList 100000 avgt 5 4928,453 ± 521,244 ns/op JMHBenchmark.prependCollection 10 ExtendedTreeList 1000 avgt 5 2433,226 ± 1091,159 ns/op JMHBenchmark.prependCollection 10 ExtendedTreeList 10000 avgt 5 6773,686 ± 3413,931 ns/op JMHBenchmark.prependCollection 10 ExtendedTreeList 100000 avgt 5 15591,935 ± 18532,698 ns/op JMHBenchmark.prependCollection 100 IndexedLinkedList 1000 avgt 5 1220,728 ± 150,346 ns/op JMHBenchmark.prependCollection 100 IndexedLinkedList 10000 avgt 5 1982,102 ± 368,925 ns/op JMHBenchmark.prependCollection 100 IndexedLinkedList 100000 avgt 5 5809,664 ± 952,962 ns/op JMHBenchmark.prependCollection 100 ExtendedTreeList 1000 avgt 5 20360,692 ± 2253,389 ns/op JMHBenchmark.prependCollection 100 ExtendedTreeList 10000 avgt 5 28826,440 ± 5104,294 ns/op JMHBenchmark.prependCollection 100 ExtendedTreeList 100000 avgt 5 44926,148 ± 23744,682 ns/op JMHBenchmark.randomAccess 10 IndexedLinkedList 1000 avgt 5 214,638 ± 38,972 ns/op JMHBenchmark.randomAccess 10 IndexedLinkedList 10000 avgt 5 630,966 ± 163,082 ns/op JMHBenchmark.randomAccess 10 IndexedLinkedList 100000 avgt 5 2939,176 ± 940,571 ns/op JMHBenchmark.randomAccess 10 ExtendedTreeList 1000 avgt 5 391,773 ± 186,860 ns/op JMHBenchmark.randomAccess 10 ExtendedTreeList 10000 avgt 5 1848,070 ± 624,529 ns/op JMHBenchmark.randomAccess 10 ExtendedTreeList 100000 avgt 5 9676,841 ± 22782,935 ns/op JMHBenchmark.randomAccess 100 IndexedLinkedList 1000 avgt 5 208,253 ± 12,756 ns/op JMHBenchmark.randomAccess 100 IndexedLinkedList 10000 avgt 5 648,338 ± 259,347 ns/op JMHBenchmark.randomAccess 100 IndexedLinkedList 100000 avgt 5 3187,098 ± 1225,270 ns/op JMHBenchmark.randomAccess 100 ExtendedTreeList 1000 avgt 5 376,236 ± 256,290 ns/op JMHBenchmark.randomAccess 100 ExtendedTreeList 10000 avgt 5 1833,622 ± 593,532 ns/op JMHBenchmark.randomAccess 100 ExtendedTreeList 100000 avgt 5 9867,902 ± 23396,900 ns/op JMHBenchmark.removeRangeSubListClear 10 IndexedLinkedList 1000 avgt 5 1457,426 ± 55,925 ns/op JMHBenchmark.removeRangeSubListClear 10 IndexedLinkedList 10000 avgt 5 12203,881 ± 1170,105 ns/op JMHBenchmark.removeRangeSubListClear 10 IndexedLinkedList 100000 avgt 5 129328,393 ± 26439,760 ns/op JMHBenchmark.removeRangeSubListClear 100 IndexedLinkedList 1000 avgt 5 1484,491 ± 75,750 ns/op JMHBenchmark.removeRangeSubListClear 100 IndexedLinkedList 10000 avgt 5 12765,925 ± 1704,982 ns/op JMHBenchmark.removeRangeSubListClear 100 IndexedLinkedList 100000 avgt 5 132070,379 ± 10856,310 ns/op
--------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
