priority qeues with mechanical sympathy

[ymo]

Hello there.

Anyone has seen this https://newsoffice.mit.edu/2015/new-priority-queues-data-structure-0130

paper here http://www.mit.edu/~jerryzli/SprayList-CR.pdf

Wonder if aeron would benefit from this.

[ymo]

Seems like code is here as well  https://github.com/jkopinsky/SprayList

[Dan Eloff]

That's an interesting idea to relax the constraint from picking the highest priority item to picking one of the highest priority items at random. Implemented in a way that plays to the skip lists strengths. With multiple threads on a contended priority queue, it's not likely you would be able to tell the difference anyway since the order threads take work items and complete them is indeterminate.

The reason it should work well is the same reason fine-grained locking works. If you spread out contended accesses then you reduce contention, and the system as a whole spends less time thrashing and more time getting useful work done.

I don't see a connection to Aeron though, why would an event replication service need a priority queue?

Thanks for the link,

Dan

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[ymo]

I have been following jctools and the aeron lockfree queues which are both based on the fastflow algorithm unless something has changed lately. Basically under high contention (read more than 80 threads) accessing the head of the queue becomes very contented. The idea behind the spray list is to access that head in a non contended fashion.

Moreover, As far as i know there is no way to introduce "priority" in aeron. Since the data is all going out the same interface it would be interesting to "tag" certain packets as higher than others and they would get delivered before any other packets.

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-sympathy+unsub...@googlegroups.com.

[Richard Warburton]

Hi,

I have been following jctools and the aeron lockfree queues which are both based on the fastflow algorithm unless something has changed lately. Basically under high contention (read more than 80 threads) accessing the head of the queue becomes very contented. The idea behind the spray list is to access that head in a non contended fashion.

I'm going to assume you mean the Aeron log buffers here. The log buffers are split up into individual sessions identified by the session id of the publisher, so the contention is really between multiple threads trying to write to the same publication. There might be more than 1 thread, but I can't think of a use case where you want to be writing to the same publication with more than 80 threads.

regards,

  Richard Warburton

  http://insightfullogic.com

  @RichardWarburto

[Todd Montgomery]

Agree with Richard here. The use case for most systems is to split the load between that many threads by using multiple (and in the case of Aeron) totally non-contending streams and/or publications.

However, I do think that the SprayList is quite intriguing.... but it is very niche from a use case perspective. Much cleaner, IMO, to use the single writer principle and split the work load "higher up" when possible. But the technique(s) in the SprayList are very interesting. Oddly, when I scanned the paper originally, I thought it had more possibilities with memory allocators...

-- Todd

--

You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.

To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.