3 ms·

Hakmem: classic programming hacks

22 points by hhm 18y ago

hhm 18y ago
This one is amazing: http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154 http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154
- scott_s 18y ago
  Er, I don't think so. If I understand that right, it assumes that the universe uses finite bits to represent numbers. I see no reason to assume that.
  - hhm 18y ago
    I didn't mean it was real science (the physical part of it), I found it fun and amusing, like a mind trick.
halo 18y ago
Anyone interested in this will likely be interested in: Bit Twiddling Hacks - http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html The book Hacker's Delight by Henry S. Warren Jr and published by Addison Wesley - homepage at http://www.hackersdelight.org/ http://www.hackersdelight.org/
kqr2 18y ago
Also, there's the famous Quake inverse square root hack. http://www.beyond3d.com/content/articles/8/ http://www.beyond3d.com/content/articles/8/
- michael_dorfman 18y ago
  That's a nice article-- it's good to see that there are folks who a) recognize the coolness of a hack like this, and b) take the time to try to find out who to credit.
DarkShikari 18y ago
Here's a personal favorite of mine that I wrote a while back; I like it because it does what seems to be a slightly complicated problem to SIMD (count the number of nonzero elements in a 16-element array of 16-bit values) and does it in a really small number of instructions: static inline int array_non_zero_count_mmx( int16_t *v ) { int count; asm( "pxor %%mm7, %%mm7 \n" "movq (%1), %%mm0 \n" "movq 8(%1), %%mm1 \n" "packsswb 16(%1), %%mm0 \n" "packsswb 24(%1), %%mm1 \n" "pcmpeqb %%mm7, %%mm0 \n" "pcmpeqb %%mm7, %%mm1 \n" "paddb %%mm0, %%mm1 \n" "psadbw %%mm7, %%mm1 \n" "movd %%mm1, %0 \n" :"=r"(count) :"r"(v) ); return (count+0x10)&0xff; } It is, not surprisingly, an order of magnitude faster than the C equivalent. Bonus points for understanding what the "0x10" is for at the end.

22 points by hhm 18y ago

hhm 18y ago

This one is amazing: http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154 http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item154

scott_s 18y ago
Er, I don't think so. If I understand that right, it assumes that the universe uses finite bits to represent numbers. I see no reason to assume that.
- hhm 18y ago
  I didn't mean it was real science (the physical part of it), I found it fun and amusing, like a mind trick.

halo 18y ago

Anyone interested in this will likely be interested in: Bit Twiddling Hacks - http://graphics.stanford.edu/~seander/bithacks.html http://graphics.stanford.edu/~seander/bithacks.html The book Hacker's Delight by Henry S. Warren Jr and published by Addison Wesley - homepage at http://www.hackersdelight.org/ http://www.hackersdelight.org/

kqr2 18y ago

Also, there's the famous Quake inverse square root hack. http://www.beyond3d.com/content/articles/8/ http://www.beyond3d.com/content/articles/8/

michael_dorfman 18y ago
That's a nice article-- it's good to see that there are folks who a) recognize the coolness of a hack like this, and b) take the time to try to find out who to credit.

DarkShikari 18y ago

Here's a personal favorite of mine that I wrote a while back; I like it because it does what seems to be a slightly complicated problem to SIMD (count the number of nonzero elements in a 16-element array of 16-bit values) and does it in a really small number of instructions: static inline int array_non_zero_count_mmx( int16_t *v ) { int count; asm( "pxor %%mm7, %%mm7 \n" "movq (%1), %%mm0 \n" "movq 8(%1), %%mm1 \n" "packsswb 16(%1), %%mm0 \n" "packsswb 24(%1), %%mm1 \n" "pcmpeqb %%mm7, %%mm0 \n" "pcmpeqb %%mm7, %%mm1 \n" "paddb %%mm0, %%mm1 \n" "psadbw %%mm7, %%mm1 \n" "movd %%mm1, %0 \n" :"=r"(count) :"r"(v) ); return (count+0x10)&0xff; } It is, not surprisingly, an order of magnitude faster than the C equivalent. Bonus points for understanding what the "0x10" is for at the end.