java - stealing bits from references

Question

How do I steal 2 MSBs from an address to do an atomic operation? I'm trying to do a single word CAS

An example

public class Node
{
    long key;
    long value;
    Node lchild; // format is flag1,flag2,address
    Node rchild; // format is flag1,flag2,address
}

public void createNode()
{
    Node n1 = new Node(); //this should create a node with format 0,0,address1
}

public void setFlag1(Node n1)
{
    Now the new address should be in format 1,0,address1
}

public void setFlag2(Node n1)
{
    Now the new address should be in format 0,1,address1
}

AtomicReference could be used if I needed only one extra flag. AtomicStampedReference could be used but it is not efficient as it creates an extra box containing timeStamp and a reference.

A similar problem in C is discussed in stealing bits from a pointer

Designation

If the pointer is word aligned, you want to steal the two LSBs not the two MSBs. Most pointers are word aligned. I have no idea how you'd get to the bit-representation of a pointer in Java, though. – Barometry

Why doesn't java.util.concurrent.AtomicReference work for you? – Borne

when I do the call Node n1 = new Node(), would the operating system always assign a space which is word aligned? I'm trying to steal MSBs to avoid ABA problem which can happen with compareAndSwap. Also can you please explain why stealing from LSBs is more efficient? – Designation

@JimGarrison: I wish I could use AtomicReference. But I need to steal two bits. I think AtomicReference uses only one extra bit. Please correct me if I'm wrong – Designation

There is no way to access the bits of a reference unless you write some native code. – Sonneteer

Have you actually tried AtomicStampedReference and found that it performed too poorly? – Surfacetosurface

@BrianGordon: Yes I tried and it is slow. I'm using this node structure in a Binary Search Tree. When AtomicStampedReference is used, each step in traversing down the tree requires to dereference the AtomicStampedReference object to get the reference to the child. – Designation

Note that you can probably get away with "stealing" a few bits on the low end on many (but not all) platforms, but taking from the high end is a lot iffier. And either way you're going to run afoul of GC, even if you manage to not simply break ordinary execution. – Sonneteer

(New objects will normally be aligned on a 8 or 16-byte boundary. However, the JVM could do goofy things with Integer objects, eg, and "allocate" them entirely in the reference. And some JVMs (so-called 32/64 implementations) use 4-byte references but shift over 4 bits to access 36 bits of address space.) – Sonneteer

will java RTTI solve my problem completely? I haven't implemented it yet. Before that, will using RTTI be faster than atomicStampedRefence? – Designation

"Java RTTI" is kind of a meaningless term. And to the extent that it has any meaning, it has essentially nothing to do with synchronization. – Sonneteer

I just solved this problem using Java RTTI. Instead of 2 bits, I had 4 subclasses of type "00", "01", "10" & "11" and a common superclass. During runtime, I identify the bits based on the class type. It gave me 2X speedup. – Designation

Answer 1

You can probably implement this using sun.misc.Unsafe

• http://www.docjar.com/docs/api/sun/misc/Unsafe.html

Among other things, this has a number of compareAndSwap methods that can work with arbitrary binary data within any Object.

Having said that, if you are implementing a binary search tree I'd suggest looking at immutable persistent data structures. Advantages of these include:

• They are thread safe by definition because of immutability
• They require no locks
• The ability to do structural sharing will be a big performance win once you start doing more complicated stuff (e.g. snapshotting of subtrees) - basically you avoid the need to take defensive copies.

Remonstrate

what is the difference between this unsafe package and the standard concurrent package in java? And Why do you think using CAS from unsafe package will solve my problem? – Designation

Basically, Unsafe lets you manipulate data in an object without following Java's usual type safety rules. This is risky, and you could easily cause some pretty nasty bugs - but on the flipside you can get some great performance. Normally I would advise against it. – Remonstrate

Answer 2

This is impossible without implementing your own JVM which supports this kind of operations and deals with the flag bits properly, e.g. when doing GC (all references need to be identified at this point and moving collectors will need to change them). Even then, this is against the design principles of Java which do not include explicit dereferencing or pointer arithmetic (which I would count changing bits in a reference and masking them for dereferencing towards).

Instead, I would recommend you to create a new composite Edge type of the flags and the Node:

public class Node {
    long key;
    long value;
    Child lchild; // child = node reference + flags
    Child rchild;
}

// this is the edge type which should also be used to reference the root node with flags
public class Child {
    Node child;
    BitSet flags;

    public Child(Node node) {
        this.child = node;
        this.flags = new BitSet(2); // we initialize the flags with 00
    }
    public void setFlag(int index) {
        this.flags.set(index); // index would be 0 or 1 here for the two flags
    }
    public boolean isFlagSet(int index) {
        return this.flags.get(index); // index would be 0 or 1 here for the two flags
    }
}

Zebulen

what do you mean by composite edge type. could you please elaborate? – Designation

@Designation I've added a code example to illustrate the suggestion. – Guenna

SchmeiBer Thanks for the example. So when I create a new node in binary search tree with this structure, should I use new Node() or new Child(). – Designation

@Designation new Child(theNode) would be correct with theNode being the node which should be integrated in the tree - the naming of the classes could be improved here, but I wanted to stay close to the question with it – Guenna

Answer 3

Copying an extract from the book "The art of multiprocessor programming" p.215 by Maurice Herlihy and Nir Shavit:

As described in detail in Pragma 9.8.1, an AtomicMarkableReference object encapsulates both a reference to an object of type T and a Boolean mark. These fields can be atomically updated, either together or individually. We make each node’s next field an AtomicMarkableReference. Thread A logically removes currA by setting the mark bit in the node’s next field, and shares the physical removal with other threads performing add() or remove(): as each thread traverses the list, it cleans up the list by physically removing (using compareAndSet()) any marked nodes it encounters. In other words, threads performing add() and remove() do not traverse marked nodes, they remove them before continuing. The contains() method remains the same as in the LazyList algorithm, traversing all nodes whether they are marked or not, and testing if an item is in the list based on its key and mark.

Kellda

Answer 4

The best suggestion I can give you for working in Java would be to do your bit-twiddling on array indices rather than addresses, since Java does not expose addresses.

Haymes

Answer 5

To take bits out of those available for object reference variables will require creating your own JVM.

You will first have to assure that the bits are not actually used (eg, by taking the low-order bits in a reference when the JVM always aligns objects on a 16-byte boundary). But some JVMs use all bits of a 32-bit reference.

Next, you'll have to inject code every time a reference is loaded to clear those bits before accessing the associated object.

Then you'll have to do the same for the garbage collector.

Sonneteer

Answer 6

You're not allowed to steal bits from a reference, but there's a way around it: you can use the AtomicStampedReference, which allows you to do a compare and swap to atomically update both a reference and an integer. You can use the integer as a status, or you can steal bits from the MSB of the integer if you want. You can do bit operations on integers in java, which is pretty cool:

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

I ended up writing a java program where I stole 2 bits from the integer of the AtomicStampedReference and used them as status bits, and I used the remaining 30 bits of the integer as a counter to prevent the ABA problem.

Endotoxin