## 5 Performance Evaluation
### Performance Results
#### 5.3.2 Kernel-Level Benchmark  
Figure 6 shows the experimental results of the kernel-level linked list and chained hash table. The top three graphs shows the results of the linked list, while the bottom three graphs represent the chained hash table's results. **Linked list:** RCU shows the best performance at the 2% update ratio, whereas the performance decreases significantly at the 20% and 50% update ratios. The performance gradually reduces after 16 and 8 threads, respectively, in the case of 20% and 50% updates. When comparing performance efficiency by number of threads, 70-thread execution has a low performance efficiency equivalent to two to three-thread execution. Contention between threads owing to the synchronization of locks between write threads is the leading cause of RCU's performance degradation. When the number of threads is modest, RLU shows scalable performance, but it degrades at update ratios of 2%, 20%, and 50% for exceeding 30, 50, and 50 threads, respectively. This is because when RLU updates an object, it overwrites the original version with an updated copied version. To securely overwrite the original object with the updated copied version, the writing thread needs to wait until all threads reading the original object have exited the RLU section. Therefore, as the update ratio and the number of threads increase, the RLU performance decreases. MV-RLU performs less well than RCU at the 2% update ratio, but it outperforms at 20% and 50% update rates. The multi-version and distributed log recycling policy of MV-RLU contribute to performance improvement even with an increase in the number of execution threads. Comparing the performance of MV-RLU and RLU, the performance difference becomes larger as the number of threads increases. The reason for this is that the rlu_synchronize() cost of RLU increases significantly as the number of threads increases. MV-RLU delays log recycling until the log size is filled, and only the latest version among multiple versions is overwritten (write back) in the original object, so the number of overwrites is reduced by \(\frac{1}{number\_of-versions}\). The performance results of RCU and MV-RLU are similar to those of the user-level linked list. It can be shown that regardless of the user or kernel level, RCU and MV-RLU show consistent performance. The performance results of RLU are significantly different from those of the user-level linked list. The user-level results of RLU show linear performance scalability, whereas the kernel-level results of RLU do not. The difference between user and kernel-level implementation of RLU is that the kernel-level RLU maintains the size of the allocated memory in metadata of each log and each node so that kfree() releases a proper size of the allocated memory (described in Section 4). It is analyzed that the tiny increase of the metadata size for keeping the allocated memory size adversely affects the performance. In particular, the cost of managing memory is expected to rise as the number of threads  
Figure 6: Linked list (**upper**) and hash table (**lower**) on kernel level. increases. As the metadata size grows, cache line bouncing between competing threads becomes more frequent, and the kmalloc()/kfree() cost grows. **Hash table:** The performance trends of the kernel-level hash table are comparable to those of the user-level hash table, with a few exceptions. RCU shows that performance increases linearly with the number of threads and subsequently decreases after 64, 48, and 16 threads at 2%, 20%, and 50% update ratios, respectively. The performance trends of RLU are comparable to those of the user-level chained hash table, with performance degrading at all update ratios. At all update ratios, performance saturates or decreases beyond 16-thread execution. The decrease is especially pronounced in the case of the 50% update. MV-RLU shows a linear performance increase at the update ratios of 2% and 20%, but at the 50% update ratio, performance saturation and decrease occur when running more than 50 threads.