Concurrent MVars for Guile

Concurrent MVars for Guile

[Mark H Weaver]

[-- 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)))))

Re: Concurrent MVars for Guile

[Mark H Weaver]

[-- 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)))

Fwd: Concurrent MVars for Guile

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 6864 bytes --]

---------- Forwarded message ----------
From: Stefan Israelsson Tampe <stefan.itampe@gmail.com>
Date: Tue, Sep 3, 2013 at 6:22 PM
Subject: Re: Concurrent MVars for Guile
To: Mark H Weaver <mhw@netris.org>


I find this code good to include due to.
1. Small and tidy code
2. Good for study to see how to how to use the primitive primitives
3. Nice semantics that are useful.

One could argue that this belongs to a library, but I agree with mark that
we need to have these primitives out of the box due to.
1. To low level to be in a library e.g. prevent dependency hell
2. It will force fine documentation of the code
3. It will unify the interface.

For 3 one could argue that it is better to allow people to play with
semantics
and develop this field in many direction. I think on the other hand that
this has been
done already in other programming environments and we should be able to
steal
the well proven semantics for guile and include it with guile.

My 2c

Cheers




On Tue, Sep 3, 2013 at 1:55 PM, Mark H Weaver <mhw@netris.org> wrote:

> 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
>
>
>
> (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)))
>
>

[-- Attachment #2: Type: text/html, Size: 8426 bytes --]

Re: Concurrent MVars for Guile

[David Thompson]

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

Re: Concurrent MVars for Guile

[Mark H Weaver]

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

Re: Concurrent MVars for Guile

[Ludovic Courtès]

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

Re: Concurrent MVars for Guile

[Andy Wingo]

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/

Re: Concurrent MVars for Guile

[Mark H Weaver]

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

Re: Concurrent MVars for Guile

[Ludovic Courtès]

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

Re: Concurrent MVars for Guile

[Mateusz Kowalczyk]

[-- 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 --]

Re: Concurrent MVars for Guile

[Mark H Weaver]

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

Re: Concurrent MVars for Guile

[Mark H Weaver]

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

Re: Concurrent MVars for Guile

[Mateusz Kowalczyk]

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.

Re: Concurrent MVars for Guile

[Mark H Weaver]

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