线程安全的排序链表 [英] 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屋！