4 ms·

Concurrency kit – Concurrency primitives and non-blocking data structures in C

143 points by misframer 11y ago

gadrfgaesgysd 11y ago
What a macro fest: https://github.com/concurrencykit/ck/blob/master/include/gcc/x86_64/ck_pr.h https://github.com/concurrencykit/ck/blob/master/include/gcc... https://github.com/concurrencykit/ck/tree/master/include/gcc https://github.com/concurrencykit/ck/tree/master/include/gcc This might not be the intention of the author, but if you want someone to use/hack with your library, please make it human-readable. Those macros reduce the amount of duplication, at the cost of legibility. At least include useful comments... /rant off
- corysama 11y ago
  To each his own. As far as macro fests go, that file looks very reasonable and legible to me. It's a single pattern repeated consistently for each function family. Writing out a dozen variants of each function explicitly would not only be much more error-prone, but would also be much harder to read and understand as a whole IMHO.
- alexforster 11y ago
  It's actually used as a way to avoid casting into and out of void* on every line. Think C++ templates. The documentation is somewhat lacking, but it's not too hard to figure out the APIs, and once you do, actually using the library is a pleasure.
- halayli 11y ago
  These are clean macros. Macros do have their place and not every time you see a macro your macro red flag should go off. It took me less than a minute scrolling through the file to figure out what's going on.
- sbahra 11y ago
  Code duplication can also mean more errors and a lot more work for porters. You'll also see plenty of other examples in popular open-source projects such as the Linux and FreeBSD kernel. The reduction in amount of duplication is significant. For example: For SPARCv9 for example, the macro system generates 138 functions from only the 25 or so the developer provides. To top it off, this would work across memory models as well.
virmundi 11y ago
How does this compare to omp? It just started learning about this in my HTC course.
- generic_user 11y ago
  There is a large amount of books, code and information about omp for the beginner. That makes a huge difference.
- zurn 11y ago
  Apart from the functional differences, OpenMP is implemented in compilers and support is currently hit-and-miss even though mainstream compilers are slowly getting there. So eg targeting Mac, Linux and Windows would probably get quite "interesting" if you wanted to support the platform's common vendor-provided compilers.
- exDM69 11y ago
  OpenMP is a bunch of compiler directives (and a runtime library) for easy data parallelism. E.g. #pragma omp parallel for. This library is a bunch of concurrent data structures (hash map, producer/consumer queue, etc) for multi threaded applications. This is more oriented to task parallelism than data parallelism (e.g. servers and such). You'd use this library together with pthreads or other threading library. Does this answer your question?
Jweb_Guru 11y ago
I have nothing but praise for this library... it's a great resource for writing high-performance parallel programs.
Keyframe 11y ago
OK, but where do I start? PS I may be dense today.
- justifier 11y ago
  if you already have a need of concurrency in your project and want to know how to utilise the library there is a documentation section on the linked page a good starting point would be the man pages if you want to know where to start on getting info on how or why you would use a library like this check out the articles or slides section, or wiki around unfamiliar words in the man pages
  - Keyframe 11y ago
    I was hoping for a mini usage showcase / sample. Maybe I'm spoiled, but I was looking through man pages and it was a meaningless dump to me as a newcomer to the library. I then looked at the articles, but it was a long read I didn't want to do at first.
    - sbahra 11y ago
      I agree. Such an article would be more emphasizing use-cases for different advanced synchronization techniques in context of Concurrency Kit. You may just not have a use for it too. I'll put up a presentation soon that may be helpful in these regards.
mingodad 11y ago
I looked at this library in the past and I could not find any usage of it in any open source project. That made me a bit scary, how a library like this with the supposed well thought construction is not used anywhere ?
- sbahra 11y ago
  It's used in a lot of mission-critical commercial applications which I think is a stronger indicator. It just so happens those aren't open-source. This ranges from mission-critical enterprise software to internal infrastructure tied directly to revenue generation. There is a serious cost to failure there (money, liability, jobs, etc...). Few software uses these advanced techniques in general, and it isn't so much about Concurrency Kit. There is a barrier to entry as folks have to invest non-trivial amounts of time in learning more about these techniques. Some open-source examples: http://www.machinekit.io/ http://www.machinekit.io/ https://labs.omniti.com/labs/reconnoiter https://labs.omniti.com/labs/reconnoiter https://github.com/Litres/turboxsl https://github.com/Litres/turboxsl Aerospike I'm sure there are others, if there's anything I'm missing, would love to hear.
