In the last week, I focus on
1) Creating an independent skip list data structure and related interfaces.
Now it has only two levels so that I don't have to modify too much existing code. But it is easy to be transformed into the data structure with any number of levels if necessary. Unfortunately, its performance is not good. In some cases, it's only 1/2 of original version. It reminded me that even conflict-tracking didn't consume too much CPU time, it was on the critical path and wrapped by a pair of lock acquiring and releasing. Slower conflicts tracking would result in more lock contentions, which would make the performance drop quickly.
2) Using some tricks to improve its performance.
For example, I found if the length of the conflict list is smaller than 10, the original linked list is faster
than the skip list. So I used it in a hybrid way: if the total conflicts are more than 10, using skip list; otherwise us ing linked list.
Now, the performance is approximately equal to the original version in different benchmarks.
But I don't found a case in which the new version is much faster.
The patch is attached.
So far, I have tried: 1) using hash table for conflict tracking.
2) reducing the global lock contention
3) using skip list for conflict tracking.
But all of them did not improve the performance. So I'm a little confused now about what to do next.
Could you please give me any suggestions?