Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Single-file public-domain/open source C libraries with minimal dependencies

github.com

Post reply on HN
Print view View original

41–50 of 51 posts

Re: Single-file public-domain/open source C libraries with minimal dependencies

#41

Post by haberman »

djcapelis wrote: post #17

Just proposed one of my projects for inclusion: https://github.com/djcapelis/atomic-ring Lock-free Single Producer, Single Consumer (SPSC) queue. The dependencies include C11 and that's it. No POSIX required, should work on any arch you can find a C11 compiler for.

I was just reading your code, which interests me since I've been interested in lock-free programming for a while but only recently started learning about the C11 and C++11 memory model and atomic operations.

I had some thoughts, which I'm offering in hopes of clarifying my understanding, and possibly helping to improve your software in the process.

I don't see any correctness problems in your code, but I do see what look like several opportunities for optimization. Though please take these with a slight grain of salt, as I am still learning the C11 atomics.

Your aring_give() ends with a release barrier and your aring_take() begins with an acquire barrier. That makes sense to me, as a way of ensuring the sequencing of the reads/writes to aring->rb and to item. However I don't see why aring_give() needs to begin with an acquire and aring_take() needs to end with a release. I think both of these could be changed to memory_order_relaxed with no change in correctness.

But I think we can go a step further actually. Your atomic_fetch_add_explicit() and atomic_fetch_sub_explicit() operations operate on a shared aring->items member. Both the reader and writer write to this variable, which requires expensive locked operations and which will degrade under contention. I don't think this is actually necessary.

Instead you could eliminate aring->items completely and simply compute it based on aring->head and aring->tail. Only the writer writes to head and only the reader writes to tail, so you could use just atomic_load_explicit()/atomic_store_explicit() with memory_order_relaxed on these variables to read and write them. Then calculate the number of items present by comparing them. This could make the overall queue significantly more efficient.

I'd be curious to hear your thoughts on this.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#42

Post by temac »

biokoda wrote: post #22
djcapelis wrote: post #21

Earlier quoted context omitted.

I strongly doubt you're going to build a faster thread-safe workqueue by adding spinlocks to it, but if you think what I wrote is too slow, feel free to build something faster and show the speed difference in a benchmark. You can use the code in test/ if you'd like. The code I wrote does leave an optimization or two on the table. Apple's lockfree queue in GCD is faster than mine because of batching. It also has a ton…

Locking is cheap, switching a pointer around is cheap. The only expensive thing is waking up a thread that is waiting on a lock. Spinlocks avoid that problem, which is why they outperform other implementations in terms of throughput (of course inversely proportional to the amount of work you do during a lock). Atomic operations have a fixed cost. Spinlocks only really have a cost when contention is high. When you're…

If you know what you are doing, the C11/C++11 memory model (or another one with roughly the same features, like the linux kernel memory model) and how a computer actually works, I don't think you will find a single architecture on which an atomic implementation of Lock-free Single Producer, Single Consumer (SPSC) queue will not outperform a spinlock.

If you use overkill sequential consistency to do that, you might actually end up slower in some cases.

Given the amount of expertise you need to use atomics properly (far more difficult than sticking to critical sections), it might as well be preferable to stick with those at application level unless you really need extreme performance and know the applicable memory model and the corresponding target stack (maybe processor architecture, maybe C11/C++11 memory model if you use it, maybe additional compiler guarantee on that and related stuffs, maybe all at the same time).

Not that in the end an acquire / release pattern is so hard to understand, but in my experience programmers already can't even stick to properly using critical sections as in textbooks (not even talking about what happens when the textbook is a piece of shit, like when it presents double-checked locking without any regard to the model needed for it to work properly => people end up writing that in C++ on plain variables...).

Really, stick to the (good) textbooks and the simplest patterns if you don't know enough about memory models and how processors and compilers work in 2016... How fast you execute buggy code is not a very interesting property, sequential consistency is expensive in lots of cases, and using weaker atomic is incredibly difficult (each time I think I know enough about weak atomics I found something that explain how various model are subtly weaker than I previously thought, not even talking about the fact that the C11/C++11 model is subtly formally unsound and compilers actually not formally respect it... so much if you try to prove some algorithms)

