search

codingskynet / concurrent-data-structure

Concurrent Data Structure for Rust
29 stars 3 forks source link

Sequential Tree들과 SeqLockAVLTree 비교 #7

Open codingskynet opened 3 years ago

codingskynet commented 3 years ago

Benchmark: cargo criterion --bench sequential (only run bench_vs_btreemap) Envirnment:

The branch main(9b211c6) result(constants are differed from the branch saved):

Detail ```text std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 100%, L: 0%, R: 0%, total: +1.92e5)/std::BTreeMap time: [23.003 ms 23.260 ms 23.580 ms] thrpt: [8.1425 Melem/s 8.2546 Melem/s 8.3466 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 100%, L: 0%, R: 0%, total: +1.92e5)/BTree time: [24.846 ms 25.120 ms 25.494 ms] thrpt: [7.5313 Melem/s 7.6434 Melem/s 7.7275 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 0%, L: 100%, R: 0%, total: +1.92e5)/std::BTreeMap time: [28.187 ms 28.552 ms 29.015 ms] thrpt: [6.6172 Melem/s 6.7245 Melem/s 6.8117 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 0%, L: 100%, R: 0%, total: +1.92e5)/BTree time: [33.296 ms 33.722 ms 34.213 ms] thrpt: [5.6118 Melem/s 5.6936 Melem/s 5.7664 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 0%, L: 0%, R: 100%, total: +1.92e5)/std::BTreeMap time: [37.202 ms 38.062 ms 39.035 ms] thrpt: [4.9186 Melem/s 5.0444 Melem/s 5.1611 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 0%, L: 0%, R: 100%, total: +1.92e5)/BTree time: [40.924 ms 41.618 ms 42.381 ms] thrpt: [4.5303 Melem/s 4.6134 Melem/s 4.6916 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 5%, L: 90%, R: 5%, total: +1.92e5)/std::BTreeMap time: [30.831 ms 31.439 ms 32.140 ms] thrpt: [5.9739 Melem/s 6.1070 Melem/s 6.2275 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 5%, L: 90%, R: 5%, total: +1.92e5)/BTree time: [34.686 ms 35.394 ms 36.158 ms] thrpt: [5.3100 Melem/s 5.4246 Melem/s 5.5354 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 30%, L: 50%, R: 20%, total: +1.92e5)/std::BTreeMap time: [32.917 ms 33.440 ms 34.044 ms] thrpt: [5.6398 Melem/s 5.7417 Melem/s 5.8329 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 30%, L: 50%, R: 20%, total: +1.92e5)/BTree time: [35.898 ms 36.209 ms 36.566 ms] thrpt: [5.2507 Melem/s 5.3025 Melem/s 5.3485 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 40%, L: 20%, R: 40%, total: +1.92e5)/std::BTreeMap time: [34.634 ms 35.121 ms 35.660 ms] thrpt: [5.3842 Melem/s 5.4669 Melem/s 5.5437 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 40%, L: 20%, R: 40%, total: +1.92e5)/BTree time: [37.758 ms 38.022 ms 38.371 ms] thrpt: [5.0038 Melem/s 5.0497 Melem/s 5.0850 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 50%, L: 0%, R: 50%, total: +1.92e5)/std::BTreeMap time: [36.850 ms 37.488 ms 38.154 ms] thrpt: [5.0322 Melem/s 5.1216 Melem/s 5.2103 Melem/s] std::BTreeMap vs BTree: Inserted +5e5, Ops (I: 50%, L: 0%, R: 50%, total: +1.92e5)/BTree time: [38.675 ms 39.182 ms 39.743 ms] thrpt: [4.8310 Melem/s 4.9002 Melem/s 4.9645 Melem/s] ```

Benchmark: cargo criterion --bench concurrent (only run bench_mixed_total_seqlockavltree)