reza_n 11y ago
It seems like a lot of these data structs are not thread safe. Other than ck_bitmap which seems to be read/write thread safe, ck_array, ck_hs, ck_ht, and parts of ck_ring only allow a single writer in the presence of many readers. Did I misread something here? Still a lot of good stuff here, but not sure if these data structures can be used without external locking.
- alexforster 11y ago
  They're mostly all some combination of lock-free/wait-free single-producer multi-consumer datastructures, meaning one thread can produce some data (think, an epoll/kqueue I/O thread) and then many other threads can consume it (think, threads that actually perform your server logic). I've found that the "SPMC" concurrency model tends to fit into my pipeline perfectly when I'm working on problems that need a specialized library like this. CK is for achieving unimaginably fast data-parallelism, like the kind you need when writing high performance drivers atop some DMA slab, or (in my case) using userspace networking to do something useful with millions of packets per second. Check out http://concurrencykit.org/articles/ck_hs.html http://concurrencykit.org/articles/ck_hs.html for a better idea about just how fast this library aims to be (spoiler: tens of nanoseconds per op).
- sbahra 11y ago
  They are. As Alex points out, a fair number are a mixture of single-reader many-writer or many-writer single-writer, and a few are many-writer many-reader. MPMC: ck_stack, ck_fifo, ck_ring (in the works), ck_disruptor (pending push), ck_bitmap (but not linearized) and ck_hp* And in some cases, these are just building blocks for more complex structures. Specialized: - Everything else, including ck_[r]h{s,t}*. The synchronization primitives are all generalized to multiple writers (exception is ck_swlock which is specialized). The manual pages should point out bounded concurrency.

143 points by misframer 11y ago

What a macro fest: https://github.com/concurrencykit/ck/blob/master/include/gcc/x86_64/ck_pr.h https://github.com/concurrencykit/ck/blob/master/include/gcc... https://github.com/concurrencykit/ck/tree/master/include/gcc https://github.com/concurrencykit/ck/tree/master/include/gcc This might not be the intention of the author, but if you want someone to use/hack with your library, please make it human-readable. Those macros reduce the amount of duplication, at the cost of legibility. At least include useful comments... /rant off

corysama 11y ago
To each his own. As far as macro fests go, that file looks very reasonable and legible to me. It's a single pattern repeated consistently for each function family. Writing out a dozen variants of each function explicitly would not only be much more error-prone, but would also be much harder to read and understand as a whole IMHO.
alexforster 11y ago
It's actually used as a way to avoid casting into and out of void* on every line. Think C++ templates. The documentation is somewhat lacking, but it's not too hard to figure out the APIs, and once you do, actually using the library is a pleasure.
halayli 11y ago
These are clean macros. Macros do have their place and not every time you see a macro your macro red flag should go off. It took me less than a minute scrolling through the file to figure out what's going on.
sbahra 11y ago
Code duplication can also mean more errors and a lot more work for porters. You'll also see plenty of other examples in popular open-source projects such as the Linux and FreeBSD kernel. The reduction in amount of duplication is significant. For example: For SPARCv9 for example, the macro system generates 138 functions from only the 25 or so the developer provides. To top it off, this would work across memory models as well.

virmundi 11y ago

How does this compare to omp? It just started learning about this in my HTC course.

