5 ms·

The Lynx Queue

35 points by jsnell 10y ago

jasonkostempski 10y ago
Link broken, cache broken. I thought maybe it was some kind of page only usable in Lynx... Nothin'. And of course now my Bash on Ubuntu on Windows is hung up. Are we joining the Lynx Queue when going to the page?
gpvos 10y ago
Google cache: http://webcache.googleusercontent.com/search?q=cache:ekFSEe6ogcAJ:www-dyn.cl.cam.ac.uk/~tmj32/wordpress/the-lynx-queue/+&cd=1&hl=nl&ct=clnk&gl=nl http://webcache.googleusercontent.com/search?q=cache:ekFSEe6...
- runeks 10y ago
  Remember to use the text-only version, or it will hang fetching other resources: http://webcache.googleusercontent.com/search?q=cache:ekFSEe6ogcAJ:www-dyn.cl.cam.ac.uk/~tmj32/wordpress/the-lynx-queue/&num=1&hl=nl&gl=nl&prmd=ivn&strip=1&vwsrc=0 http://webcache.googleusercontent.com/search?q=cache:ekFSEe6...
  - gpvos 10y ago
    Ah, sorry. My content blocker does that for me.
pkhuong 10y ago
Why do the authors report performance at O0 and O1? AFAICT, the experiments are all single socket. There's an important difference in coherency overhead for single VS multiple sockets; same for futzing with page protection. It also looks like they only tested a single producer/consumer pair. I expect page protection tricks don't scale as nicely when you have 20+ pairs on two sockets: contention on the page table and IPI storms. The mprotect trick also seems to depend on using small (4K) pages, unless you're OK with fairly stale data; probably not ideal for overall app performance. Also while they indirectly mention the batching trick of the disruptor (keep a reader-local copy of the write index and vice versa), it's not tested… and also not tested with a forced lag between the reader and the writer. If you want to avoid the ping pong, you can let the reader keep a copy of the writer's write pointer (and update the copy when the reader catches up), and artificially make the reader lag behind the writer. That lag gives much simpler code on the hotpath than the MCQueue they mention, which would be the closest equivalent to a laggy disruptor (keeping in mind that the disruptor pattern tends to be used in low latency settings, so that configuration is unlikely to be benchmarked, except indirectly, with cacheline-sized queue items). It's interesting work, but as is too often the case, the benchmarks give me no actionable information.
- Jweb_Guru 10y ago
  I think the single socket assumption is justified because they are talking about pairing each executing core with a checker core partner, right? So I don't think the paper is misleading for that use case. (I do agree that they aren't really fairly representing prior work in this area, though, and that nobody optimizing for high performance on commodity hardware is likely to be using 4kb pages).
eloff 10y ago
It's an interesting technique that I haven't seen before in the context of a queue. It's not without drawbacks, relying on handling sigsegv is a pain to make portable (libsigsegv helps!) HotSpot handles sigsegv, but I think it's possible to install your own handler as well by setting it before loading the JVM. When the JVM loads it will chain pre-existing signal handlers behind its own, and they'll be invoked if the signal doesn't pertain to HotSpot. LD_PRELOAD can be used to accomplish that. My information may only apply to an older version of HotSpot though, I don't know if that's still the case. The other thing is relying on the TLB here becomes trickier with huge pages. It seems to me that the section and queue boundary trap pages are set just once at queue init and then never changed - so one could do the same with 2mb huge pages, without wasting memory, if the sections are sufficiently large. The problem is that requires the producer and consumer to be at least 2mb of queue apart, which is probably too much delay for many applications where latency is important. But I really don't see the need for huge pages here. A queue where both producer and consumer are repeatedly touching the same page seems like the ideal use case for the TLB anyway. Not all applications can tolerate a sectioned queue though, for example what happens when the producer writes less than a full section of items to the queue and then pauses for a long time? The consumer won't be able to access that data until the producer finishes the section.
- stcredzero 10y ago
  relying on handling sigsegv is a pain to make portable Is there any effect due to virtualization?
webaholic 10y ago
The article is quite simplified I presume to make the reader understand the technique. There are many more details in the paper. I like that the simpler version is available, kind of like the simple version of an article in wikipedia to quickly skim through before diving deep.

