From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mateusz Kowalczyk Newsgroups: gmane.lisp.guile.devel Subject: Re: Concurrent MVars for Guile Date: Sat, 18 Jan 2014 01:05:10 +0000 Message-ID: <52D9D346.3040800@fuuzetsu.co.uk> References: <87fvtn1wv8.fsf@tines.lan> <52D8CEC6.9080800@fuuzetsu.co.uk> <878uuequb2.fsf@netris.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Trace: ger.gmane.org 1390007128 31045 80.91.229.3 (18 Jan 2014 01:05:28 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 18 Jan 2014 01:05:28 +0000 (UTC) Cc: guile-devel@gnu.org To: Mark H Weaver Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sat Jan 18 02:05:35 2014 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1W4KLr-0003Qw-7O for guile-devel@m.gmane.org; Sat, 18 Jan 2014 02:05:31 +0100 Original-Received: from localhost ([::1]:40819 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4KLq-0007rD-FK for guile-devel@m.gmane.org; Fri, 17 Jan 2014 20:05:30 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:38308) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4KLf-0007qx-Vw for guile-devel@gnu.org; Fri, 17 Jan 2014 20:05:25 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1W4KLZ-00044Z-UI for guile-devel@gnu.org; Fri, 17 Jan 2014 20:05:19 -0500 Original-Received: from mailex.mailcore.me ([94.136.40.62]:42614) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1W4KLZ-00044K-Li for guile-devel@gnu.org; Fri, 17 Jan 2014 20:05:13 -0500 Original-Received: from host86-178-69-186.range86-178.btcentralplus.com ([86.178.69.186] helo=[192.168.1.15]) by smtp02.mailcore.me with esmtpa (Exim 4.80.1) (envelope-from ) id 1W4KLX-0006Us-LL; Sat, 18 Jan 2014 01:05:12 +0000 User-Agent: Mozilla/5.0 (X11; Linux i686; rv:24.0) Gecko/20100101 Thunderbird/24.1.0 In-Reply-To: <878uuequb2.fsf@netris.org> X-Enigmail-Version: 1.6 X-Mailcore-Auth: 11603993 X-Mailcore-Domain: 1390428 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 94.136.40.62 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:16816 Archived-At: On 17/01/14 19:31, Mark H Weaver wrote: > Hi, > > Mateusz Kowalczyk writes: > >> First of all, let's quickly outline something that Guilers might not be >> familiar with: MVars are based on an important property of the GHC's >> (GHC is the main Haskell compiler) thread scheduling mechanism, that is >> its fairness policy. GHC uses a round-robin scheduler which means that >> all threads will eventually get to run (although not with equal CPU >> slices). A book by Simon Marlow, the person who has for many many years >> been the main brain behind GHC's RTS says this: >> >> “No thread can be blocked indefinitely on an MVar unless another thread >> holds that MVar indefinitely”.[1] > > "Concurrent Haskell" by Simon Peyton Jones, Andrew Gordon, and Sigbjorn > Finne, which introduced MVars, states in section 6.3 (Fairness): > > Assuming that no process holds the MVar indefinitely, it should not > be possible for any of the competing processes to be denied access > indefinitely. One way to avoid such indefinite denial would be to > specify a FIFO order for processes blocked on an MVar, but that is > perhaps too strong. [...] > > Since our discussion on IRC, I've looked more closely at the > implementation of Guile's fat mutexes and condition variables, upon > which my MVars implementation is based. I will not claim to have fully > audited the code for correctness, but both of them use FIFO wait queues. > > Here's what experiment shows: > > scheme@(guile-user)> (use-modules (ice-9 mvars)) > scheme@(guile-user)> (define mv (new-empty-mvar)) > scheme@(guile-user)> (define producers > (map (lambda (i) > (usleep 200000) > (call-with-new-thread > (lambda () > (let loop () > (put-mvar mv i) > (loop))))) > (iota 10))) > scheme@(guile-user)> (map (lambda (_) (take-mvar mv)) (iota 100)) > $1 = (0 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8) > > I confess that I do not yet understand why the first thread was able to > put the first two values into the MVar, and I intend to investigate > further. Nonetheless, it's clear that the producers are being treated > fairly here. > > What about competing consumers? > > scheme@(guile-user)> (use-modules (ice-9 mvars) (ice-9 threads)) > scheme@(guile-user)> (define mv (new-empty-mvar)) > scheme@(guile-user)> (define m (make-mutex)) > scheme@(guile-user)> (define consumers > (map (lambda (i) > (usleep 200000) > (call-with-new-thread > (lambda () > (let loop () > (let ((x (take-mvar mv))) > (with-mutex m > (format #t "Thread ~a got ~s\n" i x)) > (loop)))))) > (iota 10))) > scheme@(guile-user)> (for-each (lambda (x) (put-mvar mv x)) (iota 30)) > Thread 0 got 0 > Thread 1 got 1 > Thread 2 got 2 > Thread 3 got 3 > Thread 4 got 4 > Thread 5 got 5 > Thread 6 got 6 > Thread 7 got 7 > Thread 8 got 8 > Thread 9 got 9 > Thread 0 got 10 > Thread 1 got 11 > Thread 2 got 12 > Thread 3 got 13 > Thread 4 got 14 > Thread 5 got 15 > Thread 6 got 16 > Thread 7 got 17 > Thread 8 got 18 > Thread 9 got 19 > Thread 0 got 20 > Thread 1 got 21 > Thread 2 got 22 > Thread 3 got 23 > Thread 4 got 24 > Thread 5 got 25 > Thread 6 got 26 > Thread 7 got 27 > Thread 8 got 28 > Thread 9 got 29 > scheme@(guile-user)> > >> Further down we find out the consequences of this guarantee: “A >> consequence of the fairness implementation is that, when multiple >> threads are blocked in takeMVar and another thread does a putMVar, only >> one of the blocked threads becomes unblocked”. > > And indeed, this is the case in this implementation of MVars. Similarly > when multiple threads are blocked in put-mvar and another thread does a > take-mvar. > > My MVars implementation is based on Guile condition variables. Each > MVar has two condition variables: one that gets signaled when the MVar > becomes full, and another that gets signaled when it becomes empty. > Threads waiting for an MVar wait on the appropriate condition variable > in the MVar. Each Guile condition variables contains a FIFO queue of > threads waiting for it. When a condition variable is signaled, one > thread is popped from this queue and woken up. > >> What's Guile's scheduling policy? Can we get a single wakeup and this >> kind of fairness guarantee? >> >> Unfortunately, Mark was not able to tell me what's the case. If this is >> to make it into core language as Mark suggests, I think it's important >> that it's first confirmed that the foundation on which MVars are built >> upon is actually present in Guile. I'm posting on this list in an >> attempt to find the person who knows how Guile's scheduler works and can >> answer my questions. > > Guile threads are pthreads, so Guile does not implement its own > scheduler. However, the mutexes and condition variables exposed to > Scheme (and used in this MVars implementation) implement their own FIFO > wait queues. > >> Of course tests can be written and it can be eyed whether or not the >> behaviour seems similar but I think a definitive ‘yes, we do this’ or >> ‘no, we don't do this’ is still necessary. > > Well, again, I haven't done a full audit of the threads code in Guile, > so I can't provide the definitive statement that you think is necessary. > > However, looking over the code, I think it's reasonably clear that there > is a FIFO policy for waiting threads, and I think the experiments above > provide reasonable confirmation of that (modulo the strange case of two > zeroes in a row at the beginning). > > I will leave it to others to decide whether this is sufficient. > > Mark > Hi Mark, Thanks for the investigation. While I have not gotten a chance to play with this myself, it does seem like your MVar implementation has a sound basis. While it'd be great to have someone familiar with the inner-workings to step in and confirm your findings, it seems that your implementation should work, at least from the scheduling perspective. I can not guess what the actual performance might be as I'm not familiar with Guile's performance profile but I suppose that's another issue. Good work! Hopefully I'll be able to find time to play with this a bit myself. -- Mateusz K.