0

I'm in need of a bitmask that can grow beyond the 64 bits that can be atomically manipulated by Java.

The "obvious" candidates (both of which require the introduction of some kind of locking scheme) are:

  • re-allocation as consecutive area of a fixed size
  • a fractured bitmask formed by chained words ("thread-safe BitSet")

Are there any papers on this matter? (Don't have to be Java-specific.)

User1291
  • 7,664
  • 8
  • 51
  • 108
  • What if you use an array of `long`s? Does finding the right `long` for a specific bit really has to be atomic with the flipping/checking of that bit? I can't imagine a use case in which that'll matter. If the check/flipping of a bit is atomic, then two threads that want to touch the same bit will perform the same calculation to figure out that bit's position, and only then try to perform the atomic action. Is that a problem? – Malt Nov 02 '17 at 09:27
  • @Malt An "array of ``long``s" *is* basically "re-allocation as a consecutive area of fixed size". And you're assuming that a bitmask operation only changes a single bit. I may, however, have to flip multiple and all of them should be flipped within the same atomic operation. Or I may need to check bits that reside in different ``long``s, where the check should be an atomic operation. – User1291 Nov 02 '17 at 09:42
  • @User1291 Is there an issue with using an array of `long`s and using locks for atomicity? I don't know of any papers about this and I can't imagine what all they'd cover if there were any, it sounds pretty straightforward to me. – xtratic Dec 08 '17 at 04:44
  • @xtratic well, the "using locks for atomicity" is the issue, mostly. It's too expensive. And I don't know if somebody hasn't examined whether the spatial locality provided by the array of longs is worth the copy-on-widening overhead. – User1291 Dec 08 '17 at 06:59

1 Answers1

0

From your clarifications, it seems like what you really need is papers on ways to write "atomic" operations in Java.

For what you want to do I can't think of a way to avoid using locks. After all, even just writing to a long or double is not atomic without synchronization.

Here are some links related to what you want to do:

You should determine what locking mechanism to use based on your expected use cases of this data structure.

https://blog.takipi.com/java-8-stampedlocks-vs-readwritelocks-and-synchronized/

Also, some people might complain about premature optimization but I also like to consider the efficiency of code before it's an issue. However using synchronization/locks in this case probably isn't as bad as you might think.

If you want lower level then I would resort to JNI.

However, no matter how low-level you go, I think using locks/synchronization would still be unavoidable since there's no guarantee the hardware would have instructions that could do what you want atomically. How would a CPU perform an or operation across multiple words atomically?

As a side note, if you are going to be using these bitmasks a lot and want the most performance, then it might possibly maybe be worth writing this code for a GPU. Though I'm not fully sure of the pros and cons, those would be left for further research...

I think you're looking for a level of efficiency that hardware simply cannot provide right now.

xtratic
  • 4,600
  • 2
  • 14
  • 32
  • Thanks for writing all that. However, that strikes me more as a general introduction to Java concurrency. I'm looking for a bit more "low level" stuff. The bitmasks I'm dealing with already are part of a locking scheme and we're on a hair trigger where we question every single new memory barrier inserted. Right now, were using bitmasks of type ``long`` because 64 bits are the most you can ``CAS`` at once and we'd like to keep what we replace that with as cheap as possible.(ideally, we'd manage to get intel tsx to work without the costly callback to Java unsafe, but no luck so far.) – User1291 Dec 08 '17 at 16:07
  • @User1291 Updated my response. Unfortunately I think you are asking for the impossible, but I still hope I answered your question. – xtratic Dec 08 '17 at 19:49