[Haskell-cafe] Concurrent reads, ordered writes?

[Jeroen Bransen]

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