-
Notifications
You must be signed in to change notification settings - Fork 1
algorithms
Jingguo Yao edited this page Sep 7, 2016
·
57 revisions
BTree vs no_free_list:
name old time/op new time/op delta
NewTree-4 3.13µs ± 8% 0.79µs ± 4% -74.76% (p=0.000 n=10+9)
Insert-4 1.90µs ± 2% 1.65µs ± 1% -13.16% (p=0.000 n=10+9)
FastInsert-4 1.83µs ± 2% 1.60µs ± 1% -12.28% (p=0.000 n=10+9)
Delete-4 3.80µs ± 1% 3.60µs ± 1% -5.18% (p=0.000 n=9+9)
Get-4 5.40µs ± 1% 5.30µs ± 2% -1.85% (p=0.000 n=9+9)
RandomInsert-4 1.97µs ± 4% 1.73µs ± 7% -12.25% (p=0.000 n=10+9)
RandomFastInsert-4 1.94µs ± 5% 1.71µs ± 5% -11.81% (p=0.000 n=10+9)
RandomDelete-4 4.00µs ± 7% 3.76µs ± 4% -6.21% (p=0.001 n=10+9)
RandomGet-4 4.96µs ±21% 4.66µs ±15% ~ (p=0.176 n=10+9)
InsertWithRangeGroupTestIntervals-4 1.53µs ± 2% 1.33µs ± 3% -13.31% (p=0.000 n=10+9)
FastInsertWithRangeGroupTestIntervals-4 1.51µs ± 3% 1.30µs ± 2% -14.41% (p=0.000 n=10+9)
DeleteWithRangeGroupTestIntervals-4 2.90µs ± 1% 2.70µs ± 0% -6.93% (p=0.000 n=9+9)
GetWithRangeGroupTestIntervals-4 2.79µs ± 1% 2.77µs ± 1% -0.48% (p=0.048 n=9+9)
Insert8-4 1.90µs ± 2% 1.65µs ± 0% -13.37% (p=0.000 n=10+9)
FastInsert8-4 1.83µs ± 2% 1.60µs ± 1% -12.70% (p=0.000 n=10+9)
Delete8-4 3.80µs ± 1% 3.61µs ± 1% -5.16% (p=0.000 n=10+9)
Get8-4 5.44µs ± 2% 5.30µs ± 2% -2.54% (p=0.000 n=10+9)
Insert100-4 30.9µs ± 1% 30.7µs ± 1% -0.74% (p=0.001 n=10+9)
FastInsert100-4 28.5µs ± 1% 28.1µs ± 0% -1.18% (p=0.000 n=9+9)
Delete100-4 67.6µs ± 1% 67.1µs ± 0% -0.72% (p=0.000 n=10+8)
Get100-4 191µs ± 3% 188µs ± 3% -1.56% (p=0.022 n=10+9)
Insert1K-4 443µs ± 0% 444µs ± 1% ~ (p=0.408 n=10+8)
FastInsert1K-4 407µs ± 0% 406µs ± 0% -0.20% (p=0.001 n=10+8)
Delete1K-4 964µs ± 1% 957µs ± 0% -0.67% (p=0.028 n=10+9)
Get1K-4 2.49ms ± 2% 2.52ms ± 2% ~ (p=0.243 n=10+9)
Insert10K-4 6.26ms ± 1% 6.25ms ± 1% ~ (p=0.274 n=10+8)
FastInsert10K-4 5.78ms ± 0% 5.78ms ± 1% ~ (p=0.740 n=10+7)
Delete10K-4 12.9ms ± 0% 12.9ms ± 2% ~ (p=0.243 n=10+9)
Get10K-4 32.5ms ± 2% 32.3ms ± 3% ~ (p=0.408 n=10+8)
Insert100K-4 77.6ms ± 0% 77.6ms ± 0% ~ (p=0.897 n=10+8)
FastInsert100K-4 73.3ms ± 1% 73.8ms ± 0% +0.70% (p=0.000 n=10+8)
Delete100K-4 166ms ± 1% 166ms ± 0% ~ (p=0.146 n=10+8)
Get100K-4 351ms ± 1% 350ms ± 1% -0.47% (p=0.036 n=9+8)
Insert1M-4 907ms ± 0% 905ms ± 0% ~ (p=0.173 n=10+8)
FastInsert1M-4 853ms ± 0% 859ms ± 0% +0.67% (p=0.000 n=10+8)
Delete1M-4 1.96s ± 0% 1.96s ± 0% ~ (p=0.408 n=10+8)
Get1M-4 4.15s ± 1% 4.15s ± 1% ~ (p=0.965 n=10+8)
RandomInsert8-4 2.31µs ± 3% 1.87µs ± 4% -19.18% (p=0.000 n=10+9)
RandomFastInsert8-4 2.25µs ± 3% 1.87µs ± 6% -16.99% (p=0.000 n=10+9)
RandomDelete8-4 4.17µs ± 5% 3.99µs ± 8% -4.46% (p=0.011 n=10+10)
RandomGet8-4 5.66µs ±21% 5.90µs ± 7% ~ (p=0.408 n=10+8)
RandomInsert100-4 42.3µs ± 1% 41.6µs ± 5% -1.76% (p=0.006 n=8+9)
RandomFastInsert100-4 41.2µs ± 1% 40.7µs ± 1% -1.25% (p=0.013 n=10+9)
RandomDelete100-4 82.8µs ± 2% 84.0µs ± 8% ~ (p=0.661 n=10+9)
RandomGet100-4 769µs ± 4% 791µs ±11% ~ (p=0.549 n=9+10)
RandomInsert1K-4 659µs ± 2% 667µs ±11% ~ (p=0.842 n=10+9)
RandomFastInsert1K-4 636µs ± 1% 642µs ± 9% ~ (p=0.968 n=10+9)
RandomDelete1K-4 1.36ms ± 1% 1.37ms ± 3% ~ (p=0.515 n=10+8)
RandomGet1K-4 87.7ms ± 1% 86.9ms ± 4% ~ (p=0.234 n=8+8)
RandomInsert10K-4 9.55ms ± 0% 9.47ms ± 2% -0.83% (p=0.000 n=9+7)
RandomFastInsert10K-4 9.30ms ± 1% 9.15ms ± 4% -1.64% (p=0.001 n=9+8)
RandomDelete10K-4 21.1ms ± 1% 21.0ms ± 5% ~ (p=0.965 n=10+8)
RandomGet10K-4 8.60s ± 3% 8.35s ± 6% -2.95% (p=0.043 n=10+8)
name old alloc/op new alloc/op delta
NewTree-4 3.52kB ± 0% 0.64kB ± 0% -81.82% (p=0.000 n=10+10)
Insert-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
FastInsert-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
Delete-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
Get-4 1.92kB ± 0% 1.92kB ± 0% ~ (all samples are equal)
RandomInsert-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
RandomFastInsert-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
RandomDelete-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
RandomGet-4 1.56kB ±51% 1.41kB ±39% ~ (p=0.268 n=10+10)
InsertWithRangeGroupTestIntervals-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
FastInsertWithRangeGroupTestIntervals-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
DeleteWithRangeGroupTestIntervals-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
GetWithRangeGroupTestIntervals-4 704B ± 0% 704B ± 0% ~ (all samples are equal)
Insert8-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
FastInsert8-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
Delete8-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
Get8-4 1.92kB ± 0% 1.92kB ± 0% ~ (all samples are equal)
Insert100-4 6.00kB ± 0% 5.71kB ± 0% -4.80% (p=0.000 n=10+10)
FastInsert100-4 6.00kB ± 0% 5.71kB ± 0% -4.80% (p=0.000 n=10+10)
Delete100-4 6.00kB ± 0% 5.71kB ± 0% -4.80% (p=0.000 n=10+10)
Get100-4 94.7kB ± 0% 94.7kB ± 0% ~ (all samples are equal)
Insert1K-4 53.6kB ± 0% 53.3kB ± 0% -0.54% (p=0.000 n=10+10)
FastInsert1K-4 53.6kB ± 0% 53.3kB ± 0% -0.54% (p=0.000 n=10+10)
Delete1K-4 53.6kB ± 0% 53.3kB ± 0% -0.54% (p=0.000 n=10+10)
Get1K-4 1.00MB ± 0% 1.00MB ± 0% ~ (all samples are equal)
Insert10K-4 538kB ± 0% 538kB ± 0% -0.05% (p=0.000 n=10+10)
FastInsert10K-4 538kB ± 0% 538kB ± 0% -0.05% (p=0.000 n=10+10)
Delete10K-4 538kB ± 0% 538kB ± 0% -0.05% (p=0.000 n=10+10)
Get10K-4 10.1MB ± 0% 10.1MB ± 0% ~ (all samples are equal)
Insert100K-4 5.39MB ± 0% 5.39MB ± 0% -0.01% (p=0.000 n=10+10)
FastInsert100K-4 5.39MB ± 0% 5.39MB ± 0% -0.01% (p=0.000 n=10+10)
Delete100K-4 5.39MB ± 0% 5.39MB ± 0% -0.01% (p=0.000 n=10+10)
Get100K-4 101MB ± 0% 101MB ± 0% ~ (all samples are equal)
Insert1M-4 53.9MB ± 0% 53.9MB ± 0% -0.00% (p=0.000 n=10+10)
FastInsert1M-4 53.9MB ± 0% 53.9MB ± 0% -0.00% (p=0.000 n=10+10)
Delete1M-4 53.9MB ± 0% 53.9MB ± 0% -0.00% (p=0.000 n=10+10)
Get1M-4 1.01GB ± 0% 1.01GB ± 0% ~ (all samples are equal)
RandomInsert8-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
RandomFastInsert8-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
RandomDelete8-4 704B ± 0% 416B ± 0% -40.91% (p=0.000 n=10+10)
RandomGet8-4 1.61kB ±38% 1.76kB ±13% ~ (p=0.364 n=10+9)
RandomInsert100-4 4.29kB ± 0% 4.00kB ± 0% -6.72% (p=0.000 n=10+10)
RandomFastInsert100-4 4.29kB ± 0% 4.00kB ± 0% -6.72% (p=0.000 n=10+10)
RandomDelete100-4 4.29kB ± 0% 4.00kB ± 0% -6.72% (p=0.000 n=10+10)
RandomGet100-4 300kB ± 3% 305kB ±10% ~ (p=0.618 n=8+10)
RandomInsert1K-4 38.0kB ± 9% 37.4kB ± 7% ~ (p=0.613 n=10+10)
RandomFastInsert1K-4 38.6kB ± 2% 37.6kB ±11% ~ (p=0.194 n=8+10)
RandomDelete1K-4 38.5kB ± 6% 38.1kB ± 8% ~ (p=0.617 n=10+10)
RandomGet1K-4 28.6MB ± 2% 28.5MB ± 2% ~ (p=0.796 n=10+10)
RandomInsert10K-4 371kB ± 4% 372kB ± 2% ~ (p=0.838 n=10+10)
RandomFastInsert10K-4 372kB ± 3% 368kB ± 3% ~ (p=0.184 n=10+10)
RandomDelete10K-4 373kB ± 1% 382kB ± 4% +2.25% (p=0.006 n=10+10)
RandomGet10K-4 4.64GB ± 1% 4.65GB ± 2% ~ (p=0.661 n=9+10)
name old allocs/op new allocs/op delta
NewTree-4 30.0 ± 0% 10.0 ± 0% -66.67% (p=0.000 n=10+10)
Insert-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
FastInsert-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
Delete-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
Get-4 32.0 ± 0% 32.0 ± 0% ~ (all samples are equal)
RandomInsert-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
RandomFastInsert-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
RandomDelete-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
RandomGet-4 29.0 ±24% 27.4 ±20% ~ (p=0.194 n=10+10)
InsertWithRangeGroupTestIntervals-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
FastInsertWithRangeGroupTestIntervals-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
DeleteWithRangeGroupTestIntervals-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
GetWithRangeGroupTestIntervals-4 17.0 ± 0% 17.0 ± 0% ~ (all samples are equal)
Insert8-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
FastInsert8-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
Delete8-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
Get8-4 32.0 ± 0% 32.0 ± 0% ~ (all samples are equal)
Insert100-4 22.0 ± 0% 20.0 ± 0% -9.09% (p=0.000 n=10+10)
FastInsert100-4 22.0 ± 0% 20.0 ± 0% -9.09% (p=0.000 n=10+10)
Delete100-4 22.0 ± 0% 20.0 ± 0% -9.09% (p=0.000 n=10+10)
Get100-4 588 ± 0% 588 ± 0% ~ (all samples are equal)
Insert1K-4 113 ± 0% 111 ± 0% -1.77% (p=0.000 n=10+10)
FastInsert1K-4 113 ± 0% 111 ± 0% -1.77% (p=0.000 n=10+10)
Delete1K-4 113 ± 0% 111 ± 0% -1.77% (p=0.000 n=10+10)
Get1K-4 5.99k ± 0% 5.99k ± 0% ~ (all samples are equal)
Insert10K-4 1.01k ± 0% 1.00k ± 0% -0.20% (p=0.000 n=10+10)
FastInsert10K-4 1.01k ± 0% 1.00k ± 0% -0.20% (p=0.000 n=10+10)
Delete10K-4 1.01k ± 0% 1.00k ± 0% -0.20% (p=0.000 n=10+10)
Get10K-4 60.0k ± 0% 60.0k ± 0% ~ (all samples are equal)
Insert100K-4 9.90k ± 0% 9.90k ± 0% -0.02% (p=0.000 n=10+10)
FastInsert100K-4 9.90k ± 0% 9.90k ± 0% -0.02% (p=0.000 n=10+10)
Delete100K-4 9.90k ± 0% 9.90k ± 0% -0.02% (p=0.000 n=10+10)
Get100K-4 600k ± 0% 600k ± 0% ~ (all samples are equal)
Insert1M-4 98.8k ± 0% 98.8k ± 0% -0.00% (p=0.000 n=10+10)
FastInsert1M-4 98.8k ± 0% 98.8k ± 0% -0.00% (p=0.000 n=10+10)
Delete1M-4 98.8k ± 0% 98.8k ± 0% -0.00% (p=0.000 n=10+10)
Get1M-4 6.00M ± 0% 6.00M ± 0% ~ (all samples are equal)
RandomInsert8-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
RandomFastInsert8-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
RandomDelete8-4 8.00 ± 0% 6.00 ± 0% -25.00% (p=0.000 n=10+10)
RandomGet8-4 29.2 ±21% 30.7 ± 5% ~ (p=0.326 n=10+9)
RandomInsert100-4 17.0 ± 0% 15.0 ± 0% -11.76% (p=0.000 n=10+10)
RandomFastInsert100-4 17.0 ± 0% 15.0 ± 0% -11.76% (p=0.000 n=10+10)
RandomDelete100-4 17.0 ± 0% 15.0 ± 0% -11.76% (p=0.000 n=10+10)
RandomGet100-4 743 ± 1% 744 ± 2% ~ (p=0.777 n=8+10)
RandomInsert1K-4 85.7 ± 5% 82.9 ± 6% ~ (p=0.107 n=10+10)
RandomFastInsert1K-4 86.8 ± 5% 83.9 ± 8% -3.34% (p=0.045 n=10+10)
RandomDelete1K-4 86.2 ± 6% 85.1 ± 5% ~ (p=0.346 n=10+9)
RandomGet1K-4 10.7k ± 0% 10.7k ± 0% ~ (p=0.868 n=10+10)
RandomInsert10K-4 706 ± 4% 704 ± 2% ~ (p=0.921 n=10+9)
RandomFastInsert10K-4 707 ± 3% 702 ± 3% ~ (p=0.218 n=10+9)
RandomDelete10K-4 703 ± 0% 720 ± 3% +2.37% (p=0.008 n=8+10)
RandomGet10K-4 177k ± 0% 177k ± 0% ~ (p=0.661 n=9+10)