viega

I always use unsigned values and do:

  while (i-- != 0) { ... }

It's more clear than the most idiomatic way, which is to drop the explicit comparison:

  while (i--) { ... }
 

All of it is better than the clunky old for-loop syntax.

A bool does automatically cast to an unsized bit slice.

Meaning, if you have a struct and you want to bit-pack your booleans, you can declare each one as, say, uint8_t some_bool : 1;

You may then do `x.some_bool = true;` etc.

It's a small nicety to avoid bitwise operators, anyway.

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.

.* does NOT match newlines, so always will stop a match at the end of a line.

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.

So maybe it should be a feature, not a bug :)

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.