[ruby-core:81684] Re: Meditations on Writing a Queue

In-Reply-To: <https://schneems.com/2017/06/14/meditations-on-writing-a-queue/>

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.

<snip>

> 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.

<snip>

> 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 <http://ccodearchive.net/> and
liburcu <http://liburcu.org/> 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: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>