New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add a bounded version #1

Closed
jfischoff opened this Issue Jul 10, 2014 · 20 comments

Comments

Projects
None yet
5 participants
@jfischoff
Contributor

jfischoff commented Jul 10, 2014

I would be fine with a fuzzy bounded version, i.e. if the count was incremented non atomically from queue such that the queue could exceed the bounds some what, or think they are higher then they are.

For most of my use cases, I need a bounded queue never blocks on writes, and returns and error code on overflow.

Anyway, very impressed with the performance. Thanks!

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Jul 11, 2014

Owner

Thanks for the feedback and kind words. So in the case that the queue was (fuzzily) found to be too large, you'd like something like writeChan :: InChan a -> a -> IO Bool to return False?

And do you mind giving me an example of a use case? I can probably guess, but I'm trying to understand better how people use FIFO queues.

Owner

jberryman commented Jul 11, 2014

Thanks for the feedback and kind words. So in the case that the queue was (fuzzily) found to be too large, you'd like something like writeChan :: InChan a -> a -> IO Bool to return False?

And do you mind giving me an example of a use case? I can probably guess, but I'm trying to understand better how people use FIFO queues.

@jfischoff

This comment has been minimized.

Show comment
Hide comment
@jfischoff

jfischoff Jul 11, 2014

Contributor

writeChan :: InChan a -> IO Bool to return False?

Yes exactly.

I use queues for data that can tolerate some amount of data loss, but it must be able to enqueue immediately. Specifically for logging and different forms of analytics.

For instance, I just wrote an application that aggregates UDP traffic in an queue an sends it in a batch over tcp. That is a pretty typical case. Send and forget followed by the occasional batch send. So around 1-10 writers and 1-2 readers.

Contributor

jfischoff commented Jul 11, 2014

writeChan :: InChan a -> IO Bool to return False?

Yes exactly.

I use queues for data that can tolerate some amount of data loss, but it must be able to enqueue immediately. Specifically for logging and different forms of analytics.

For instance, I just wrote an application that aggregates UDP traffic in an queue an sends it in a batch over tcp. That is a pretty typical case. Send and forget followed by the occasional batch send. So around 1-10 writers and 1-2 readers.

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Jul 11, 2014

Owner

Oh interesting, so in the UDP example a writer that sees a False return value might decide it's time to do some reads to aggregate and send over TCP?

Would a function that always enqueues but returns back the fuzzy queue size work just as well for you? That would probably be faster for the general successful write case, but return slightly slower than a writeChanBounded that returned False.

Owner

jberryman commented Jul 11, 2014

Oh interesting, so in the UDP example a writer that sees a False return value might decide it's time to do some reads to aggregate and send over TCP?

Would a function that always enqueues but returns back the fuzzy queue size work just as well for you? That would probably be faster for the general successful write case, but return slightly slower than a writeChanBounded that returned False.

@jfischoff

This comment has been minimized.

Show comment
Hide comment
@jfischoff

jfischoff Jul 11, 2014

Contributor

On Fri, Jul 11, 2014 at 3:21 PM, Brandon Simmons notifications@github.com
wrote:

Oh interesting, so in the UDP example a writer that sees a False return
value might decide it's time to do some reads to aggregate and send over
TCP?

Naw, if the readers can't keep up it logs a failure. The data is not that
important.

Would a function that always enqueues but returns back the fuzzy queue
size work just as well for you? That would probably be faster for the
general successful write case, but return slightly slower than a
writeChanBounded that returned False.

Not really because I would need to implement the failure functionality on
top of it and would not gain much.

Reply to this email directly or view it on GitHub
#1 (comment).

Contributor

jfischoff commented Jul 11, 2014

On Fri, Jul 11, 2014 at 3:21 PM, Brandon Simmons notifications@github.com
wrote:

Oh interesting, so in the UDP example a writer that sees a False return
value might decide it's time to do some reads to aggregate and send over
TCP?

Naw, if the readers can't keep up it logs a failure. The data is not that
important.

Would a function that always enqueues but returns back the fuzzy queue
size work just as well for you? That would probably be faster for the
general successful write case, but return slightly slower than a
writeChanBounded that returned False.

Not really because I would need to implement the failure functionality on
top of it and would not gain much.

