java - 线程安全的排序链表

Question

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

细粒度:

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();                                                               
}

我在插入 20000 个整数的 4 个线程(在 4 个逻辑 CPU 内核上)上为两个版本计时。每个线程的时间显示 CPU 时间(即不包括等待时间)。

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% 的时间.我的第二个猜测是细粒度解决方案有更多的缓存未命中，但我对此表示怀疑，因为与数组不同，单个链表天生就容易发生缓存未命中。

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

Answer 1

您可以获得接近每线程粗粒度版本的挂墙时间 首先在没有锁的情况下遍历列表以找到间隙，然后从 当前，这次使用锁，遍历列表以确保没有干预 在 current 和 current->next 之间由其他线程插入。 (当然，我否认“头”总是至高无上的事实:)