Optimistic Lock Coupling

from paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method"

In actual projects, there are some lock-free data structures, especially database-related ones such as BwTree, Split-Ordered List (also known as Lock Free HashTable) when there are many write conflicts. The performance loss is very serious, and sometimes it is not as good as the brainless Mutex. However, the performance of the brainless Mutex is often very bad under normal circumstances, so is there an intermediate form that can solve this problem?

This is the intermediate form. So this can be used everywhere as a general lock, and the performance is satisfactory.

But I have a lock-free data structure that is well designed and optimized for usage scenarios. Can’t it be your implementation?

Of course, this is better, but when you don't have 114514 PHD students to optimize your data structure, and you don't have 1919810 powerful debugging masters to deal with problems such as Memory Order, it will be tricky.

At this time, my project is already online, the investor has given me money.

So what are the disadvantages of such a data structure?

Of course there is~

The disadvantage of this data structure is mainly because of the use of a 61bit version, when this version is full, we can lie flat. Of course, your data structure is crazy to change to this binary, it should be a problem for you to write the code.

Bench Mark

source code is under \benches dir. you can run it on your own~

Bench Result on my MacOS 2.3 GHz Intel Core i5 Images

• heavy read
• heavy write
• read only
• write only

Drawback

The shortcomings of optimistic lock are obvious. When there is a serious conflict, it will be slammed by Mutex and others. But when read > write, optimistic locking works better.

Lock Usage

when 3 reader core and 2 writer core

removed intermediate part of blocking log