News for hackers. Stuff that matters.
Re:Shift-to-Middle Array: A Faster Alternative to Std:Deque? by duped on Sunday March 23, 2025 @08:44PM (#43457005)
I've seen this trick used around, where it really shines is when you want to prepare/commit a range of the ring buffer when interfacing with something that wants a contiguous chunk as an arg, using the mmap hack lets you pass any pointer into the ring buffer without needing to split it to handle the wraparound case.

There are a few blog posts out there about it, eg https://lo.calho.st/posts/black-magic-buffer/. One data structure that works around the limitations is the bip buffer: https://www.codeproject.com/Articles/3479/The-Bip-Buffer-The.... In that article the author talks about the mmap trick.

Re:Shift-to-Middle Array: A Faster Alternative to Std:Deque? by pcwalton on Sunday March 23, 2025 @11:16PM (#43457564)
Oh, I see, it's actually on Wikipedia [1]. I figured I wasn't the first one to invent the idea :)

[1]: https://en.wikipedia.org/wiki/Circular_buffer#Optimization

Re:Shift-to-Middle Array: A Faster Alternative to Std:Deque? by scottlamb on Monday March 24, 2025 @10:27AM (#43461492)
I don't think the bip buffer solves a real problem. Let's say I'm using it as a read buffer.

> The upshot of all of this is that on average, the buffer always has the maximal amount of free space available to be used, while not requiring any data copying or reallocation to free up space at the end of the buffer. ... Another possibility which was brought up in the bulletin board (and the person who brought it up shall remain nameless, if just because they... erm... are nameless) was that of just splitting the calls across wraps. Well, this is one way of working around the wrapping problem, but it has the unfortunate side-effect that as your buffer fills, the amount of free space which you pass out to any calls always decreases to 1 byte at the minimum - even if you've got another 128kb of free space at the beginning of your buffer, at the end of it, you're still going to have to deal with ever shrinking block sizes.

So it maximizes the contiguous free bytes. I feel like the author just never knew about readv? Passing a couple iovecs completely solves this problem in a much better way.

What seems far more valuable for the used space to be contiguous, as parsing APIs often expect this. bip buffers don't offer that, right?

Now let's say I'm using it as a write buffer. I've never had the problem of needing it to be contiguous on either side. On the input side, I could imagine some application API that really wants to write into a contiguous buffer, but it hasn't been my experience. On the output side, there's writev.