Lock free linked list is performing worse than the locked counterpart

Question

I am trying to compare the performance of locked and lock free linked list data structure. I have implemented this algorithm for lock free linked list. Both the programs are implemented in C.

I am testing for 4 threads. Each thread has 1000 insert operations.

I am using Intel PCM tool to measure the performance.

Here are my findings: Lock free:

Median of L3 Misses=1012699
Median of L2 Misses=1479741
Median of L3 Hits=484128
Median of L2 Hits=1797537
Median of Time=1.80696
Median of Cycles=5296042019
Median of IPC=1.536135
Median of Bytes Read=444423232
Median of Bytes Written=25414144 

Locked:

Median of L3 Misses=711796.5
Median of L2 Misses=1517899
Median of L3 Hits=819408.5
Median of L2 Hits=2282527
Median of Time=0.244517
Median of Cycles=894265192
Median of IPC=0.8495695
Median of Bytes Read=174872576
Median of Bytes Written=24722912

The locked version performs better on every count except IPC. Is this what is supposed to happen? Or the lock Free data structure should perform better?

If yes, then what is the benefit of using lock free data structures? Any help will be appreciated.

Answer 1

The locked version performs better on every count except IPC. Is this what is supposed to happen? Or the lock Free data structure should perform better?

Generally speaking, which will perform better is a function of both workload details and implementation details. The paper you reference says

Lock-free data structures also have the potential to have better performance

(emphasis added), but it does not promise better performance in every case. Although multiple threads may be able to modify the lock-free data structure at the same time, each modification involves more operations even when there are no conflicts. When there are conflicts, performance degrades.

I observe also that your lock-free code has a higher proportion of cache misses than does your locked code. Although I cannot confidently explain that, I can think of at least two plausible reasons why that would be an expected consequence of the lock-free implementation. Naturally, less effective cache usage significantly degrades performance.

If yes, then what is the benefit of using lock free data structures?

The paper says that the primary benefit is:

If an implementation is lock-free, delays or failures of individual processes do not block the progress of other processes in the system.