generic_user 11y ago
There is a large amount of books, code and information about omp for the beginner. That makes a huge difference.
zurn 11y ago
Apart from the functional differences, OpenMP is implemented in compilers and support is currently hit-and-miss even though mainstream compilers are slowly getting there. So eg targeting Mac, Linux and Windows would probably get quite "interesting" if you wanted to support the platform's common vendor-provided compilers.
exDM69 11y ago
OpenMP is a bunch of compiler directives (and a runtime library) for easy data parallelism. E.g. #pragma omp parallel for. This library is a bunch of concurrent data structures (hash map, producer/consumer queue, etc) for multi threaded applications. This is more oriented to task parallelism than data parallelism (e.g. servers and such). You'd use this library together with pthreads or other threading library. Does this answer your question?

Jweb_Guru 11y ago

I have nothing but praise for this library... it's a great resource for writing high-performance parallel programs.

Keyframe 11y ago

OK, but where do I start? PS I may be dense today.

justifier 11y ago
if you already have a need of concurrency in your project and want to know how to utilise the library there is a documentation section on the linked page a good starting point would be the man pages if you want to know where to start on getting info on how or why you would use a library like this check out the articles or slides section, or wiki around unfamiliar words in the man pages
- Keyframe 11y ago
  I was hoping for a mini usage showcase / sample. Maybe I'm spoiled, but I was looking through man pages and it was a meaningless dump to me as a newcomer to the library. I then looked at the articles, but it was a long read I didn't want to do at first.
  - sbahra 11y ago
    I agree. Such an article would be more emphasizing use-cases for different advanced synchronization techniques in context of Concurrency Kit. You may just not have a use for it too. I'll put up a presentation soon that may be helpful in these regards.

mingodad 11y ago

I looked at this library in the past and I could not find any usage of it in any open source project. That made me a bit scary, how a library like this with the supposed well thought construction is not used anywhere ?

sbahra 11y ago
It's used in a lot of mission-critical commercial applications which I think is a stronger indicator. It just so happens those aren't open-source. This ranges from mission-critical enterprise software to internal infrastructure tied directly to revenue generation. There is a serious cost to failure there (money, liability, jobs, etc...). Few software uses these advanced techniques in general, and it isn't so much about Concurrency Kit. There is a barrier to entry as folks have to invest non-trivial amounts of time in learning more about these techniques. Some open-source examples: http://www.machinekit.io/ http://www.machinekit.io/ https://labs.omniti.com/labs/reconnoiter https://labs.omniti.com/labs/reconnoiter https://github.com/Litres/turboxsl https://github.com/Litres/turboxsl Aerospike I'm sure there are others, if there's anything I'm missing, would love to hear.

reza_n 11y ago

It seems like a lot of these data structs are not thread safe. Other than ck_bitmap which seems to be read/write thread safe, ck_array, ck_hs, ck_ht, and parts of ck_ring only allow a single writer in the presence of many readers. Did I misread something here? Still a lot of good stuff here, but not sure if these data structures can be used without external locking.

alexforster 11y ago
They're mostly all some combination of lock-free/wait-free single-producer multi-consumer datastructures, meaning one thread can produce some data (think, an epoll/kqueue I/O thread) and then many other threads can consume it (think, threads that actually perform your server logic). I've found that the "SPMC" concurrency model tends to fit into my pipeline perfectly when I'm working on problems that need a specialized library like this. CK is for achieving unimaginably fast data-parallelism, like the kind you need when writing high performance drivers atop some DMA slab, or (in my case) using userspace networking to do something useful with millions of packets per second. Check out http://concurrencykit.org/articles/ck_hs.html http://concurrencykit.org/articles/ck_hs.html for a better idea about just how fast this library aims to be (spoiler: tens of nanoseconds per op).
sbahra 11y ago
They are. As Alex points out, a fair number are a mixture of single-reader many-writer or many-writer single-writer, and a few are many-writer many-reader. MPMC: ck_stack, ck_fifo, ck_ring (in the works), ck_disruptor (pending push), ck_bitmap (but not linearized) and ck_hp* And in some cases, these are just building blocks for more complex structures. Specialized: - Everything else, including ck_[r]h{s,t}*. The synchronization primitives are all generalized to multiple writers (exception is ck_swlock which is specialized). The manual pages should point out bounded concurrency.