Lista vinculada classificada com segurança para threads
Estou tentando escrever um lista vinculada classificada segura com thread. Escrevi duas versões: sincronização de granulação grossa e sincronização de granulação fina. Aqui estão as duas implementações:
Fine grained:
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();
}
Grão granulado:
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();
}
Cronometrei a versão duas em 4 threads (em 4 núcleos lógicos de CPU) inserindo 20000 números inteiros. O tempo por thread mostra o tempo da CPU (ou seja, não inclui o tempo de espera
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
Meu pensamento inicial foi que.lock()
e.unlock()
são o problema, mas criei um perfil da implementação e, juntos, eles consumiram apenas 30% do tempo. Meu segundo palpite é que a solução refinada tem mais falhas de cache, mas duvido que uma única lista vinculada, diferente de uma matriz, seja inerentemente propensa a falhas de cach
Alguma idéia de por que não recebo a paralelização esperad