121–130 of 175 posts
Earlier quoted context omitted.
Subtraction requires a branch, which could be worse (or not) depending on architecture.
Oh, come on, you don't need a branch to do a conditional subtraction. Reify the condition to 0/1 and use multiplication, or use AND with a two's complement of the condition.
This is of course not a new invention. The earliest instance I could find with a bit of searching was from 2004, with Andrew Morton mentioning in it a code review so casually that it seems to have been a well established trick. But the vast majority of implementations I looked at do not do this. I was doing this in 1992 so it's at least 12 years older than the 2004 implementation. I suspect it was being done long bef…
> It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask. The cost of a mask can probably be entirely buried in the instruction pipeline, so that it's hardly any more expensive than whatever it costs just to move from one register to another. Modulo requires division. Division requires a hardware algorithm that iterates, consuming multiple cycles (pipeline stall).
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> Join me next week for the exciting sequel to this post, "I've been tying my shoelaces wrong all these years". Probably. Use the Ian Knot: http://www.fieggen.com/shoelace/ianknot.htm Seriously, spend 20 mins practising this, and you'll never go back to the clumsy old way again.
The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
Earlier quoted context omitted.
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. T…
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.
; precondition: 0 = N
sbb y, 0 ; subtract 1 from y if carry flag set
and x, y ; set x to zero if x == NEarlier quoted context omitted.
You do not need modulo or division to implement non-power-of-2 ring buffers. Because you will only increment by one. So instead of "x = x % BufferSize" you can do "if (x >= BufferSize) x -= BufferSize;" or similar. That's for "normal" ring buffers. I suspect that the design described in the article can be implemented for non power-of-two without division but I'll need to think about the details.
You could also do a predicated conditional move instead. Just do the subtraction every time, and use something like cmov to only do the write if you need to. I don't know if it would end up being faster, though.
The general rule is to only use cmov if your test condition is mostly random.
Earlier quoted context omitted.
The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
This is the double slip knot, I think. I have recently started using it (the standard knot is going loose too fast the way I wear my shoes) and will never go back to the standard knot. Just so good.
Earlier quoted context omitted.
Don't use a modulo then. Use subtraction.
Subtraction requires a branch, which could be worse (or not) depending on architecture.
Earlier quoted context omitted.
> It's unclear to me why the focus on a 2^n sized buffer just so you can use & for the mask. The cost of a mask can probably be entirely buried in the instruction pipeline, so that it's hardly any more expensive than whatever it costs just to move from one register to another. Modulo requires division. Division requires a hardware algorithm that iterates, consuming multiple cycles (pipeline stall).
You do not need modulo or division to implement non-power-of-2 ring buffers. Because you will only increment by one. So instead of "x = x % BufferSize" you can do "if (x >= BufferSize) x -= BufferSize;" or similar. That's for "normal" ring buffers. I suspect that the design described in the article can be implemented for non power-of-two without division but I'll need to think about the details.
Earlier quoted context omitted.
It's not just an optimization, it's necessary for correct operation. With a non-power of two buffer the integer wraparound causes a discontinuity.
As far as I can tell that int wrap around could be avoided by - subtracting buffer size from both pointers once the read pointer has wrapped. - choosing a longer int for the math operation where possible That seems a small price for the freedom to be able to choose an appropriate buffer size.
Earlier quoted context omitted.
The Ian Knot is quick, but as someone who never ties their shoes and just slips them on and off, I much prefer Ian's Secure Knot: http://www.fieggen.com/shoelace/secureknot.htm I usually tie this knot twice over the lifetime of a pair of shoes. Once when I get them, and once more when they're worn in and need to be tightened.
I don't get it - both of these knots seem to be identical to the standard shoelace knot, just illustrated differently.
1. Regular (tied in the fast way): http://www.fieggen.com/shoelace/ianknot.htm
2. Secure: http://www.fieggen.com/shoelace/secureknot.htm
Try the secure knot. It's basically like the bunny-ears way of tying a regular knot (where you hold both bunny-ears and slip one under the other), but you leave the hole open and slip the second back under the first as well.
It's much more secure than a double-knot, in my experience, and looks a lot nicer. But I still can't instinctually do it -- it takes me an extra couple of seconds each time.