Потокобезопасный отсортированный связанный список

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

Я рассчитал две версии на 4 потока (на 4 логических ядрах процессора)) вставив 20000 целых чисел.Время на поток показывает время ЦП (т.е. оно не включает время ожидания).

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

Вы могли бы достичь времени стены, близкого к времени для крупнозернистой версии для каждого потока, сначала пройдясь по списку без блокировок, чтобы найти разрыв, а затем по текущему, и на этот раз используя блокировки, пройдясь по списку, чтобы убедиться, чтоне было никаких промежуточных вставок другими потоками между текущим и текущим-> следующим.(Конечно, я обесцениваю тот факт, что «голова» всегда царит:)

Answer 2

Да, возможно, это связано с отсутствием кэша.Строки кэша, содержащие блокировки, постоянно пересекаются между процессорами.

Также обратите внимание, что вы получили довольно много параллелизма:

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

Хотя каждый отдельный поток занимает намного больше временииз-за промахов в кеше (а также из-за увеличения накладных расходов) весь процесс лишь немного медленнее.

Answer 3

в дополнение к ответу ninjalj - точные блокировки также

1. отключает некоторые оптимизации компилятора в существующем коде
2. отключает некоторые оптимизации ЦП - например, предварительная выборка
3. принудительно использует памятьполучать семантику при блокировке и освобождать семантику при разблокировке - вызывая межпроцессорную синхронизацию и аннулирование кэшей - что напрямую не отображается как стоимость lock () в профилировщике, но увеличивает стоимость последующего доступа к данным.

Answer 4

Появляется проблема с производительностью. Я думаю, вам следует сравнить производительность со встроенной реализацией и однопоточной версией.

for (int r = 0; r < 5; r++) {
    long start = System.nanoTime();
    ConcurrentLinkedQueue<Integer> list = new ConcurrentLinkedQueue<Integer>();
    for (int i = 0; i < 500000; i++)
        list.add(i);
    long time = System.nanoTime() - start;
    System.out.printf("Adding 500K %,d took ms%n", time / 1000 / 1000);
}

печать

Adding 500K 192 took ms
Adding 500K 154 took ms
Adding 500K 95 took ms
Adding 500K 211 took ms
Adding 500K 424 took ms

Answer 5

Я что-то упустил? Я не вижу никакого типа кэширования в вашем коде. Кроме того, вы должны пересмотреть способ использования блокировки. Вам следует блокировать список целиком, чтобы ограничить количество блокировок, а также предотвратить состояние гонки, как показано ниже.

thread1: Read Element X
thread2: Removes X + 1
thread1: Read Element X + 1 and fails since the element is no long valid.
thread1: Is unable to finish going through the list since it has been removed.

Вы можете разбить список на части, но вам нужно разобраться со случаем, когда вы читаете последний элемент в разделе и удаляете первый элемент в следующем разделе.

Вы также можете сделать так, чтобы блокировать / разблокировать нужно было только определенным функциям, в зависимости от того, какой тип операции выполняется (т.е. это операция чтения, и в данный момент операция записи не выполняется).