Yep, virtual memory aliasing comes in handy when you’re working with data structures that can have page-level granularity. One of my favorite tricks is to create a ‘magic ring buffer’ by mapping two contiguous virtual pages to the same physical page, so that the wraparound is handled transparently by the MMU at no extra cost.
No. Suppose I have a ring buffer, and the dashes represent the first page, and the tildes represent the second page (which just aliases the first page), and each dash/tilde represents a single byte:
p = memory address of the beginning of the first page
o = the head index
s = the size
C = capacity = size of page
Now suppose I wish to append 10 bytes. I would simply do:
memcpy(p + (o + s) % C, input_data, 10)
s += 10
Or, to remove 15 bytes from the beginning, I would do:
o = (o + 15) % C
s -= 15
Because any given 'slice' of the ring buffer's space can be represented as a contiguous range of memory (thanks to the second page), I can use the already optimized memcpy routine for adding and removing data at the beginning or end of the buffer. But I still need to make sure that the head index is always updated modulo the capacity, or it will increment unboundedly, as you say.
As you can tell in the above example, I'm not adding/removing individual bytes. Magic ring buffers only make sense when you frequently need to add or remove several elements from the ends of the buffer. It's particularly well suited for when you have a stream of data and need to operate on it in chunks.
4 comments
[ 3.2 ms ] story [ 18.6 ms ] threadStill it sounds super cool. Do you have an example implementation you can link to?
https://i.imgur.com/NfZTICG.png
p = memory address of the beginning of the first page
o = the head index
s = the size
C = capacity = size of page
Now suppose I wish to append 10 bytes. I would simply do:
memcpy(p + (o + s) % C, input_data, 10)
s += 10
Or, to remove 15 bytes from the beginning, I would do:
o = (o + 15) % C
s -= 15
Because any given 'slice' of the ring buffer's space can be represented as a contiguous range of memory (thanks to the second page), I can use the already optimized memcpy routine for adding and removing data at the beginning or end of the buffer. But I still need to make sure that the head index is always updated modulo the capacity, or it will increment unboundedly, as you say.
As you can tell in the above example, I'm not adding/removing individual bytes. Magic ring buffers only make sense when you frequently need to add or remove several elements from the ends of the buffer. It's particularly well suited for when you have a stream of data and need to operate on it in chunks.
Here's a GitHub repo that contains an implementation of the magic ring buffer: https://github.com/willemt/cbuffer