35 points by jsnell 10y ago

Link broken, cache broken. I thought maybe it was some kind of page only usable in Lynx... Nothin'. And of course now my Bash on Ubuntu on Windows is hung up. Are we joining the Lynx Queue when going to the page?

gpvos 10y ago

Google cache: http://webcache.googleusercontent.com/search?q=cache:ekFSEe6ogcAJ:www-dyn.cl.cam.ac.uk/~tmj32/wordpress/the-lynx-queue/+&cd=1&hl=nl&ct=clnk&gl=nl http://webcache.googleusercontent.com/search?q=cache:ekFSEe6...

runeks 10y ago
Remember to use the text-only version, or it will hang fetching other resources: http://webcache.googleusercontent.com/search?q=cache:ekFSEe6ogcAJ:www-dyn.cl.cam.ac.uk/~tmj32/wordpress/the-lynx-queue/&num=1&hl=nl&gl=nl&prmd=ivn&strip=1&vwsrc=0 http://webcache.googleusercontent.com/search?q=cache:ekFSEe6...
- gpvos 10y ago
  Ah, sorry. My content blocker does that for me.

pkhuong 10y ago

Why do the authors report performance at O0 and O1? AFAICT, the experiments are all single socket. There's an important difference in coherency overhead for single VS multiple sockets; same for futzing with page protection. It also looks like they only tested a single producer/consumer pair. I expect page protection tricks don't scale as nicely when you have 20+ pairs on two sockets: contention on the page table and IPI storms. The mprotect trick also seems to depend on using small (4K) pages, unless you're OK with fairly stale data; probably not ideal for overall app performance. Also while they indirectly mention the batching trick of the disruptor (keep a reader-local copy of the write index and vice versa), it's not tested… and also not tested with a forced lag between the reader and the writer. If you want to avoid the ping pong, you can let the reader keep a copy of the writer's write pointer (and update the copy when the reader catches up), and artificially make the reader lag behind the writer. That lag gives much simpler code on the hotpath than the MCQueue they mention, which would be the closest equivalent to a laggy disruptor (keeping in mind that the disruptor pattern tends to be used in low latency settings, so that configuration is unlikely to be benchmarked, except indirectly, with cacheline-sized queue items). It's interesting work, but as is too often the case, the benchmarks give me no actionable information.

Jweb_Guru 10y ago
I think the single socket assumption is justified because they are talking about pairing each executing core with a checker core partner, right? So I don't think the paper is misleading for that use case. (I do agree that they aren't really fairly representing prior work in this area, though, and that nobody optimizing for high performance on commodity hardware is likely to be using 4kb pages).

eloff 10y ago

It's an interesting technique that I haven't seen before in the context of a queue. It's not without drawbacks, relying on handling sigsegv is a pain to make portable (libsigsegv helps!) HotSpot handles sigsegv, but I think it's possible to install your own handler as well by setting it before loading the JVM. When the JVM loads it will chain pre-existing signal handlers behind its own, and they'll be invoked if the signal doesn't pertain to HotSpot. LD_PRELOAD can be used to accomplish that. My information may only apply to an older version of HotSpot though, I don't know if that's still the case. The other thing is relying on the TLB here becomes trickier with huge pages. It seems to me that the section and queue boundary trap pages are set just once at queue init and then never changed - so one could do the same with 2mb huge pages, without wasting memory, if the sections are sufficiently large. The problem is that requires the producer and consumer to be at least 2mb of queue apart, which is probably too much delay for many applications where latency is important. But I really don't see the need for huge pages here. A queue where both producer and consumer are repeatedly touching the same page seems like the ideal use case for the TLB anyway. Not all applications can tolerate a sectioned queue though, for example what happens when the producer writes less than a full section of items to the queue and then pauses for a long time? The consumer won't be able to access that data until the producer finishes the section.

stcredzero 10y ago
relying on handling sigsegv is a pain to make portable Is there any effect due to virtualization?

webaholic 10y ago

The article is quite simplified I presume to make the reader understand the technique. There are many more details in the paper. I like that the simpler version is available, kind of like the simple version of an article in wikipedia to quickly skim through before diving deep.