[prev in list] [next in list] [prev in thread] [next in thread]
List: haskell-cafe
Subject: Re: [Haskell-cafe] Concurrent reads, ordered writes?
From: Alexander Vershilov <alexander.vershilov () gmail ! com>
Date: 2019-09-09 19:26:24
Message-ID: C444FB33-2132-4F24-80A7-ECD5EDC057C0 () gmail ! com
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
Hello,
it's possible to create no additional threads and return values via TBQueue (TMVar \
a). Then thread that reads replies can block on getting the result from the first \
thread, while other workers are working. Here is a basic example:
https://github.com/qnikst/haskell-fun/blob/cdaf070758fd9b61b37582f06f44d284c6c3b824/jobs/Main.hs \
<https://github.com/qnikst/haskell-fun/blob/cdaf070758fd9b61b37582f06f44d284c6c3b824/jobs/Main.hs>
But this very naive and I didn't even try to do anything about exceptions \
asynchronous or not.
--
Best wishes,
Alexander.
> On 9 Sep 2019, at 18:30, amindfv@gmail.com wrote:
>
> Hi Jeroen - thanks! I hadn't heard from anyone so over the weekend I sketched up an \
> early version of a library for this purpose:
> https://hackage.haskell.org/package/orderly-workers
>
> A few decisions you and I made are the same (a thread each for input and output \
> chans to avoid race conditions, MVars for finished work so worker threads aren't \
> blocked waiting for their "turn" at the output). In other ways our code is \
> different and I'm looking forward to digging into differences! (For example, I \
> already see a place I should be forcing strictness instead of assuming it'll be \
> forced in user code).
> For the use-case orderly-workers was designed for, it's got the task from ~6 mins \
> to ~2 mins with 5 worker threads. I'm happy with this, as the producer and consumer \
> processes are also doing substantial work.
> Open to any comments/criticism of the library.
>
> Thanks!
> Tom
>
> > El 9 sept 2019, a las 04:32, Jeroen Bransen <jeroen@chordify.net> escribió:
> >
> > Hello Tom,
> >
> > I am not aware of any specific algorithm or existing package for this
> > purpose, the best that I can come up with is [1]. It works by using two
> > auxillary queues and two main worker threads that have a special task.
> > One of them is the only thread reading from the input queue, thereby
> > avoiding race conditions in the "take an item and store where in the
> > output this element should come"-stage. It creates an MVar for each
> > item, puts that in the job queue together with the input, and puts that
> > in the other auxillary queue as well. The other main worker thread is
> > reading the MVars in order and is the only thread writing to the output
> > queue, thereby again avoiding race conditions. Now the real worker
> > threads only need to read from the auxillary queue where they get the A
> > and and MVar where they write the B.
> >
> > I am not sure whether or not this satisfies your "cleanness" desire, but
> > I believe it has two nice properties which are not so easy to get:
> > 1. The worker threads only do the real work, and are not blocked by
> > other workers still working on earlier items
> > 2. It is not hard to prove that this approach does not lead to deadlocks
> >
> > Regards,
> > Jeroen
> >
> >
> > [1] https://gist.github.com/jbransen/be81d70cfe2a85fe7d2dfbafc00b561c
> >
> > Op 6-9-2019 om 21:00 schreef amindfv@gmail.com:
> > > I've implemented a solution for this problem, but it seems a bit less clean \
> > > than it could be, which leaves me wondering if there's a data structure or \
> > > algorithm specifically for this purpose:
> > > We've got multiple concurrent thereads reading items from a (TBQueue A), \
> > > calling f :: A -> B, and writing to a (TBQueue B). We must, though, write items \
> > > into the (TBQueue B) in the order that the corresponding As were read (the \
> > > order they were put in the (TBQueue A)).
> > > Are there existing libraries which solve this or a similar problem? Ideally \
> > > with niceties like configuring whether the pending out-of-order writes block \
> > > the worker threads, and a way of signalling there's no more work to perform.
> > > Thanks!
> > > Tom
> > >
> > >
> > >
> > > _______________________________________________
> > > Haskell-Cafe mailing list
> > > To (un)subscribe, modify options or view archives go to:
> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > > Only members subscribed via the mailman list are allowed to post.
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > To (un)subscribe, modify options or view archives go to:
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> > Only members subscribed via the mailman list are allowed to post.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
[Attachment #5 (unknown)]
<html><head><meta http-equiv="Content-Type" content="text/html; \
charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; \
line-break: after-white-space;" class="">Hello,<div class=""><br class=""></div><div \
class="">it's possible to create no additional threads and return values via TBQueue \
(TMVar a). Then thread</div><div class="">that reads replies can block on getting the \
result from the first thread, while other workers are working.</div><div \
class="">Here is a basic example:</div><div class=""><br class=""></div><div \
class=""><a href="https://github.com/qnikst/haskell-fun/blob/cdaf070758fd9b61b37582f06f44d284c6c3b824/jobs/Main.hs" \
class="">https://github.com/qnikst/haskell-fun/blob/cdaf070758fd9b61b37582f06f44d284c6c3b824/jobs/Main.hs</a></div><div \
class=""><br class=""></div><div class="">But this very naive and I didn't even try \
to do anything about exceptions asynchronous or not.</div><div class=""><br \
class=""></div><div class="">--</div><div class="">Best wishes,</div><div \
class="">Alexander.<br class=""><div><br class=""><blockquote type="cite" \
class=""><div class="">On 9 Sep 2019, at 18:30, <a href="mailto:amindfv@gmail.com" \
class="">amindfv@gmail.com</a> wrote:</div><br class="Apple-interchange-newline"><div \
class=""><div class="">Hi Jeroen - thanks! I hadn't heard from anyone so over the \
weekend I sketched up an early version of a library for this purpose:<br class=""><br \
class=""><a href="https://hackage.haskell.org/package/orderly-workers" \
class="">https://hackage.haskell.org/package/orderly-workers</a><br class=""><br \
class="">A few decisions you and I made are the same (a thread each for input and \
output chans to avoid race conditions, MVars for finished work so worker threads \
aren't blocked waiting for their "turn" at the output). In other ways our code is \
different and I'm looking forward to digging into differences! (For example, I \
already see a place I should be forcing strictness instead of assuming it'll be \
forced in user code).<br class=""><br class="">For the use-case orderly-workers was \
designed for, it's got the task from ~6 mins to ~2 mins with 5 worker threads. I'm \
happy with this, as the producer and consumer processes are also doing substantial \
work.<br class=""><br class="">Open to any comments/criticism of the library.<br \
class=""><br class="">Thanks!<br class="">Tom<br class=""><br class=""><blockquote \
type="cite" class="">El 9 sept 2019, a las 04:32, Jeroen Bransen \
<jeroen@chordify.net> escribió:<br class=""><br class="">Hello Tom,<br \
class=""><br class="">I am not aware of any specific algorithm or existing package \
for this<br class="">purpose, the best that I can come up with is [1]. It works by \
using two<br class="">auxillary queues and two main worker threads that have a \
special task.<br class="">One of them is the only thread reading from the input \
queue, thereby<br class="">avoiding race conditions in the "take an item and store \
where in the<br class="">output this element should come"-stage. It creates an MVar \
for each<br class="">item, puts that in the job queue together with the input, and \
puts that<br class="">in the other auxillary queue as well. The other main worker \
thread is<br class="">reading the MVars in order and is the only thread writing to \
the output<br class="">queue, thereby again avoiding race conditions. Now the real \
worker<br class="">threads only need to read from the auxillary queue where they get \
the A<br class="">and and MVar where they write the B.<br class=""><br class="">I am \
not sure whether or not this satisfies your "cleanness" desire, but<br class="">I \
believe it has two nice properties which are not so easy to get:<br class="">1. The \
worker threads only do the real work, and are not blocked by<br class="">other \
workers still working on earlier items<br class="">2. It is not hard to prove that \
this approach does not lead to deadlocks<br class=""><br class="">Regards,<br \
class="">Jeroen<br class=""><br class=""><br class="">[1] \
https://gist.github.com/jbransen/be81d70cfe2a85fe7d2dfbafc00b561c<br class=""><br \
class="">Op 6-9-2019 om 21:00 schreef amindfv@gmail.com:<br class=""><blockquote \
type="cite" class="">I've implemented a solution for this problem, but it seems a bit \
less clean than it could be, which leaves me wondering if there's a data structure or \
algorithm specifically for this purpose:<br class=""><br class="">We've got multiple \
concurrent thereads reading items from a (TBQueue A), calling f :: A -> B, and \
writing to a (TBQueue B). We must, though, write items into the (TBQueue B) in the \
order that the corresponding As were read (the order they were put in the (TBQueue \
A)).<br class=""><br class="">Are there existing libraries which solve this or a \
similar problem? Ideally with niceties like configuring whether the pending \
out-of-order writes block the worker threads, and a way of signalling there's no more \
work to perform.<br class=""><br class="">Thanks!<br class="">Tom<br class=""><br \
class=""><br class=""><br class="">_______________________________________________<br \
class="">Haskell-Cafe mailing list<br class="">To (un)subscribe, modify options or \
view archives go to:<br \
class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe<br \
class="">Only members subscribed via the mailman list are allowed to post.<br \
class=""></blockquote><br class="">_______________________________________________<br \
class="">Haskell-Cafe mailing list<br class="">To (un)subscribe, modify options or \
view archives go to:<br \
class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe<br \
class="">Only members subscribed via the mailman list are allowed to post.<br \
class=""></blockquote>_______________________________________________<br \
class="">Haskell-Cafe mailing list<br class="">To (un)subscribe, modify options or \
view archives go to:<br \
class="">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe<br \
class="">Only members subscribed via the mailman list are allowed to \
post.</div></div></blockquote></div><br class=""></div></body></html>
[Attachment #6 (text/plain)]
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic