News for hackers. Stuff that matters.
Re:Using black magic to make a fast circular buffer by vdupras on Saturday January 11, 2025 @08:50AM (#42665856)
> 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?

Re:Using black magic to make a fast circular buffer by tom_ on Saturday January 11, 2025 @10:30AM (#42666490)
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-buff... - see also the comments.

Re:Using black magic to make a fast circular buffer by vdupras on Saturday January 11, 2025 @11:39AM (#42666990)
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.
Re:Using black magic to make a fast circular buffer by tom_ on Saturday January 11, 2025 @04:39PM (#42669118)
I updated the author's benchmark: 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
Re:Using black magic to make a fast circular buffer by coldpepper on Saturday January 11, 2025 @10:10AM (#42666366)
Exactly. I don't know how could the blog post author have missed this.
Re:Using black magic to make a fast circular buffer by lq0000 on Saturday January 11, 2025 @11:39AM (#42666991)
Author here. I was 22 when I wrote this nearly 8 years ago. I just thought it was neat, give me a break. Thanks.
Re:Using black magic to make a fast circular buffer by superjan on Saturday January 11, 2025 @12:57PM (#42667622)
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.
Re:Using black magic to make a fast circular buffer by ahartmetz on Saturday January 11, 2025 @08:41PM (#42670486)
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).