Mam dwie implementacje stosu, jedną opartach na lockach, a drugą non-blocking:
package ds;
import java.util.concurrent.atomic.AtomicInteger;
public class BlockingStack<E> {
private Node<E> head = new Node<>();
private final AtomicInteger size = new AtomicInteger();
public synchronized void push(E e) {
final Node<E> newNode = new Node<>();
newNode.value = e;
newNode.next = head;
head = newNode;
size.getAndIncrement();
}
public synchronized E pop() {
final Node<E> oldHead = head;
if (oldHead == null) {
return null;
}
head = oldHead.next;
size.getAndDecrement();
return oldHead.value;
}
public int size() {
return size.get();
}
class Node<E> {
E value;
Node<E> next;
}
}
package ds;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.locks.LockSupport;
public class NonBlockingStack<E> {
private final AtomicReference<Node<E>> head =
new AtomicReference<>();
private final AtomicInteger size = new AtomicInteger();
public int size() {
return size.get();
}
public void push(E e) {
Node<E> newNode = new Node<>();
newNode.value = e;
Node<E> oldHead;
do {
oldHead = head.get();
newNode.next = oldHead;
} while (!compareAndSet(oldHead, newNode));
size.getAndIncrement();
}
public E pop() {
Node<E> oldHead;
Node<E> newHead;
do {
oldHead = head.get();
if (oldHead == null) {
return null;
}
newHead = oldHead.next;
} while (!compareAndSet(oldHead, newHead));
size.getAndDecrement();
return oldHead.value;
}
public boolean compareAndSet(final Node<E> current, final Node<E> next) {
if (head.compareAndSet(current, next)) {
return true;
} else {
LockSupport.parkNanos(1);
return false;
}
}
class Node<E> {
E value;
Node<E> next;
}
}
Chciałem przetestować wydajność obu implementacji przy różnych ilościach wątków/operacji:
package buffers;
import ds.BlockingStack;
import ds.NonBlockingStack;
import java.util.concurrent.CountDownLatch;
public class Main {
private static final int NUM_OF_THREADS = 8;
private static final int OPERATIONS = 100_000;
private static final Thread[] THREADS = new Thread[NUM_OF_THREADS];
public static void main(String[] args) throws InterruptedException {
final BlockingStack<Integer> ints = new BlockingStack<>();
// final NonBlockingStack<Integer> ints = new NonBlockingStack<>();
final CountDownLatch cdl = new CountDownLatch(NUM_OF_THREADS + 1);
for (int i = 0; i < NUM_OF_THREADS; i++) {
THREADS[i] = new Thread(() -> {
try {
cdl.countDown();
cdl.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
for (int j = 0; j < OPERATIONS; j++) {
ints.push(j);
}
});
}
for (Thread t : THREADS) {
t.start();
}
long start = System.nanoTime();
cdl.countDown();
for (Thread t : THREADS) {
t.join();
}
long elapsed = System.nanoTime() - start;
System.out.println("elapsed: " + elapsed);
System.out.println("size: " + ints.size());
long nsPerItem = elapsed / (NUM_OF_THREADS * (long) OPERATIONS);
System.out.print("throughput: " + nsPerItem + " ns/item");
}
}
Efekt jest taki, że przykładowo dla 8 wątków, z 100.000 operacjami stack z lockami jest szybszy/taki sam niż/jak ten nieblokujący. Czemu?