On 15/11/2023 10:55 PM, claptrap wrote:
> That doesnt make any sense, the whole point of CAS is that it is atomic, immediately after it has completed you have no guarantees anyway, what difference does it make if it's wrapped in a function call?

I understand that it seems like it does not make sense. Lock-free concurrent data structures are a highly advanced topic, that very few people in the world today can implement successfully. About the only people who are qualified to touch them for production software would be kernel developers for a specific cpu family.

They rely quite heavily on the premise that atomic operations happen immediately in the codegen and then based upon the results do set actions in response. This is timing based it has to be preciese or they will interfere with each other. You do not have much lee-way before you start getting segfaults.

I only ever saw partial success with ldc after seven months of researching them. For obvious reasons I do not recommend people going down this particular path of study, because you are going to get burned pretty badly guaranteed.



Regardless compilers like gcc have intrinsics for all of stdatomic. We need to be matching it otherwise what D supports will not line up with what the system C compiler can offer in terms of use cases. https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

On Wednesday, 15 November 2023 at 10:26:32 UTC, Richard (Rikki) Andrew Cattermole wrote:
> They rely quite heavily on the premise that atomic operations happen immediately in the codegen and then based upon the results do set actions in response. This is timing based it has to be preciese or they will interfere with each other. You do not have much lee-way before you start getting segfaults.

whoever write code like that deserves all the problems it creates.
This assumes specific CPU behaviour and may be completely broken on other systems.

On 16/11/2023 2:26 AM, DrDread wrote:
> whoever write code like that deserves all the problems it creates.
> This assumes specific CPU behaviour and may be completely broken on other systems.

Yup, that's lock-free concurrent data structures for you. Need specialists to have any chance of working reliably.

On Wednesday, 15 November 2023 at 10:26:32 UTC, Richard (Rikki) Andrew Cattermole wrote:
> On 15/11/2023 10:55 PM, claptrap wrote:
> I understand that it seems like it does not make sense. Lock-free concurrent data structures are a highly advanced topic, that very few people in the world today can implement successfully. About the only people who are qualified to touch them for production software would be kernel developers for a specific cpu family.

Im saying it doesnt make sense because i have worked on / implemented some lock free data structures. Ive shipped software that relied on them.

None of the literature ive read ever had any algorithms that relied on "getting things done quickly" after a CAS.

Fundamentally it cant work since the thread can be interupted immediatly after completing the CAS. So if you algorithm relies on something else happening within a specific time frame after a CAS it is not going to work.

So im looking for an explanation or a pointer to an algorithm that exhibits what you describe because it is counter to my experience.


> They rely quite heavily on the premise that atomic operations happen immediately in the codegen and then based upon the results do set actions in response. This is timing based it has to be preciese or they will interfere with each other. You do not have much lee-way before you start getting segfaults.

I can see that getting an update done quickly can help with contention, but if the algorithm breaks when things arnt done quickly you're pretty much screwed afaik. I mean theres no way to guarantee any sequence of instructions gets completed with in given time frame, on x86 at least.

On 16/11/2023 2:48 AM, claptrap wrote:
> So im looking for an explanation or a pointer to an algorithm that exhibits what you describe because it is counter to my experience.

By any chance did you use GC based memory management for it?

If you did, that would explain it. GC based memory management removes a lot of complexity surrounding removing of elements.

On Wednesday, 15 November 2023 at 14:44:52 UTC, Richard (Rikki) Andrew Cattermole wrote:
> On 16/11/2023 2:48 AM, claptrap wrote:
>> So im looking for an explanation or a pointer to an algorithm that exhibits what you describe because it is counter to my experience.
>
> By any chance did you use GC based memory management for it?
>
> If you did, that would explain it. GC based memory management removes a lot of complexity surrounding removing of elements.

What's wrong with using the gc?

On Wednesday, 15 November 2023 at 14:44:52 UTC, Richard (Rikki) Andrew Cattermole wrote:
> On 16/11/2023 2:48 AM, claptrap wrote:
>> So im looking for an explanation or a pointer to an algorithm that exhibits what you describe because it is counter to my experience.
>
> By any chance did you use GC based memory management for it?
>
> If you did, that would explain it. GC based memory management removes a lot of complexity surrounding removing of elements.

C++ and assembler. I used a MPSC "garbage queue" for freeing memory, and there were points in the application where I knew it was safe to empty the queue. So you could maybe see that as "GC like".

But GC or not doesn't answer the main question, what LF algorithm depends on a a sequence of instructions being done immediately after a CAS? How do you ever enforce that on x86?

On 11/15/2023 1:55 AM, Richard (Rikki) Andrew Cattermole wrote:
> A random fun fact, the book I recommend on the subject "The Art of Multiprocessor Programming" one of the authors teachers at the same university as Roy!
> 
> https://shop.elsevier.com/books/the-art-of-multiprocessor-programming/herlihy/978-0-12-415950-1

Thanks for the book recommendation. The review comments, though, say its examples are all in Java. Being in Java, an interpreter, is it relevant to machine level programming?

On 16/11/2023 3:30 PM, Walter Bright wrote:
> Being in Java, an interpreter, is it relevant to machine level programming?

Yes it is.

Java has a well defined memory sub system, it isn't a toy interpreter.

I.e.

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/atomic/package-summary.html

As a subject matter I would consider it in the category of cross referencing required. So even if it isn't the book you want to reference, its still worth cross referencing to it at times.

For $7 from thriftbooks its worth a risk.

On 16/11/2023 8:53 AM, claptrap wrote:
> C++ and assembler. I used a MPSC "garbage queue" for freeing memory, and there were points in the application where I knew it was safe to empty the queue. So you could maybe see that as "GC like".

If you had known good points to release it, yeah that is a known to be good strategy.

I went totally manual without any such external assistance.

So if you want to know the area of the literature that I was reading it was anything that did not apply outside help to deallocate.

> But GC or not doesn't answer the main question, what LF algorithm depends on a a sequence of instructions being done immediately after a CAS? How do you ever enforce that on x86?

That's the fun part, you can't enforce it on any ISA.

Signals, interrupts.

If I hadn't been so distracted by the fact that things could work on ldc but not on dmd, I would've realized that what I was trying to do couldn't work.

There is only one way to describe myself going down that path, a fool ;)