I am currently preparing some trainingpapers about multithreading and I thought some things might be of interest for you.
For pretty long the only possible way for save multithreading in java was to do locking using either synchronized or a mutex/semaphore… These techniques are quite heavy weight and nearly unusable for treestructures when you want to have locks for each node.
A long time ago some wise guys invented the compareandset operations which are atomically executed. Since jdk 5 the java.util.atomic package provides versions of the primitive dataypes that support this operation.
Compare and set means that within one operation the cpu checks a value and if the value has the expected value sets it to a new one.
To showcase what you can do I wrote up a little quadtree using this functionality.
Some notes:
- cas only makes sense on a MULTICORE or MULTIPROCESSOR system as it is aimed at systems with several processors (on a singlecore system cas will actually reduce the efficiency of your system).
- cas sometimes uses something that probably got taught to you as a nono but due to the nature of the algorithm and the multiple cores is a big yesyes: SPINLOCKS
- the quadtree does breadth first search to allow multiple threads to work on the structure
- the code might contain bugs, I will be able to look over it later this week (this is my first cas based quadtree, i only used cas for some dataproccessing in the past)
- cas is dangerous as you have to watch more closely what you lock and what you release, there is no help from java for that stuff as is for standard locks
This nodeclass allows several threads to manipulate/create the structure.
package de.pflanzenmoerder.trees.quadtree;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.atomic.AtomicBoolean;
/**
* A node in the quadtree.
*
* @author jochen
*
*/
public class Node {
/**
* Bounding volume of this node.
*/
private BoundingVolume volume;
/**
* Contains all the children of this node.
*/
private Set<QuadLeaf> children;
/**
* Contains all the child nodes of this node.
*/
private Set<Node> childNodes;
/**
* Is this node a leaf?
*/
private boolean leaf;
/**
* Minimum size of a node.
*/
private Float minExtend;
/**
* Atomic boolean for cas operations.
*/
private AtomicBoolean lockBool = new AtomicBoolean(false);
/**
* Constructor.
*
* @param volume
* boundingvolume of this node.
*/
public Node(BoundingVolume volume, Float minExtend) {
this.volume = volume;
this.minExtend = minExtend;
if (minExtend.equals(volume.getExtend())) {
leaf = true;
children = new HashSet<QuadLeaf>();
return;
}
leaf = false;
childNodes = new HashSet<Node>();
}
/**
* Check if the node is a leaf.
*
* @return
*/
public boolean isLeaf() {
return leaf;
}
/**
* Check if the given leaf intersects the node.
* @param child
* @return
*/
public boolean intersects(QuadLeaf child) {
return volume.intersects(child.getBoundingVolume());
}
/**
* Add a new child to the node.
* @param child
*/
public void addChild(QuadLeaf child) {
Set<Node> collectedNodes=new HashSet<Node>();
if (leaf) {
children.add(child);
return;
}
if (childNodes.size() == 0) {
Float _extend = volume.getExtend() / 2;
Node newNode;
// left top
newNode = new Node(new BoundingVolume(volume.getX() - _extend,
volume.getY() - _extend, _extend), minExtend);
newNode.addChild(child);
if (newNode.intersects(child)) {
newNode.lock();
collectedNodes.add(newNode);
}
childNodes.add(newNode);
// right top
newNode = new Node(new BoundingVolume(volume.getX() + _extend,
volume.getY() - _extend, _extend), minExtend);
newNode.addChild(child);
if (newNode.intersects(child)) {
newNode.lock();
collectedNodes.add(newNode);
}
childNodes.add(newNode);
// left bottom
newNode = new Node(new BoundingVolume(volume.getX() - _extend,
volume.getY() + _extend, _extend), minExtend);
newNode.addChild(child);
if (newNode.intersects(child)) {
newNode.lock();
collectedNodes.add(newNode);
}
childNodes.add(newNode);
// right bottom
newNode = new Node(new BoundingVolume(volume.getX() + _extend,
volume.getY() + _extend, _extend), minExtend);
newNode.addChild(child);
if (newNode.intersects(child)) {
newNode.lock();
collectedNodes.add(newNode);
}
childNodes.add(newNode);
}
if (collectedNodes.size() == 0) {
//check what nodes the child intersects
for (Node node : childNodes) {
if (node.intersects(child)) {
collectedNodes.add(node);
do{
//spinlock!!! :)
}while(!node.lock());
}
}
}
//we are done processing, unlock
unlock();
for (Node node : collectedNodes) {
node.addChild(child);
}
}
/**
* Used to perform a cas for locking this node.
*
* @return false if the lock failed.
*/
public boolean lock() {
return lockBool.compareAndSet(false, true);
}
/**
* Used to perform a cas for unlocking this node.
*
* @return false if the unlock failed.
*/
public boolean unlock() {
return lockBool.compareAndSet(true, false);
}
}
If there is interest I will post another class that shows how to do multithreaded collisiondetection when I am done with it.
Thank you for contributing this pflanzenmoerder!