Re: Single-file public-domain/open source C libraries with minimal dependencies

#43

Post by rat87 »

kyberias wrote: post #29
rat87 wrote: post #24

Earlier quoted context omitted.

Oops. You're absolutely right it's C11.

Yeah, I wondered about that because I thought VC's C99 implementation is _relatively_ useful but again C11 might never arrive there.

Looks I'm wrong again, it's been a while since I wrote it it also uses typeof gcc/llvm extension, there might be a way to fix that but since msvc lacks _Generic I didn't bother.

I was also hoping to support c++ but c++ doesn't do designated initializers.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#44

Post by temac »

haberman wrote: post #41
djcapelis wrote: post #17

Just proposed one of my projects for inclusion: https://github.com/djcapelis/atomic-ring Lock-free Single Producer, Single Consumer (SPSC) queue. The dependencies include C11 and that's it. No POSIX required, should work on any arch you can find a C11 compiler for.

I was just reading your code, which interests me since I've been interested in lock-free programming for a while but only recently started learning about the C11 and C++11 memory model and atomic operations. I had some thoughts, which I'm offering in hopes of clarifying my understanding, and possibly helping to improve your software in the process. I don't see any correctness problems in your code, but I do see what…

Not the author, but anyway; I'm not sure you can release on one variable and acquire on an other while having ordering guarantee between the two.

Anyway, I agree that having both acq and rel on both reader on writer side seems weird. I guess you can come with a solution with only one rel for the writer and only one acq for the reader.

UPDATE: I'm stupid, actually not possible if you don't want to overflow.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#45

Post by haberman »

temac wrote: post #44
haberman wrote: post #41

Earlier quoted context omitted.

I was just reading your code, which interests me since I've been interested in lock-free programming for a while but only recently started learning about the C11 and C++11 memory model and atomic operations. I had some thoughts, which I'm offering in hopes of clarifying my understanding, and possibly helping to improve your software in the process. I don't see any correctness problems in your code, but I do see what…

Not the author, but anyway; I'm not sure you can release on one variable and acquire on an other while having ordering guarantee between the two. Anyway, I agree that having both acq and rel on both reader on writer side seems weird. I guess you can come with a solution with only one rel for the writer and only one acq for the reader. UPDATE: I'm stupid, actually not possible if you don't want to overflow.

Interesting, it was my impression that the release/acquire are not specific to a memory location. They are just barriers, aren't they? But as I said I'm just learning.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#46

Post by temac »

haberman wrote: post #45
temac wrote: post #44

Earlier quoted context omitted.

Not the author, but anyway; I'm not sure you can release on one variable and acquire on an other while having ordering guarantee between the two. Anyway, I agree that having both acq and rel on both reader on writer side seems weird. I guess you can come with a solution with only one rel for the writer and only one acq for the reader. UPDATE: I'm stupid, actually not possible if you don't want to overflow.

Interesting, it was my impression that the release/acquire are not specific to a memory location. They are just barriers, aren't they? But as I said I'm just learning.

They are specific. See 5 in 5.1.2.4 Multi-threaded executions and data races in n1570.

