-
Notifications
You must be signed in to change notification settings - Fork 1
algorithms
Jingguo Yao edited this page Sep 9, 2016
·
57 revisions
llrb vs no_free_list:
name old time/op new time/op delta
NewTree-4 577ns ± 4% 789ns ± 4% +36.72% (p=0.000 n=10+9)
Insert-4 1.91µs ± 2% 1.65µs ± 1% -13.51% (p=0.000 n=10+9)
FastInsert-4 1.75µs ± 3% 1.60µs ± 1% -8.24% (p=0.000 n=10+9)
Delete-4 3.45µs ± 2% 3.60µs ± 1% +4.38% (p=0.000 n=9+9)
Get-4 8.24µs ± 0% 5.30µs ± 2% -35.61% (p=0.000 n=9+9)
RandomInsert-4 2.17µs ±14% 1.73µs ± 7% -20.31% (p=0.000 n=10+9)
RandomFastInsert-4 1.81µs ±11% 1.71µs ± 5% ~ (p=0.065 n=10+9)
RandomDelete-4 3.76µs ±12% 3.76µs ± 4% ~ (p=1.000 n=10+9)
RandomGet-4 7.61µs ±12% 4.66µs ±15% -38.73% (p=0.000 n=10+9)
InsertWithRangeGroupTestIntervals-4 1.37µs ± 2% 1.33µs ± 3% -3.07% (p=0.000 n=10+9)
FastInsertWithRangeGroupTestIntervals-4 1.30µs ± 5% 1.30µs ± 2% ~ (p=0.985 n=10+9)
DeleteWithRangeGroupTestIntervals-4 2.24µs ± 1% 2.70µs ± 0% +20.66% (p=0.000 n=10+9)
GetWithRangeGroupTestIntervals-4 3.73µs ± 1% 2.77µs ± 1% -25.67% (p=0.000 n=10+9)
Insert8-4 1.91µs ± 2% 1.65µs ± 0% -13.60% (p=0.000 n=10+9)
FastInsert8-4 1.73µs ± 2% 1.60µs ± 1% -7.73% (p=0.000 n=10+9)
Delete8-4 3.45µs ± 0% 3.61µs ± 1% +4.51% (p=0.000 n=9+9)
Get8-4 8.23µs ± 0% 5.30µs ± 2% -35.59% (p=0.000 n=10+9)
Insert100-4 44.8µs ± 0% 30.7µs ± 1% -31.54% (p=0.000 n=9+9)
FastInsert100-4 32.8µs ± 1% 28.1µs ± 0% -14.23% (p=0.000 n=10+9)
Delete100-4 98.2µs ± 0% 67.1µs ± 0% -31.64% (p=0.000 n=10+8)
Get100-4 308µs ± 1% 188µs ± 3% -39.02% (p=0.000 n=10+9)
Insert1K-4 658µs ± 0% 444µs ± 1% -32.60% (p=0.000 n=10+8)
FastInsert1K-4 451µs ± 1% 406µs ± 0% -9.85% (p=0.000 n=10+8)
Delete1K-4 1.61ms ± 0% 0.96ms ± 0% -40.57% (p=0.000 n=8+9)
Get1K-4 3.70ms ± 1% 2.52ms ± 2% -31.97% (p=0.000 n=10+9)
Insert10K-4 9.38ms ± 0% 6.25ms ± 1% -33.40% (p=0.000 n=9+8)
FastInsert10K-4 6.26ms ± 1% 5.78ms ± 1% -7.73% (p=0.000 n=10+7)
Delete10K-4 24.2ms ± 0% 12.9ms ± 2% -46.43% (p=0.000 n=8+9)
Get10K-4 44.4ms ± 1% 32.3ms ± 3% -27.17% (p=0.000 n=9+8)
Insert100K-4 119ms ± 0% 78ms ± 0% -34.86% (p=0.000 n=9+8)
FastInsert100K-4 77.8ms ± 1% 73.8ms ± 0% -5.16% (p=0.000 n=10+8)
Delete100K-4 324ms ± 1% 166ms ± 0% -48.85% (p=0.000 n=10+8)
Get100K-4 490ms ± 0% 350ms ± 1% -28.59% (p=0.000 n=10+8)
Insert1M-4 1.39s ± 0% 0.91s ± 0% -34.70% (p=0.000 n=9+8)
FastInsert1M-4 924ms ± 1% 859ms ± 0% -7.01% (p=0.000 n=8+8)
Delete1M-4 3.93s ± 0% 1.96s ± 0% -50.12% (p=0.000 n=10+8)
Get1M-4 5.34s ± 1% 4.15s ± 1% -22.22% (p=0.000 n=9+8)
RandomInsert8-4 2.60µs ± 8% 1.87µs ± 4% -28.22% (p=0.000 n=10+9)
RandomFastInsert8-4 2.52µs ± 6% 1.87µs ± 6% -25.83% (p=0.000 n=9+9)
RandomDelete8-4 4.01µs ±10% 3.99µs ± 8% ~ (p=0.953 n=10+10)
RandomGet8-4 7.97µs ±17% 5.90µs ± 7% -25.92% (p=0.000 n=10+8)
RandomInsert100-4 60.2µs ± 3% 41.6µs ± 5% -30.90% (p=0.000 n=10+9)
RandomFastInsert100-4 43.2µs ± 2% 40.7µs ± 1% -5.81% (p=0.000 n=10+9)
RandomDelete100-4 128µs ± 4% 84µs ± 8% -34.27% (p=0.000 n=10+9)
RandomGet100-4 1.28ms ± 7% 0.79ms ±11% -38.31% (p=0.000 n=9+10)
RandomInsert1K-4 1.01ms ± 1% 0.67ms ±11% -34.08% (p=0.000 n=9+9)
RandomFastInsert1K-4 721µs ± 3% 642µs ± 9% -10.94% (p=0.000 n=9+9)
RandomDelete1K-4 2.27ms ± 2% 1.37ms ± 3% -39.91% (p=0.000 n=9+8)
RandomGet1K-4 143ms ± 5% 87ms ± 4% -39.22% (p=0.000 n=10+8)
RandomInsert10K-4 15.3ms ± 2% 9.5ms ± 2% -38.19% (p=0.000 n=9+7)
RandomFastInsert10K-4 10.5ms ± 3% 9.2ms ± 4% -12.83% (p=0.000 n=9+8)
RandomDelete10K-4 36.9ms ± 2% 21.0ms ± 5% -43.01% (p=0.000 n=9+8)
RandomGet10K-4 19.4s ± 1% 8.3s ± 6% -56.91% (p=0.000 n=9+8)
name old alloc/op new alloc/op delta
NewTree-4 320B ± 0% 640B ± 0% +100.00% (p=0.000 n=10+10)
Insert-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
FastInsert-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
Delete-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
Get-4 1.92kB ± 0% 1.92kB ± 0% ~ (all samples are equal)
RandomInsert-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
RandomFastInsert-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
RandomDelete-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
RandomGet-4 1.68kB ±16% 1.41kB ±39% -15.97% (p=0.047 n=10+10)
InsertWithRangeGroupTestIntervals-4 608B ± 0% 416B ± 0% -31.58% (p=0.000 n=10+10)
FastInsertWithRangeGroupTestIntervals-4 608B ± 0% 416B ± 0% -31.58% (p=0.000 n=10+10)
DeleteWithRangeGroupTestIntervals-4 608B ± 0% 416B ± 0% -31.58% (p=0.000 n=10+10)
GetWithRangeGroupTestIntervals-4 704B ± 0% 704B ± 0% ~ (all samples are equal)
Insert8-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
FastInsert8-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
Delete8-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
Get8-4 1.92kB ± 0% 1.92kB ± 0% ~ (all samples are equal)
Insert100-4 9.63kB ± 0% 5.71kB ± 0% -40.70% (p=0.000 n=10+10)
FastInsert100-4 9.63kB ± 0% 5.71kB ± 0% -40.70% (p=0.000 n=10+10)
Delete100-4 9.63kB ± 0% 5.71kB ± 0% -40.70% (p=0.000 n=10+10)
Get100-4 94.7kB ± 0% 94.7kB ± 0% ~ (all samples are equal)
Insert1K-4 96.0kB ± 0% 53.3kB ± 0% -44.54% (p=0.000 n=10+10)
FastInsert1K-4 96.0kB ± 0% 53.3kB ± 0% -44.54% (p=0.000 n=10+10)
Delete1K-4 96.0kB ± 0% 53.3kB ± 0% -44.54% (p=0.000 n=10+10)
Get1K-4 1.00MB ± 0% 1.00MB ± 0% ~ (all samples are equal)
Insert10K-4 960kB ± 0% 538kB ± 0% -43.98% (p=0.000 n=10+10)
FastInsert10K-4 960kB ± 0% 538kB ± 0% -43.98% (p=0.000 n=10+10)
Delete10K-4 960kB ± 0% 538kB ± 0% -43.98% (p=0.000 n=10+10)
Get10K-4 10.1MB ± 0% 10.1MB ± 0% ~ (all samples are equal)
Insert100K-4 9.60MB ± 0% 5.39MB ± 0% -43.84% (p=0.000 n=10+10)
FastInsert100K-4 9.60MB ± 0% 5.39MB ± 0% -43.84% (p=0.000 n=10+10)
Delete100K-4 9.60MB ± 0% 5.39MB ± 0% -43.84% (p=0.000 n=10+10)
Get100K-4 101MB ± 0% 101MB ± 0% ~ (all samples are equal)
Insert1M-4 96.0MB ± 0% 53.9MB ± 0% -43.82% (p=0.000 n=10+10)
FastInsert1M-4 96.0MB ± 0% 53.9MB ± 0% -43.82% (p=0.000 n=10+10)
Delete1M-4 96.0MB ± 0% 53.9MB ± 0% -43.82% (p=0.000 n=10+10)
Get1M-4 1.01GB ± 0% 1.01GB ± 0% ~ (all samples are equal)
RandomInsert8-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
RandomFastInsert8-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
RandomDelete8-4 800B ± 0% 416B ± 0% -48.00% (p=0.000 n=10+10)
RandomGet8-4 1.58kB ±11% 1.76kB ±13% +10.89% (p=0.022 n=8+9)
RandomInsert100-4 9.63kB ± 0% 4.00kB ± 0% -58.47% (p=0.000 n=10+10)
RandomFastInsert100-4 9.63kB ± 0% 4.00kB ± 0% -58.47% (p=0.000 n=10+10)
RandomDelete100-4 9.63kB ± 0% 4.00kB ± 0% -58.47% (p=0.000 n=10+10)
RandomGet100-4 301kB ± 7% 305kB ±10% ~ (p=0.713 n=8+10)
RandomInsert1K-4 96.0kB ± 0% 37.4kB ± 7% -61.00% (p=0.000 n=10+10)
RandomFastInsert1K-4 96.0kB ± 0% 37.6kB ±11% -60.83% (p=0.000 n=10+10)
RandomDelete1K-4 96.0kB ± 0% 38.1kB ± 8% -60.29% (p=0.000 n=10+10)
RandomGet1K-4 28.6MB ± 3% 28.5MB ± 2% ~ (p=1.000 n=10+10)
RandomInsert10K-4 960kB ± 0% 372kB ± 2% -61.29% (p=0.000 n=10+10)
RandomFastInsert10K-4 960kB ± 0% 368kB ± 3% -61.68% (p=0.000 n=10+10)
RandomDelete10K-4 960kB ± 0% 382kB ± 4% -60.25% (p=0.000 n=10+10)
RandomGet10K-4 4.66GB ± 2% 4.65GB ± 2% ~ (p=0.436 n=10+10)
name old allocs/op new allocs/op delta
NewTree-4 10.0 ± 0% 10.0 ± 0% ~ (all samples are equal)
Insert-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
FastInsert-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
Delete-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
Get-4 32.0 ± 0% 32.0 ± 0% ~ (all samples are equal)
RandomInsert-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
RandomFastInsert-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
RandomDelete-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
RandomGet-4 30.0 ±10% 27.4 ±20% -8.67% (p=0.045 n=10+10)
InsertWithRangeGroupTestIntervals-4 7.00 ± 0% 6.00 ± 0% -14.29% (p=0.000 n=10+10)
FastInsertWithRangeGroupTestIntervals-4 7.00 ± 0% 6.00 ± 0% -14.29% (p=0.000 n=10+10)
DeleteWithRangeGroupTestIntervals-4 7.00 ± 0% 6.00 ± 0% -14.29% (p=0.000 n=10+10)
GetWithRangeGroupTestIntervals-4 17.0 ± 0% 17.0 ± 0% ~ (all samples are equal)
Insert8-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
FastInsert8-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
Delete8-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
Get8-4 32.0 ± 0% 32.0 ± 0% ~ (all samples are equal)
Insert100-4 101 ± 0% 20 ± 0% -80.20% (p=0.000 n=10+10)
FastInsert100-4 101 ± 0% 20 ± 0% -80.20% (p=0.000 n=10+10)
Delete100-4 101 ± 0% 20 ± 0% -80.20% (p=0.000 n=10+10)
Get100-4 588 ± 0% 588 ± 0% ~ (all samples are equal)
Insert1K-4 1.00k ± 0% 0.11k ± 0% -88.91% (p=0.000 n=10+10)
FastInsert1K-4 1.00k ± 0% 0.11k ± 0% -88.91% (p=0.000 n=10+10)
Delete1K-4 1.00k ± 0% 0.11k ± 0% -88.91% (p=0.000 n=10+10)
Get1K-4 5.99k ± 0% 5.99k ± 0% ~ (all samples are equal)
Insert10K-4 10.0k ± 0% 1.0k ± 0% -89.95% (p=0.000 n=10+10)
FastInsert10K-4 10.0k ± 0% 1.0k ± 0% -89.95% (p=0.000 n=10+10)
Delete10K-4 10.0k ± 0% 1.0k ± 0% -89.95% (p=0.000 n=10+10)
Get10K-4 60.0k ± 0% 60.0k ± 0% ~ (all samples are equal)
Insert100K-4 100k ± 0% 10k ± 0% -90.10% (p=0.000 n=10+10)
FastInsert100K-4 100k ± 0% 10k ± 0% -90.10% (p=0.000 n=10+10)
Delete100K-4 100k ± 0% 10k ± 0% -90.10% (p=0.000 n=10+10)
Get100K-4 600k ± 0% 600k ± 0% ~ (all samples are equal)
Insert1M-4 1.00M ± 0% 0.10M ± 0% -90.12% (p=0.000 n=10+10)
FastInsert1M-4 1.00M ± 0% 0.10M ± 0% -90.12% (p=0.000 n=10+10)
Delete1M-4 1.00M ± 0% 0.10M ± 0% -90.12% (p=0.000 n=10+10)
Get1M-4 6.00M ± 0% 6.00M ± 0% ~ (all samples are equal)
RandomInsert8-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
RandomFastInsert8-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
RandomDelete8-4 9.00 ± 0% 6.00 ± 0% -33.33% (p=0.000 n=10+10)
RandomGet8-4 28.9 ±13% 30.7 ± 5% +6.11% (p=0.036 n=10+9)
RandomInsert100-4 101 ± 0% 15 ± 0% -85.15% (p=0.000 n=10+10)
RandomFastInsert100-4 101 ± 0% 15 ± 0% -85.15% (p=0.000 n=10+10)
RandomDelete100-4 101 ± 0% 15 ± 0% -85.15% (p=0.000 n=10+10)
RandomGet100-4 743 ± 2% 744 ± 2% ~ (p=0.881 n=8+10)
RandomInsert1K-4 1.00k ± 0% 0.08k ± 6% -91.72% (p=0.000 n=10+10)
RandomFastInsert1K-4 1.00k ± 0% 0.08k ± 8% -91.62% (p=0.000 n=10+10)
RandomDelete1K-4 1.00k ± 0% 0.09k ± 5% -91.50% (p=0.000 n=10+9)
RandomGet1K-4 10.7k ± 0% 10.7k ± 0% ~ (p=0.868 n=10+10)
RandomInsert10K-4 10.0k ± 0% 0.7k ± 2% -92.96% (p=0.000 n=10+9)
RandomFastInsert10K-4 10.0k ± 0% 0.7k ± 3% -92.99% (p=0.000 n=10+9)
RandomDelete10K-4 10.0k ± 0% 0.7k ± 3% -92.80% (p=0.000 n=10+10)
RandomGet10K-4 177k ± 0% 177k ± 0% ~ (p=0.393 n=10+10)