From: Eric Wong Date: 2017-06-14T22:17:40+00:00 Subject: [ruby-core:81684] Re: Meditations on Writing a Queue In-Reply-To: Hi Richard, your article title piqued my interest since I deal with queues all the time. And it also references changes I've made to Ruby trunk for 2.5 :) +Cc ruby-core since it could also use more eyes. > The C programming language does not come with a queue structure > out of the box like Ruby, but it provides all the primitives to > build one. I���m learning C currently and I���ve been writing > threading code, so having a queue structure helps simplify my > end programs. If you know C, feel free to critique (but not > criticize) my implementation: feedback is how we all get > better. Will do :) I'm no expert on C, either; but I manage to get by. > I wanted my queue to be able to grow to arbitrary length > without putting any constraints on the system. I chose to use a > linked list to do this. Good choice :) > tiny_queue_t* tiny_queue_create() { A common mistake, but function parameters should have an empty "()" AFAIK, C compilers won't do arg checking that way. So: tiny_queue_t* tiny_queue_create(void) { ... to declare it takes no args. > struct tiny_queue_t* queue = (struct tiny_queue_t*)malloc(sizeof(struct tiny_queue_t)); Minor nit: in plain C, it's not necessary to cast the result of malloc. "void *" (from malloc) has implicit cast to other types. But maybe compatibility to C++ (or just plain broken) compilers requires the cast; so Ruby has an RB_ALLOC macro to do most of that for us. > queue->mutex = (pthread_mutex_t)PTHREAD_MUTEX_INITIALIZER; > queue->wakeup = (pthread_cond_t)PTHREAD_COND_INITIALIZER; > > I do know that PTHREAD_MUTEX_INITIALIZER and > PTHREAD_COND_INITIALIZER are macros, which I don���t entirely > understand yet. I also know that the type casting is required, > but I���m not sure why. Either way just know that we���re setting > these variables. AFAIK, using those macros + cast that way with dynamically allocated structs is not portable and probably unsafe if dynamically linking libc/pthreads. Generally, functions like pthread_mutex_init/pthread_cond_init should be used for initializing dynamically allocated memory. The pthread_*_t types are intended to be opaque types; so the program using it shouldn't have any visibility into the structs. If provided, macros are for static initialization where everything about the struct is known at compile-time. Same goes for ccan/list used by Ruby... > First off I was surprised to find that as recently as Ruby 2.0, > the Queue was written in Ruby (instead of C). Click on the > Queue docs for Ruby 2.0 then ���toggle source���. > > In 2.4.1 it is written in C and points to thread_sync.c. I���m > actually going to look at the most recent implementation on > trunk (Ruby uses trunk instead of master branch). Here���s a link > to the code i���ll be reviewing Yeah, I actually rewrote most of thread_sync.c for 2.5 so Queue no longer uses a Struct in trunk: https://bugs.ruby-lang.org/issues/13517 https://bugs.ruby-lang.org/issues/13552 ... mainly to prepare them as auto-Fiber scheduling points: https://bugs.ruby-lang.org/issues/13618 But it was also good getting immediate speedups and size reductions without API changes in the process :) > The C code looks a bit different than mine because the > interface is intended to be consumed by Ruby and not another C > code. a VALUE for example is not a C type but one that Ruby can > understand. Heh, yes. All that new code (stack-allocated list nodes + intrusive doubly-linked list) is inspired by how the waitq + scheduler API works in the Linux kernel. In fact ccan/list used in Ruby is a CC0 implementation with the same characteristics of the well-known list implementation used by the Linux kernel. AFAIK there's been several good articles written about that list over the years; and also the container_of macro for working with intrusive data structures. > Notice in this code they don���t have to mess around with > pointers and heads and tails, that���s because they already have > a list structure (implemented as an Array) that they can use. We actually still use a linked list for the wait queue, ccan/list handles that for us :) > Once the element is added to the array���s tail then a condition > variable signal is sent to wake up any blocked threads > > wakeup_one(&q->waitq); > > One thing you might notice is that there���s no mutexes in this > code. There���s no locking or unlocking. That is because instead > of having a lock in each method, there is a global lock on the > entire Ruby interpreter. This is called a GIL or a GVL and > Python has a similar concept. This lock prevents two threads > from running Ruby code at the same time. This means that only > one thread could be operating on the Array at a time. Yep, this is very different in trunk. The <= 2.4 version was similar to your code with the mutex/condvar for Mutex. > I���m guessing that Ruby���s C calls are atomic so by putting all > that code within queue_do_push means that all those operations > happen in one atomic chunk: check for closed, add element, > signal to blocked threads. Yes. And even without GVL, some initialization operations stack can be doable without any fine-grained locks, and some checks may be performed locklessly. > This is one of the benefits of having a GIL, from an > implementer���s perspective it makes coding extremely easy > because you don���t have to worry about wrapping everything in a > call to lock and unlock. Yeah, after-the-fact is a bit difficult and time consuming but I remain hopeful it'll be possible with lock-free operations (and RCU). Actually, RCU can be though of as a poor-man's GC, and Ruby already has a full GC. Furthermore, write barriers added for RGenGC visibility can probably be adapted for MT use, too. > This is interesting to me because at my second RubyConf in > Denver, I remember someone asking Matz if we could ever get rid > of the GIL. His response was one of shock and horror. I think > he basically said ���no���. After digging in I can understand a bit > more now that it���s not just some flag that needs to be unset, > but rather the entire codebase would need to be re-written to > be threadsafe, which would be an extremely hard effort for any > organization. ... Heh, not everybody in ruby-core likes threads or shared memory :) > This makes effort���s like Koichi���s work on ���guilds��� or another > concurrency model even more interesting. Essentially the idea > is that instead of getting rid of the GIL, we can have multiple > GILs without having to spawn multiple processes. Each ���guild��� > would essentially behave like a cross between a process and a > thread. I���ve always thought of them as a process with a > resource sharing model. We haven't seen guilds, yet, but I expect it to be implemented with native threads with new APIs and non-shared ObjectSpace; but still with process-wide elements (FD, signal handlers) shared across guilds. > I���m having a blast writing C code. While it does take me 20 > hours to do something that would take 20 minutes in Ruby, it���s > a huge accomplishment when I get something to work. It���s also > neat not having the crutch of a huge standard library with > pre-made data structures for me. The real pay-off though is > that the more I learn about C, the less foreign and > unapproachable the source code behind Ruby becomes. I���m not > saying that everyone should learn C, but if you���re looking for > a challenge in a language that���s extremely fast and used all > over the world, it���s not a bad language to be familiar with. Cool. Fwiw, I'm a big fan of CCAN and liburcu which have Linux-kernel-influenced data structures and idioms accessible to userspace. I find them much easier to deal with than the macro-heavy ALL_CAPS_HURTS_MY_EYES APIs of sys/queue.h and sys/tree.h found on *BSD systems :) Unsubscribe: