Interesting; while I knew about `preserve_all` and `preserve_most` attributes, I didn't have an inkling that they've added `preserve_none`. But that's much cleaner that the traditional `setjmp()` or custom asm (which I've never needed-- `setjmp()` has always seemed to get the job done portably).
As for stack bounds, address of a local is easy enough to make work well, but if you care about scanning thread stacks, I'm not aware of a good way to do that with compiler intrinsics only. If you're willing to assume pthreads, it's doable, but even that requires platform-specific code. The only viable portable approaches for dealing w/ thread stacks I'm aware of aren't awesome:
1. Assume your control of thread creation isn't circumventable, and add your own sentinel at the other end of the stack.
2. Probe the stack for the first access violation.
No option is particularly satisfying there; wonder if I missed some other intrinsic added along the way to solve that problem.
For me, I’ve got use cases where it’s valuable to keep event data interleaved because it will also get used in flight. It works well enough I also use it for things where it’s not necessary like in memory debug rings (which requires a bit of additional work).
The epoch isn’t CAS’d; it is FAA. The epoch is then used to determine if there is contention due to the tail meeting the head, or due to a wrap-around due to slow writes.
There’s also a back-off scheme to ease contention for a full queue.
Though, I did originally have a variant that adds a fairly straightforward ‘help’ mechanism that makes the algorithm wait-free and reduces the computational complexity.
However, the extra overhead didn’t seem worth it, so I took it out pretty quickly. Iirc, the only place where the ring in the queue wouldn’t out-perform it are on tiny queues with a huge write imbalance.
If you go run the tests in the repo associated w the article, you probably will see that a ring with only 16 entries will tend to start being non-performant at about a 4:1 writer to reader ratio. But iirc that effect goes away before 128 slots in the ring.
There, the ring still fits in a page, and even with a big imbalance I can’t remember seeing less than 1m ops per second on my Mac laptop.
Real world observational data beats worst case analysis, and I’ve never seen an issue for scenarios I consider reasonable.
But, if my unrealistic is realistic to you, let me know and I can break out the wait free version for you.
BTW, should be noted that the need to issue a cache line lock on x86 does seem to slow down 128-bit CAS quite a bit on x86-64 platforms. On arm64, there's no reason to skimp with a 64-bit CAS.
You can use a 64-bit CAS if you want to use a 32-bit epoch and a pointer compression scheme of any kind, or just a 32-bit index into regions that are thread specific. I think I did the later when I did the original work, using the core primitive to build ring buffers that have arbitrary sized slots instead of 64-bit slots (which requires a bit of additional gymnastics, but the basic trick is to have the ring index into a bigger ring that you can FAA into, where the bigger ring has more slots by at least the max number of threads (I use this primitive heavily still for in-memory debug logging). Maybe at some point I'll do an article on that too.
Yes, I meant to clarify the memory model discussion; I had tried to simplify and did a poor job; I got similar feedback after it was published, and never remembered to get to it. Will try to do it soon, though it's about the worst time for this to have hit, not sure when I'll be able to sit down for it, but will try to get it done in the next day. Hopefully it doesn't wait until next time it gets some views.
So that work came after mine, and seems to be a FIFO not a ring buffer. The library I built at the time also had FIFOs and LIFOs that were tweaks on previous algorithms, but nothing earth shaking. I'll check this one out when I can though.
I don't think I even saw this until I published the article. I don't think it was academically published, or googled well back in 2000. Nor did it match my needs for a ring buffer at the time, which was to drop stale data (I think in that algorithm, write operations fail when the buffer is full), so if I did see it, I wouldn't have payed enough attention to notice if it even had users. It's good work for sure, but that's why it didn't get mentioned.
Well, when I was doing the original work on it (about 5 years ago now), I spent a lot of time trying to find something else in the literature. I couldn't find anything that wasn't SPMC or MPSC, unless it had severe limitations, like not actually having a drop policy when full.
However, I definitely did not see the paper you've sited, but just spent a few minutes with the paper you cited. Section 5.2 seems to cover their version. It's far from clear what their algorithm is, but they are talking about page eviction; it doesn't seem like they're using even a single fixed array for the ring, but I'm not 100% sure because it's pretty light on any detail. a
Agreed that this is not a critical problem, and the cooperative side channel can be useful in otherwise uncooperative environments.
The article does mention wanting to coordinate across multiple identical processes running on the same node in a wide variety of environments as the motivator.
By the way, the run-time type checking is one of the use cases where I really would like to have a tractable interface for hashing at compile time, preventing unbounded strcmps, and turning them into an integer compare (without having to manage caching such things at runtime).
Same thing would be for making it much easier to statically lay out fixed caches implemented via hashing, instead of inserting into them at start-up, etc.
Some of the stuff you're doing in the library I've also been doing recently, and has been working well, like using the string of the type name to allow for run-time checking of, what I would called "mixed" data (your variadic type). I've also done the same basic thing as your option type in a way that's closer to your sum type than the maybe type.
But I'd had enough problems trying to get something like your vector actually working that I'd given up, but I think now I'll build something at some point over the holidays. I think as I'm coming up to speed on the history of changes to _Generic that's partially due to the attempts before I had a C23 compiler, but even then, your code there is impressive-- both clear and clever.
I also have enough stuff passed via pointer that the option type for me needed to handle pointers differently-- I basically just have run-time code that does the null check at run time when set. At that point, there doesn't really need to be an 'is_set' type flag.
From my read, that article doesn't have anything in it that isn't standards compliant C. My memory is getting worse as I get older, but I'd say by C17 all that was standard, and definitely in C23.
I've noticed many people are still building on systems where the compiler is a bit older, and defaults to C11, even if it has support for C17, so perhaps that's the problem?
It is-- if you click in to their full list, you should see it near the top in their "above the water" section, under `#pragma once`. I suspect it was added after the meme image was produced.
But, if it weren't on the iceberg page, it'd make sense. The semantics of `do { ... } while(0)` are in the standard, and the preprocessor has nothing to do with those semantics.
You are, of course, right, that the construct is used all over the place in macros for good reason, though these days every compiler I care about has the same (I believe not in the standard) syntax for statement expressions, which will work in even more contexts.
To be clear, the example I provided for the other person explains the bit you're missing where the names aren't working... if you carefully follow the rules, the # and ## operators don't allow expansion on their arguments, so you have to use a layer of indirection to get them expanded first.
Thanks. Also, per another person in the thread, here are the two annotations he or she was asking for, heavily annotated.
They are both only a couple lines, but it deals with things like the fact that you've got one more argument than you should have commas, and the use of the # and ## operators in these things.
Okay, finally found some time to provide you with a fully annotated example of your original ask here, assuming you wanted to transform the arguments passed to F into IDs, and the arguments passed to G into strings (as seemed to be the case from the rest of the thread).
I've fully annotated it, so it might seem like more than it is. About half the macro code is from the original article (the chunk at the top). And I do implement both transforms for you.
Each one I think is only 6 lines of code by itself, despite the rediculous amount of exposition in the comments.
As for stack bounds, address of a local is easy enough to make work well, but if you care about scanning thread stacks, I'm not aware of a good way to do that with compiler intrinsics only. If you're willing to assume pthreads, it's doable, but even that requires platform-specific code. The only viable portable approaches for dealing w/ thread stacks I'm aware of aren't awesome:
1. Assume your control of thread creation isn't circumventable, and add your own sentinel at the other end of the stack. 2. Probe the stack for the first access violation.
No option is particularly satisfying there; wonder if I missed some other intrinsic added along the way to solve that problem.