线程安全的已排序链表 [英] Thread-safe sorted linked list

问题描述

我正在尝试编写一个线程安全的已排序单个链表。我写了两个版本：粗粒度同步和细粒度同步。以下是两种实现方式：

I'm trying to write a thread-safe sorted single linked list. I wrote two versions: coarse grained synchronization and fine grained synchronization. Here are the two implementations:

细粒度：

public void add(T t) {                                                         
  Node curr = head;
  curr.lock.lock();

  while (curr.next != null) {
    // Invariant: curr is locked                                               
    // Invariant: curr.data < t                                                
    curr.next.lock.lock();                                                     

    if (t.compareTo(curr.next.data) <= 0) {                                    
      break;                                                                   
    }                                                                          

    Node tmp = curr.next;                                                      
    curr.lock.unlock();                                                        
    curr = tmp;                                                                
  }                                                                            

  // curr is acquired                                                          
  curr.next = new Node(curr.next, t);                                          
  if (curr.next.next != null) {  // old curr's next is acquired                
    curr.next.next.lock.unlock();                                              
  }                                                                            
  curr.lock.unlock();                                                          
}                                                                              

粗粒度：

public void add(T t) {
  lock.lock();
  Node curr = head;
  while (curr.next != null) {
    if (t.compareTo(curr.next.data) <= 0) {
      break;
    }                                                                          
    curr = curr.next;                                                          
  }                                                                            
  curr.next = new Node(curr.next, t);                                          
  lock.unlock();                                                               
}

我在4个线程（4个逻辑CPU核心）上插入两个版本20000个整数。每个线程的时间显示CPU时间（即它不包括等待时间）。

I timed the two version on 4 threads (on 4 logical CPU cores) inserting 20000 integers. The time per thread shows CPU time (i.e. it does not include waiting time).

Fine grained:
Worked 1 spent 1080 ms
Worked 2 spent 1230 ms
Worked 0 spent 1250 ms
Worked 3 spent 1260 ms
wall time: 1620 ms

Coarse grained:
Worked 1 spent 190 ms
Worked 2 spent 270 ms
Worked 3 spent 410 ms
Worked 0 spent 280 ms
wall time: 1298 ms

我最初的想法是 .lock（）和 .unlock（）是问题，但我分析了实现，他们一起只消耗了30％的时间。我的第二个猜测是细粒度的解决方案有更多的缓存未命中，但我怀疑它是因为单个链表与数组不同，本质上容易出现缓存未命中。

My initial thought was that .lock() and .unlock() are the problem, but I profiled the implementation and together they consumed only 30% of the time. My second guess is that the fine grained solution has more cache misses, but I doubt it because a single linked list, unlike an array, is inherently prone to cache misses.

知道为什么我没有得到预期的并行化吗？

Any idea why I don't get the expected parallelization?

推荐答案

是的，这可能是由于缓存未命中。包含锁的缓存行在CPU之间不断反弹。

Yes, that is probably due to cache misses. The cache lines containing the locks are continually bouncing between CPUs.

另外，请注意你已经获得了很多相似之处：

Also, note that you have gained quite a lot of parallellism:

Fine grained:
Worked 1 spent 1080 ms
Worked 2 spent 1230 ms
Worked 0 spent 1250 ms
Worked 3 spent 1260 ms
wall time: 1620 ms

Coarse grained:
Worked 1 spent 190 ms
Worked 2 spent 270 ms
Worked 3 spent 410 ms
Worked 0 spent 280 ms
wall time: 1298 ms

虽然每个人由于缓存未命中（并且还增加了开销），线程需要花费更多时间，整个过程只会稍慢。

Although each individual thread takes a lot more time, due to cache misses (and also increased overhead), the entire process is only slightly slower.

这篇关于线程安全的已排序链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！