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

Shinmera · 2019-01-24T08:29:26Z

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.*.

The text was updated successfully, but these errors were encountered:

easye · 2019-01-24T15:43:52Z

@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 · 2020-01-01T18:04:49Z

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 · 2020-01-02T09:05:40Z

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 · 2020-01-02T21:13:35Z

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 · 2020-06-06T14:31:22Z

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 · 2020-06-07T06:43:08Z

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 · 2020-06-07T17:55:18Z

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 ***@***.***> 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 <#92 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AD7Y3JZ3SMAEQRYHXDBW6X3RVMZIPANCNFSM4GSBOVXQ> .

easye · 2020-06-08T05:16:09Z

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 · 2020-06-12T17:25:42Z

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

easye · 2020-06-17T14:01:38Z

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

easye · 2020-10-06T15:53:12Z

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 · 2020-10-06T16:55:56Z

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 ***@***.***> 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 <#92 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAHV3NR4S65VVD5ABXQJPKTSJM4PTANCNFSM4GSBOVXQ> .

easye · 2020-10-06T18:16:26Z

Sent from my iPad

On 06.10.2020, at 18:56, Alessio Stalla ***@***.***> 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 · 2020-10-07T08:37:15Z

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 ***@***.***> wrote: Sent from my iPad > On 06.10.2020, at 18:56, Alessio Stalla ***@***.***> 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 <#92 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAHV3NSV6O5FTDOHAXRM7VLSJNNITANCNFSM4GSBOVXQ> .

easye · 2020-10-07T08:42:05Z

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 · 2020-10-07T08:54:34Z

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 ***@***.***> 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 <#92 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAHV3NU6SWZ3HWGM2RMXNLDSJQSW3ANCNFSM4GSBOVXQ> .

davidsun0 · 2021-11-19T16:03:34Z

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 · 2021-11-19T16:38:12Z

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

VarHandles were introduced in openjdk9, so the code needs to be conditionalized somehow. It is currently being developed on openjdk17. <armedbear#92>

Shinmera changed the title ~~Add Support for Compare-And-Swap~~ Add Support for Atomic Operators (like CAS, etc.) Jan 24, 2019

Shinmera mentioned this issue Jan 24, 2019

Support More Implementations Shinmera/atomics#1

Open

mdbergmann mentioned this issue Jun 3, 2021

failed on ABCL mdbergmann/cl-gserver#29

Closed

easye self-assigned this Jun 22, 2023

easye added a commit to easye/abcl that referenced this issue Jun 28, 2023

Explorations in adding atomic compare and swap

04bd305

VarHandles were introduced in openjdk9, so the code needs to be conditionalized somehow. It is currently being developed on openjdk17. <armedbear#92>

easye mentioned this issue Jun 28, 2023

Explorations in adding atomic compare and swap #602

Open

easye added a commit to easye/abcl that referenced this issue Jun 29, 2023

Explorations in adding atomic compare and swap

2a88f22

VarHandles were introduced in openjdk9, so the code needs to be conditionalized somehow. It is currently being developed on openjdk17. <armedbear#92>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

Shinmera commented Jan 24, 2019

easye commented Jan 24, 2019

Slids commented Jan 1, 2020

easye commented Jan 2, 2020 •

edited

Loading

Slids commented Jan 2, 2020

easye commented Jun 6, 2020 •

edited

Loading

easye commented Jun 7, 2020

Slids commented Jun 7, 2020 via email

easye commented Jun 8, 2020 •

edited

Loading

Slids commented Jun 12, 2020

easye commented Jun 17, 2020

easye commented Oct 6, 2020 •

edited

Loading

alessiostalla commented Oct 6, 2020 via email

easye commented Oct 6, 2020 via email •

edited

Loading

alessiostalla commented Oct 7, 2020 via email

easye commented Oct 7, 2020 •

edited

Loading

alessiostalla commented Oct 7, 2020 via email

davidsun0 commented Nov 19, 2021

mdbergmann commented Nov 19, 2021

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

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

Comments

Shinmera commented Jan 24, 2019

easye commented Jan 24, 2019

Slids commented Jan 1, 2020

easye commented Jan 2, 2020 • edited Loading

Slids commented Jan 2, 2020

easye commented Jun 6, 2020 • edited Loading

easye commented Jun 7, 2020

Slids commented Jun 7, 2020 via email

easye commented Jun 8, 2020 • edited Loading

Slids commented Jun 12, 2020

easye commented Jun 17, 2020

easye commented Oct 6, 2020 • edited Loading

alessiostalla commented Oct 6, 2020 via email

easye commented Oct 6, 2020 via email • edited Loading

alessiostalla commented Oct 7, 2020 via email

easye commented Oct 7, 2020 • edited Loading

alessiostalla commented Oct 7, 2020 via email

davidsun0 commented Nov 19, 2021

mdbergmann commented Nov 19, 2021

easye commented Jan 2, 2020 •

edited

Loading

easye commented Jun 6, 2020 •

edited

Loading

easye commented Jun 8, 2020 •

edited

Loading

easye commented Oct 6, 2020 •

edited

Loading

easye commented Oct 6, 2020 via email •

edited

Loading

easye commented Oct 7, 2020 •

edited

Loading