* Re: [Caml-list] Smart ways to implement worker threads
2010-07-15 18:24 ` Goswin von Brederlow
@ 2010-07-15 18:37 ` David McClain
2010-07-15 18:40 ` David McClain
2010-07-15 19:56 ` Rich Neswold
2 siblings, 0 replies; 31+ messages in thread
From: David McClain @ 2010-07-15 18:37 UTC (permalink / raw)
To: caml-list
[-- Attachment #1: Type: text/plain, Size: 10990 bytes --]
> It is too bad I don't want to lear CML but use Ocaml. The CML examples
> from the book don't translate into ocaml since the interface is just a
> little bit different and those differences are what throws me off. I
That may appear to be the case from only a cursory review of CML. But
I find that OCaml's notions of Events, Channels, etc, correspond
quite closely to what John Reppy describes.
The whole point of Reppy's work was to show how "Events" could be
made into functional objects, with operations for combination among
them.
I don't have the "sort" routine translated, but here is some Lisp
code that attempts to provide the multiple-readers / single-writer
locks as might be used in a database application. It demonstrates the
use of wrap, sync, etc...
-----------------------------------
;; rwgate.lisp -- Multiple Reader/Single Writer using Reppy's Channels
;;
;; DM/MCFA 01/00
;; ----------------------------------------------------
(defpackage "RWGATE"
(:use "USEFUL-MACROS" "COMMON-LISP" "REPPY-CHANNELS" "SPM"
"LISPWORKS")
(:export "MAKE-LOCK"
"WRAP-RDLOCKEVT"
"WRAP-WRLOCKEVT"
"WITH-READLOCK"
"WITH-WRITELOCK"))
(in-package "RWGATE")
;; ---------------------------------------------------------------
;; This package implements a multiple-reader/single-writer lock
;; protocol using the amazing capabilities of the Reppy channels.
;;
;; Rule of engagement:
;;
;; 1. A lock is available for reading if no write locks are in place,
;; or else the read lock requestor is equal to the write lock holder.
;;
;; 2. A lock is available for writing if no read locks and no write
locks
;; are in place,
;; or else the write lock requestor is equal to the write lock
holder,
;; or else the write lock requestor is equal to every read lock
holder.
;;
;; These rules ensure that multiple readers can run, while only one
;; writer can run. No requirements for nesting of read/write lock
;; requests. That is, a writer can request a read lock and vice versa,
;; and issue lock releases in any order.
;;
;; A lock holder can request any number of additional locks. The lock
will
;; actually be released when an equal number of releases of like kind
;; have been obtained. For every write lock there is a write release,
;; and for every read lock there is a read release.
;;
;; The Reppy protocol is protected with UNWIND-PROTECT to ensure that
;; locks held are released on exit from the function block being
executed
;; within the province of a lock. Lock releases are handled
transparently
;; to the user.
;;
;; ---------------------------------------------------------------
;; Lock server protocol with event combinators
(defclass rw-lock (<serviceable-protocol-mixin>)
((rdlocks :accessor rw-lock-rdlocks :initform 0)
(wrlocks :accessor rw-lock-wrlocks :initform 0)
(wrowner :accessor rw-lock-wrowner :initform nil)
(rdqueue :accessor rw-lock-rdqueue :initform nil)
(rdowners :accessor rw-lock-rdowners :initform nil)
(wrqueue :accessor rw-lock-wrqueue :initform nil)))
(defun make-lock ()
(make-instance
'rw-lock
:handlers (list
:read
#'(lambda (req gate who)
(declare (ignore req))
(labels ((take-it ()
(incf (rw-lock-rdlocks gate))
(push who (rw-lock-rdowners gate))
(spawn #'send who t)))
(cond ((eq who (rw-lock-wrowner gate))
;; we own a write lock already so go ahead...
(take-it))
((plusp (rw-lock-wrlocks gate))
;; outstanding write lock so enqueue in
;; pending readers queue...
(push who (rw-lock-rdqueue gate)))
(t
;; no outstanding writer so take it...
(take-it))
)))
:release-read
#'(lambda (req gate who)
(declare (ignore req))
(removef (rw-lock-rdowners gate) who :count 1)
(if (and (zerop (decf (rw-lock-rdlocks gate)))
(zerop (rw-lock-wrlocks gate)))
;; no more readers and no more writers
;; (a writer might have been me...)
;; so go ahead and start writers
;; there should be no pending readers
;; since there were no writers
(let ((writer (pop (rw-lock-wrqueue gate))))
(when writer
(incf (rw-lock-wrlocks gate))
(setf (rw-lock-wrowner gate) writer)
(spawn #'send writer t))
)))
:write
#'(lambda (req gate who)
(declare (ignore req))
(labels ((take-it ()
(incf (rw-lock-wrlocks gate))
(setf (rw-lock-wrowner gate) who)
(spawn #'send who t)))
(cond ((and (zerop (rw-lock-rdlocks gate))
(zerop (rw-lock-wrlocks gate)))
;; gate available so take it
(take-it))
((eq who (rw-lock-wrowner gate))
;; gate already owned by requestor
;; so incr lock count and tell him its okay...
(take-it))
((every #'(lambda (rdr)
(eq rdr who))
(rw-lock-rdowners gate))
;; only one reader and it is me...
;; but I may be in the list numerous
times...
;; so go ahead and grab a write lock.
(take-it))
(t
;; gate not available -- put caller on
;; waiting writers queue
(conc1f (rw-lock-wrqueue gate) who))
)))
:release-write
#'(lambda (req gate who)
(declare (ignore req who))
(labels
((run-writer ()
(let ((writer (pop (rw-lock-wrqueue gate))))
(if writer
(progn
(incf (rw-lock-wrlocks gate))
(setf (rw-lock-wrowner gate) writer)
(spawn #'send writer t)
t)
nil)))
(run-readers ()
(let ((readers (rw-lock-rdqueue gate)))
(if readers
(progn
(setf (rw-lock-rdqueue gate) nil)
(appendf (rw-lock-rdowners gate) readers)
(incf (rw-lock-rdlocks gate)
(length readers))
(dolist (reader readers)
(spawn #'send reader t))
t)
nil))))
(when (zerop (decf (rw-lock-wrlocks gate)))
;; no more writers (was only me anyway...)
(setf (rw-lock-wrowner gate) nil)
(if (zerop (rw-lock-rdlocks gate))
;; if no active readers either
;; then it is a toss up whether to
;; start writers or readers
(if (zerop (random 2)) ;; add some non-determinism
(unless (run-writer)
(run-readers))
(unless (run-readers)
(run-writer)))
;; but if I was a reader too,
;; then it is only safe to start other
;; readers.
(run-readers)))
))
)))
(defun wrap-lockEvt (lock fn args req rel)
(guard
#'(lambda ()
(let ((replyCh (make-channel)))
(labels
((acquire-lock ()
(service-request req lock replyCh))
(release-lock ()
(service-request rel lock replyCh)))
(spawn #'acquire-lock)
(wrap-abort
(wrap (recvEvt replyCh)
#'(lambda (reply)
(declare (ignore reply))
(unwind-protect
(apply fn args)
(spawn #'release-lock))))
#'(lambda ()
(spawn #'(lambda ()
(recv replyCh)
(release-lock)))))
)))
))
(defmethod wrap-rdLockEvt ((lock rw-lock) fn &rest args)
(wrap-lockEvt lock fn args :read :release-read))
(defmethod wrap-wrLockEvt ((lock rw-lock) fn &rest args)
(wrap-lockEvt lock fn args :write :release-write))
(defmethod with-readlock ((lock rw-lock) fn &rest args)
(sync (apply #'wrap-rdLockEvt lock fn args)))
(defmethod with-writelock ((lock rw-lock) fn &rest args)
(sync (apply #'wrap-wrLockEvt lock fn args)))
-----------------------------------
Dr. David McClain
Chief Technical Officer
Refined Audiometrics Laboratory
4391 N. Camino Ferreo
Tucson, AZ 85750
email: dbm@refined-audiometrics.com
phone: 1.520.390.3995
web: http://refined-audiometrics.com
On Jul 15, 2010, at 11:24, Goswin von Brederlow wrote:
> Rich Neswold <rich.neswold@gmail.com> writes:
>
>> On Wed, Jul 14, 2010 at 11:09 AM, Goswin von Brederlow <goswin-v-
>> b@web.de>
>> wrote:
>>
>> 4) Do some magic with Event.t?
>>
>> Problem: never used this and I could use a small example how
>> to use
>> this.
>>
>>
>> Event.t (and its associated library) *is* magical in that it
>> provides an
>> absolutely beautiful concurrent programming model. Forget about
>> select() and
>> mutexes and other ugly threading concepts. Event.t and friends is
>> how it should
>> be done.
>>
>> John H. Reppy's "Concurrent Programming in ML" provides a thorough
>> understanding of how to use this module effectively. This book
>> presents the
>> material in a very understandable way: deficiencies in current
>> threading
>> models are discussed as well as how CML solves the limitations and
>> constraints.
>> The book can be purchased or downloaded free online.
>
> It is too bad I don't want to lear CML but use Ocaml. The CML examples
> from the book don't translate into ocaml since the interface is just a
> little bit different and those differences are what throws me off. I
> figue spawn becomes Thread.cread and I have to add Event.sync or
> Event.select and Event.wrap at some points. At which point the book
> becomes useless to understanding how Ocamls Event module is to be used
> I'm afraid. Also doesn't tell me what Ocamls limitations and
> constraints
> are.
>
> So if you have used this in ocaml could you give a short example?
> E.g. the merge sort from the book.
>
> MfG
> Goswin
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>
[-- Attachment #2: Type: text/html, Size: 30795 bytes --]
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Smart ways to implement worker threads
2010-07-15 18:24 ` Goswin von Brederlow
2010-07-15 18:37 ` David McClain
@ 2010-07-15 18:40 ` David McClain
2010-07-15 19:56 ` Rich Neswold
2 siblings, 0 replies; 31+ messages in thread
From: David McClain @ 2010-07-15 18:40 UTC (permalink / raw)
To: caml-list
[-- Attachment #1: Type: text/plain, Size: 8725 bytes --]
It is too bad I don't want to lear CML but use Ocaml. The CML examples
from the book don't translate into ocaml since the interface is just a
little bit different and those differences are what throws me off. I
That may appear to be the case from only a cursory review of CML. But
I find that OCaml's notions of Events, Channels, etc, correspond
quite closely to what John Reppy describes.
The whole point of Reppy's work was to show how "Events" could be
made into functional objects, with operations for combination among
them.
I don't have the "sort" routine translated, but here is some Lisp
code that attempts to provide the multiple-readers / single-writer
locks as might be used in a database application. It demonstrates the
use of wrap, sync, etc...
-----------------------------------
;; rwgate.lisp -- Multiple Reader/Single Writer using Reppy's Channels
;;
;; DM/MCFA 01/00
;; ----------------------------------------------------
(defpackage "RWGATE"
(:use "USEFUL-MACROS" "COMMON-LISP" "REPPY-CHANNELS" "SPM"
"LISPWORKS")
(:export "MAKE-LOCK"
"WRAP-RDLOCKEVT"
"WRAP-WRLOCKEVT"
"WITH-READLOCK"
"WITH-WRITELOCK"))
(in-package "RWGATE")
;; ---------------------------------------------------------------
;; This package implements a multiple-reader/single-writer lock
;; protocol using the amazing capabilities of the Reppy channels.
;;
;; Rule of engagement:
;;
;; 1. A lock is available for reading if no write locks are in place,
;; or else the read lock requestor is equal to the write lock holder.
;;
;; 2. A lock is available for writing if no read locks and no write
locks
;; are in place,
;; or else the write lock requestor is equal to the write lock
holder,
;; or else the write lock requestor is equal to every read lock
holder.
;;
;; These rules ensure that multiple readers can run, while only one
;; writer can run. No requirements for nesting of read/write lock
;; requests. That is, a writer can request a read lock and vice versa,
;; and issue lock releases in any order.
;;
;; A lock holder can request any number of additional locks. The lock
will
;; actually be released when an equal number of releases of like kind
;; have been obtained. For every write lock there is a write release,
;; and for every read lock there is a read release.
;;
;; The Reppy protocol is protected with UNWIND-PROTECT to ensure that
;; locks held are released on exit from the function block being
executed
;; within the province of a lock. Lock releases are handled
transparently
;; to the user.
;;
;; ---------------------------------------------------------------
;; Lock server protocol with event combinators
(defclass rw-lock (<serviceable-protocol-mixin>)
((rdlocks :accessor rw-lock-rdlocks :initform 0)
(wrlocks :accessor rw-lock-wrlocks :initform 0)
(wrowner :accessor rw-lock-wrowner :initform nil)
(rdqueue :accessor rw-lock-rdqueue :initform nil)
(rdowners :accessor rw-lock-rdowners :initform nil)
(wrqueue :accessor rw-lock-wrqueue :initform nil)))
(defun make-lock ()
(make-instance
'rw-lock
:handlers (list
:read
#'(lambda (req gate who)
(declare (ignore req))
(labels ((take-it ()
(incf (rw-lock-rdlocks gate))
(push who (rw-lock-rdowners gate))
(spawn #'send who t)))
(cond ((eq who (rw-lock-wrowner gate))
;; we own a write lock already so go ahead...
(take-it))
((plusp (rw-lock-wrlocks gate))
;; outstanding write lock so enqueue in
;; pending readers queue...
(push who (rw-lock-rdqueue gate)))
(t
;; no outstanding writer so take it...
(take-it))
)))
:release-read
#'(lambda (req gate who)
(declare (ignore req))
(removef (rw-lock-rdowners gate) who :count 1)
(if (and (zerop (decf (rw-lock-rdlocks gate)))
(zerop (rw-lock-wrlocks gate)))
;; no more readers and no more writers
;; (a writer might have been me...)
;; so go ahead and start writers
;; there should be no pending readers
;; since there were no writers
(let ((writer (pop (rw-lock-wrqueue gate))))
(when writer
(incf (rw-lock-wrlocks gate))
(setf (rw-lock-wrowner gate) writer)
(spawn #'send writer t))
)))
:write
#'(lambda (req gate who)
(declare (ignore req))
(labels ((take-it ()
(incf (rw-lock-wrlocks gate))
(setf (rw-lock-wrowner gate) who)
(spawn #'send who t)))
(cond ((and (zerop (rw-lock-rdlocks gate))
(zerop (rw-lock-wrlocks gate)))
;; gate available so take it
(take-it))
((eq who (rw-lock-wrowner gate))
;; gate already owned by requestor
;; so incr lock count and tell him its okay...
(take-it))
((every #'(lambda (rdr)
(eq rdr who))
(rw-lock-rdowners gate))
;; only one reader and it is me...
;; but I may be in the list numerous
times...
;; so go ahead and grab a write lock.
(take-it))
(t
;; gate not available -- put caller on
;; waiting writers queue
(conc1f (rw-lock-wrqueue gate) who))
)))
:release-write
#'(lambda (req gate who)
(declare (ignore req who))
(labels
((run-writer ()
(let ((writer (pop (rw-lock-wrqueue gate))))
(if writer
(progn
(incf (rw-lock-wrlocks gate))
(setf (rw-lock-wrowner gate) writer)
(spawn #'send writer t)
t)
nil)))
(run-readers ()
(let ((readers (rw-lock-rdqueue gate)))
(if readers
(progn
(setf (rw-lock-rdqueue gate) nil)
(appendf (rw-lock-rdowners gate) readers)
(incf (rw-lock-rdlocks gate)
(length readers))
(dolist (reader readers)
(spawn #'send reader t))
t)
nil))))
(when (zerop (decf (rw-lock-wrlocks gate)))
;; no more writers (was only me anyway...)
(setf (rw-lock-wrowner gate) nil)
(if (zerop (rw-lock-rdlocks gate))
;; if no active readers either
;; then it is a toss up whether to
;; start writers or readers
(if (zerop (random 2)) ;; add some non-determinism
(unless (run-writer)
(run-readers))
(unless (run-readers)
(run-writer)))
;; but if I was a reader too,
;; then it is only safe to start other
;; readers.
(run-readers)))
))
)))
(defun wrap-lockEvt (lock fn args req rel)
(guard
#'(lambda ()
(let ((replyCh (make-channel)))
(labels
((acquire-lock ()
(service-request req lock replyCh))
(release-lock ()
(service-request rel lock replyCh)))
(spawn #'acquire-lock)
(wrap-abort
(wrap (recvEvt replyCh)
#'(lambda (reply)
(declare (ignore reply))
(unwind-protect
(apply fn args)
(spawn #'release-lock))))
#'(lambda ()
(spawn #'(lambda ()
(recv replyCh)
(release-lock)))))
)))
))
(defmethod wrap-rdLockEvt ((lock rw-lock) fn &rest args)
(wrap-lockEvt lock fn args :read :release-read))
(defmethod wrap-wrLockEvt ((lock rw-lock) fn &rest args)
(wrap-lockEvt lock fn args :write :release-write))
(defmethod with-readlock ((lock rw-lock) fn &rest args)
(sync (apply #'wrap-rdLockEvt lock fn args)))
(defmethod with-writelock ((lock rw-lock) fn &rest args)
(sync (apply #'wrap-wrLockEvt lock fn args)))
-----------------------------------
Dr. David McClain
Chief Technical Officer
Refined Audiometrics Laboratory
4391 N. Camino Ferreo
Tucson, AZ 85750
email: dbm@refined-audiometrics.com
phone: 1.520.390.3995
web: http://refined-audiometrics.com
[-- Attachment #2: Type: text/html, Size: 62623 bytes --]
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Smart ways to implement worker threads
2010-07-15 18:24 ` Goswin von Brederlow
2010-07-15 18:37 ` David McClain
2010-07-15 18:40 ` David McClain
@ 2010-07-15 19:56 ` Rich Neswold
2010-07-16 4:02 ` Goswin von Brederlow
2 siblings, 1 reply; 31+ messages in thread
From: Rich Neswold @ 2010-07-15 19:56 UTC (permalink / raw)
To: Goswin von Brederlow; +Cc: caml-list
[-- Attachment #1.1: Type: text/plain, Size: 850 bytes --]
On Thu, Jul 15, 2010 at 1:24 PM, Goswin von Brederlow <goswin-v-b@web.de>wrote:
> It is too bad I don't want to learn CML but use Ocaml. The CML examples
> from the book don't translate into ocaml since the interface is just a
> little bit different and those differences are what throws me off.
>
> So could you give a short example? E.g. the merge sort from the book.
>
You're right: OCaml's syntax differs enough from the text that it's annoying
to cut-n-paste the examples. Fortunately most example are a few lines of
code, so I didn't realize how difficult it could be on a larger example
(like the merge sort example.)
Attached is my translation of the mergeSort from the book. You get to play
with it and see if it works :)
--
Rich
Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net
[-- Attachment #1.2: Type: text/html, Size: 1444 bytes --]
[-- Attachment #2: mergesort.ml --]
[-- Type: text/x-ocaml, Size: 1487 bytes --]
open Event
let mySend c d = sync (send c d)
and myRecv c = sync (receive c)
let spawn f =
ignore (Thread.create f ())
let split (inCh, outCh1, outCh2) =
let rec loop = function
| (None, _, _) -> (mySend outCh1 None; mySend outCh2 None)
| (x, out1, out2) -> (mySend out1 x; loop (myRecv inCh, out2, out1))
in
loop (myRecv inCh, outCh1, outCh2)
let merge (inCh1, inCh2, (outCh : int option channel)) =
let rec copy (fromCh, toCh) =
let rec loop v =
begin
mySend toCh v;
match v with
| Some _ -> loop (myRecv fromCh)
| None -> ()
end
in
loop (myRecv fromCh)
and mergep (from1, from2) =
match (from1, from2) with
| (None, None) -> mySend outCh None
| (_, None) -> (mySend outCh from1; copy (inCh1, outCh))
| (None, _) -> (mySend outCh from2; copy (inCh2, outCh))
| (Some a, Some b) ->
if a < b then
(mySend outCh from1; mergep (myRecv inCh1, from2))
else
(mySend outCh from2; mergep (from1, myRecv inCh2))
in
mergep (myRecv inCh1, myRecv inCh2)
let rec mergeSort () =
let ch = new_channel() in
let sort () =
(match myRecv ch with
| None -> ()
| v1 ->
begin
(match myRecv ch with
| None -> mySend ch v1
| v2 ->
let ch1 = mergeSort()
and ch2 = mergeSort()
in
begin
mySend ch1 v1;
mySend ch2 v2;
split (ch, ch1, ch2);
merge (ch1, ch2, ch)
end);
mySend ch None
end)
in
(spawn sort; ch)
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Smart ways to implement worker threads
2010-07-15 19:56 ` Rich Neswold
@ 2010-07-16 4:02 ` Goswin von Brederlow
2010-07-16 4:23 ` Rich Neswold
2010-07-17 18:34 ` Eray Ozkural
0 siblings, 2 replies; 31+ messages in thread
From: Goswin von Brederlow @ 2010-07-16 4:02 UTC (permalink / raw)
To: Rich Neswold; +Cc: Goswin von Brederlow, caml-list
Rich Neswold <rich.neswold@gmail.com> writes:
> On Thu, Jul 15, 2010 at 1:24 PM, Goswin von Brederlow <goswin-v-b@web.de>
> wrote:
>
> It is too bad I don't want to learn CML but use Ocaml. The CML examples
> from the book don't translate into ocaml since the interface is just a
> little bit different and those differences are what throws me off.
>
> Â
>
> So could you give a short example? E.g. the merge sort from the book.
>
>
> You're right: OCaml's syntax differs enough from the text that it's annoying to
> cut-n-paste the examples. Fortunately most example are a few lines of code, so
> I didn't realize how difficult it could be on a larger example (like the merge
> sort example.)
>
> Attached is my translation of the mergeSort from the book. You get to play with
> it and see if it works  :)
Thanks. That is about what I got so I do seem to understand the
differences right.
For my use case this would then come down to implement solution 3 with
channels instead of my own queues. Well, channels are thread safe queues
just by another name. I think I see now how they make the code simpler
to write.
MfG
Goswin
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Smart ways to implement worker threads
2010-07-16 4:02 ` Goswin von Brederlow
@ 2010-07-16 4:23 ` Rich Neswold
2010-07-16 13:02 ` Goswin von Brederlow
2010-07-17 18:34 ` Eray Ozkural
1 sibling, 1 reply; 31+ messages in thread
From: Rich Neswold @ 2010-07-16 4:23 UTC (permalink / raw)
To: Goswin von Brederlow; +Cc: caml-list
[-- Attachment #1: Type: text/plain, Size: 1065 bytes --]
On Thu, Jul 15, 2010 at 11:02 PM, Goswin von Brederlow <goswin-v-b@web.de>wrote:
> Rich Neswold <rich.neswold@gmail.com> writes:
>
> Thanks. That is about what I got so I do seem to understand the
> differences right.
>
> For my use case this would then come down to implement solution 3 with
> channels instead of my own queues. Well, channels are thread safe queues
> just by another name. I think I see now how they make the code simpler
> to write.
>
Channels are a thread-safe communication channel of depth one (i.e. you can
only pass one item at a time.) The channel is a primitive that allows
reliable synchronized communication between threads. The Reppy book
describes in later chapters how to use the channel primitive to build up
queues and other, more complicated constructs (like RPCs and multicasting to
many processes.)
In fact, you might use the RPC ideas to pass your checksumming requests to
worker tasks and receive the results.
--
Rich
Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net
[-- Attachment #2: Type: text/html, Size: 1570 bytes --]
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Smart ways to implement worker threads
2010-07-16 4:23 ` Rich Neswold
@ 2010-07-16 13:02 ` Goswin von Brederlow
2010-07-16 14:40 ` Dawid Toton
` (2 more replies)
0 siblings, 3 replies; 31+ messages in thread
From: Goswin von Brederlow @ 2010-07-16 13:02 UTC (permalink / raw)
To: Rich Neswold; +Cc: Goswin von Brederlow, caml-list
Rich Neswold <rich.neswold@gmail.com> writes:
> On Thu, Jul 15, 2010 at 11:02 PM, Goswin von Brederlow <goswin-v-b@web.de>
> wrote:
>
> Rich Neswold <rich.neswold@gmail.com> writes:
>
> Thanks. That is about what I got so I do seem to understand the
> differences right.
>
> For my use case this would then come down to implement solution 3 with
> channels instead of my own queues. Well, channels are thread safe queues
> just by another name. I think I see now how they make the code simpler
> to write.
>
>
> Channels are a thread-safe communication channel of depth one (i.e. you can
> only pass one item at a time.) The channel is a primitive that allows reliable
Urgs, so what happens if I call "sync (send ...)" twice without the
other end calling recieve? Lets test:
let ch = Event.new_channel ()
let reciever () =
for i = 0 to 10 do
Printf.printf "recieved %d\n" (Event.sync (Event.receive ch));
flush_all ();
Unix.sleep 2;
done
let _ =
ignore (Thread.create reciever ());
for i = 0 to 10 do
Printf.printf "sending %d\n" i;
flush_all ();
Event.sync (Event.send ch i);
Unix.sleep 1;
done
% ocamlopt -thread -o foo unix.cmxa threads.cmxa foo.ml && ./foo
sending 0
recieved 0
sending 1
recieved 1
sending 2
recieved 2
sending 3
recieved 3
...
So the send blocks until the event is recieved. That certainly isn't
helpfull for me. One could say I want asynchronous remote function calls
(and returns).
> synchronized communication between threads. The Reppy book describes in later
> chapters how to use the channel primitive to build up queues and other, more
> complicated constructs (like RPCs and multicasting to many processes.)
>
> In fact, you might use the RPC ideas to pass your checksumming requests to
> worker tasks and receive the results.
Yeah. But then why not build it around the simple Mutex and Condition
modules instead of Event? At first glance the blocking aspect of Events
seem to be more of a hindrance than help.
I find it odd that there is no Threaded_Queue module, a thread save
version of Queue with 2 extra functions:
val wait_and_take : 'a t -> 'a
wait_and_take q waits for the queue q to be not empty and removes and
returns the first element in queue q. Raises Empty when the queue is
closed.
val close : 'a t -> unit
close q closes the queue and wakes up waiting threads.
MfG
Goswin
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: Smart ways to implement worker threads
2010-07-16 13:02 ` Goswin von Brederlow
@ 2010-07-16 14:40 ` Dawid Toton
2010-07-16 16:18 ` [Caml-list] " Rich Neswold
2010-07-20 4:54 ` Satoshi Ogasawara
2 siblings, 0 replies; 31+ messages in thread
From: Dawid Toton @ 2010-07-16 14:40 UTC (permalink / raw)
To: caml-list
> I find it odd that there is no Threaded_Queue module, a thread save
> version of Queue with 2 extra functions: (...)
>
I use such a thread-safe queue a lot [1]. This is very simple yet
universal enough. Honestly I can hardly remember using more elaborate
constructs.
Dawid
[1] http://pfpleia.if.uj.edu.pl/projects/HLibrary/browser/HQueue.ml
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Smart ways to implement worker threads
2010-07-16 13:02 ` Goswin von Brederlow
2010-07-16 14:40 ` Dawid Toton
@ 2010-07-16 16:18 ` Rich Neswold
2010-07-17 17:53 ` Eray Ozkural
2010-07-20 4:54 ` Satoshi Ogasawara
2 siblings, 1 reply; 31+ messages in thread
From: Rich Neswold @ 2010-07-16 16:18 UTC (permalink / raw)
To: Goswin von Brederlow; +Cc: caml-list
[-- Attachment #1: Type: text/plain, Size: 1563 bytes --]
On Fri, Jul 16, 2010 at 8:02 AM, Goswin von Brederlow <goswin-v-b@web.de>wrote:
> Yeah. But then why not build it around the simple Mutex and Condition
> modules instead of Event? At first glance the blocking aspect of Events
> seem to be more of a hindrance than help.
>
The problem with Mutex and Condition is all the management that goes with
them. You must make sure your unlocks match your locks -- even in the
presence of exceptions. None of this bookkeeping is required from the
programmer when using Event.
The bigger win for Events, though, is that they're composable.
Let's say you decide to have two queues to communicate with two workers.
With the mutex/queue scenario, you'd have to resort to polling each queue --
locking and unlocking each mutex in turn (or decide that a single mutex
protects both queues ... but this approach doesn't scale well.)
With events, you pass a list of events to 'Event.choose' and the process
will be awakened when one of the events returns a value. No need to widen
the protection of mutexes; adding more events to the list is enough.
Granted, if you mix and match event types (sends and receives, for instance)
you may have to use 'Event.wrap' to make sure they return a compatible type.
Event may not be the best solution for your problem, or it may even lie
outside your comfort zone. Hopefully this discussion has, at the very least,
made some OCaml users take another look at the Event module.
--
Rich
Google Reader: https://www.google.com/reader/shared/rich.neswold
Jabber ID: rich@neswold.homeunix.net
[-- Attachment #2: Type: text/html, Size: 2091 bytes --]
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Smart ways to implement worker threads
2010-07-16 16:18 ` [Caml-list] " Rich Neswold
@ 2010-07-17 17:53 ` Eray Ozkural
0 siblings, 0 replies; 31+ messages in thread
From: Eray Ozkural @ 2010-07-17 17:53 UTC (permalink / raw)
To: Rich Neswold; +Cc: Goswin von Brederlow, caml-list
It does encourage me to take a shot at using the Event module.
One of the advantages of object orientation was that event-driven programming and concurrent processes would/could fit well.
Yet years later event driven programming exists mostly as the main loop of GUI libraries and implemented in cumbersome imperative languages.
It has been suggested that traditional synchronization primitives are deficient. Like with message passing libraries it's too easy to write incorrect code with them (since they assume all programmers must be naive enough to still code in C.). I think it's so much easier to make a buggy implementation in posix threads that I advise against (having to) use it in any language.
In my experience with shared memory programming I found it a better option to write code in openmp. Charm++ like spawn directives aren't too bad either and they fit functional languages.
I suppose with some compiler help we could have such parallelization; maybe just some camlp4 macros are enough. After all, it's not a bad idea to isolate synchronization in the program and I bet it can be done in a safe way. What would be needed to adapt the openmp idea to ocaml? Assuming we have proper multicore support (lock-free parallel garbage collector, real threads etc.)
Considering that architectural details cannot be so easily ignored on a multicore architecture I wonder how to do this best. Perhaps some way to specify fine-grain parallelism would be more flexible (like fine-grain kernels in cuda) I think architectural details would be important for parallel code optimizations.
We had used a thread/critical region based intermediate program representation for C but I think we could do better with functional languages, towards a fully implicit parallel PL.
Of course there are various existing approaches to implementing explicit parallelism on top of ocaml. I wonder if the INRIA team would consider adapting those to a shared memory architecture. Short of the high technology we need (implicit parallelism) we can be satisfied with cool functional and architecture agnostic parallelism primitives.
So my wishlist is:
1) low level shared memory programming primitives and lang support
2) high level parallel programming facility that is completely independent of target architecture
3) implicit parallelism that uses an automatic parallelization approach
Cheers,
Eray
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Smart ways to implement worker threads
2010-07-16 13:02 ` Goswin von Brederlow
2010-07-16 14:40 ` Dawid Toton
2010-07-16 16:18 ` [Caml-list] " Rich Neswold
@ 2010-07-20 4:54 ` Satoshi Ogasawara
2 siblings, 0 replies; 31+ messages in thread
From: Satoshi Ogasawara @ 2010-07-20 4:54 UTC (permalink / raw)
To: Goswin von Brederlow; +Cc: Rich Neswold, caml-list
On 2010/07/16, at 22:02, Goswin von Brederlow wrote:
> Urgs, so what happens if I call "sync (send ...)" twice without the
> other end calling recieve? Lets test:
>
> let ch = Event.new_channel ()
> ...
That's not good use of synchronous channels. If you want to asynchronous,
try Mbox module in concurrent cell.
https://forge.ocamlcore.org/scm/viewvc.php/trunk/mbox.mli?view=markup&root=ccell
open Printf
open Ccell
open Event
let mbox = Mbox.make ()
let receiver () =
for i = 0 to 10 do
printf "received %d\n%!" (sync (Mbox.pop mbox));
Thread.delay 2.;
done
let _ =
ignore (Thread.create receiver ());
for i = 0 to 10 do
printf "sending %d\n%!" i;
sync (Mbox.push mbox i);
Thread.delay 1.;
done
wednesday:tmp osiire$ ocamlc -thread unix.cma threads.cma -I +site-lib/ccell ccell.cma async.ml && ./a.out
sending 0
received 0
sending 1
received 1
sending 2
sending 3
received 2
sending 4
sending 5
received 3
sending 6
sending 7
received 4
sending 8
sending 9
received 5
sending 10
With Mbox module, you can also wait and select long calculation results like this.
open Printf
open Ccell
open Event
let rec forever f x =
let v = f x in forever f v
let spawn_loop f x =
ignore (Thread.create (forever f) x)
let make_worker f =
let input, output = Mbox.make (), Mbox.make () in
let work () =
sync (Mbox.push output (f (sync (Mbox.pop input))));
in
spawn_loop work ();
input, output
let request (input, _) p =
sync (Mbox.push input p)
let response (_, output) =
Mbox.pop output
let worker1 = make_worker (printf "action worker1 %d\n%!")
let worker2 = make_worker (printf "action worker2 %d\n%!")
let after_long_calc (e1, e2) =
select [
wrap e1 (fun _ -> printf "after work1\n%!"; (response worker1, e2));
wrap e2 (fun _ -> printf "after work2\n%!"; (e1, response worker2));
]
let _ =
spawn_loop after_long_calc (response worker1, response worker2);
request worker1 1;
Thread.delay 1.;
request worker2 2;
Thread.delay 1.;
request worker2 3;
Thread.delay 1.;
request worker1 4;
Thread.delay 2.
wednesday:tmp osiire$ ocamlc -thread unix.cma threads.cma -I +site-lib/ccell ccell.cma worker.ml && ./a.out
action worker1 1
after work1
action worker2 2
after work2
action worker2 3
after work2
action worker1 4
after work1
I hope this will be helpful for you.
---
satoshi ogasawara
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Smart ways to implement worker threads
2010-07-16 4:02 ` Goswin von Brederlow
2010-07-16 4:23 ` Rich Neswold
@ 2010-07-17 18:34 ` Eray Ozkural
2010-07-17 19:35 ` Goswin von Brederlow
1 sibling, 1 reply; 31+ messages in thread
From: Eray Ozkural @ 2010-07-17 18:34 UTC (permalink / raw)
To: Goswin von Brederlow; +Cc: Rich Neswold, caml-list
When I'm implementing a parallel/dist algorithm I take care of making the communication code abstract enough to be re-used. Since abstraction in C derivative languages (function pointers, templates etc) are a joke; one need not bother with this as expected future code re-use isn't much.
On the other hand in ocaml we have the best module system which can be used to create advanced parallel data structures and algorithms. A shared mem queue would be among the most trivial of such constructs. If we think of world domination we have to see the whole picture. Parallel programming is considered difficult because common programmers don't understand enough algebra to see that most problems could be solved by substituting an operator in a generic parallel algorithm template. Or that optimal algorithms could be re-used combinatorially (consider the relation of a mesh topology to a linear topology with s/f routing)
The fact is that an efficient parallel algorithm need not be long (theory suggests that fastest is shortest). It is our collective lack of creativity that usually makes it long.
Cheers,
Eray
Ps: parallelism is not tangential here. I believe it is unnecessary to implement asynchronous processes just for the sake of handling overlapping I/O and computation. That's like parallelism for high school programming class.
^ permalink raw reply [flat|nested] 31+ messages in thread
* Re: [Caml-list] Smart ways to implement worker threads
2010-07-17 18:34 ` Eray Ozkural
@ 2010-07-17 19:35 ` Goswin von Brederlow
2010-07-17 22:00 ` Eray Ozkural
0 siblings, 1 reply; 31+ messages in thread
From: Goswin von Brederlow @ 2010-07-17 19:35 UTC (permalink / raw)
To: Eray Ozkural; +Cc: Goswin von Brederlow, Rich Neswold, caml-list
Eray Ozkural <examachine@gmail.com> writes:
> When I'm implementing a parallel/dist algorithm I take care of making
> the communication code abstract enough to be re-used. Since
> abstraction in C derivative languages (function pointers, templates
> etc) are a joke; one need not bother with this as expected future code
> re-use isn't much.
>
> On the other hand in ocaml we have the best module system which can be
> used to create advanced parallel data structures and algorithms. A
> shared mem queue would be among the most trivial of such
> constructs. If we think of world domination we have to see the whole
> picture. Parallel programming is considered difficult because common
> programmers don't understand enough algebra to see that most problems
> could be solved by substituting an operator in a generic parallel
> algorithm template. Or that optimal algorithms could be re-used
> combinatorially (consider the relation of a mesh topology to a linear
> topology with s/f routing)
Yeah. I would love to have all the basic ocaml modules also as a thread
safe flavour.
> The fact is that an efficient parallel algorithm need not be long
> (theory suggests that fastest is shortest). It is our collective lack
> of creativity that usually makes it long.
>
> Cheers,
>
> Eray
>
> Ps: parallelism is not tangential here. I believe it is unnecessary to
> implement asynchronous processes just for the sake of handling
> overlapping I/O and computation. That's like parallelism for high
> school programming class.
I'm a big fan of doing IO asynchronously in a single thread. Given that
ocaml can only run one thread at a time anyway there is usualy no speed
gain in using multiple threads. The overhead of making the code thread
save is big in complexity (if only we hade thread save modules :) and
all you end up doing is waiting on more cores.
The exception is when you offload work to C code that can run within
enter_blocking_section() / leave_blocking_section() and you have enough
work to keep multiple cores busy. For example doing blockwise sha256
sums with 4 cores is 3-3.8 times as fast as single threaded depending on
blocksize.
MfG
Goswin
^ permalink raw reply [flat|nested] 31+ messages in thread* Re: [Caml-list] Smart ways to implement worker threads
2010-07-17 19:35 ` Goswin von Brederlow
@ 2010-07-17 22:00 ` Eray Ozkural
0 siblings, 0 replies; 31+ messages in thread
From: Eray Ozkural @ 2010-07-17 22:00 UTC (permalink / raw)
To: Goswin von Brederlow; +Cc: Goswin von Brederlow, Rich Neswold, caml-list
It looks like the multi core architectures will be around for a while only to be superseded by more advanced parallel micro-architectures.
Of course computation-bound apps will benefit more but this does not mean that memory intensive apps will not run well on multi core architectures. Carefully optimized code will run great on multi core architectures with high memory bandwidth. Depending on the application of course.
Right now it seems to me that shared mem is more suitable for data mining apps (and many other including scientific computing apps). Data mining has never been embarrassingly parallel and it's difficult to get good speedup on distributed architectures. I should know I've worked on the parallel solution of two such problems. Provided that the space complexity is manageable, I think such network-bound cluster algorithms have more efficient counter-parts on multi-core. In data mining algos some data may have to be replicated or communicated. If the space doesn't blow up, NVIDIA Fermi would be ideal for those problems. No more copying. On the new Tesla max memory will be 6x4=24gb.
For all I care Intel is obsolete until they give me a thousand cores.
Shared memory support is essential at any rate. I don't see why we can't have it in an excellent way!
Best,
Eray
^ permalink raw reply [flat|nested] 31+ messages in thread