The 8-Byte Two-Step
zinascii.com
The 8-Byte Two-Step
1–10 of 34 posts
Re: The 8-Byte Two-Step
#2I'd agree with his last sentence: "My guess, this was done more as an idiom of systems programming than as an optimization."
Re: The 8-Byte Two-Step
#3Thank you for the careful writeup and submission here. I recently picked up a copy of Beautiful Code, but I was hoping it would have more stuff like this.
Re: The 8-Byte Two-Step
#4Holy shit, mind blown.
I've done this before, but usually take modulo 8 rather than bitwise-and negative 7 as the final step.
Re: The 8-Byte Two-Step
#5It's a fun trick I've used for years, I think originally I gleaned it from http://graphics.stanford.edu/~seander/bithacks.html (or maybe not, now that I look through that page - though it is full of goodies)
Re: The 8-Byte Two-Step
#6I'd agree with his last sentence: "My guess, this was done more as an idiom of systems programming than as an optimization."
Or for consistency with the rest of the code. It is one way, if not the fastest way to do alingment. Every systems programer knows that pattern, it is easily recognizable. You find it plentiful in kernels and low-level system libraries.
Re: The 8-Byte Two-Step
#7I'd agree with his last sentence: "My guess, this was done more as an idiom of systems programming than as an optimization."
Doubly agreed -- similar patterns appear elsewhere to avoid off-by-one errors and bitmasking is fairly intuitive to anyone regularly working at that level. I was surprised at the author not recognizing this idiom, but you have to learn it sometime!
I was further stunned by the seeming naivety of the author's align_2() implementation, but then it does get the job done, eventually. My naive approach would've been roughly align_3(), but using integer math and modulus.
On the other hand, younger team members were recently stunned by code I did for translation of a binary protocol into more easily handled pieces using what I think of as typical idioms, so this article might get sent around Monday morning.
Re: The 8-Byte Two-Step
#8Holy shit, mind blown. I've done this before, but usually take modulo 8 rather than bitwise-and negative 7 as the final step.
Doesn't matter, any major compiler will transform this into an bitwise and.
Re: The 8-Byte Two-Step
#9Maybe you shouldn't care about cycles, but using a loop for something that can be done without branches is a definite cognitive overhead.
If we want to avoid bit twiddling, how about this:
(mqhp->mq_maxsz + MQ_ALIGNSIZE - 1) / MQ_ALIGNSIZE * MQ_ALIGNSIZE;
I would expect a compiler to emit the same instructions as the original, but at worst you would have an add and two shifts rather than jumps or complex float operations.
Re: The 8-Byte Two-Step
#10I'd agree with his last sentence: "My guess, this was done more as an idiom of systems programming than as an optimization."
Doubly agreed -- similar patterns appear elsewhere to avoid off-by-one errors and bitmasking is fairly intuitive to anyone regularly working at that level. I was surprised at the author not recognizing this idiom, but you have to learn it sometime! I was further stunned by the seeming naivety of the author's align_2() implementation, but then it does get the job done, eventually. My naive approach would've been rough…
Hi, author here. My align_2 implementation is indeed very naive. Part of that was to show just how much overhead a naive implementation could add, in this case 3 orders of magnitude. I'm also new to systems programming. This article should serve as a reminder to experienced hackers that idioms are often only obvious _after_ they've been explained. My last 4 years were spent working on a distributed database; I could bring up "obvious" idioms from that world that might perplex a kernel hacker.
But you are right, this is indeed a very obvious line of code once you understand it. Thank you for your comments.