Detail ```text SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1.92e5) by 1 threads time: [200.10 ms 204.57 ms 209.83 ms] thrpt: [915.05 Kelem/s 938.58 Kelem/s 959.52 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +9.6e4) by 2 threads time: [122.30 ms 126.74 ms 132.83 ms] thrpt: [1.4455 Melem/s 1.5149 Melem/s 1.5699 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +4.8e4) by 4 threads time: [72.743 ms 75.622 ms 79.524 ms] thrpt: [2.4144 Melem/s 2.5390 Melem/s 2.6394 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +2.4e4) by 8 threads time: [60.798 ms 62.065 ms 63.351 ms] thrpt: [3.0307 Melem/s 3.0935 Melem/s 3.1580 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1.6e4) by 12 threads time: [51.383 ms 53.083 ms 55.021 ms] thrpt: [3.4896 Melem/s 3.6170 Melem/s 3.7366 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1.92e5) by 1 threads time: [132.85 ms 133.18 ms 133.52 ms] thrpt: [1.4380 Melem/s 1.4417 Melem/s 1.4453 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +9.6e4) by 2 threads time: [64.178 ms 65.188 ms 66.492 ms] thrpt: [2.8876 Melem/s 2.9453 Melem/s 2.9917 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +4.8e4) by 4 threads time: [33.729 ms 33.890 ms 34.068 ms] thrpt: [5.6358 Melem/s 5.6653 Melem/s 5.6924 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +2.4e4) by 8 threads time: [18.494 ms 18.574 ms 18.660 ms] thrpt: [10.289 Melem/s 10.337 Melem/s 10.382 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1.6e4) by 12 threads time: [14.196 ms 14.658 ms 15.176 ms] thrpt: [12.652 Melem/s 13.099 Melem/s 13.525 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1.92e5) by 1 threads time: [175.70 ms 176.13 ms 176.58 ms] thrpt: [1.0873 Melem/s 1.0901 Melem/s 1.0928 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +9.6e4) by 2 threads time: [88.666 ms 90.187 ms 91.823 ms] thrpt: [2.0910 Melem/s 2.1289 Melem/s 2.1654 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +4.8e4) by 4 threads time: [56.011 ms 57.361 ms 59.114 ms] thrpt: [3.2480 Melem/s 3.3472 Melem/s 3.4279 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +2.4e4) by 8 threads time: [32.342 ms 33.061 ms 33.872 ms] thrpt: [5.6684 Melem/s 5.8074 Melem/s 5.9366 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1.6e4) by 12 threads time: [24.813 ms 25.069 ms 25.354 ms] thrpt: [7.5729 Melem/s 7.6588 Melem/s 7.7378 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1.92e5) by 1 threads time: [145.53 ms 149.50 ms 155.65 ms] thrpt: [1.2335 Melem/s 1.2843 Melem/s 1.3193 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +9.6e4) by 2 threads time: [75.120 ms 79.658 ms 84.691 ms] thrpt: [2.2671 Melem/s 2.4103 Melem/s 2.5559 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +4.8e4) by 4 threads time: [40.794 ms 41.208 ms 41.616 ms] thrpt: [4.6136 Melem/s 4.6592 Melem/s 4.7066 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +2.4e4) by 8 threads time: [25.172 ms 25.874 ms 26.693 ms] thrpt: [7.1930 Melem/s 7.4204 Melem/s 7.6274 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1.6e4) by 12 threads time: [18.940 ms 19.330 ms 19.764 ms] thrpt: [9.7147 Melem/s 9.9329 Melem/s 10.137 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1.92e5) by 1 threads time: [175.46 ms 177.71 ms 180.23 ms] thrpt: [1.0653 Melem/s 1.0804 Melem/s 1.0942 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +9.6e4) by 2 threads time: [92.361 ms 93.314 ms 94.419 ms] thrpt: [2.0335 Melem/s 2.0576 Melem/s 2.0788 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +4.8e4) by 4 threads time: [57.761 ms 58.356 ms 59.054 ms] thrpt: [3.2513 Melem/s 3.2902 Melem/s 3.3241 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +2.4e4) by 8 threads time: [40.063 ms 40.305 ms 40.577 ms] thrpt: [4.7317 Melem/s 4.7636 Melem/s 4.7924 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1.6e4) by 12 threads time: [32.397 ms 33.408 ms 34.868 ms] thrpt: [5.5065 Melem/s 5.7471 Melem/s 5.9264 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 40%, L: 20%, R: 40%, per: +1.92e5) by 1 threads time: [193.10 ms 197.05 ms 201.29 ms] thrpt: [953.83 Kelem/s 974.36 Kelem/s 994.31 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 40%, L: 20%, R: 40%, per: +9.6e4) by 2 threads time: [102.11 ms 104.04 ms 106.22 ms] thrpt: [1.8076 Melem/s 1.8455 Melem/s 1.8804 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 40%, L: 20%, R: 40%, per: +4.8e4) by 4 threads time: [62.983 ms 63.647 ms 64.382 ms] thrpt: [2.9822 Melem/s 3.0166 Melem/s 3.0485 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 40%, L: 20%, R: 40%, per: +2.4e4) by 8 threads time: [46.276 ms 46.715 ms 47.173 ms] thrpt: [4.0701 Melem/s 4.1101 Melem/s 4.1490 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 40%, L: 20%, R: 40%, per: +1.6e4) by 12 threads time: [38.970 ms 39.644 ms 40.358 ms] thrpt: [4.7574 Melem/s 4.8431 Melem/s 4.9269 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1.92e5) by 1 threads time: [194.74 ms 198.45 ms 202.61 ms] thrpt: [947.63 Kelem/s 967.51 Kelem/s 985.91 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +9.6e4) by 2 threads time: [109.27 ms 111.71 ms 114.52 ms] thrpt: [1.6766 Melem/s 1.7188 Melem/s 1.7572 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +4.8e4) by 4 threads time: [68.425 ms 69.296 ms 70.455 ms] thrpt: [2.7251 Melem/s 2.7707 Melem/s 2.8060 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +2.4e4) by 8 threads time: [52.074 ms 52.885 ms 53.797 ms] thrpt: [3.5690 Melem/s 3.6305 Melem/s 3.6871 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1.6e4) by 12 threads time: [42.036 ms 42.523 ms 43.059 ms] thrpt: [4.4590 Melem/s 4.5153 Melem/s 4.5675 Melem/s] ```
codingskynet commented 3 years ago

아니 SeqLockAVLTree 짱 느려

codingskynet commented 3 years ago
Images ![5e5_seqlockavltree_100_0_0_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795340-e2b6ee4d-9823-4c02-a536-910a97a20821.png) ![5e5_seqlockavltree_0_100_0_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795357-0a8553db-611a-42b2-bfb8-698ca73067ac.png) ![5e5_seqlockavltree_0_0_100_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795371-0dd8b8a6-12ce-4124-990a-d235d99ef9ca.png) ![5e5_seqlockavltree_5_90_5_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795380-220f703c-fa37-4e3f-b4d3-ee6dbf571de5.png) ![5e5_seqlockavltree_30_50_20_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795403-a1365e34-0571-42a0-a007-8fe7c4f1c1e8.png) ![5e5_seqlockavltree_40_20_40_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795422-f292f820-0868-478a-8ac8-ce6f2cc86342.png) ![5e5_seqlockavltree_50_0_50_total_1 92e5](https://user-images.githubusercontent.com/8104782/141795434-8d66a188-3d09-44c8-9723-fde5ff8ad400.png)