[SeqlockAVLTree] Optimize thoroughly

[codingskynet]

ARM 64코어 머신(AWS EC2: c6g.metal)에서 기존의 SeqLockAVLTree를 벤치마크해본 결과, 16코어 이상에서 많은 throughput 하락이 있었습니다. 이는 아마도 각 operation에서 실패할 경우 loop를 돌 때, backoff가 없어서 생긴 contention으로 추정되기 때문에, 각 operation에 backoff를 추가해봤습니다.

[codingskynet]

Benchmark: cargo criterion --bench concurrnet (only run bench_mixed_seqlockavltree) Envirnment:

• SW: Amazon Linux 2(4.14.248-189.473.amzn2.aarch64)
• HW: AWS EC2 c6g.metal(Graviton 2, 64 cores, 128GiB)

SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 1 threads
                        time:   [627.13 ms 637.08 ms 641.85 ms]
                        thrpt:  [779.00 Kelem/s 784.83 Kelem/s 797.28 Kelem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 2 threads
                        time:   [743.90 ms 752.42 ms 758.41 ms]
                        thrpt:  [1.3185 Melem/s 1.3290 Melem/s 1.3443 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 4 threads
                        time:   [918.26 ms 922.39 ms 929.03 ms]
                        thrpt:  [2.1528 Melem/s 2.1683 Melem/s 2.1780 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 8 threads
                        time:   [1.4921 s 1.4989 s 1.5054 s]
                        thrpt:  [2.6571 Melem/s 2.6687 Melem/s 2.6808 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 16 threads
                        time:   [2.7280 s 3.7645 s 5.1387 s]
                        thrpt:  [1.5568 Melem/s 2.1251 Melem/s 2.9325 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 32 threads
                        time:   [12.262 s 18.323 s 24.065 s]
                        thrpt:  [664.86 Kelem/s 873.20 Kelem/s 1.3049 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 48 threads
                        time:   [16.228 s 26.590 s 37.322 s]
                        thrpt:  [643.06 Kelem/s 902.59 Kelem/s 1.4789 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 64 threads
                        time:   [41.926 s 54.231 s 63.360 s]
                        thrpt:  [505.05 Kelem/s 590.07 Kelem/s 763.25 Kelem/s]

scalability가 아직도 안 좋긴 하다.

[codingskynet]

같은 조건에서 main(b9ddbed)을 돌렸을 때 결과:

SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 1 threads
                        time:   [619.82 ms 629.81 ms 634.21 ms]
                        thrpt:  [788.39 Kelem/s 793.89 Kelem/s 806.68 Kelem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 2 threads
                        time:   [762.19 ms 770.69 ms 776.51 ms]
                        thrpt:  [1.2878 Melem/s 1.2975 Melem/s 1.3120 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 4 threads
                        time:   [899.90 ms 904.88 ms 910.03 ms]
                        thrpt:  [2.1977 Melem/s 2.2102 Melem/s 2.2225 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 8 threads
                        time:   [1.3461 s 1.3542 s 1.3618 s]
                        thrpt:  [2.9372 Melem/s 2.9538 Melem/s 2.9716 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 16 threads
                        time:   [2.5384 s 3.2486 s 4.1637 s]
                        thrpt:  [1.9214 Melem/s 2.4626 Melem/s 3.1516 Melem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 32 threads
                        time:   [20.542 s 24.320 s 27.556 s]
                        thrpt:  [580.64 Kelem/s 657.90 Kelem/s 778.88 Kelem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 48 threads
                        time:   [40.407 s 43.032 s 45.451 s]
                        thrpt:  [528.04 Kelem/s 557.73 Kelem/s 593.96 Kelem/s]
SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +5e5) by 64 threads
                        time:   [61.687 s 64.075 s 65.964 s]
                        thrpt:  [485.11 Kelem/s 499.42 Kelem/s 518.75 Kelem/s]

코어가 많아지면 소폭 이득을 보는 추세지만, 16코어에서 살짝 성능이 떨어진다는 게 보여진다. 전략을 수정하여 개선해보는 것이 좋을 듯.

[codingskynet]

Backoff를 제거하고, 일부 쓸모없는 명령어들 지우고, 아마 가장 병목이 컸을 get_height에서 write_lock 대신 read_lock을 쓰도록 하여, c5n.metal에서 taskset -c 0-17 cargo criterion --bench concurrrent로 scalability 어느 정도 잘 나오는 것 확인함. 그리고 parent쪽 read lock validation이 왜 필요한가에 대한 연구가 필요하다.

[codingskynet]

연구해본 결과, recover 함수쪽이 잘못된 것으로 판명되었다. 실제로 lock coupling이 유지가 되려면, node read guard를 validate한 후에, 다시 그 node의 parent read guard도 validate한 지를 해야 하는데 안 했던 것이 이유였다. 따라서, main에서 move_next의 node 및 node parent의 read guard를 validate 체크한 것이 위의 recover의 버그를 해결하는 수가 된 것이었다.

[codingskynet]

Benchmark: cargo criterion --bench concurrent (only run bench_mixed_seqlockavltree) Envirnment:

• SW: Windows 10 Pro 10.0.19043 Build 19043, WSL 2 Ubuntu 20.04(5.10.16.3-microsoft-standard-WSL2), w/ other minor programs running (Discord, Chrome, etc...)
• HW: Ryzen 5 3600 (6c 12t, static clock 4.2GHz), DDR4 3600MHz 16GiB

The branch seqlockavltree/backoff(5debcd5) result:

Detail

```text SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 1 threads time: [6.8761 ms 7.0022 ms 7.1394 ms] thrpt: [1.4007 Melem/s 1.4281 Melem/s 1.4543 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 2 threads time: [9.2419 ms 9.4737 ms 9.7234 ms] thrpt: [2.0569 Melem/s 2.1111 Melem/s 2.1641 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 4 threads time: [14.588 ms 15.048 ms 15.591 ms] thrpt: [2.5656 Melem/s 2.6582 Melem/s 2.7419 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 8 threads time: [23.097 ms 23.378 ms 23.661 ms] thrpt: [3.3811 Melem/s 3.4220 Melem/s 3.4637 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 12 threads time: [30.726 ms 31.399 ms 32.179 ms] thrpt: [3.7291 Melem/s 3.8217 Melem/s 3.9055 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 1 threads time: [7.6767 ms 7.8453 ms 8.0344 ms] thrpt: [1.2447 Melem/s 1.2747 Melem/s 1.3026 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 2 threads time: [7.1554 ms 7.3394 ms 7.5698 ms] thrpt: [2.6421 Melem/s 2.7250 Melem/s 2.7951 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 4 threads time: [7.4753 ms 7.5756 ms 7.6825 ms] thrpt: [5.2066 Melem/s 5.2801 Melem/s 5.3510 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 8 threads time: [8.2736 ms 8.4517 ms 8.6451 ms] thrpt: [9.2538 Melem/s 9.4656 Melem/s 9.6693 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 12 threads time: [9.6401 ms 9.8682 ms 10.107 ms] thrpt: [11.873 Melem/s 12.160 Melem/s 12.448 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 1 threads time: [11.272 ms 11.424 ms 11.573 ms] thrpt: [864.10 Kelem/s 875.35 Kelem/s 887.15 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 2 threads time: [12.388 ms 12.822 ms 13.321 ms] thrpt: [1.5014 Melem/s 1.5598 Melem/s 1.6144 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 4 threads time: [13.785 ms 14.054 ms 14.384 ms] thrpt: [2.7809 Melem/s 2.8462 Melem/s 2.9016 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 8 threads time: [17.477 ms 17.987 ms 18.537 ms] thrpt: [4.3157 Melem/s 4.4477 Melem/s 4.5775 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 12 threads time: [16.891 ms 17.201 ms 17.586 ms] thrpt: [6.8235 Melem/s 6.9764 Melem/s 7.1043 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 1 threads time: [7.7348 ms 7.8599 ms 7.9977 ms] thrpt: [1.2504 Melem/s 1.2723 Melem/s 1.2929 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 2 threads time: [7.8069 ms 7.9749 ms 8.1495 ms] thrpt: [2.4541 Melem/s 2.5079 Melem/s 2.5618 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 4 threads time: [8.9391 ms 9.0435 ms 9.1542 ms] thrpt: [4.3696 Melem/s 4.4231 Melem/s 4.4747 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 8 threads time: [10.352 ms 10.452 ms 10.569 ms] thrpt: [7.5696 Melem/s 7.6539 Melem/s 7.7280 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 12 threads time: [11.968 ms 12.151 ms 12.345 ms] thrpt: [9.7205 Melem/s 9.8758 Melem/s 10.027 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 1 threads time: [8.9909 ms 9.1337 ms 9.2861 ms] thrpt: [1.0769 Melem/s 1.0948 Melem/s 1.1122 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 2 threads time: [9.3845 ms 9.5580 ms 9.7590 ms] thrpt: [2.0494 Melem/s 2.0925 Melem/s 2.1312 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 4 threads time: [11.564 ms 11.719 ms 11.881 ms] thrpt: [3.3667 Melem/s 3.4133 Melem/s 3.4590 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 8 threads time: [16.308 ms 16.538 ms 16.828 ms] thrpt: [4.7540 Melem/s 4.8373 Melem/s 4.9055 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 12 threads time: [20.771 ms 21.342 ms 22.046 ms] thrpt: [5.4432 Melem/s 5.6228 Melem/s 5.7772 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 1 threads time: [9.3303 ms 9.4467 ms 9.5722 ms] thrpt: [1.0447 Melem/s 1.0586 Melem/s 1.0718 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 2 threads time: [10.770 ms 11.031 ms 11.316 ms] thrpt: [1.7674 Melem/s 1.8131 Melem/s 1.8569 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 4 threads time: [14.591 ms 15.013 ms 15.483 ms] thrpt: [2.5834 Melem/s 2.6644 Melem/s 2.7413 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 8 threads time: [22.158 ms 22.530 ms 22.930 ms] thrpt: [3.4888 Melem/s 3.5508 Melem/s 3.6104 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 12 threads time: [27.334 ms 27.752 ms 28.142 ms] thrpt: [4.2642 Melem/s 4.3240 Melem/s 4.3901 Melem/s] ```

[codingskynet]

Benchmark: cargo criterion --bench concurrnet (only run bench_mixed_seqlockavltree) Envirnment:

• SW: Amazon Linux 2(4.14.248-189.473.amzn2.aarch64)
• HW: AWS EC2 c6g.metal(Graviton 2, 64 cores, 128GiB)

The branch seqlockavltree/backoff(5debcd5) result:

Detail

```text SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 1 threads time: [12.196 ms 12.307 ms 12.456 ms] thrpt: [802.81 Kelem/s 812.58 Kelem/s 819.96 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 2 threads time: [17.864 ms 17.998 ms 18.141 ms] thrpt: [1.1025 Melem/s 1.1112 Melem/s 1.1196 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 4 threads time: [22.387 ms 22.621 ms 22.902 ms] thrpt: [1.7466 Melem/s 1.7682 Melem/s 1.7868 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 8 threads time: [32.580 ms 32.749 ms 32.930 ms] thrpt: [2.4294 Melem/s 2.4429 Melem/s 2.4555 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 16 threads time: [56.639 ms 56.846 ms 57.056 ms] thrpt: [2.8042 Melem/s 2.8146 Melem/s 2.8249 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 32 threads time: [105.32 ms 105.69 ms 106.02 ms] thrpt: [3.0182 Melem/s 3.0278 Melem/s 3.0382 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 48 threads time: [143.85 ms 144.19 ms 144.56 ms] thrpt: [3.3203 Melem/s 3.3289 Melem/s 3.3367 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 64 threads time: [191.36 ms 191.83 ms 192.28 ms] thrpt: [3.3284 Melem/s 3.3363 Melem/s 3.3445 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 1 threads time: [9.0065 ms 9.0651 ms 9.1192 ms] thrpt: [1.0966 Melem/s 1.1031 Melem/s 1.1103 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 2 threads time: [10.075 ms 10.083 ms 10.092 ms] thrpt: [1.9819 Melem/s 1.9835 Melem/s 1.9851 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 4 threads time: [14.765 ms 14.827 ms 14.891 ms] thrpt: [2.6861 Melem/s 2.6978 Melem/s 2.7090 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 8 threads time: [26.539 ms 26.754 ms 26.963 ms] thrpt: [2.9670 Melem/s 2.9902 Melem/s 3.0144 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 16 threads time: [51.035 ms 51.176 ms 51.322 ms] thrpt: [3.1176 Melem/s 3.1265 Melem/s 3.1351 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 32 threads time: [94.338 ms 94.505 ms 94.671 ms] thrpt: [3.3801 Melem/s 3.3861 Melem/s 3.3921 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 48 threads time: [148.91 ms 149.21 ms 149.49 ms] thrpt: [3.2109 Melem/s 3.2169 Melem/s 3.2233 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 64 threads time: [193.48 ms 193.69 ms 193.92 ms] thrpt: [3.3004 Melem/s 3.3042 Melem/s 3.3078 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 1 threads time: [14.844 ms 14.912 ms 14.974 ms] thrpt: [667.81 Kelem/s 670.58 Kelem/s 673.69 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 2 threads time: [18.150 ms 18.192 ms 18.234 ms] thrpt: [1.0969 Melem/s 1.0994 Melem/s 1.1019 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 4 threads time: [22.086 ms 22.145 ms 22.205 ms] thrpt: [1.8014 Melem/s 1.8063 Melem/s 1.8111 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 8 threads time: [33.198 ms 33.290 ms 33.381 ms] thrpt: [2.3966 Melem/s 2.4031 Melem/s 2.4098 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 16 threads time: [58.444 ms 58.656 ms 58.863 ms] thrpt: [2.7182 Melem/s 2.7278 Melem/s 2.7376 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 32 threads time: [105.16 ms 105.39 ms 105.60 ms] thrpt: [3.0304 Melem/s 3.0364 Melem/s 3.0429 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 48 threads time: [144.29 ms 144.87 ms 145.57 ms] thrpt: [3.2975 Melem/s 3.3132 Melem/s 3.3266 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 64 threads time: [179.47 ms 180.17 ms 180.82 ms] thrpt: [3.5394 Melem/s 3.5523 Melem/s 3.5660 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 1 threads time: [9.5720 ms 9.6295 ms 9.6848 ms] thrpt: [1.0325 Melem/s 1.0385 Melem/s 1.0447 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 2 threads time: [11.244 ms 11.265 ms 11.284 ms] thrpt: [1.7724 Melem/s 1.7755 Melem/s 1.7787 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 4 threads time: [15.910 ms 15.974 ms 16.046 ms] thrpt: [2.4929 Melem/s 2.5040 Melem/s 2.5141 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 8 threads time: [26.107 ms 26.233 ms 26.359 ms] thrpt: [3.0350 Melem/s 3.0496 Melem/s 3.0644 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 16 threads time: [50.989 ms 51.132 ms 51.276 ms] thrpt: [3.1204 Melem/s 3.1292 Melem/s 3.1379 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 32 threads time: [95.853 ms 96.061 ms 96.286 ms] thrpt: [3.3234 Melem/s 3.3312 Melem/s 3.3384 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 48 threads time: [142.57 ms 142.78 ms 142.98 ms] thrpt: [3.3570 Melem/s 3.3618 Melem/s 3.3669 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 64 threads time: [192.32 ms 192.42 ms 192.54 ms] thrpt: [3.3240 Melem/s 3.3260 Melem/s 3.3278 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 1 threads time: [11.180 ms 11.227 ms 11.273 ms] thrpt: [887.04 Kelem/s 890.72 Kelem/s 894.49 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 2 threads time: [14.334 ms 14.381 ms 14.428 ms] thrpt: [1.3862 Melem/s 1.3908 Melem/s 1.3953 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 4 threads time: [17.646 ms 17.721 ms 17.801 ms] thrpt: [2.2471 Melem/s 2.2572 Melem/s 2.2668 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 8 threads time: [28.651 ms 28.737 ms 28.823 ms] thrpt: [2.7755 Melem/s 2.7838 Melem/s 2.7922 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 16 threads time: [51.824 ms 52.122 ms 52.413 ms] thrpt: [3.0527 Melem/s 3.0697 Melem/s 3.0874 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 32 threads time: [95.964 ms 96.102 ms 96.245 ms] thrpt: [3.3249 Melem/s 3.3298 Melem/s 3.3346 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 48 threads time: [142.59 ms 143.07 ms 143.70 ms] thrpt: [3.3403 Melem/s 3.3550 Melem/s 3.3662 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 64 threads time: [193.27 ms 193.38 ms 193.49 ms] thrpt: [3.3077 Melem/s 3.3095 Melem/s 3.3114 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 1 threads time: [13.279 ms 13.342 ms 13.397 ms] thrpt: [746.45 Kelem/s 749.52 Kelem/s 753.09 Kelem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 2 threads time: [17.848 ms 17.991 ms 18.128 ms] thrpt: [1.1033 Melem/s 1.1117 Melem/s 1.1206 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 4 threads time: [22.519 ms 22.575 ms 22.635 ms] thrpt: [1.7672 Melem/s 1.7718 Melem/s 1.7763 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 8 threads time: [31.761 ms 31.922 ms 32.085 ms] thrpt: [2.4934 Melem/s 2.5061 Melem/s 2.5188 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 16 threads time: [52.958 ms 53.275 ms 53.599 ms] thrpt: [2.9851 Melem/s 3.0033 Melem/s 3.0213 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 32 threads time: [107.59 ms 107.85 ms 108.08 ms] thrpt: [2.9609 Melem/s 2.9671 Melem/s 2.9742 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 48 threads time: [143.38 ms 143.65 ms 143.93 ms] thrpt: [3.3349 Melem/s 3.3414 Melem/s 3.3477 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 64 threads time: [192.95 ms 193.64 ms 194.26 ms] thrpt: [3.2945 Melem/s 3.3051 Melem/s 3.3169 Melem/s] ```

[codingskynet]

Benchmark: cargo criterion --bench concurrnet (only run bench_mixed_seqlockavltree) Envirnment:

• SW: Amazon Linux 2(4.14.248-189.473.amzn2.x86_64)
• HW: AWS EC2 c5.12xlarge(Intel Xeon Platinum 8275CL CPU @ 3.00GHz, 24 cores 48 threads, 96GiB)

The branch seqlockavltree/backoff(5debcd5) result:

Detail

```text SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 1 threads time: [8.4092 ms 8.5250 ms 8.7274 ms] thrpt: [1.1458 Melem/s 1.1730 Melem/s 1.1892 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 2 threads time: [12.787 ms 12.901 ms 13.055 ms] thrpt: [1.5320 Melem/s 1.5502 Melem/s 1.5641 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 4 threads time: [15.472 ms 15.781 ms 16.219 ms] thrpt: [2.4662 Melem/s 2.5347 Melem/s 2.5854 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 8 threads time: [20.357 ms 20.802 ms 21.310 ms] thrpt: [3.7540 Melem/s 3.8457 Melem/s 3.9298 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 16 threads time: [27.325 ms 28.444 ms 29.640 ms] thrpt: [5.3980 Melem/s 5.6251 Melem/s 5.8554 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 32 threads time: [41.372 ms 43.474 ms 45.525 ms] thrpt: [7.0292 Melem/s 7.3607 Melem/s 7.7347 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 48 threads time: [53.452 ms 56.008 ms 58.564 ms] thrpt: [8.1962 Melem/s 8.5703 Melem/s 8.9800 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 1 threads time: [5.4864 ms 5.5035 ms 5.5224 ms] thrpt: [1.8108 Melem/s 1.8170 Melem/s 1.8227 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 2 threads time: [5.5352 ms 5.5438 ms 5.5531 ms] thrpt: [3.6016 Melem/s 3.6076 Melem/s 3.6133 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 4 threads time: [5.6590 ms 5.6660 ms 5.6732 ms] thrpt: [7.0506 Melem/s 7.0596 Melem/s 7.0684 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 8 threads time: [5.6745 ms 5.6788 ms 5.6842 ms] thrpt: [14.074 Melem/s 14.088 Melem/s 14.098 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 16 threads time: [5.7052 ms 5.7083 ms 5.7116 ms] thrpt: [28.013 Melem/s 28.029 Melem/s 28.045 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 32 threads time: [6.3647 ms 6.3681 ms 6.3715 ms] thrpt: [50.224 Melem/s 50.251 Melem/s 50.278 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 48 threads time: [6.9164 ms 6.9200 ms 6.9238 ms] thrpt: [69.326 Melem/s 69.364 Melem/s 69.400 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 1 threads time: [8.4593 ms 8.4800 ms 8.5047 ms] thrpt: [1.1758 Melem/s 1.1792 Melem/s 1.1821 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 2 threads time: [11.477 ms 11.513 ms 11.551 ms] thrpt: [1.7314 Melem/s 1.7371 Melem/s 1.7426 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 4 threads time: [10.980 ms 11.008 ms 11.036 ms] thrpt: [3.6245 Melem/s 3.6338 Melem/s 3.6429 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 8 threads time: [9.4674 ms 9.4918 ms 9.5170 ms] thrpt: [8.4060 Melem/s 8.4283 Melem/s 8.4500 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 16 threads time: [7.8493 ms 7.9014 ms 7.9483 ms] thrpt: [20.130 Melem/s 20.250 Melem/s 20.384 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 32 threads time: [9.8751 ms 10.010 ms 10.136 ms] thrpt: [31.571 Melem/s 31.968 Melem/s 32.405 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 48 threads time: [8.6940 ms 8.7828 ms 8.8665 ms] thrpt: [54.136 Melem/s 54.652 Melem/s 55.211 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 1 threads time: [5.9332 ms 5.9450 ms 5.9576 ms] thrpt: [1.6785 Melem/s 1.6821 Melem/s 1.6854 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 2 threads time: [6.5141 ms 6.5273 ms 6.5413 ms] thrpt: [3.0575 Melem/s 3.0641 Melem/s 3.0703 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 4 threads time: [6.8935 ms 6.9114 ms 6.9297 ms] thrpt: [5.7723 Melem/s 5.7875 Melem/s 5.8025 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 8 threads time: [7.2754 ms 7.2913 ms 7.3065 ms] thrpt: [10.949 Melem/s 10.972 Melem/s 10.996 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 16 threads time: [7.9145 ms 7.9478 ms 7.9786 ms] thrpt: [20.054 Melem/s 20.131 Melem/s 20.216 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 32 threads time: [9.6808 ms 9.7471 ms 9.8186 ms] thrpt: [32.591 Melem/s 32.830 Melem/s 33.055 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 48 threads time: [11.147 ms 11.297 ms 11.443 ms] thrpt: [41.948 Melem/s 42.489 Melem/s 43.061 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 1 threads time: [7.1532 ms 7.1911 ms 7.2433 ms] thrpt: [1.3806 Melem/s 1.3906 Melem/s 1.3980 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 2 threads time: [9.5376 ms 9.5811 ms 9.6254 ms] thrpt: [2.0778 Melem/s 2.0874 Melem/s 2.0970 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 4 threads time: [10.775 ms 10.830 ms 10.884 ms] thrpt: [3.6751 Melem/s 3.6936 Melem/s 3.7123 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 8 threads time: [12.001 ms 12.080 ms 12.159 ms] thrpt: [6.5797 Melem/s 6.6227 Melem/s 6.6660 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 16 threads time: [14.003 ms 14.164 ms 14.323 ms] thrpt: [11.171 Melem/s 11.296 Melem/s 11.426 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 32 threads time: [18.981 ms 19.465 ms 19.960 ms] thrpt: [16.032 Melem/s 16.440 Melem/s 16.859 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 48 threads time: [25.543 ms 26.225 ms 26.898 ms] thrpt: [17.845 Melem/s 18.303 Melem/s 18.792 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 1 threads time: [8.5571 ms 8.6111 ms 8.6916 ms] thrpt: [1.1505 Melem/s 1.1613 Melem/s 1.1686 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 2 threads time: [12.232 ms 12.299 ms 12.374 ms] thrpt: [1.6162 Melem/s 1.6262 Melem/s 1.6351 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 4 threads time: [14.385 ms 14.465 ms 14.543 ms] thrpt: [2.7504 Melem/s 2.7654 Melem/s 2.7807 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 8 threads time: [16.155 ms 16.280 ms 16.398 ms] thrpt: [4.8786 Melem/s 4.9140 Melem/s 4.9520 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 16 threads time: [19.262 ms 19.593 ms 19.921 ms] thrpt: [8.0315 Melem/s 8.1662 Melem/s 8.3067 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 32 threads time: [30.670 ms 31.440 ms 32.194 ms] thrpt: [9.9398 Melem/s 10.178 Melem/s 10.434 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 48 threads time: [34.412 ms 35.807 ms 37.240 ms] thrpt: [12.889 Melem/s 13.405 Melem/s 13.949 Melem/s] ```

[codingskynet]

Benchmark: cargo criterion --bench concurrnet (only run bench_mixed_seqlockavltree) Envirnment:

• SW: Amazon Linux 2(4.14.248-189.473.amzn2.x86_64)
• HW: AWS EC2 c5.12xlarge(Intel Xeon Platinum 8275CL CPU @ 3.00GHz, 24 cores 48 threads, 96GiB)

The branch seqlockavltree/backoff(5debcd5) result w/o Backoff:

Detail

```text SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 1 threads time: [8.2447 ms 8.3524 ms 8.5486 ms] thrpt: [1.1698 Melem/s 1.1973 Melem/s 1.2129 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 2 threads time: [12.587 ms 12.757 ms 12.951 ms] thrpt: [1.5443 Melem/s 1.5677 Melem/s 1.5889 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 4 threads time: [15.231 ms 15.508 ms 15.893 ms] thrpt: [2.5169 Melem/s 2.5793 Melem/s 2.6262 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 8 threads time: [19.370 ms 19.849 ms 20.372 ms] thrpt: [3.9270 Melem/s 4.0303 Melem/s 4.1302 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 16 threads time: [27.135 ms 28.383 ms 29.746 ms] thrpt: [5.3788 Melem/s 5.6373 Melem/s 5.8964 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 32 threads time: [42.098 ms 44.217 ms 46.399 ms] thrpt: [6.8968 Melem/s 7.2370 Melem/s 7.6014 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 100%, L: 0%, R: 0%, per: +1e4) by 48 threads time: [53.700 ms 55.752 ms 57.785 ms] thrpt: [8.3067 Melem/s 8.6096 Melem/s 8.9385 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 1 threads time: [5.3039 ms 5.3223 ms 5.3415 ms] thrpt: [1.8721 Melem/s 1.8789 Melem/s 1.8854 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 2 threads time: [5.3801 ms 5.3887 ms 5.3975 ms] thrpt: [3.7054 Melem/s 3.7115 Melem/s 3.7174 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 4 threads time: [5.4616 ms 5.4664 ms 5.4714 ms] thrpt: [7.3107 Melem/s 7.3175 Melem/s 7.3238 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 8 threads time: [5.4894 ms 5.4932 ms 5.4971 ms] thrpt: [14.553 Melem/s 14.563 Melem/s 14.574 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 16 threads time: [5.5063 ms 5.5090 ms 5.5118 ms] thrpt: [29.028 Melem/s 29.043 Melem/s 29.057 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 32 threads time: [6.2014 ms 6.2085 ms 6.2161 ms] thrpt: [51.479 Melem/s 51.542 Melem/s 51.601 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 100%, R: 0%, per: +1e4) by 48 threads time: [6.7858 ms 6.7912 ms 6.7964 ms] thrpt: [70.625 Melem/s 70.680 Melem/s 70.736 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 1 threads time: [8.2202 ms 8.2375 ms 8.2552 ms] thrpt: [1.2114 Melem/s 1.2140 Melem/s 1.2165 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 2 threads time: [10.749 ms 10.782 ms 10.814 ms] thrpt: [1.8494 Melem/s 1.8550 Melem/s 1.8607 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 4 threads time: [10.702 ms 10.739 ms 10.773 ms] thrpt: [3.7129 Melem/s 3.7247 Melem/s 3.7377 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 8 threads time: [9.1784 ms 9.2108 ms 9.2419 ms] thrpt: [8.6563 Melem/s 8.6855 Melem/s 8.7161 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 16 threads time: [7.5335 ms 7.5788 ms 7.6223 ms] thrpt: [20.991 Melem/s 21.111 Melem/s 21.238 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 32 threads time: [7.0536 ms 7.1198 ms 7.1852 ms] thrpt: [44.536 Melem/s 44.945 Melem/s 45.367 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 0%, L: 0%, R: 100%, per: +1e4) by 48 threads time: [6.1537 ms 6.2225 ms 6.3054 ms] thrpt: [76.125 Melem/s 77.140 Melem/s 78.002 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 1 threads time: [5.9662 ms 6.1685 ms 6.3692 ms] thrpt: [1.5701 Melem/s 1.6211 Melem/s 1.6761 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 2 threads time: [6.3248 ms 6.4349 ms 6.5698 ms] thrpt: [3.0442 Melem/s 3.1081 Melem/s 3.1622 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 4 threads time: [6.6900 ms 6.7002 ms 6.7107 ms] thrpt: [5.9606 Melem/s 5.9700 Melem/s 5.9791 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 8 threads time: [6.9945 ms 7.0125 ms 7.0307 ms] thrpt: [11.379 Melem/s 11.408 Melem/s 11.438 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 16 threads time: [7.5345 ms 7.5586 ms 7.5826 ms] thrpt: [21.101 Melem/s 21.168 Melem/s 21.236 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 32 threads time: [9.3520 ms 9.4386 ms 9.5212 ms] thrpt: [33.609 Melem/s 33.904 Melem/s 34.217 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 5%, L: 90%, R: 5%, per: +1e4) by 48 threads time: [10.920 ms 11.027 ms 11.128 ms] thrpt: [43.133 Melem/s 43.531 Melem/s 43.957 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 1 threads time: [6.9659 ms 7.0041 ms 7.0525 ms] thrpt: [1.4179 Melem/s 1.4277 Melem/s 1.4356 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 2 threads time: [9.4642 ms 9.5181 ms 9.5890 ms] thrpt: [2.0857 Melem/s 2.1013 Melem/s 2.1132 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 4 threads time: [10.659 ms 10.727 ms 10.792 ms] thrpt: [3.7065 Melem/s 3.7288 Melem/s 3.7525 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 8 threads time: [11.762 ms 11.852 ms 11.933 ms] thrpt: [6.7041 Melem/s 6.7498 Melem/s 6.8017 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 16 threads time: [13.534 ms 13.692 ms 13.862 ms] thrpt: [11.542 Melem/s 11.685 Melem/s 11.822 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 32 threads time: [19.101 ms 19.638 ms 20.174 ms] thrpt: [15.862 Melem/s 16.295 Melem/s 16.753 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 30%, L: 50%, R: 20%, per: +1e4) by 48 threads time: [24.118 ms 24.794 ms 25.458 ms] thrpt: [18.854 Melem/s 19.359 Melem/s 19.902 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 1 threads time: [8.3703 ms 8.4168 ms 8.4864 ms] thrpt: [1.1784 Melem/s 1.1881 Melem/s 1.1947 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 2 threads time: [12.120 ms 12.200 ms 12.281 ms] thrpt: [1.6286 Melem/s 1.6394 Melem/s 1.6502 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 4 threads time: [14.119 ms 14.205 ms 14.290 ms] thrpt: [2.7993 Melem/s 2.8160 Melem/s 2.8331 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 8 threads time: [15.793 ms 15.950 ms 16.102 ms] thrpt: [4.9683 Melem/s 5.0156 Melem/s 5.0656 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 16 threads time: [18.660 ms 19.039 ms 19.432 ms] thrpt: [8.2336 Melem/s 8.4039 Melem/s 8.5744 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 32 threads time: [27.923 ms 28.887 ms 29.788 ms] thrpt: [10.743 Melem/s 11.078 Melem/s 11.460 Melem/s] SeqLockAVLTree/Inserted +5e5 SeqlockAVLTree Ops (I: 50%, L: 0%, R: 50%, per: +1e4) by 48 threads time: [32.954 ms 34.263 ms 35.560 ms] thrpt: [13.498 Melem/s 14.009 Melem/s 14.566 Melem/s] ```

[codingskynet]

위에 통계들 취합하여 그려보면 다음과 같다. Backoff를 없애는 게, 이득이 큰 듯. 특히, 100% remove에서 차이가 너무 큼

Detail

     

[codingskynet]

주말에 cursor를 ThreadLocal로 가지고 있을 수 있도록 짜서 다시 벤치마크 돌려볼 것. 특히, ARM 서버(c6g.metal) 대신 NUMA 없이 잘 돌아가는 c5.12xlarge를 중심으로 벤치마킹하며, 성능을 깎아보는 것이 좋아 보인다.

[codingskynet]

Benchmark: cargo criterion --bench concurrnet (only run bench_mixed_seqlockavltree) Envirnment:

• SW: Amazon Linux 2(4.14.248-189.473.amzn2.x86_64)
• HW: AWS EC2 c5.12xlarge(Intel Xeon Platinum 8275CL CPU @ 3.00GHz, 24 cores 48 threads, 96GiB)

조금씩 수정한 것을 간단히 벤치마킹 돌려봤는데, 유의할만한 성능 변화는 없는 듯하다. 일단, 현재 짠 것이 semantics 상에선 최선이라 생각되기 때문에 이렇게 머지한다. cursor쪽 작업 등의 최적화는 다음 branch에서 하기로 함.

The branch seqlockavltree/backoff(5debcd5, 7117483, b8ab144) result w/o Backoff:

Detail