Geek Answers Handbook

Java - stealing bits from links

How do I steal 2 MSBs from an address to perform an atomic operation? I'm trying to make one word cas

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 can be used if I need only one additional flag. AtomicStampedReference can be used, but it is inefficient, as it creates an additional box containing timeStamp and a link.

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

+6
source share
6 answers

Perhaps you can implement this using sun.misc.Unsafe

Among other things, it has several compareAndSwap methods that can work with arbitrary binary data inside any object.

Having said that, if you are embedding a binary search tree, I would suggest looking at the immutable constant data structures . The benefits of this include:

  • They are thread safe by definition due to immutability
  • They do not require locks.
  • The ability to perform structural sharing will be a big improvement in performance if you start doing more complex things (such as subtree snapshots) - basically you avoid the need to take protective copies.
+3
source

This is not possible without implementing your own JVM, which supports this kind of operation and correctly handles the flag bit, for example. when executing the GC (all links must be identified at this point, and moving collectors will need to change them). Even then, this contradicts the principles of Java development, which do not include explicit dereferencing or arithmetic of pointers (which I would recount by changing the bits in the link and masking them for dereferencing).

Instead, I recommend that you create a new composite Edge type for flags and 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 } }
+3
source

Copying extracts from the book “The Art of Multiprocessing Programming” p. 215 of 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 label. These fields can be atomically updated, either together or individually. We make each subsequent field node s AtomicMarkableReference. Thread A logically deletes currA by setting the label bit in the next field node s and sharing the physical delete with other threads executing add () or remove (): as each thread moves the list, it clears the list by physically deleting (using compareAndSet ()) any marked nodes that he is facing. In other words, threads executing add () and remove () do not intersect marked nodes, they delete them before continuing. The contains () method remains the same as in the LazyList algorithm, traversing all nodes whether they are checked or not, and testing if the item is in the list based on its key and label.

+1
source

The best suggestion I can give you for working in Java would be to make your bit-twiddling by array indexes, not addresses, since Java does not expose addresses.

0
source

To extract bits from objects available for reference variables, you will need to create your own JVM.

First you need to make sure that the bits are not actually used (for example, taking the least significant bits in a link when the JVM always aligns objects on a 16-byte boundary). But some JVMs use all bits of a 32-bit link.

Then you will need to enter the code every time the link loads to clear these bits before accessing the related object.

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

0
source

You are not allowed to steal bits from a link, but there is a way around this: you can use AtomicStampedReference, which allows you to perform comparisons and swaps to atomically update both the link and the integer. You can use an integer as status, or you can steal bits from an MSB integer if you want. You can do bit operations with 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 an AtomicStampedReference integer and used them as a status bit, and I used the remaining 30 bits of the integer as a counter to prevent the ABA problem.

0
source

More articles:


All Articles