In term of real hardware it translates well in MESI/MESI-like protocol on cache lines on ooo cores, without much more constraints (of course some arch are sufficiently weak to still require special instructions, but on the other hand x86 don't need anything for acq/rel). If the different cores never touch the same cache line, they don't need to do interact at all even when both execute unrelated acq/rel atomics.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#47

Post by haberman »

temac wrote: post #46
haberman wrote: post #45

Earlier quoted context omitted.

Interesting, it was my impression that the release/acquire are not specific to a memory location. They are just barriers, aren't they? But as I said I'm just learning.

They are specific. See 5 in 5.1.2.4 Multi-threaded executions and data races in n1570. In term of real hardware it translates well in MESI/MESI-like protocol on cache lines on ooo cores, without much more constraints (of course some arch are sufficiently weak to still require special instructions, but on the other hand x86 don't need anything for acq/rel). If the different cores never touch the same cache line, they…

Interesting. I bought C++ Concurrency in Action today and am learning all these details of the memory model.

You mention of caches makes me realize that a single-reader single-writer queue can probably also be optimized by putting the head pointer and the tail pointer on different cache lines. The reader and writer can cache the other's value on their own page, and only reload it when the queue otherwise looks full or empty, respectively. This should allow the reader and writer to act without needing to synchronize cache lines for many operations.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#48

Post by djcapelis »

haberman wrote: post #41
djcapelis wrote: post #17

Just proposed one of my projects for inclusion: https://github.com/djcapelis/atomic-ring Lock-free Single Producer, Single Consumer (SPSC) queue. The dependencies include C11 and that's it. No POSIX required, should work on any arch you can find a C11 compiler for.

I was just reading your code, which interests me since I've been interested in lock-free programming for a while but only recently started learning about the C11 and C++11 memory model and atomic operations. I had some thoughts, which I'm offering in hopes of clarifying my understanding, and possibly helping to improve your software in the process. I don't see any correctness problems in your code, but I do see what…

As you might have guessed, after a few conversations today (not very good ones, for the most part, I was tempted to give up the Internet.) I've been thinking about this code quite a bit in the last 12 hours.

I think you're right that there might be an opportunities for improvement. I admit that once the performance hit about 140 cycles per item, I mostly shrugged and called it a day. I felt a lot more concerned about its safety across various architectures than bringing that cycle count down to the absolute minimum. But I also did my benchmarking on x86_64, which has surprisingly strong memory guarantees by default, and so the difference here may be larger on other architectures.

Thanks for looking it over! I definitely am interested and hope to grab some time to try benchmark some tweaks (and test for correctness) on a bunch of different architectures.

Unfortunately I don't have all the state I'd need sitting at the top of my brain to revise this code at the moment, or even know whether your proposed changes are safe, since I find I can't write atomics code safely unless I devote at least an afternoon to the process of analyzing the problem's safety.

I remember there was a reason I chose using a shared item count instead of having the pointers be shared, I think mostly just to minimize the shared state to one thing, but it may not be the fastest choice.

If you want to give trying some changes a shot, I'd love to hear what you find! Email is in my profile. :)

Re: Single-file public-domain/open source C libraries with minimal dependencies

#49

Post by djcapelis »

haberman wrote: post #47
temac wrote: post #46

Earlier quoted context omitted.

They are specific. See 5 in 5.1.2.4 Multi-threaded executions and data races in n1570. In term of real hardware it translates well in MESI/MESI-like protocol on cache lines on ooo cores, without much more constraints (of course some arch are sufficiently weak to still require special instructions, but on the other hand x86 don't need anything for acq/rel). If the different cores never touch the same cache line, they…

Interesting. I bought C++ Concurrency in Action today and am learning all these details of the memory model. You mention of caches makes me realize that a single-reader single-writer queue can probably also be optimized by putting the head pointer and the tail pointer on different cache lines. The reader and writer can cache the other's value on their own page, and only reload it when the queue otherwise looks full o…

I think that works on some architectures but would not be guaranteed behavior. In theory on a system with no memory ordering constraints, the pointers could update before the cache lines for the underlying ring buffer. Which means that without an acquire barrier at the beginning of aring_take, which without an item count, would require writes to the shared head/tail pointers to sync anyway, you can't ensure the the data written to the ring buffer is visible to the thread, even though your pointers would indicate there's data there and so you may load either torn or completely different data into the consumer thread.

Which means that if your memory barriers are operating correctly, they're just causing two cache lines to sync for the metadata instead of one, if the pointers are split across two lines.

Whereas with an item count, only one line ever has to sync, even if the pointers are split across two, since the pointers aren't shared between threads.

In practice, the compiler might not be smart enough to realize this and might be enforcing order for all side effects before the barriers though, even if the other thread doesn't read them. So maybe this isn't a good approach.

Re: Single-file public-domain/open source C libraries with minimal dependencies

#50

Post by CyberDildonics »

biokoda wrote: post #35
CyberDildonics wrote: post #34

Earlier quoted context omitted.

You are making a big assumption that threads will be woken up in the first place. Also when it comes to concurrency it is all about scaling, and whatever scales will perform better as there are more cores.

I never said spinlocks are better in every situation. I'm saying they are better in this situation (SPSC queue).

I didn't say that you said that.

Why would spinlocks be better than no locks at all?

Post reply on HN