Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reversing Bits in C

corner.squareup.com

Post reply on HN
Print view View original

71–80 of 91 posts

Re: Reversing Bits in C

#71

Post by csom »

jandrewrogers wrote: post #66
caf wrote: post #63

Earlier quoted context omitted.

Have you published your hash function?

Not yet but will soon. It is not just one function but an entire family of functions with some interesting aspects beyond just the algorithms. The hash functions were algorithmically optimized around a scaffolding I designed that guaranteed certain performance characteristics and easy analyzability. It has literally produced many, many thousands of high quality hash functions. Tens of thousands of CPU hours have been…

how does it compare to, say, tabulation as in

Mihai Patrascu, Mikkel Thorup: The Power of Simple Tabulation Hashing. J. ACM 59(3): 14 (2012) http://doi.acm.org/10.1145/2220357.2220361 (free version: http://arxiv.org/abs/1011.5200)

or also

Mihai Patrascu, Mikkel Thorup: Twisted Tabulation Hashing. SODA 2013: 209-228 http://knowledgecenter.siam.org/0236-000005/

Re: Reversing Bits in C

#72

Post by TwoBit »

jandrewrogers wrote: post #66
caf wrote: post #63

Earlier quoted context omitted.

Have you published your hash function?

Not yet but will soon. It is not just one function but an entire family of functions with some interesting aspects beyond just the algorithms. The hash functions were algorithmically optimized around a scaffolding I designed that guaranteed certain performance characteristics and easy analyzability. It has literally produced many, many thousands of high quality hash functions. Tens of thousands of CPU hours have been…

This is exactly what I was planning on doing one of these days. After looking at CityHash I was sure it could be beat.

Re: Reversing Bits in C

#73

Post by pbsd »

nkurz wrote: post #68
rainforest wrote: post #5

The multiplication trick reminds me of this StackOverflow answer[1] where an SMT solver (z3) is used to derive mask and multiplier to extract chosen bits from a byte. [1] : http://stackoverflow.com/questions/14547087/extracting-bits-...

