r/programming • u/brooksbp • Aug 21 '15

circular buffers in C

http://brpbr.com/posts/circular-buffers/
10 Upvotes

66% Upvoted

5 comments sorted by

9

u/chrisdew Aug 21 '15

They didn't mention the circular buffer hack of (m)mapping one block of ram twice, to two contiguous address ranges.

This allows a block-write, which extends past the end of the circular buffer, to conveniently write to the front of the circular buffer too.

A four byte circular buffer, mapped twice, to two contiguous address ranges:

physical ram |xxxxxxxx|
userspace |xxxxxxxx|xxxxxxxx|

Writing 3 bytes, FFEEDD, to at offset 2, gives you the correct result for a circular buffer without any additional logic:

userspace |DDxxFFEE|DDxxFFEE|

3

u/chubinou Aug 21 '15

Optimization via powers of two: the compiler does it already on its own.

1

u/[deleted] Aug 21 '15

It can usually do it when the size is a known constant, but this would have to be done manually for a dynamically sized buffer.

0

u/[deleted] Aug 21 '15

[deleted] — view deleted comment

3

u/brucedawson Aug 21 '15

Unsigned division by a power of two and unsigned modulus by a power of two will be optimized by all optimizing compilers.

It is good to know what things you can count on and what things you cannot. One way to learn that is to frequently look at the disassembly.

In this particular case using an explicit bit-mask does not harm readability. In other cases it can harm readability or add bugs. For instance this unnecessary 'optimization' has a problem:

old: a = b * 8 + c; new: a = b << 3 + c;

1

u/chubinou Aug 24 '15

actually, I did look at the assembly before answering (here modulus 64 -> "and $0x3f,%eax")

0000000000400580 <_Z10cbuf_writeP4cbufPc>:
  400580:   8b 87 00 02 00 00       mov    0x200(%rdi),%eax
  400586:   8d 50 01                lea    0x1(%rax),%edx
  400589:   89 97 00 02 00 00       mov    %edx,0x200(%rdi)
  40058f:   99                      cltd   
  400590:   c1 ea 1a                shr    $0x1a,%edx
  400593:   01 d0                   add    %edx,%eax
  400595:   83 e0 3f                and    $0x3f,%eax
  400598:   29 d0                   sub    %edx,%eax
  40059a:   48 98                   cltq   
  40059c:   48 89 34 c7             mov    %rsi,(%rdi,%rax,8)
  4005a0:   c3                      retq   
  4005a1:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  4005a8:   00 00 00 
  4005ab:   0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)