I've been writing ring buffers wrong all these years

Re:I've been writing ring buffers wrong all these years by caf on Wednesday December 14, 2016 @03:44PM (#13179491)

Modulo by a constant doesn't require a division, you can instead use multiplications, shifts, adds and subtracts. This transform is typical for compilers. For example, this is what gcc targetting x86_64 does to perform % 17 on the unsigned value in %edi:

  movl	$-252645135, %edx
  movl	%edi, %eax
  mull	%edx
  movl	%edx, %eax
  shrl	$4, %eax
  movl	%eax, %edx
  sall	$4, %edx
  addl	%edx, %eax
  subl	%eax, %edi

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by userbinator on Wednesday December 14, 2016 @09:13PM (#13181772)

It doesn't require division, but how is that long sequence of instructions going to beat an AND?

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by lorenzhs on Wednesday December 14, 2016 @05:36PM (#13180329)

That only works for compile time constants, though. With a power of two sized buffer you can just store the mask and decide how large you want your buffer to be at runtime.

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by _ihaque on Wednesday December 14, 2016 @07:32PM (#13181173)

libdivide (http://libdivide.com) implements similar logic at runtime

[ Parent | on HN ]

Re:I've been writing ring buffers wrong all these years by nullc on Thursday December 15, 2016 @04:42AM (#13183485)

You can also compute the optimization at runtime, same as the compiler does. Libtheora contains code for this, used for quantizing video data.

[ Parent | on HN ]