* Concurrent MVars for Guile
@ 2013-09-02 7:55 Mark H Weaver
2013-09-03 11:55 ` Mark H Weaver
` (3 more replies)
0 siblings, 4 replies; 14+ messages in thread
From: Mark H Weaver @ 2013-09-02 7:55 UTC (permalink / raw)
To: guile-devel
[-- Attachment #1: Type: text/plain, Size: 588 bytes --]
Hello all,
I've attached a preliminary implementation of MVars à la Concurrent
Haskell for Guile. I made a few small changes to the API to better
match Scheme conventions, and added atomicity guarantees for 'read-mvar'
and 'swap-mvar'. I also added the interface 'try-read-mvar'.
Note that the fairness of this implementation relies upon the fairness
of Guile's mutexes and condition variables, which I have not checked.
Comments and suggestions welcome.
I was thinking that maybe we should add something like this to core
Guile. What do you think?
Mark
[-- Attachment #2: MVars for Guile --]
[-- Type: text/plain, Size: 5368 bytes --]
(define-module (ice-9 mvars)
#:use-module (srfi srfi-8) ; receive
#:use-module (srfi srfi-9) ; records
#:use-module (srfi srfi-9 gnu)
#:use-module (ice-9 threads)
#:export (new-mvar mvar? mvar-empty?
take-mvar put-mvar read-mvar swap-mvar
try-take-mvar try-put-mvar try-read-mvar
with-mvar modify-mvar modify-mvar*))
(define-record-type <mvar>
(make-mvar contents empty? mutex condvar)
mvar?
(contents mvar-contents set-mvar-contents!)
(empty? mvar-empty? set-mvar-empty?!)
(mutex mvar-mutex)
(condvar mvar-condvar))
(set-record-type-printer!
<mvar>
(lambda (mvar port)
(display "#<mvar " port)
(display (number->string (object-address mvar) 16) port)
(display " " port)
(write (receive (x full?) (try-read-mvar mvar)
(if full? (list x) '()))
port)
(display ">" port)))
(define new-mvar
(case-lambda
"Return a freshly allocated mvar. The optional argument, if provided,\n\
specifies the initial contents of the mvar, otherwise it will be empty."
(() (make-mvar #f #t (make-mutex) (make-condition-variable)))
((x) (make-mvar x #f (make-mutex) (make-condition-variable)))))
(define (take-mvar mvar)
"Block until MVAR is full, then atomically remove and return its contents."
(with-mutex (mvar-mutex mvar)
(when (mvar-empty? mvar)
(wait-condition-variable (mvar-condvar mvar) (mvar-mutex mvar))
(when (mvar-empty? mvar)
(error "take-mvar: expected full mvar after waiting")))
(let ((x (mvar-contents mvar)))
(set-mvar-contents! mvar #f)
(set-mvar-empty?! mvar #t)
(signal-condition-variable (mvar-condvar mvar))
x)))
(define (put-mvar mvar x)
"Block until MVAR is empty, then put X into it."
(with-mutex (mvar-mutex mvar)
(unless (mvar-empty? mvar)
(wait-condition-variable (mvar-condvar mvar) (mvar-mutex mvar))
(unless (mvar-empty? mvar)
(error "put-mvar: expected empty mvar after waiting")))
(set-mvar-contents! mvar x)
(set-mvar-empty?! mvar #f)
(signal-condition-variable (mvar-condvar mvar))
*unspecified*))
(define (read-mvar mvar)
"Block until MVAR is full, then return its contents, leaving MVAR unchanged."
(with-mutex (mvar-mutex mvar)
(when (mvar-empty? mvar)
(wait-condition-variable (mvar-condvar mvar) (mvar-mutex mvar))
(when (mvar-empty? mvar)
(error "read-mvar: expected full mvar after waiting")))
(mvar-contents mvar)))
(define (swap-mvar mvar new)
"Block until MVAR is full, and then atomically swap its contents\n\
with NEW and return the previous contents."
(with-mutex (mvar-mutex mvar)
(when (mvar-empty? mvar)
(wait-condition-variable (mvar-condvar mvar) (mvar-mutex mvar))
(when (mvar-empty? mvar)
(error "swap-mvar: expected full mvar after waiting")))
(let ((old (mvar-contents mvar)))
(set-mvar-contents! mvar new)
old)))
(define (try-take-mvar mvar)
"If MVAR is full, return its contents and #t, else return #f and #f."
(with-mutex (mvar-mutex mvar)
(if (mvar-empty? mvar)
(values #f #f)
(let ((x (mvar-contents mvar)))
(set-mvar-contents! mvar #f)
(set-mvar-empty?! mvar #t)
(signal-condition-variable (mvar-condvar mvar))
(values x #t)))))
(define (try-put-mvar mvar x)
"If MVAR is empty, put X into it and return #t, else return #f."
(with-mutex (mvar-mutex mvar)
(and (mvar-empty? mvar)
(begin
(set-mvar-contents! mvar x)
(set-mvar-empty?! mvar #f)
(signal-condition-variable (mvar-condvar mvar))
#t))))
(define (try-read-mvar mvar)
"If MVAR is full, return its contents and #t, else return #f and #f."
(with-mutex (mvar-mutex mvar)
(if (mvar-empty? mvar)
(values #f #f)
(values (mvar-contents mvar) #t))))
(define (with-mvar mvar proc)
"Take a value from MVAR and apply PROC to it. If an exception is raised,\n\
the original value is put back into MVAR. This procedure is atomic only if\n\
there are no other producers for MVAR."
(let ((x (take-mvar mvar)))
(catch #t
(lambda () (proc x))
(lambda (key . args)
(put-mvar mvar x)
(apply throw key args)))))
(define (modify-mvar mvar f)
"Take a value x from MVAR, and then put back (F x). If an exception is\n\
raised, the original value is put back into MVAR. This procedure is\n\
atomic only if there are no other producers for MVAR."
(let ((old (take-mvar mvar)))
(catch #t
(lambda () (put-mvar mvar (f old)))
(lambda (key . args)
(put-mvar mvar old)
(apply throw key args)))))
(define (modify-mvar* mvar f)
"Take a value x from MVAR, and apply F to it. (F x) should return one\n\
or more values: the new value to be put back into MVAR, and zero or more\n\
additional values to be returned from MODIFY-MVAR*. If an exception is\n\
raised, the original value is put back into MVAR. This procedure is\n\
atomic only if there are no other producers for MVAR."
(let ((old (take-mvar mvar)))
(catch #t
(lambda ()
(receive (new . results) (f old)
(put-mvar mvar new)
(apply values results)))
(lambda (key . args)
(put-mvar mvar old)
(apply throw key args)))))
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: Concurrent MVars for Guile
2013-09-02 7:55 Concurrent MVars for Guile Mark H Weaver
@ 2013-09-03 11:55 ` Mark H Weaver
[not found] ` <CAGua6m3o_NexANbGuDYd5_rbPQqsbXkK504ONaFE7PGdQd98og@mail.gmail.com>
2013-09-05 2:10 ` David Thompson
` (2 subsequent siblings)
3 siblings, 1 reply; 14+ messages in thread
From: Mark H Weaver @ 2013-09-03 11:55 UTC (permalink / raw)
To: guile-devel
[-- Attachment #1: Type: text/plain, Size: 456 bytes --]
Hello all,
I've attached an improved (but still preliminary) implementation of
MVars for Guile. Apart from fixing some bugs, this version follows the
Haskell API and semantics more closely. In particular, I now refrain
from adding atomicity guarantees beyond those promised by the Haskell
API. I also added locking to 'mvar-empty?', to ensure that we meet the
"ordering" requirement of the Haskell API.
Comments and suggestions welcome.
Mark
[-- Attachment #2: mvars for guile (preliminary) --]
[-- Type: text/plain, Size: 5047 bytes --]
(define-module (ice-9 mvars)
#:use-module (ice-9 threads)
#:use-module (srfi srfi-8) ; receive
#:use-module (srfi srfi-9) ; records
#:use-module (srfi srfi-9 gnu)
#:export (mvar?
mvar-empty? new-empty-mvar new-mvar
take-mvar put-mvar read-mvar swap-mvar
try-take-mvar try-put-mvar
with-mvar modify-mvar modify-mvar*))
(define-record-type <mvar>
(make-mvar contents empty? mutex full-condition empty-condition)
mvar?
(contents %mvar-contents %set-mvar-contents!)
(empty? %mvar-empty? %set-mvar-empty?!)
(mutex mvar-mutex)
(full-condition mvar-full-condition)
(empty-condition mvar-empty-condition))
(define (mvar-empty? mvar)
(with-mutex (mvar-mutex mvar)
(%mvar-empty? mvar)))
(define (new-empty-mvar)
"Return a freshly allocated mvar that is initially empty."
(make-mvar #f ; contents
#t ; empty?
(make-mutex)
(make-condition-variable)
(make-condition-variable)))
(define (new-mvar x)
"Return a freshly allocated mvar with initial contents X."
(make-mvar x ; contents
#f ; empty?
(make-mutex)
(make-condition-variable)
(make-condition-variable)))
(define (take-mvar mvar)
"Block until MVAR is full, then atomically remove and return its contents."
(with-mutex (mvar-mutex mvar)
(when (%mvar-empty? mvar)
(wait-condition-variable (mvar-full-condition mvar) (mvar-mutex mvar)))
(let ((x (%mvar-contents mvar)))
(%set-mvar-contents! mvar #f)
(%set-mvar-empty?! mvar #t)
(signal-condition-variable (mvar-empty-condition mvar))
x)))
(define (put-mvar mvar x)
"Block until MVAR is empty, then put X into it."
(with-mutex (mvar-mutex mvar)
(unless (%mvar-empty? mvar)
(wait-condition-variable (mvar-empty-condition mvar) (mvar-mutex mvar)))
(%set-mvar-contents! mvar x)
(%set-mvar-empty?! mvar #f)
(signal-condition-variable (mvar-full-condition mvar))
*unspecified*))
(define (read-mvar mvar)
"Take a value x from MVAR, then put it back and return x. This
procedure is atomic only if there are no other producers for MVAR."
(let ((x (take-mvar mvar)))
(put-mvar mvar x)
x))
(define (swap-mvar mvar y)
"Take a value x from MVAR, then put Y into MVAR and return x. This
procedure is atomic only if there are no other producers for MVAR."
(let ((x (take-mvar mvar)))
(put-mvar mvar y)
x))
(define (try-take-mvar mvar)
"If MVAR is full, return its contents and #t, else return #f and #f."
(with-mutex (mvar-mutex mvar)
(if (%mvar-empty? mvar)
(values #f #f)
(let ((x (%mvar-contents mvar)))
(%set-mvar-contents! mvar #f)
(%set-mvar-empty?! mvar #t)
(signal-condition-variable (mvar-empty-condition mvar))
(values x #t)))))
(define (try-put-mvar mvar x)
"If MVAR is empty, put X into it and return #t, else return #f."
(with-mutex (mvar-mutex mvar)
(and (%mvar-empty? mvar)
(begin
(%set-mvar-contents! mvar x)
(%set-mvar-empty?! mvar #f)
(signal-condition-variable (mvar-full-condition mvar))
#t))))
(define (with-mvar mvar proc)
"Take a value from MVAR and apply PROC to it. If an exception is raised,
the original value is put back into MVAR. This procedure is atomic only if
there are no other producers for MVAR."
(let ((x (take-mvar mvar)))
(catch #t
(lambda () (proc x))
(lambda (key . args)
(put-mvar mvar x)
(apply throw key args)))))
(define (modify-mvar mvar f)
"Take a value x from MVAR, and then put back (F x). If an exception is
raised, the original value is put back into MVAR. This procedure is
atomic only if there are no other producers for MVAR."
(let ((old (take-mvar mvar)))
(catch #t
(lambda () (put-mvar mvar (f old)))
(lambda (key . args)
(put-mvar mvar old)
(apply throw key args)))))
(define (modify-mvar* mvar f)
"Take a value x from MVAR, and apply F to it. (F x) should return one
or more values: the new value to be put back into MVAR, and zero or more
additional values to be returned from MODIFY-MVAR*. If an exception is
raised, the original value is put back into MVAR. This procedure is
atomic only if there are no other producers for MVAR."
(let ((old (take-mvar mvar)))
(catch #t
(lambda ()
(receive (new . results) (f old)
(put-mvar mvar new)
(apply values results)))
(lambda (key . args)
(put-mvar mvar old)
(apply throw key args)))))
(set-record-type-printer!
<mvar>
(lambda (mvar port)
(display "#<mvar " port)
(display (number->string (object-address mvar) 16) port)
(display " " port)
(write (with-mutex (mvar-mutex mvar)
(if (%mvar-empty? mvar)
'()
(list (%mvar-contents mvar))))
port)
(display ">" port)))
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: Concurrent MVars for Guile
2013-09-02 7:55 Concurrent MVars for Guile Mark H Weaver
2013-09-03 11:55 ` Mark H Weaver
@ 2013-09-05 2:10 ` David Thompson
2013-09-05 2:53 ` Mark H Weaver
2013-09-14 13:59 ` Ludovic Courtès
2014-01-17 6:33 ` Mateusz Kowalczyk
3 siblings, 1 reply; 14+ messages in thread
From: David Thompson @ 2013-09-05 2:10 UTC (permalink / raw)
To: Mark H Weaver; +Cc: guile-devel
On 09/02/2013 03:55 AM, Mark H Weaver wrote:
> Hello all,
>
> I've attached a preliminary implementation of MVars à la Concurrent
> Haskell for Guile. I made a few small changes to the API to better
> match Scheme conventions, and added atomicity guarantees for 'read-mvar'
> and 'swap-mvar'. I also added the interface 'try-read-mvar'.
>
> Note that the fairness of this implementation relies upon the fairness
> of Guile's mutexes and condition variables, which I have not checked.
>
> Comments and suggestions welcome.
>
> I was thinking that maybe we should add something like this to core
> Guile. What do you think?
>
> Mark
>
>
I am using this for my game library, guile-2d (the first version that
you posted). A user ran into trouble installing guile-2d because of an
error with case-lambda in this module. They are using Guile 2.0.7.
Thoughts?
~/Downloads/guile-2d $ make
GEN2d/game-loop.go
ice-9/boot-9.scm:106:20: In procedure#<procedure 9f50900 at ice-9/boot-9.scm:97:6 (thrown-k . args)>:
ice-9/boot-9.scm:106:20: Syntax error:
2d/mvars.scm:52:2: case-lambda: badcase-lambda in form(case-lambda "Return a freshly allocated mvar. The optional argument, if provided,\nspecifies the initial contents of the mvar, otherwise it will be empty." (() (make-mvar#f #t (make-mutex) (make-condition-variable))) ((x) (make-var x #f (make-mutex) (make-condition-variable))))
make: *** [2d/game-loop.go] Error 1
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Concurrent MVars for Guile
2013-09-05 2:10 ` David Thompson
@ 2013-09-05 2:53 ` Mark H Weaver
0 siblings, 0 replies; 14+ messages in thread
From: Mark H Weaver @ 2013-09-05 2:53 UTC (permalink / raw)
To: David Thompson; +Cc: guile-devel
Hi David,
David Thompson <dthompson2@worcester.edu> writes:
> I am using this for my game library, guile-2d (the first version that
> you posted). A user ran into trouble installing guile-2d because of an
> error with case-lambda in this module. They are using Guile 2.0.7.
That's because in the old version, the 'case-lambda' had the docstring
outside of the clauses -- a syntax that wasn't supported before 2.0.9.
However, you should switch to using the new version of mvars.scm, which
avoids the 'case-lambda' altogether, and also fixes some bugs. The new
version should work on older versions of Guile.
Mark
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Concurrent MVars for Guile
2013-09-02 7:55 Concurrent MVars for Guile Mark H Weaver
2013-09-03 11:55 ` Mark H Weaver
2013-09-05 2:10 ` David Thompson
@ 2013-09-14 13:59 ` Ludovic Courtès
2013-09-17 20:18 ` Andy Wingo
2014-01-17 6:33 ` Mateusz Kowalczyk
3 siblings, 1 reply; 14+ messages in thread
From: Ludovic Courtès @ 2013-09-14 13:59 UTC (permalink / raw)
To: guile-devel
Hi!
It looks like a useful tool to me.
I don’t like the name “mvar” (“monadic variable”, I guess). Perhaps
“synchronized box”, or “transactional variable”, or...? The downside of
choosing another name is that people familiar with the concept won’t
recognize it first-hand.
Thanks,
Ludo’.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Concurrent MVars for Guile
2013-09-14 13:59 ` Ludovic Courtès
@ 2013-09-17 20:18 ` Andy Wingo
2014-01-16 0:47 ` Mark H Weaver
0 siblings, 1 reply; 14+ messages in thread
From: Andy Wingo @ 2013-09-17 20:18 UTC (permalink / raw)
To: Ludovic Courtès; +Cc: guile-devel
On Sat 14 Sep 2013 15:59, ludo@gnu.org (Ludovic Courtès) writes:
> It looks like a useful tool to me.
FWIW I totally agree!
> I don’t like the name “mvar” (“monadic variable”, I guess). Perhaps
> “synchronized box”, or “transactional variable”, or...? The downside of
> choosing another name is that people familiar with the concept won’t
> recognize it first-hand.
I guess I can see this. I prefer "box" to "variable" fwiw. How about
"tbox"? (The T for threadsafe or transactional or something; perhaps
this is a bad idea.)
Dunno :)
Andy
--
http://wingolog.org/
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Concurrent MVars for Guile
2013-09-17 20:18 ` Andy Wingo
@ 2014-01-16 0:47 ` Mark H Weaver
2014-01-16 13:01 ` Ludovic Courtès
0 siblings, 1 reply; 14+ messages in thread
From: Mark H Weaver @ 2014-01-16 0:47 UTC (permalink / raw)
To: Andy Wingo; +Cc: Ludovic Courtès, guile-devel
Hi! Reviving an old thread...
Andy Wingo <wingo@pobox.com> writes:
> On Sat 14 Sep 2013 15:59, ludo@gnu.org (Ludovic Courtès) writes:
>
>> It looks like a useful tool to me.
>
> FWIW I totally agree!
>
>> I don’t like the name “mvar” (“monadic variable”, I guess). Perhaps
>> “synchronized box”, or “transactional variable”, or...? The downside of
>> choosing another name is that people familiar with the concept won’t
>> recognize it first-hand.
>
> I guess I can see this. I prefer "box" to "variable" fwiw. How about
> "tbox"? (The T for threadsafe or transactional or something; perhaps
> this is a bad idea.)
My preference would be to keep the "mvars" name, however imperfect,
simply because many people in the neighboring Haskell community already
know them as "mvars".
There are many different ways that one can design threadsafe and/or
transactional boxes. In the future, we might very well support some
slightly different mechanism that could just as easily be called tboxes,
and then we will have to invent yet another name. Given that these
mvars have identical semantics to the ones in Haskell, I think it's
probably best to just reuse the name that already exists.
However, I don't feel strongly. If you and Ludovic can agree on a name,
I'll rename them. Mainly I just want to get this module, or something
like it, into stable-2.0 relatively soon.
What do you think?
Mark
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: Concurrent MVars for Guile
2014-01-16 0:47 ` Mark H Weaver
@ 2014-01-16 13:01 ` Ludovic Courtès
0 siblings, 0 replies; 14+ messages in thread
From: Ludovic Courtès @ 2014-01-16 13:01 UTC (permalink / raw)
To: Mark H Weaver; +Cc: Andy Wingo, guile-devel
Mark H Weaver <mhw@netris.org> skribis:
> Andy Wingo <wingo@pobox.com> writes:
>
>> On Sat 14 Sep 2013 15:59, ludo@gnu.org (Ludovic Courtès) writes:
>>
>>> It looks like a useful tool to me.
>>
>> FWIW I totally agree!
>>
>>> I don’t like the name “mvar” (“monadic variable”, I guess). Perhaps
>>> “synchronized box”, or “transactional variable”, or...? The downside of
>>> choosing another name is that people familiar with the concept won’t
>>> recognize it first-hand.
>>
>> I guess I can see this. I prefer "box" to "variable" fwiw. How about
>> "tbox"? (The T for threadsafe or transactional or something; perhaps
>> this is a bad idea.)
>
> My preference would be to keep the "mvars" name, however imperfect,
> simply because many people in the neighboring Haskell community already
> know them as "mvars".
OK, I think that makes sense then (I’ve seen mvars mentioned in various
places in the meantime.)
Hopefully the manual will make it clear what this is about. ;-)
Ludo’.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Concurrent MVars for Guile
2013-09-02 7:55 Concurrent MVars for Guile Mark H Weaver
` (2 preceding siblings ...)
2013-09-14 13:59 ` Ludovic Courtès
@ 2014-01-17 6:33 ` Mateusz Kowalczyk
2014-01-17 19:31 ` Mark H Weaver
3 siblings, 1 reply; 14+ messages in thread
From: Mateusz Kowalczyk @ 2014-01-17 6:33 UTC (permalink / raw)
To: guile-devel
[-- Attachment #1: Type: text/plain, Size: 2895 bytes --]
On 02/09/13 08:55, Mark H Weaver wrote:
> Hello all,
>
> I've attached a preliminary implementation of MVars à la Concurrent
> Haskell for Guile. I made a few small changes to the API to better
> match Scheme conventions, and added atomicity guarantees for 'read-mvar'
> and 'swap-mvar'. I also added the interface 'try-read-mvar'.
>
> Note that the fairness of this implementation relies upon the fairness
> of Guile's mutexes and condition variables, which I have not checked.
>
> Comments and suggestions welcome.
>
> I was thinking that maybe we should add something like this to core
> Guile. What do you think?
>
> Mark
>
>
Hi all,
We've just had a little discussion in the #guile IRC channel about this
and I'm seeking some confirmation.
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]
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”. I think it's rather clear
why this property is desirable: we don't want to wake every thread
waiting on an MVar whenever we put into it or we'll have a huge
performance hit. As Simon himself says, these properties are why we
simply aren't using STM instead.
Keeping all this in mind, my questions are:
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.
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. In case that Guile does _not_
support such scheduling, I think it's important to note this in any
relevant documentation.
You can find examples of simple programs one could try to implement as
part of tests for this in Chapters 7 and 8 of [1].
Thanks
[1]: http://chimera.labs.oreilly.com/books/1230000000929
--
Mateusz K.
[-- Attachment #2: 0x2ADA9A97.asc --]
[-- Type: application/pgp-keys, Size: 5619 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: Concurrent MVars for Guile
2014-01-17 6:33 ` Mateusz Kowalczyk
@ 2014-01-17 19:31 ` Mark H Weaver
2014-01-18 0:46 ` Mark H Weaver
2014-01-18 1:05 ` Mateusz Kowalczyk
0 siblings, 2 replies; 14+ messages in thread
From: Mark H Weaver @ 2014-01-17 19:31 UTC (permalink / raw)
To: Mateusz Kowalczyk; +Cc: guile-devel
Hi,
Mateusz Kowalczyk <fuuzetsu@fuuzetsu.co.uk> 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
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: Concurrent MVars for Guile
2014-01-17 19:31 ` Mark H Weaver
@ 2014-01-18 0:46 ` Mark H Weaver
2014-01-18 1:05 ` Mateusz Kowalczyk
1 sibling, 0 replies; 14+ messages in thread
From: Mark H Weaver @ 2014-01-18 0:46 UTC (permalink / raw)
To: Mateusz Kowalczyk; +Cc: guile-devel
Mark H Weaver <mhw@netris.org> writes:
> 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
I see now why that happened. The first thread was able to immediately
put the first 0 into the MVar without waiting, and then became the first
entry in the wait queue to put the second 0, before the second thread
started waiting to put the first 1.
So, the experiments are perfectly consistent with my understanding from
looking over the code in threads.c, that Guile's mutexes and condition
variables have a FIFO policy for waiting threads. Therefore my MVar
implementation also has a FIFO policy, and therefore meets the fairness
requirements.
Mark
^ permalink raw reply [flat|nested] 14+ messages in thread* Re: Concurrent MVars for Guile
2014-01-17 19:31 ` Mark H Weaver
2014-01-18 0:46 ` Mark H Weaver
@ 2014-01-18 1:05 ` Mateusz Kowalczyk
2014-01-21 5:38 ` Mark H Weaver
1 sibling, 1 reply; 14+ messages in thread
From: Mateusz Kowalczyk @ 2014-01-18 1:05 UTC (permalink / raw)
To: Mark H Weaver; +Cc: guile-devel
On 17/01/14 19:31, Mark H Weaver wrote:
> Hi,
>
> Mateusz Kowalczyk <fuuzetsu@fuuzetsu.co.uk> 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.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: Concurrent MVars for Guile
2014-01-18 1:05 ` Mateusz Kowalczyk
@ 2014-01-21 5:38 ` Mark H Weaver
0 siblings, 0 replies; 14+ messages in thread
From: Mark H Weaver @ 2014-01-21 5:38 UTC (permalink / raw)
To: Mateusz Kowalczyk; +Cc: guile-devel
Mateusz Kowalczyk <fuuzetsu@fuuzetsu.co.uk> writes:
> 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.
That's good! Thanks for making sure we understood the requirements.
> 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.
I wouldn't expect very high performance from the current implementation,
which was written in Scheme in the most straightforward manner possible,
and built upon fairly heavy "fat" mutexes and condition variables. I
could write a much faster implementation in C, based on other pthread
primitives and perhaps optimized using primitives from libatomicops, and
perhaps we should do that at some point.
Mark
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2014-01-21 5:38 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-09-02 7:55 Concurrent MVars for Guile Mark H Weaver
2013-09-03 11:55 ` Mark H Weaver
[not found] ` <CAGua6m3o_NexANbGuDYd5_rbPQqsbXkK504ONaFE7PGdQd98og@mail.gmail.com>
2013-09-04 6:27 ` Fwd: " Stefan Israelsson Tampe
2013-09-05 2:10 ` David Thompson
2013-09-05 2:53 ` Mark H Weaver
2013-09-14 13:59 ` Ludovic Courtès
2013-09-17 20:18 ` Andy Wingo
2014-01-16 0:47 ` Mark H Weaver
2014-01-16 13:01 ` Ludovic Courtès
2014-01-17 6:33 ` Mateusz Kowalczyk
2014-01-17 19:31 ` Mark H Weaver
2014-01-18 0:46 ` Mark H Weaver
2014-01-18 1:05 ` Mateusz Kowalczyk
2014-01-21 5:38 ` Mark H Weaver
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).