Hacker News Reader

Comment by kitsuac | Hacker News Reader

It's odd that you were using ring buffers in 1992 for low level code but don't understand the value of avoiding a modulus instruction. Masking is far more efficient and often a ring buffer will be used in code where performance is absolutely critical.

View on HN

You wouldn't use the modulus operation. You aren't adding some arbitrary number that's going to make you increase either index by more than the buffer length so you know that at worse you are going to need to subtract the length of the buffer.

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.

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.

>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...

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

The cmov looks better than sbb, but both have data dependencies than a predicted branch wouldn't.

Ahh! Serves me right for reading books from before the 486 :P

The 286/386 didn't have a cache so that wasn't a worry at that time.

>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.

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.

Reply on news.ycombinator.com