Concurrent reads, ordered writes?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Concurrent reads, ordered writes?

amindfv
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.
Reply | Threaded
Open this post in threaded view
|

Re: Concurrent reads, ordered writes?

Jeroen Bransen-2
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 [hidden email]:

> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concurrent reads, ordered writes?

amindfv
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 <[hidden email]> 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 [hidden email]:
>> 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.
Reply | Threaded
Open this post in threaded view
|

Re: Concurrent reads, ordered writes?

Alexander Vershilov
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:


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, [hidden email] 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 <[hidden email]> 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 [hidden email]:
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.


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