Reply to this email directly or view it on GitHub
#1 (comment).

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Jul 12, 2014

Owner

Would a function that always enqueues but returns back the fuzzy queue
size work just as well for you? That would probably be faster for the
general successful write case, but return slightly slower than a
writeChanBounded that returned False.

Not really because I would need to implement the failure functionality on
top of it and would not gain much.

Ah, okay I think I see. With the function I proposed your writers would keep seeing that the queue was too big, but the queue would still just continue to grow. And am I right that you don't care so much about bounding memory usage, but rather about bounding latency of your messages?

On the subject of memory it's interesting to remember we don't in general do any queue-related allocation on write; an object is in the heap already at that point, and an array has probably been pre-allocated.

Thanks for explaining.

Owner

jberryman commented Jul 12, 2014

Would a function that always enqueues but returns back the fuzzy queue
size work just as well for you? That would probably be faster for the
general successful write case, but return slightly slower than a
writeChanBounded that returned False.

Not really because I would need to implement the failure functionality on
top of it and would not gain much.

Ah, okay I think I see. With the function I proposed your writers would keep seeing that the queue was too big, but the queue would still just continue to grow. And am I right that you don't care so much about bounding memory usage, but rather about bounding latency of your messages?

On the subject of memory it's interesting to remember we don't in general do any queue-related allocation on write; an object is in the heap already at that point, and an array has probably been pre-allocated.

Thanks for explaining.

@gregorycollins

This comment has been minimized.

Show comment
Hide comment
@gregorycollins

gregorycollins Jul 16, 2014

For most of my use cases, I need a bounded queue never blocks on writes, and returns and error code on overflow.

And personally I would also want a bounded queue that blocks on write when the queue is full.

gregorycollins commented Jul 16, 2014

For most of my use cases, I need a bounded queue never blocks on writes, and returns and error code on overflow.

And personally I would also want a bounded queue that blocks on write when the queue is full.

@mwotton

This comment has been minimized.

Show comment
Hide comment
@mwotton

mwotton Jul 18, 2014

+1 to @gregorycollins - backpressure is the whole reason to use bounded queues for me.
By that, I mean that I would launch some number of threads to do a job that then push their result into a channel upstream, and some other set of threads handle the next stage. If I don't have some mechanism for blocking the first set of threads when the second is overwhelmed, they will end up doing more work than can be processed, and crowding out threads that could be doing useful work.

(If there had to be a hard maximum, I suppose 100 would be ok. Hell, at the moment I tend to use max length 1 channels, or as I call them, MVars :)

mwotton commented Jul 18, 2014

+1 to @gregorycollins - backpressure is the whole reason to use bounded queues for me.
By that, I mean that I would launch some number of threads to do a job that then push their result into a channel upstream, and some other set of threads handle the next stage. If I don't have some mechanism for blocking the first set of threads when the second is overwhelmed, they will end up doing more work than can be processed, and crowding out threads that could be doing useful work.

(If there had to be a hard maximum, I suppose 100 would be ok. Hell, at the moment I tend to use max length 1 channels, or as I call them, MVars :)

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Jul 20, 2014

Owner

@gregorycollins @mwotton Thanks for the feedback. One design I sketched out for a blocking bounded queue would involve unblocking writers in batches, where at a high level the actual "size" of the queue at any given time can vary between bounds and bounds*2. Put another way blocked writers may be unblocked up to bounds reads too early.

This would let us eliminate a lot of overhead, and hopefully result in sort of healthier queue stride behavior: apparently (and this makes intuitive sense to me) a queue with fine-grained bounding and unblocking is likely to be either almost always empty or almost always at capacity (in which case it limps along with unblocking overheads at each read).

Let me know if that sounds like it would be a solution for y'all.

Owner

jberryman commented Jul 20, 2014

@gregorycollins @mwotton Thanks for the feedback. One design I sketched out for a blocking bounded queue would involve unblocking writers in batches, where at a high level the actual "size" of the queue at any given time can vary between bounds and bounds*2. Put another way blocked writers may be unblocked up to bounds reads too early.

