Comparison of Multithreaded Performance for Different Synchronization Methods in Linked Lists

The performance table compares the execution time of different synchronization techniques as the number of threads increases, based on a set of operations performed on a linked list. Here are the key findings:

Synchronization Type	1 Thread	2 Threads	4 Threads	8 Threads	16 Threads
Coarse-grained	1211ms	3265ms	3965ms	77828ms	79354ms
Fine-grained	7074ms	6680ms	6817ms	80780ms	81509ms
Optimistic	1819ms	1452ms	1222ms	6330ms	10995ms
Lazy	1297ms	1066ms	902ms	5743ms	10618ms
Non-blocking	841ms	532ms	340ms	336ms	341ms

Key Observations:

1. Coarse-grained synchronization: This method has the highest execution time and shows significant performance degradation as the number of threads increases. It is less efficient because it locks the entire data structure for each operation, preventing multiple threads from performing concurrent operations.

2. Fine-grained synchronization: This approach performs better than coarse-grained synchronization but still suffers from substantial performance drops as the number of threads increases. Fine-grained synchronization locks only the necessary parts of the data structure, but still involves locking individual components for each operation.

3. Optimistic synchronization: Optimistic synchronization, which assumes no conflicts and validates at the end, performs better than both coarse-grained and fine-grained synchronization, especially as the number of threads increases. It reduces contention by not locking data structures during operations, only checking for conflicts afterward.

4. Lazy synchronization: Lazy synchronization, which postpones certain operations until necessary, outperforms both coarse-grained and fine-grained methods, especially as the number of threads increases. It reduces contention by delaying some synchronization work.

5. Non-blocking synchronization: This is the most efficient method across all thread counts. Non-blocking synchronization allows threads to operate concurrently without locking, leading to the best performance in both low and high thread counts.

void task(int num_threads)
{
    int key;

    for (int i = 0; i < NUM_TEST / num_threads; i++) {
        switch (rand() % 3) {
        case 0: key = rand() % KEY_RANGE;
            list.Add(key);
            break;
        case 1: key = rand() % KEY_RANGE;
            list.Remove(key);
            break;
        case 2: key = rand() % KEY_RANGE;
            list.Contains(key);
            break;
        default: cout << "Error\n";
            exit(-1);
        }
    }
}

int main()
{
    vector  threads;
    for (int i = 1; i <= 16; i *= 2){
        threads.clear();
        list.Init();
        auto s = high_resolution_clock::now();
        for (int j = 0; j < i; ++j)
            threads.push_back(thread{ task, i });
        for (auto &t : threads) t.join();
        auto d = high_resolution_clock::now() - s;
        cout << i << " Threads.   ";
        cout << duration_cast(d).count() << "msec\n";
    }
}

Source Code Explanation:

The code provided uses a task function to perform random operations (add, remove, or check for the presence of a key) on a linked list. The number of threads is varied, and the performance is measured using high_resolution_clock. The results of the execution times are printed to the console.

• Key Operations:
  • Add(key): Adds a new key to the list.
  • Remove(key): Removes a key from the list.
  • Contains(key): Checks if a key exists in the list.
• Thread Creation: Threads are created based on the number of desired threads (from 1 to 16) and the task function is executed in parallel.

Performance Insights:

• Non-blocking and lazy synchronization methods show significant performance improvements, especially as the number of threads increases, by reducing locking contention and allowing threads to perform operations more concurrently.
• Coarse-grained and fine-grained synchronization methods, while useful in some scenarios, are not well-suited for high concurrency scenarios as they can cause significant contention and performance degradation as the number of threads increases.

This comparison shows that in highly concurrent environments, non-blocking and lazy synchronization methods offer the best performance, whereas coarse-grained and fine-grained synchronization techniques are less effective in scaling with increasing threads.