Add Support for Atomic Operators (like CAS, etc.)

[Shinmera]

It would be great if ABCL offered support for CAS and other atomic operators in order to allow the implementation of lock-free datastructures and algorithms.

A variety of implementations already offer support for operations like cas, atomic-incf, atomic-push, and atomic-pop. For instance, both ECL and SBCL follow the protocol described in the SBCL manual.

I've accumulated the information for atomic operator support in a new portability library called Atomics. For ABCL to be supported, it would need to offer CAS on at least svref, car, cdr, and structure accessor places. Naturally it would be great if it offered more than that still, but those are the most fundamental.

As for how to achieve this: since I don't know anything about ABCL internals I can't say too much, though Java itself offers support for CAS through sun.misc.Unsafe and java.util.concurrent.atomic.*.

[easye]

@Shinmera I'll take a look at what we need to do. I have some notes from a couple years back that I need to dig up…

[Slids]

So I did a little looking. The obvious thing to do is use varhandles (and not use unsafe as it may go way): https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/invoke/VarHandle.html

Sadly this requires targeting 1.7 and not 1.6

[easye]

ABCL 2 will ~probably~ targets Java 8 (neé 1.8) as the lowest JVM supported, so we can add "true CAS operations" as part of its feature list.

Thanks for looking into this.

[Slids]

I'd be happy to work on this bug but I've no idea when abcl 2 is being release, so if you have some method of notification please drop me a message.

[easye]

ABCL 2 is scheduled for September 2020, when I intend to release a version targeting openjdk8

@Slids I guess I should fork ABCL now to give ya a place to add patches. Stay tuned…

https://abcl.org/trac/milestone/2.0.0

[easye]

boolean compareAndSet(expectedValue, updateValue)

is the basic operation on Java Atomics. It was introduced in openjdk8, but I wonder if it is possible to synthesize a version in pure Java that would work on openjdk6? Then we could add a compatibility layer to back-port.

[Slids]

The real problem is with calling compare and set on vectors, you have to look at the type possibilities.

On Sun, Jun 7, 2020, 2:43 AM Mark Evenson notifications@github.com wrote:

boolean compareAndSet(expectedValue, updateValue)

is the basic operation on Java Atomics. It was introduced in openjdk8, but I wonder if it is possible to synthesize a version in pure Java that would work on openjdk6? Then we could add a compatibility layer to back-port.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/armedbear/abcl/issues/92#issuecomment-640166402, or unsubscribe https://github.com/notifications/unsubscribe-auth/AD7Y3JZ3SMAEQRYHXDBW6X3RVMZIPANCNFSM4GSBOVXQ .

[easye]

The real problem is with calling compare and set on vectors, you have to look at the type possibilities.

Having my paws bloody overhauling our byte vectors with java.nio.ByteBuffer makes this a problem that I would be ready to tackle. @Slids Do you have some sort of reference to or implementation of the efficient algorithms for compare and set on sequence types that I could perhaps study a bit? I have naive ideas of how to approach this, so it would probably be best if I educated myself a bit more on the prior art here.

[Slids]

I would avoid any self implementation and just sue the java concurrent libraries. Have to find the ones I was using though...

[easye]

Some notes on ABCL2 https://abcl-dev.blogspot.com/2020/06/a-future-history-of-arming-bears.html

[easye]

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/invoke/VarHandle.html

Actually this requires openjdk9, which we don't support, so the current target of minimum openjdk8 for the next ABCL is not sufficient if we wish to efficiently implement the necessary semantics on any memory that a cons can reference.

So, the question becomes: it is ok if ABCL2 drops openjdk8 support, and only supports openjdk11?

Discussion https://mailman.common-lisp.net/pipermail/armedbear-devel/2020-October/004143.html

[alessiostalla]

It's OK for me! However, doesn't this require the compiler to target newer bytecode? Isn't it still targeting Java 5 bytecode?

On Tue, 6 Oct 2020 at 17:53, Mark Evenson notifications@github.com wrote:

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/invoke/VarHandle.html

Actually this requires openjdk9, which we don't support.

So, the question becomes: it is ok if ABCL2 drops openjdk8 support, and only supports openjdk11?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/armedbear/abcl/issues/92#issuecomment-704374220, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHV3NR4S65VVD5ABXQJPKTSJM4PTANCNFSM4GSBOVXQ .

[easye]

Sent from my iPad

On 06.10.2020, at 18:56, Alessio Stalla notifications@github.com wrote:

 It's OK for me! However, doesn't this require the compiler to target newer bytecode? Isn't it still targeting Java 5 bytecode?

Nope. We compile and load Java 5 bytecode today, working through openjdk15.

The Bear lopes through the loophole that while the system classloaders require an advanced minimum bytecode, one is still able to load Java 5 bytecode from arrays of bytes.

[alessiostalla]

I mean, to use VarHandles, doesn't the classfile version have to be quite recent?

On Tue, 6 Oct 2020 at 20:16, Mark Evenson notifications@github.com wrote:

Sent from my iPad

On 06.10.2020, at 18:56, Alessio Stalla notifications@github.com wrote:

 It's OK for me! However, doesn't this require the compiler to target newer bytecode? Isn't it still targeting Java 5 bytecode?

Nope. We compile and load Java 5 bytecode today, working through openjdk15.

The Bear lopes through the loophole that while the system classloaders require an advanced minimum bytecode, one is still able to load Java 5 bytecode from arrays of bytes.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/armedbear/abcl/issues/92#issuecomment-704458602, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHV3NSV6O5FTDOHAXRM7VLSJNNITANCNFSM4GSBOVXQ .

[easye]

I mean, to use VarHandles, doesn't the classfile version have to be quite recent?

Hmm. Not sure, as it depends if we would have to change our compiler. The Java code of the ABCL gets compiled with javac against the JDK platform libraries, so if we were able to replace LispObject purely Java-side, we wouldn't necessarily need to change our compiler.

But modernizing the compiler output is certainly one of the high-priority tasks with the putative ABCL2 codebase.

[alessiostalla]

Oh I see I thought it was another thing like InvokeDynamic which cannot be expressed in Java but I was wrong.

On Wed, 7 Oct 2020 at 10:42, Mark Evenson notifications@github.com wrote:

I mean, to use VarHandles, doesn't the classfile version have to be quite recent?

Hmm. Not sure, as it depends if we would have to change our compiler. The Java code of the ABCL gets compiled with javac against the JDK platform libraries, so if we were able to replace LispObject purely Java-side, we wouldn't necessarily need to change the compiler.

But modernizing the compiler output is certainly one of the high-priority tasks with the putative ABCL2 codebase.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/armedbear/abcl/issues/92#issuecomment-704787119, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAHV3NU6SWZ3HWGM2RMXNLDSJQSW3ANCNFSM4GSBOVXQ .

[davidsun0]

Would using AtomicReferenceFieldUpdater work? It wouldn't require updating to a newer Java version (available since Java 5) and it wouldn't require changing the compiler.

The downside is that fields like car and cdr would have to be declared volatile, which might degrade performance when not using CAS.

[mdbergmann]

Not sure if relevant. Ignore if not. I've implemented AtomicReference here: https://github.com/mdbergmann/cl-gserver/blob/master/src/atomic/atomic-abcl.lisp