This would let us eliminate a lot of overhead, and hopefully result in sort of healthier queue stride behavior: apparently (and this makes intuitive sense to me) a queue with fine-grained bounding and unblocking is likely to be either almost always empty or almost always at capacity (in which case it limps along with unblocking overheads at each read).

Let me know if that sounds like it would be a solution for y'all.

@mwotton

This comment has been minimized.

Show comment
Hide comment
@mwotton

mwotton Jul 21, 2014

sounds good to me.

On Mon, Jul 21, 2014 at 6:22 AM, Brandon Simmons notifications@github.com
wrote:

@gregorycollins https://github.com/gregorycollins @mwotton
https://github.com/mwotton Thanks for the feedback. One design I
sketched out for a blocking bounded queue would involve unblocking writers
in batches, where at a high level the actual "size" of the queue at any
given time can vary between bounds and bounds*2. Put another way blocked
writers may be unblocked up to bounds reads too early.

This would let us eliminate a lot of overhead, and hopefully result in
sort of healthier queue stride behavior: apparently (and this makes
intuitive sense to me) a queue with fine-grained bounding and unblocking is
likely to either almost always empty or almost always at capacity (in which
case it limps along with unblocking overheads at each read).

Let me know if that sounds like it would be a solution for y'all.


Reply to this email directly or view it on GitHub
#1 (comment).

A UNIX signature isn't a return address, it's the ASCII equivalent of a
black velvet clown painting. It's a rectangle of carets surrounding a
quote from a literary giant of weeniedom like Heinlein or Dr. Who.
-- Chris Maeda

mwotton commented Jul 21, 2014

sounds good to me.

On Mon, Jul 21, 2014 at 6:22 AM, Brandon Simmons notifications@github.com
wrote:

@gregorycollins https://github.com/gregorycollins @mwotton
https://github.com/mwotton Thanks for the feedback. One design I
sketched out for a blocking bounded queue would involve unblocking writers
in batches, where at a high level the actual "size" of the queue at any
given time can vary between bounds and bounds*2. Put another way blocked
writers may be unblocked up to bounds reads too early.

This would let us eliminate a lot of overhead, and hopefully result in
sort of healthier queue stride behavior: apparently (and this makes
intuitive sense to me) a queue with fine-grained bounding and unblocking is
likely to either almost always empty or almost always at capacity (in which
case it limps along with unblocking overheads at each read).

Let me know if that sounds like it would be a solution for y'all.


Reply to this email directly or view it on GitHub
#1 (comment).

A UNIX signature isn't a return address, it's the ASCII equivalent of a
black velvet clown painting. It's a rectangle of carets surrounding a
quote from a literary giant of weeniedom like Heinlein or Dr. Who.
-- Chris Maeda

@gregorycollins

This comment has been minimized.

Show comment
Hide comment
@gregorycollins

gregorycollins Jul 21, 2014

Yes, I don't think you care about getting blocking writes when the queue has exactly N elements, just that you know that your total memory consumption is bounded above by some N (and that producers cannot race too far ahead of consumers).

gregorycollins commented Jul 21, 2014

Yes, I don't think you care about getting blocking writes when the queue has exactly N elements, just that you know that your total memory consumption is bounded above by some N (and that producers cannot race too far ahead of consumers).

@reiddraper

This comment has been minimized.

Show comment
Hide comment
@reiddraper

reiddraper Jul 26, 2014

I find the TBQueue semantics and API quite nice.

reiddraper commented Jul 26, 2014

I find the TBQueue semantics and API quite nice.

@gregorycollins

This comment has been minimized.

Show comment
Hide comment
@gregorycollins

gregorycollins Jul 28, 2014

@reiddraper yes those semantics are nice but as @jberryman points out, with those semantics the queue is likely to always be either completely empty or totally full, and in the degenerate case (which is easy to achieve here) the queue will perform as badly under contention as Chan does.

Loosening the boundedness requirement, such that the queue will block on write when the buffer has e.g. between N and 2N elements, may allow you to use better lock-free techniques.

gregorycollins commented Jul 28, 2014

@reiddraper yes those semantics are nice but as @jberryman points out, with those semantics the queue is likely to always be either completely empty or totally full, and in the degenerate case (which is easy to achieve here) the queue will perform as badly under contention as Chan does.

