As shown on the previous post, the basic Harris algorithm has one node for each key, where each node has a "next" member with one bit reserved for the "marked" variable:
We also talked about the fact that managed languages (like Java) do not allow bit manipulation of references, which means that the classic Harris algorithm can not be implemented in Java. We can instead implement a variant which is HarrisAMR.
The source code for HarrisAMR can be seen in section 9.8 of "The Art of Multiprocessor Programming", the problem is that there are a few errors in the code, if you look at the first edition of this book. The revised edition has the correct code, but here are the modifications needed in case you only have the first edition:
Figure 9.26, line 27 should be:
snip = curr.next.compareAndSet(succ, succ, false, true);
Figure 9.27, line 40 should be:
curr = curr.next.getReference();
If you have neither the "first edition" nor the "revised first edition", then here is a link to our own implementation:
http://sourceforge.net/projects/ccfreaks/files/java/src/com/concurrencyfreaks/lists/HarrisAMRLinkedList.java
The AtomicMarkableReference class in java.util.concurrent uses the Copy-On-Write pattern to modify its member variables. It is composed of a "reference" and a boolean flag named "mark", both variables being final. Whenever one (or both) of these variables need to be modified, a new instance must created and replace the old one using a Compare-And-Swap (CAS). This technique is Lock-Free for modifications, which means it can be applied to Harris linked list without loss of guarantees of progress conditions.
In fact, in Java there is an extra indirection, caused by the existence of the class Pair inside the AtomicMarkableReference, as can be seen on the source code here. The Pair is the class that actually contains the "reference" and the "mark", but for simplicity, we will talk about AMR as being the everything put together, otherwise the next schematics would have been (even more) insane. On HarrisAMR, the "reference" in the AMR is a reference to the next node in the list.
This technique uses more memory and creates a slightly more complex linked list where the true nodes and the AMR instances alternate with each other, as shown in this figure:
Having an higher memory occupancy and slower traversal is not the only disadvantage of the HarrisAMR. To understand why, lets start by looking at what happens when we do an insertion in the list. Suppose for example we want to add the key B to the set on the following configuration, starting by creating Node B:
Now, a new AMR instance is created inside AtomicMarkableReference which references Node D and has a mark at false:
On Node A, we must now replace the AMR instance that is pointing to Node D with a new instance that points to Node B. Remember that these instances have an immutable (final) reference and mark so they can't be changed and a new instance must be created to replace the old one, using a CAS:
All that's left is for the Garbage Collector to cleanup the old instance that is pointing to Node D:
This whole procedure, not only causes churn on the GC, it also causes cache flushing because now the "old" AMR reference that is going to be collected by the GC no longer needs to be in cache, and four new pointers have to be put in the cache: from next to AMR B, from AMR B to Node B, from Node B do AMR D, and from AMR D to Node D.
So, for a single add(), we had to create three new objects in memory, and cleanup an old instance... and we didn't even look a the case where the add() has to retry because another thread did an add() in front of it, in that case, even more (unused) objects will be created!
No comments:
Post a Comment