Skip to content

Instantly share code, notes, and snippets.

@erikrozendaal

erikrozendaal/delete

Last active December 18, 2015 06:59
Show Gist options
  • Save erikrozendaal/5743636 to your computer and use it in GitHub Desktop.
Save erikrozendaal/5743636 to your computer and use it in GitHub Desktop.
Download ZIP
Performance of initial implementation in-memory B-Tree vs the standard Scala Red-Black Tree implementation used by TreeSet. The B-Tree is about 5 times more memory efficient, so it works better for large sets due to memory locality effects. Update: initial delete implementation + benchmark numbers added.
Raw
delete
Benchmark comparison (in 9.612 s): delete 1 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.76712 95% CI 0.73631 - 0.79793 (n=20)
btree 78.60 ns 95% CI 75.96 ns - 81.25 ns
treeset 60.30 ns 95% CI 58.98 ns - 61.62 ns
Benchmark comparison (in 13.16 s): delete 10 shuffled values
btree vs treeset
Significantly different (p ~= 7.567e-11)
Time ratio: 1.06081 95% CI 1.04667 - 1.07495 (n=20)
btree 526.1 ns 95% CI 521.0 ns - 531.2 ns
treeset 558.1 ns 95% CI 553.0 ns - 563.2 ns
Benchmark comparison (in 11.78 s): delete 100 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.72825 95% CI 0.71747 - 0.73903 (n=20)
btree 12.72 us 95% CI 12.57 us - 12.88 us
treeset 9.265 us 95% CI 9.187 us - 9.342 us
Benchmark comparison (in 13.46 s): delete 1000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.72338 95% CI 0.71335 - 0.73342 (n=20)
btree 329.9 us 95% CI 327.2 us - 332.6 us
treeset 238.7 us 95% CI 236.0 us - 241.3 us
Benchmark comparison (in 10.51 s): delete 10000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.88329 95% CI 0.86847 - 0.89810 (n=20)
btree 5.029 ms 95% CI 4.956 ms - 5.103 ms
treeset 4.442 ms 95% CI 4.406 ms - 4.479 ms
Benchmark comparison (in 22.01 s): delete 100000 shuffled values
btree vs treeset
Significantly different (p ~= 7.777e-08)
Time ratio: 1.08306 95% CI 1.05681 - 1.10931 (n=20)
btree 86.42 ms 95% CI 84.88 ms - 87.96 ms
treeset 93.60 ms 95% CI 92.06 ms - 95.14 ms
Benchmark comparison (in 356.9 s): delete 1000000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.27255 95% CI 1.26971 - 1.27540 (n=20)
btree 1.220 s 95% CI 1.218 s - 1.222 s
treeset 1.553 s 95% CI 1.551 s - 1.555 s
Benchmark comparison (in 9.134 s): delete 1 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.74113 95% CI 0.72636 - 0.75590 (n=20)
btree 76.84 ns 95% CI 75.57 ns - 78.11 ns
treeset 56.95 ns 95% CI 56.31 ns - 57.58 ns
Benchmark comparison (in 12.08 s): delete 10 sequential values
btree vs treeset
Significantly different (p ~= 3.666e-10)
Time ratio: 0.93923 95% CI 0.92509 - 0.95338 (n=20)
btree 517.4 ns 95% CI 512.1 ns - 522.7 ns
treeset 486.0 ns 95% CI 480.6 ns - 491.3 ns
Warning: order-of-evaluation effects in timing (p ~= 0.0436) of up to 7.394%%
Benchmark comparison (in 10.84 s): delete 100 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.67645 95% CI 0.66808 - 0.68483 (n=20)
btree 12.13 us 95% CI 12.01 us - 12.25 us
treeset 8.204 us 95% CI 8.144 us - 8.265 us
Benchmark comparison (in 11.30 s): delete 1000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.51046 95% CI 0.50511 - 0.51580 (n=20)
btree 236.5 us 95% CI 234.7 us - 238.2 us
treeset 120.7 us 95% CI 119.8 us - 121.6 us
Benchmark comparison (in 10.33 s): delete 10000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.46607 95% CI 0.46443 - 0.46772 (n=20)
btree 3.568 ms 95% CI 3.559 ms - 3.576 ms
treeset 1.663 ms 95% CI 1.659 ms - 1.667 ms
Benchmark comparison (in 13.51 s): delete 100000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.45984 95% CI 0.45858 - 0.46110 (n=20)
btree 47.00 ms 95% CI 46.91 ms - 47.09 ms
treeset 21.61 ms 95% CI 21.57 ms - 21.66 ms
Benchmark comparison (in 103.2 s): delete 1000000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.45460 95% CI 0.45411 - 0.45508 (n=20)
btree 575.6 ms 95% CI 575.3 ms - 575.8 ms
treeset 261.6 ms 95% CI 261.4 ms - 261.9 ms
Raw
initial
scala> Seq(1, 10, 100, 1000, 10000, 100000, 1000000) foreach { i => val xs = BTreeThyme.shuffled.take(i); th.pbenchOff(s"insert $i shuffled values")(BTree(xs: _*).size, ftitle="btree")(TreeSet(xs: _*).size,htitle="treeset") }
Benchmark comparison (in 13.25 s): insert 1 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.95089 95% CI 0.94399 - 0.95779 (n=20)
btree 69.54 ns 95% CI 69.19 ns - 69.89 ns
treeset 66.12 ns 95% CI 65.78 ns - 66.47 ns
Benchmark comparison (in 10.24 s): insert 10 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.25867 95% CI 1.24631 - 1.27103 (n=20)
btree 525.6 ns 95% CI 522.9 ns - 528.4 ns
treeset 661.6 ns 95% CI 656.1 ns - 667.1 ns
Benchmark comparison (in 12.42 s): insert 100 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.92296 95% CI 0.91319 - 0.93272 (n=20)
btree 11.52 us 95% CI 11.42 us - 11.63 us
treeset 10.64 us 95% CI 10.58 us - 10.69 us
Benchmark comparison (in 9.856 s): insert 1000 shuffled values
btree vs treeset
Significantly different (p ~= 2.386e-14)
Time ratio: 1.05373 95% CI 1.04438 - 1.06308 (n=20)
btree 205.7 us 95% CI 204.3 us - 207.0 us
treeset 216.7 us 95% CI 215.4 us - 218.0 us
Benchmark comparison (in 9.280 s): insert 10000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.11736 95% CI 1.10286 - 1.13186 (n=20)
btree 3.047 ms 95% CI 3.018 ms - 3.077 ms
treeset 3.405 ms 95% CI 3.375 ms - 3.434 ms
Benchmark comparison (in 15.96 s): insert 100000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.19766 95% CI 1.18319 - 1.21213 (n=20)
btree 59.63 ms 95% CI 59.08 ms - 60.18 ms
treeset 71.42 ms 95% CI 70.86 ms - 71.97 ms
Benchmark comparison (in 284.0 s): insert 1000000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.32641 95% CI 1.32013 - 1.33268 (n=20)
btree 933.7 ms 95% CI 930.2 ms - 937.2 ms
treeset 1.238 s 95% CI 1.235 s - 1.242 s
scala> Seq(1, 10, 100, 1000, 10000, 100000, 1000000) foreach { i => val xs = BTreeThyme.values.take(i); th.pbenchOff(s"insert $i sequential values")(BTree(xs: _*).size, ftitle="btree")(TreeSet(xs: _*).size,htitle="treeset") }
Benchmark comparison (in 13.86 s): insert 1 sequential values
btree vs treeset
Significantly different (p ~= 2.557e-13)
Time ratio: 0.95209 95% CI 0.94351 - 0.96068 (n=20)
btree 71.52 ns 95% CI 71.07 ns - 71.96 ns
treeset 68.09 ns 95% CI 67.65 ns - 68.54 ns
Benchmark comparison (in 15.69 s): insert 10 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.46570 95% CI 1.45331 - 1.47809 (n=20)
btree 521.5 ns 95% CI 517.9 ns - 525.2 ns
treeset 764.4 ns 95% CI 760.8 ns - 768.0 ns
Benchmark comparison (in 9.067 s): insert 100 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.21295 95% CI 1.19958 - 1.22633 (n=20)
btree 10.76 us 95% CI 10.67 us - 10.85 us
treeset 13.05 us 95% CI 12.96 us - 13.14 us
Benchmark comparison (in 13.35 s): insert 1000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.25609 95% CI 1.23951 - 1.27268 (n=20)
btree 172.0 us 95% CI 170.8 us - 173.2 us
treeset 216.0 us 95% CI 213.6 us - 218.4 us
Benchmark comparison (in 14.88 s): insert 10000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.28716 95% CI 1.27371 - 1.30061 (n=20)
btree 2.186 ms 95% CI 2.168 ms - 2.204 ms
treeset 2.813 ms 95% CI 2.795 ms - 2.831 ms
Benchmark comparison (in 10.59 s): insert 100000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.27124 95% CI 1.25907 - 1.28342 (n=20)
btree 27.29 ms 95% CI 27.08 ms - 27.49 ms
treeset 34.69 ms 95% CI 34.48 ms - 34.89 ms
Benchmark comparison (in 123.2 s): insert 1000000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.27002 95% CI 1.26592 - 1.27411 (n=20)
btree 326.1 ms 95% CI 325.2 ms - 326.9 ms
treeset 414.1 ms 95% CI 413.3 ms - 414.9 ms
scala> Seq(1, 10, 100, 1000, 10000, 100000, 1000000) foreach { i => val xs = BTreeThyme.shuffled.take(i); val btree = BTree(xs:_*); val ts = TreeSet(xs:_*); th.pbenchOff(s"contains $i shuffled values")(xs.forall(btree.contains),ftitle="btree")(xs.forall(ts.contains),htitle="treeset") }
Benchmark comparison (in 11.31 s): contains 1 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.88545 95% CI 0.87385 - 0.89704 (n=20)
btree 37.67 ns 95% CI 37.24 ns - 38.10 ns
treeset 33.35 ns 95% CI 33.14 ns - 33.57 ns
Benchmark comparison (in 11.22 s): contains 10 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.51984 95% CI 0.51384 - 0.52583 (n=20)
btree 308.4 ns 95% CI 305.2 ns - 311.6 ns
treeset 160.3 ns 95% CI 159.5 ns - 161.1 ns
Benchmark comparison (in 7.296 s): contains 100 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.40074 95% CI 0.39595 - 0.40554 (n=20)
btree 5.485 us 95% CI 5.444 us - 5.526 us
treeset 2.198 us 95% CI 2.178 us - 2.219 us
Benchmark comparison (in 11.20 s): contains 1000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.56626 95% CI 0.56185 - 0.57067 (n=20)
btree 114.0 us 95% CI 113.4 us - 114.7 us
treeset 64.58 us 95% CI 64.24 us - 64.91 us
Benchmark comparison (in 11.88 s): contains 10000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.74780 95% CI 0.73997 - 0.75562 (n=20)
btree 1.661 ms 95% CI 1.647 ms - 1.675 ms
treeset 1.242 ms 95% CI 1.235 ms - 1.249 ms
Benchmark comparison (in 10.59 s): contains 100000 shuffled values
btree vs treeset
Significantly different (p ~= 3.562e-13)
Time ratio: 1.10238 95% CI 1.08237 - 1.12239 (n=20)
btree 31.96 ms 95% CI 31.53 ms - 32.39 ms
treeset 35.23 ms 95% CI 34.80 ms - 35.66 ms
Benchmark comparison (in 148.7 s): contains 1000000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.24535 95% CI 1.23923 - 1.25147 (n=20)
btree 551.8 ms 95% CI 549.7 ms - 553.9 ms
treeset 687.1 ms 95% CI 685.0 ms - 689.3 ms
scala> Seq(1, 10, 100, 1000, 10000, 100000, 1000000) foreach { i => val xs = BTreeThyme.values.take(i); val btree = BTree(xs:_*); val ts = TreeSet(xs:_*); th.pbenchOff(s"contains $i sequential values")(xs.forall(btree.contains),ftitle="btree")(xs.forall(ts.contains),htitle="treeset") }
Benchmark comparison (in 13.73 s): contains 1 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.89173 95% CI 0.88295 - 0.90050 (n=20)
btree 37.29 ns 95% CI 37.04 ns - 37.53 ns
treeset 33.25 ns 95% CI 33.01 ns - 33.49 ns
Benchmark comparison (in 11.42 s): contains 10 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.53453 95% CI 0.52562 - 0.54343 (n=20)
btree 308.3 ns 95% CI 303.7 ns - 313.0 ns
treeset 164.8 ns 95% CI 163.7 ns - 166.0 ns
Benchmark comparison (in 11.53 s): contains 100 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.38313 95% CI 0.37739 - 0.38887 (n=20)
btree 5.668 us 95% CI 5.637 us - 5.698 us
treeset 2.171 us 95% CI 2.141 us - 2.202 us
Benchmark comparison (in 13.56 s): contains 1000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.54496 95% CI 0.54104 - 0.54887 (n=20)
btree 95.24 us 95% CI 94.91 us - 95.57 us
treeset 51.90 us 95% CI 51.57 us - 52.23 us
Benchmark comparison (in 7.323 s): contains 10000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.52983 95% CI 0.52097 - 0.53870 (n=20)
btree 1.242 ms 95% CI 1.227 ms - 1.257 ms
treeset 658.2 us 95% CI 650.7 us - 665.8 us
Benchmark comparison (in 13.64 s): contains 100000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.84397 95% CI 0.83356 - 0.85437 (n=20)
btree 14.78 ms 95% CI 14.63 ms - 14.94 ms
treeset 12.48 ms 95% CI 12.40 ms - 12.55 ms
Benchmark comparison (in 31.25 s): contains 1000000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.56850 95% CI 0.56542 - 0.57157 (n=20)
btree 166.1 ms 95% CI 165.6 ms - 166.5 ms
treeset 94.40 ms 95% CI 93.96 ms - 94.85 ms
Raw
iterate
Benchmark comparison (in 10.15 s): iterate 1 shuffled values
btree vs treeset
Significantly different (p ~= 0.0066)
Time ratio: 0.96190 95% CI 0.93574 - 0.98805 (n=20)
btree 27.76 ns 95% CI 27.24 ns - 28.29 ns
treeset 26.70 ns 95% CI 26.18 ns - 27.23 ns
Benchmark comparison (in 8.441 s): iterate 10 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.77022 95% CI 0.75628 - 0.78416 (n=20)
btree 70.85 ns 95% CI 69.78 ns - 71.93 ns
treeset 54.57 ns 95% CI 54.04 ns - 55.11 ns
Benchmark comparison (in 7.157 s): iterate 100 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.52465 95% CI 0.51501 - 0.53429 (n=20)
btree 591.3 ns 95% CI 583.5 ns - 599.2 ns
treeset 310.2 ns 95% CI 306.3 ns - 314.2 ns
Benchmark comparison (in 8.790 s): iterate 1000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.49490 95% CI 0.48733 - 0.50247 (n=20)
btree 6.000 us 95% CI 5.936 us - 6.065 us
treeset 2.970 us 95% CI 2.937 us - 3.002 us
Benchmark comparison (in 10.85 s): iterate 10000 shuffled values
btree vs treeset
Significantly different (p ~= 1.753e-14)
Time ratio: 0.91356 95% CI 0.89967 - 0.92744 (n=20)
btree 61.30 us 95% CI 60.67 us - 61.93 us
treeset 56.00 us 95% CI 55.37 us - 56.63 us
Benchmark comparison (in 11.69 s): iterate 100000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.24022 95% CI 1.21418 - 1.26626 (n=20)
btree 612.2 us 95% CI 605.4 us - 619.0 us
treeset 759.3 us 95% CI 745.7 us - 772.8 us
Benchmark comparison (in 10.59 s): iterate 1000000 shuffled values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 1.39180 95% CI 1.37251 - 1.41108 (n=20)
btree 6.255 ms 95% CI 6.185 ms - 6.325 ms
treeset 8.706 ms 95% CI 8.635 ms - 8.776 ms
Benchmark comparison (in 11.28 s): iterate 1 sequential values
btree vs treeset
Significantly different (p ~= 1.749e-04)
Time ratio: 1.11884 95% CI 1.05789 - 1.17979 (n=20)
btree 28.73 ns 95% CI 27.57 ns - 29.90 ns
treeset 32.15 ns 95% CI 30.98 ns - 33.31 ns
Benchmark comparison (in 12.26 s): iterate 10 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.78015 95% CI 0.76705 - 0.79325 (n=20)
btree 71.34 ns 95% CI 70.60 ns - 72.08 ns
treeset 55.66 ns 95% CI 54.92 ns - 56.39 ns
Benchmark comparison (in 7.136 s): iterate 100 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.50380 95% CI 0.49029 - 0.51731 (n=20)
btree 592.2 ns 95% CI 581.0 ns - 603.5 ns
treeset 298.4 ns 95% CI 292.7 ns - 304.0 ns
Benchmark comparison (in 8.671 s): iterate 1000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.47358 95% CI 0.46639 - 0.48076 (n=20)
btree 5.897 us 95% CI 5.836 us - 5.959 us
treeset 2.793 us 95% CI 2.762 us - 2.823 us
Benchmark comparison (in 11.19 s): iterate 10000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.48645 95% CI 0.47744 - 0.49546 (n=20)
btree 59.35 us 95% CI 58.59 us - 60.12 us
treeset 28.87 us 95% CI 28.49 us - 29.26 us
Benchmark comparison (in 10.65 s): iterate 100000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.48877 95% CI 0.47972 - 0.49782 (n=20)
btree 602.8 us 95% CI 597.9 us - 607.7 us
treeset 294.6 us 95% CI 289.7 us - 299.5 us
Benchmark comparison (in 9.863 s): iterate 1000000 sequential values
btree vs treeset
Significantly different (p ~= 0)
Time ratio: 0.56377 95% CI 0.52999 - 0.59755 (n=20)
btree 6.377 ms 95% CI 6.091 ms - 6.663 ms
treeset 3.595 ms 95% CI 3.452 ms - 3.738 ms
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment