Я имел в виду попадания / пропуски кэша процессора. Придется еще раз подумать, но я не думаю, что ваше состояние гонки действительно, потому что для удаления элемента X + 1 вам нужно будет приобрести X.
аюсь написатьпотокобезопасный отсортированный единый связанный список, Я написал две версии: грубая и точная синхронизация. Вот две реализации:
Мелкозернистый:
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% времени. Мое второе предположение состоит в том, что мелкозернистое решение имеет больше ошибок кеширования, но я сомневаюсь в этом, потому что один связанный список, в отличие от массива, по своей природе подвержен ошибкам кэширования.
Есть идеи, почему я не получаю ожидаемого распараллеливания?