Loosening the boundedness requirement, such that the queue will block on write when the buffer has e.g. between N and 2N elements, may allow you to use better lock-free techniques.

@reiddraper

This comment has been minimized.

Show comment
Hide comment
@reiddraper

reiddraper Jul 28, 2014

but as @jberryman points out, with those semantics the queue is likely to always be either completely empty or totally full

Maybe I misread, but he didn't seem definitive on that. @jberryman says:

apparently (and this makes intuitive sense to me) a queue with fine-grained bounding and unblocking is likely to be either almost always empty or almost always at capacity

I imagine that's quite implementation and workload dependent. That being said, I don't have much skin in this game: TBQueue works well enough for me. So I'm not able to offer much in terms of what guarantees make sense for me to give up in exchange for higher-performance, which is presumably the end-goal compared to an STM-based solution.

From an API point-of-view, the fuzzy-bounded idea seems reasonable, since my general use-case for bounding a channel/queue is just to limit memory consumption.

reiddraper commented Jul 28, 2014

but as @jberryman points out, with those semantics the queue is likely to always be either completely empty or totally full

Maybe I misread, but he didn't seem definitive on that. @jberryman says:

apparently (and this makes intuitive sense to me) a queue with fine-grained bounding and unblocking is likely to be either almost always empty or almost always at capacity

I imagine that's quite implementation and workload dependent. That being said, I don't have much skin in this game: TBQueue works well enough for me. So I'm not able to offer much in terms of what guarantees make sense for me to give up in exchange for higher-performance, which is presumably the end-goal compared to an STM-based solution.

From an API point-of-view, the fuzzy-bounded idea seems reasonable, since my general use-case for bounding a channel/queue is just to limit memory consumption.

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Jul 28, 2014

Owner

Thanks for the feedback. I agree the TBQueue semantics are ideal.
Unfortunately it does have some of the worse performance under contention.
I even had to remove it from some benchmarks because I was seeing lovelock!
That's not necessarily because of the blocking semantics of writes, it's
just that I'd like to make this version comparable in performance to the
other Unagi variants, and I think by relaxing the bounds requirement in this way I
can get something much faster. So I'm glad you think that could
work for you too!

Also FYI I'm actively working on a blocking bounded version, but am on
vacation for a couple weeks. But hopefully that should land in 2-3 weeks.
Thanks all
On Jul 28, 2014 10:43 AM, "Reid Draper" notifications@github.com wrote:

but as @jberryman https://github.com/jberryman points out, with those
semantics the queue is likely to always be either completely empty or
totally full

Maybe I misread, but he didn't seem definitive on that. @jberryman
https://github.com/jberryman says:

apparently (and this makes intuitive sense to me) a queue with
fine-grained bounding and unblocking is likely to be either almost always
empty or almost always at capacity

I imagine that's quite implementation and workload dependent. That being
said, I don't have much skin in this game: TBQueue works well enough for
me. So I'm not able to offer much in terms of what guarantees make sense
for me to give up in exchange for higher-performance, which is presumably
the end-goal compared to an STM-based solution.

From an API point-of-view, the fuzzy-bounded idea seems reasonable, since
my general use-case for bounding a channel/queue is just to limit memory
consumption.


Reply to this email directly or view it on GitHub
#1 (comment).

Owner

jberryman commented Jul 28, 2014

Thanks for the feedback. I agree the TBQueue semantics are ideal.
Unfortunately it does have some of the worse performance under contention.
I even had to remove it from some benchmarks because I was seeing lovelock!
That's not necessarily because of the blocking semantics of writes, it's
just that I'd like to make this version comparable in performance to the
other Unagi variants, and I think by relaxing the bounds requirement in this way I
can get something much faster. So I'm glad you think that could
work for you too!

Also FYI I'm actively working on a blocking bounded version, but am on
vacation for a couple weeks. But hopefully that should land in 2-3 weeks.
Thanks all
On Jul 28, 2014 10:43 AM, "Reid Draper" notifications@github.com wrote:

but as @jberryman https://github.com/jberryman points out, with those
semantics the queue is likely to always be either completely empty or
totally full

Maybe I misread, but he didn't seem definitive on that. @jberryman
https://github.com/jberryman says:

