## 5 Performance Evaluation
### Performance Results
#### 5.3.1 User-Level Benchmark  
Figure 5 shows the experimental results of the user-level linked list and chained hash table. The top three graphs shows the results of linked list, while the bottom three graphs represent the chained hash table's results. **Linked list:** RCU shows linear performance scalability up to 50 threads at an update ratio of 2%, but the performance is significantly reduced at update ratios of 20% and 50%. RLU shows the best performance among the others. MV-RLU shows the lowest performance at an update ratio of 2%, but it offers linear performance scalability in all update cases. The RCU performance decreases significantly as the update ratio increases or the running threads increase. As seen in Section 4.1, the RCU uses spinlock for write operations, so write threads are processed serially. In particular, since user-level RCU uses blocking wait (rcu_synchronization()) for memory reclamation, the performance scalability decreases as the update ratio increases or the number of execution threads grows. Therefore, if the update ratio is low and the number of running threads is not high, RCU shows linear scalability, as shown in Figure 5a, whereas the performance significantly drops when the update ratios increase, as shown in Figure 5b,c. The performance of RLU and MV-RLU increases as the number of threads increases, regardless of the update ratio. The reason that MV-RLU performs worse than RLU is because of the way MV-RLU traverses for data structures. MV-RLU and RLU both read data structures in a similar fashion. That is, it reads the latest valid version when threads enter the critical section. MV-RLU maintains more versions than RLU to increase parallelism. Therefore, in MV-RLU, if the critical section lengthens similarly to a linked list, the number of versions grows, which increases the version traversal cost when traversing for data structures. The average length of the linked list we evaluated is 200 times longer than the average length of a chained hash table with 1000 nodes. Therefore, as the critical section of MV-RLU becomes longer, the cost of version traversal increases, affecting performance. RLU outperforms them  
Figure 5: Linked list (**upper**) and hash table (**lower**) on user level. all due to its lower version traversal cost and fewer write conflicts. RLU allows concurrent operations between threads, unless writing to the same object. When the number of threads is low compared to the nodes, the probability of a write conflict for the same object falls. In this case, the log reclaiming cost of RLU is reduced. Since RLU maintains only two versions, the version search cost is relatively low when traversing nodes in the linked list. In the case of RCU, since the write thread is synchronized with a spinlock, the performance decreases considerably when the number of threads and the update ratio increase. **Hash table:** The performance result of the chained hash table is quite different from that of the linked list. RCU shows a performance increase in proportion to the number of threads in all update ratios, but a certain number of threads experience a performance drop or saturation. These phenomena are clearly observed in the execution of 18 and 24 threads that exceed the NUMA node boundary in all update cases. Please note that the main thread of the benchmark is pinned to the core 0 of CPU 0, and the threads that perform benchmark operations are sequentially allocated to the core 1 to 17 of CPU 0, so the 18 th thread is assigned to CPU 1. RLU shows the best performance in the linked list evaluation but the lowest in the chained hash tables. At the 2% update ratio, performance tends to increase relatively linearly, but at the 20% or 50% update ratio, the performance decreases or gets saturated after running 18 threads. MV-RLU shows the best performance among the synchronization schemes. Although the performance of MV-RLU is almost in par with RCU on the 2% update ratio, MV-RLU shows the best performance in almost all cases.