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