Re:I've been writing ring buffers wrong all these years
by kitsuac on Wednesday December 14, 2016 @12:50PM
(#13178003)
You are still introducing a conditional by detecting the need to subtract, and iterating backward through memory is horrific for cache performance. If you need a specific, non power-of-2 sized buffer, then of course you make that design decision and pay the performance penalty. But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.
Re:I've been writing ring buffers wrong all these years
by tbirdz on Wednesday December 14, 2016 @01:56PM
(#13178636)
>iterating backward through memory is horrific for cache performance
This isn't true for Intel chips since Netburst Pentium 4. The hardware prefetchers can handle predicting iterating through an array forwards, backwards, and even strided accesses [0]. The arrays takes up the same number of cache lines in both cases, so going forwards or backwards are still going to have the same number of cache misses.
0: https://software.intel.com/en-us/articles/optimizing-applica...
Re:I've been writing ring buffers wrong all these years
by SamReidHughes on Wednesday December 14, 2016 @04:02PM
(#13179628)
You don't need a conditional. You can set up a mask using sbb.
; precondition: 0 <= x <= N
; (N is constant)
mov y, 0 ; set up mask
cmp x, N-1 ; set carry flag if x >= N
sbb y, 0 ; subtract 1 from y if carry flag set
and x, y ; set x to zero if x == N
Re:I've been writing ring buffers wrong all these years
by jnordwick on Wednesday December 14, 2016 @10:23PM
(#13182130)
The cmov looks better than sbb, but both have data dependencies than a predicted branch wouldn't.
Re:I've been writing ring buffers wrong all these years
by SamReidHughes on Thursday December 15, 2016 @12:00AM
(#13182557)
Ahh! Serves me right for reading books from before the 486 :P
Re:I've been writing ring buffers wrong all these years
by jgrahamc on Wednesday December 14, 2016 @01:00PM
(#13178098)
The 286/386 didn't have a cache so that wasn't a worry at that time.
Re:I've been writing ring buffers wrong all these years
by coldtea on Wednesday December 14, 2016 @01:21PM
(#13178284)
>But I restate it's odd that you weren't even aware of the cost in 1992 as a system level programmer.
Costs were very different in the pipelines (or lack thereof) of eighties/early nineties hardware.
Re:I've been writing ring buffers wrong all these years
by to3m on Wednesday December 14, 2016 @01:52PM
(#13178593)
Have you tested this recently? I haven't for some years now but performance was identical regardless of direction. Maybe I need to try it again. I'd expect going backwards to be no worse than "not as good" - like say perhaps the prefetching mechanism doesn't cater for this case - but maybe my standards aren't high enough and this is enough to tip things over into the horrific.
IIRC the way we made this really fast was the write the buffer backwards. That way you can detect wrapping around the buffer because DEC will underflow and set the sign flag. Then you can JS to whatever code needs to ADD back the buffer length to handle the wrap around.
But 2^n has another problem (back in that era): buffer size. You are stuck with 1K, 2K, 4K, etc. buffers. When memory is tight you likely need something very specific, so you end up with the solution we had.
But, hey, if memory is free use 2^n bytes for your buffer.