Highly Scalable: Lock-Free Linked List (LF List) with Execution Time Analysis

The provided source code implements a lock-free linked list (LF List) using atomic operations to ensure thread safety without using traditional locking mechanisms. The operations provided include:

Add: Adds a new element to the list.
Remove: Removes an element from the list.
Contains: Checks if an element exists in the list.
Find: Locates a specific element in the list.

Key Concepts in the Code:

Atomic Compare and Swap (CAS):
- The CAS method ensures that updates to the next pointer of a node are done atomically. The CAS operation checks if the current value of the next pointer matches the expected value and then updates it to the new value. If another thread modifies the pointer in the meantime, the operation fails, and the process is retried.
Marking and Unmarking:
- The list uses a "marking" technique to help with lazy deletion. This allows a node to be logically deleted without physically removing it right away, preventing inconsistencies in concurrent access. The GetMark and AttemptMark methods are used to handle the marking mechanism.
Memory Management:
- The CAS and AttemptMark operations ensure memory is safely manipulated without locking, offering thread safety and improved performance compared to traditional lock-based structures.

Execution Time Analysis:

The performance of the lock-free linked list under different thread loads is measured, and the results show how the execution time changes as the number of threads increases. Here’s the performance table:

Number of Threads	Execution Time (ms)
1 Thread	841ms
2 Threads	532ms
4 Threads	340ms
8 Threads	336ms
16 Threads	341ms

Key Insights:

Performance Scaling: As the number of threads increases from 1 to 8, the execution time decreases significantly, likely due to better parallelism. However, after 8 threads, the performance reaches a plateau around 340ms, suggesting that the system's resources (e.g., CPU, memory) are being fully utilized.
No Significant Increase in Execution Time for 16 Threads: The performance doesn't degrade significantly when increasing from 8 to 16 threads. This suggests the lock-free design is effectively handling higher concurrency without significant contention or locking overhead.

Hardware Specifications:

CPU: Intel Core i5-3570 (3.40 GHz)
RAM: 8GB DDR3

The system specifications indicate a moderate-level processor and sufficient memory for handling the workload of a lock-free linked list with up to 16 threads.

Conclusion:

The lock-free linked list provides excellent performance even under high concurrency, making it suitable for applications requiring low-latency and high-throughput operations.
Atomic operations are key to its success, as they prevent blocking and reduce contention between threads, especially when scaling up the number of concurrent threads.
The results show a strong performance advantage over traditional locking mechanisms, especially in highly concurrent environments.

This lock-free design is beneficial for applications where scalability and performance are critical, such as real-time systems or multi-threaded applications.

Source code

class LFNODE {
public:
    int key;
    LFNODE *next;

    LFNODE(int v) {
        key = v;
        next = nullptr;
    }

    LFNODE() {
        next = nullptr;
    }

    bool CAS(LFNODE *old_node, LFNODE *new_node, bool oldMark, bool newMark) {
        int oldvalue = reinterpret_cast(old_node);
        if (oldMark) oldvalue = oldvalue | 0x1;
        else oldvalue = oldvalue & 0xFFFFFFFE;

        int newvalue = reinterpret_cast(new_node);
        if (newMark) newvalue = newvalue | 0x1;
        else newvalue = newvalue & 0xFFFFFFFE;
        return CAS(oldvalue, newvalue);
    }

    bool CAS(int oldValue, int newValue) {
        return atomic_compare_exchange_strong(reinterpret_cast(&next), &oldValue, newValue);
    }

    LFNODE *GetNext() {
        int temp = reinterpret_cast(next);
        return reinterpret_cast(temp & 0xFFFFFFFE);
    }

    LFNODE *GetNextMark(bool *deleted){
        int temp = reinterpret_cast(next);
        *deleted = (temp & 0x1) != 0;
        return reinterpret_cast(temp & 0xFFFFFFFE);
    }

    bool GetMark() {
        int temp = reinterpret_cast(next);
        return (temp & 0x1);
    }

    bool AttemptMark(LFNODE *oldValue, bool newMark) {
        int temp = reinterpret_cast(oldValue);
        temp = temp & 0xFFFFFFFE;

        int newValue = temp;
        if (newMark) newValue = newValue | 0x1;

        return CAS(temp, newValue);
    }
};

class LFLIST{
private:
    LFNODE head, tail;
public:
    LFLIST(){
        head.key = 0x80000000;
        tail.key = 0x7FFFFFFF;
        head.next = &tail;
    }

    void Init(){
        while (head.next != &tail) {
            LFNODE *temp = head.next;
            head.next = head.next->GetNext();
            delete temp;
        }
    }

    void Find(int key, LFNODE **pred, LFNODE **curr) {

        bool deleted = false;

        retry:
        *pred = &head;
        *curr = (*pred)->next;

        while (true) {
            LFNODE *succ = (*curr)->GetNextMark(&deleted);

            while (deleted) {
                if ((*pred)->CAS((*curr), succ, false, false) == false){
                    goto retry;
                }
            }

            if ((*curr)->key >= key) {
                return;
            }
            (*pred) = (*curr);
            (*curr) = succ;
        }
    }

    bool Add(int x)
    {
        LFNODE *pred, *curr;

        while (true) {

            Find(x, &pred, &curr);
            
            if (curr->key == x) {
                return false;
            }

            LFNODE *node = new LFNODE(x);
            node->next = curr;
            if (pred->CAS(curr, node, false, false)) {
                return true;
            }
            delete node;
        }
    }

    bool Remove(int x)
    {
        LFNODE *pred, *curr;

        while (true) {

            Find(x, &pred, &curr);

            if (curr->key != x) {
                return false;
            }

            LFNODE *succ = curr->GetNext();

            if (curr->AttemptMark(succ, true) == false) continue;

            pred->CAS(curr, succ, false, false);
            return true;
        }
    }

    bool Contains(int x)
    {
        LFNODE *curr = &head;
        while (curr->key < x) {
            curr = curr->GetNext();            
        }
        return (curr->key == x && curr->GetMark() == false);
    }
};

Execution time of threads

1 Threads. 841msec
2 Threads. 532msec
4 Threads. 340msec
8 Threads. 336msec
16 Threads. 341msec

Hardware specification

Intel(R) Core(TM) i5-3570 CPU @ 3.40GHz
8.00 GB DDR3

Monday, June 2, 2014

Lock-Free Linked List (LF List) with Execution Time Analysis