That's really interesting, and an approach to such problems that I'd never considered. I was excited that a "Code generator for bit permutations" ( http://programming.sirrida.de/calcperm.php ) exists, but using a theorem prover is really another level of possibility. Now I need to figure out how to apply it to the problem I'm currently thinking about: http://stackoverflow.com/questions/17880178/how-do-i-sum-the...

We can use the exact same approach used in the bit reversal trick of the article:

  ((x * 0x01010101) & 0xC0300C03) % 1023
This is probably not gonna be faster than the naive approach, though.

Re: Reversing Bits in C

#75

Post by stephencanon »

nitrogen wrote: post #67
stephencanon wrote: post #37

Earlier quoted context omitted.

This is an excellent point, however, there are a few things to keep in mind: first, compilers can (and do) perform this optimization for you (ignoring details about re-associating floating-point since we’re talking about bit twiddling). Second, bit-reversal never exists in a vacuum. There are other operations taking place around it, which will fill in unused execution resources, thanks to out-of-order execution. (And…

This is an excellent point, however, there are a few things to keep in mind: first, compilers can (and do) perform this optimization for you (ignoring details about re-associating floating-point since we’re talking about bit twiddling). For people who know what they're doing (e.g. DarkShikari), the compiler doesn't stand a chance: http://www.scribd.com/doc/137419114/Introduction-to-AVX2-opt... (via https://news.ycomb…

Non-trivial vectorization is an entirely different sort of optimization than re-association to extract ILP (especially in the integer domain where the vector instructions often have no exact non-vector analogue).

Yes, there are people who have the knowledge and experience to regularly beat the compiler. I do it professionally. My point is not "don't bother optimizing, let the compiler do it". My point is "this particular micro-optimization is less valuable in the real world than focused benchmarks suggest, and good compilers often do it (this one specific optimization) for you, anyway."

Re: Reversing Bits in C

#76

Post by stephencanon »

onan_barbarian wrote: post #61
stephencanon wrote: post #37

Earlier quoted context omitted.

This is an excellent point, however, there are a few things to keep in mind: first, compilers can (and do) perform this optimization for you (ignoring details about re-associating floating-point since we’re talking about bit twiddling). Second, bit-reversal never exists in a vacuum. There are other operations taking place around it, which will fill in unused execution resources, thanks to out-of-order execution. (And…

Absolutely true. Note that micro-fusion can allow you to push the number of uops retired per cycle to 5-6 (SNB would be 3 ALU, 2 loads, Haswell could be 4 ALU, 2 loads), as the issue/retire rates are on the fused domain. It's a far cry from RISC - like a load/store machine. All that being said micro-fusion only works with an ALU op and load from the same instruction and you obviously have to be careful to ensure that…

You also need to have loads to do. Adding spurious loads just to boost uop retirement rate would be an interesting choice. :)

Re: Reversing Bits in C

#77

Post by pbsd »

pbsd wrote: post #73
nkurz wrote: post #68

Earlier quoted context omitted.

That's really interesting, and an approach to such problems that I'd never considered. I was excited that a "Code generator for bit permutations" ( http://programming.sirrida.de/calcperm.php ) exists, but using a theorem prover is really another level of possibility. Now I need to figure out how to apply it to the problem I'm currently thinking about: http://stackoverflow.com/questions/17880178/how-do-i-sum-the...

We can use the exact same approach used in the bit reversal trick of the article: ((x * 0x01010101) & 0xC0300C03) % 1023 This is probably not gonna be faster than the naive approach, though.

Thinking a little further about this, I believe using PSHUFB is the way to go, at least for when the count is large. This is because we can do 2 iterations in essentially one go (haven't tested the code, it's mostly a sketch):

  vmovdqa xmm0, [0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3, 4, 5, 6]
  vmovdqa xmm15, [0x0f, 0x0f, ..., 0x0f]
  vmovdqu xmm7, [rdi]
  _loop_body:
  vpand   xmm8, xmm15, [rdi]
  vpsrlw  xmm9, xmm7, 4
  vpand   xmm9, xmm9, xmm15
  vpshufb xmm8, xmm0, xmm8
  vpshufb xmm9, xmm0, xmm9
  vpaddb  xmm8, xmm8, xmm9

  vpshufb xmm7, xmm8, xmm8 ; since sum
This is likely extendable to 32-byte vectors with AVX2; have not thought much about that case.

Re: Reversing Bits in C

#78

Post by daniel-cussen »

keenerd wrote: post #16
daniel-cussen wrote: post #6

In the GA144, lookup tables are pretty painful, so the way I implement reverse there is: reverse: a! 16 push . 2 dup . . begin +x 2* 2* unext +x 2* a . + nip ; In Intel x86/64, the fastest way I know of is to use SIMD instructions, and break the 64-bit word into 16 nibbles (4-bit pieces), and use PSHUFB to perform a parallel lookup against another 128-bit xmm register. Then you aggregate the nibbles in reverse order,…

This does an 18 bit word, right?

Yep. I thought this would be a huge issue when using this, but first, it's really necessary for the instruction set, and second, a lot of hardware uses 18-bit, including FPGA's (often packed w/ 18x18 multipliers and 18bit SRAMs, in order to support 8b/10b SERDES) and 72-bit DDR3.

Re: Reversing Bits in C

#79

Post by saalweachter »

groby_b wrote: post #60
nly wrote: post #53

Earlier quoted context omitted.

256B is quite large for sure, but what about going for 2 nibble lookups in a 16 byte table? Or a 2 bit swap and a 6 bit lookup in a 64B table? (current x86-64 CPUs typically have 64B L1 cache lines?)

8 words to an L1 line on the original iPhone ARM, so yes, you'd fit it into a smaller table. You'll still face the memory latency issue if you're using this outside a tight loop. (Cache is only 4-way set associative. But at least I & D cache are separate) But really, if you spend that much time thinking about the performance, you really shouldn't have that abstracted into a function. Calling that costs cycles and blo…

... don't C++ people always tell us that inlining is the single easiest optimization for a compiler to perform?

Re: Reversing Bits in C

#80

Post by grn »

jandrewrogers wrote: post #35

This article overlooks a major factor in bit-twiddling performance on modern CPUs: saturation of the execution ports in a CPU core. An Intel i7 core has six execution ports, three of which are ALUs of various types. Depending on the specific instruction and the dependencies between instructions, the CPU can execute up to 3 simple integer operations every clock cycle mixed with operations like loads and stores at the…

Could you recommend a good reading (a book preferably) for learning about CPU architecture. I'm aware of Intel Software Developer's Manual. What other resources are worth reading?
Post reply on HN