apparently (and this makes intuitive sense to me) a queue with
fine-grained bounding and unblocking is likely to be either almost always
empty or almost always at capacity

I imagine that's quite implementation and workload dependent. That being
said, I don't have much skin in this game: TBQueue works well enough for
me. So I'm not able to offer much in terms of what guarantees make sense
for me to give up in exchange for higher-performance, which is presumably
the end-goal compared to an STM-based solution.

From an API point-of-view, the fuzzy-bounded idea seems reasonable, since
my general use-case for bounding a channel/queue is just to limit memory
consumption.


Reply to this email directly or view it on GitHub
#1 (comment).

@jfischoff

This comment has been minimized.

Show comment
Hide comment
@jfischoff

jfischoff Aug 15, 2014

Contributor

I was seeing livelock

Are you referring to this code?

replicateM_ n1000 $ atomically $ writeTBQueue c ()

I've seen that code, not livelock, but lead to poor scheduling (runs 10000 times the reader runs once). Add a yield or compile with -fno-omit-yields and see if that fixes it (although it will bias the benchmarks).

Contributor

jfischoff commented Aug 15, 2014

I was seeing livelock

Are you referring to this code?

replicateM_ n1000 $ atomically $ writeTBQueue c ()

I've seen that code, not livelock, but lead to poor scheduling (runs 10000 times the reader runs once). Add a yield or compile with -fno-omit-yields and see if that fixes it (although it will bias the benchmarks).

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Aug 16, 2014

Owner

@jfischoff Thanks. Hm, no that wasn't what I was seeing, but I'll definitely keep that flag in mind for future benchmarks. It seems unavoidable that with a lot of contention all these composed STM operations would get stuck endlessly retrying, but that's just my guess as to what I saw, and obviously you might never see this in real code (unless you had lots of cores and lots of threads).

Owner

jberryman commented Aug 16, 2014

@jfischoff Thanks. Hm, no that wasn't what I was seeing, but I'll definitely keep that flag in mind for future benchmarks. It seems unavoidable that with a lot of contention all these composed STM operations would get stuck endlessly retrying, but that's just my guess as to what I saw, and obviously you might never see this in real code (unless you had lots of cores and lots of threads).

@mwotton

This comment has been minimized.

Show comment
Hide comment
@mwotton

mwotton Sep 22, 2014

@jberryman any progress on this?

mwotton commented Sep 22, 2014

@jberryman any progress on this?

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Sep 22, 2014

Owner

Yeah, I'm just working on finishing some tests and benchmarks and hope to
upload a bounded variant within a week or so, but the main work is done.
Thanks for your patience; I've been traveling and running around a lot.
On Sep 21, 2014 8:43 PM, "Mark Wotton" notifications@github.com wrote:

@jberryman https://github.com/jberryman any progress on this?


Reply to this email directly or view it on GitHub
#1 (comment).

Owner

jberryman commented Sep 22, 2014

Yeah, I'm just working on finishing some tests and benchmarks and hope to
upload a bounded variant within a week or so, but the main work is done.
Thanks for your patience; I've been traveling and running around a lot.
On Sep 21, 2014 8:43 PM, "Mark Wotton" notifications@github.com wrote:

@jberryman https://github.com/jberryman any progress on this?


Reply to this email directly or view it on GitHub
#1 (comment).

@mwotton

This comment has been minimized.

Show comment
Hide comment
@mwotton

mwotton Sep 22, 2014

no worries, just itching to dump a whole bunch of awful MVar-driven stuff :)

mwotton commented Sep 22, 2014

no worries, just itching to dump a whole bunch of awful MVar-driven stuff :)

@jberryman jberryman closed this in 1e3a650 Oct 7, 2014

@jberryman

This comment has been minimized.

Show comment
Hide comment
@jberryman

jberryman Oct 7, 2014

Owner

Thanks for the feedback and patience, all. @jfischoff I hope Control.Concurrent.Chan.Unagi.Bounded.tryWriteChan works for you; feel free to open a new request if not.

Owner

jberryman commented Oct 7, 2014

Thanks for the feedback and patience, all. @jfischoff I hope Control.Concurrent.Chan.Unagi.Bounded.tryWriteChan works for you; feel free to open a new request if not.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment