4 ms·

> The fact that a modulo operation is necessary to index into the array makes this function hard (if not impossible) to vectorize, and thus unnecessarily slow.

> The fact that a modulo operation is necessary to index into the array makes this function hard (if not impossible) to vectorize, and thus unnecessarily slow. It seems to me that this benchmark conflates two optimizations that could be tackled separately. For example, if you took the naive approach and just use a power-of-2 buffer size so that modulo could be replaced with "&", you'd get a pretty good speedup without resorting to mmap, no?

coldpepper 2y ago
Exactly. I don't know how could the blog post author have missed this.
- lq0000 2y ago
  Author here. I was 22 when I wrote this nearly 8 years ago. I just thought it was neat, give me a break. Thanks.
  - superjan 2y ago
    Don’t worry. It _is_ a neat trick, and it was nice to post complete instructions and benchmarks. And it wasn’t you who put it to the HN frontpage.
tom_ 2y ago
But it's the same thing: extra per byte overhead. You can polish this turd, or (better, in my view) give up entirely and do what the subsequent snippet does and copy the data in 1 or 2 blocks. Whatever you do, there's another advantage to the mmap trick: if the items are variable sizes, they never need to be split. (Split items are often a pain to deal with.) The circularity becomes the buffer's problem alone, and consumers don't have to handle it. Another article about this here: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff... - see also the comments.
- vdupras 2y ago
  Certainly, but by conflating the two, it makes the mmap trick appear better than it is in reality. There are good chances that a "&" change brings a very significant speedup.
  - tom_ 2y ago
    I updated the author's benchmark: https://gcc.godbolt.org/z/bxEzerjc8 https://gcc.godbolt.org/z/bxEzerjc8 While updating it, I noticed a couple of things: 1. the Makefile doesn't specify -O, which seems to imply -O0, unreasonably flattering the 1-memcpy case because there's only 1 call to a generic memcpy rather than 2. With -O3 the memcpys get inlined 2. make the message size more annoying. The queue size was a multiple of the message size, so the 2-memcpy case was never exercised - and -O3 could see this (Change 2 actually slightly cancels out change 1, and now the 2-memcpy case is terrible again...) Who even knows what sort of system the Compiler Explorer executor runs the programs on, but this is what I got from running it, and the relative speeds might be representative: %: 0.033716 microseconds per write &: 0.031772 microseconds per write slow: 0.009715 microseconds per write fast: 0.001035 microseconds per write
ahartmetz 2y ago
Actually, even "if (pos >= bufSize) { pos -= bufSize; }" is much faster than pos = pos % bufSize. Division (and modulo) are like the only basic math operations that a modern wide ALU doesn't easily do three to four of per cycle (they are much more expensive), OTOH easily predicted branches are fairly cheap (or even compiled into conditional moves here).

coldpepper 2y ago

Exactly. I don't know how could the blog post author have missed this.

lq0000 2y ago
Author here. I was 22 when I wrote this nearly 8 years ago. I just thought it was neat, give me a break. Thanks.
- superjan 2y ago
  Don’t worry. It _is_ a neat trick, and it was nice to post complete instructions and benchmarks. And it wasn’t you who put it to the HN frontpage.

tom_ 2y ago

But it's the same thing: extra per byte overhead. You can polish this turd, or (better, in my view) give up entirely and do what the subsequent snippet does and copy the data in 1 or 2 blocks. Whatever you do, there's another advantage to the mmap trick: if the items are variable sizes, they never need to be split. (Split items are often a pain to deal with.) The circularity becomes the buffer's problem alone, and consumers don't have to handle it. Another article about this here: https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buffer/ https://fgiesen.wordpress.com/2012/07/21/the-magic-ring-buff... - see also the comments.

vdupras 2y ago
Certainly, but by conflating the two, it makes the mmap trick appear better than it is in reality. There are good chances that a "&" change brings a very significant speedup.
- tom_ 2y ago
  I updated the author's benchmark: https://gcc.godbolt.org/z/bxEzerjc8 https://gcc.godbolt.org/z/bxEzerjc8 While updating it, I noticed a couple of things: 1. the Makefile doesn't specify -O, which seems to imply -O0, unreasonably flattering the 1-memcpy case because there's only 1 call to a generic memcpy rather than 2. With -O3 the memcpys get inlined 2. make the message size more annoying. The queue size was a multiple of the message size, so the 2-memcpy case was never exercised - and -O3 could see this (Change 2 actually slightly cancels out change 1, and now the 2-memcpy case is terrible again...) Who even knows what sort of system the Compiler Explorer executor runs the programs on, but this is what I got from running it, and the relative speeds might be representative: %: 0.033716 microseconds per write &: 0.031772 microseconds per write slow: 0.009715 microseconds per write fast: 0.001035 microseconds per write

ahartmetz 2y ago

Actually, even "if (pos >= bufSize) { pos -= bufSize; }" is much faster than pos = pos % bufSize. Division (and modulo) are like the only basic math operations that a modern wide ALU doesn't easily do three to four of per cycle (they are much more expensive), OTOH easily predicted branches are fairly cheap (or even compiled into conditional moves here).