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

81–90 of 91 posts

Re: Reversing Bits in C

#81

Post by comatose_kid »

grn wrote: post #80
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?

Computer Architecture: A Quantitative Approach by Hennesey and Patterson is the definitive text, and it is good (at least the 3rd edition I read back in 02).

One way to put the ideas you learn into practice is to try to write an optimized large NxN matrix multiplication routine. Start in C, converting the kernel to x86 code. Also disassemble the generated C code in the kernel to see what the compiler is doing. See how close you can get to the theoretical peak CPU performance.

It is fun stuff. While this kind of optimization is rarely needed, doing so (like learning lisp) will make you a better programmer.

Re: Reversing Bits in C

#82

Post by anonymous »

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…

Was there a followup to that article? I'm pretty sure the NDA period should be up by now and I'm wondering if the author posted a more in-depth explanation and overview.

Re: Reversing Bits in C

#83

Post by groby_b »

saalweachter wrote: post #79
groby_b wrote: post #60

Earlier quoted context omitted.

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?

Yeah. Sure. Especially across libraries.

If you're talking to a dev with a background in firmware dev, I'd say you'd be hard pressed to find any body who'll put a single asm instruction into a separate function if it's speed-critical.

Sure, the compiler might (and probably will) inline, but it means any change in your tool chain or a whim of the inline heuristic can cause serious performance regressions that are completely avoidable.

When it comes to performance, the embedded mindset will always be "belt and suspenders" ;)

Re: Reversing Bits in C

#84

Post by Dylan16807 »

millstone wrote: post #70
drivers99 wrote: post #43

Earlier quoted context omitted.

If you define N<=8 from the beginning, then there exists some constant that is the maximum time the function will take. That makes it O(1).

So every terminating function is O(1) since your computer has only a finite number of possible states! The real question is whether the input is big enough that the cost is dominated by the asymptotic behavior, and not the constant coefficient. The O(N) "obvious" algorithm was faster than the O(1) "3 ops 64 bit algorithm," so I think the answer is no, it is not big enough. N=8 sufficiently small that the asymptotic c…

I think the logical way to look at algorithmic efficiency starts by picking a reasonable N. "Number of bits in a byte" is something that very rarely changes, and never reaches high values, so it makes a bad N. The flip side of this is that something like "number of bits in main memory" is very flexible and reaches extremely large numbers, so it shouldn't be a constant.

If I wasn't making a point about different methods to flip bits, and I was just naively classifying these byte flippers, I would probably call all of these O(1). Or perhaps O(N) where N is the size of input in bytes.

Re: Reversing Bits in C

#85

Post by nkurz »

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.

Thanks for looking at this! This is wonderful and succinct (presuming it works, I'm still staring at it), but the 20+ latency of DIV makes it impractical. I think I can do it with multiply, and, multiply, shift, but even 3 cycle latency for the multiplies is too much:

  key *= 0x04040400UL;
  key &= 0x30C30C00UL;
  key *= 0x00041041UL;
  key >>= 28;
Let me stare at your shuffling solution for a bit...

Re: Reversing Bits in C

#86

Post by nkurz »

pbsd wrote: post #77
pbsd wrote: post #73

Earlier quoted context omitted.

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, x…

This is exciting, but I think I may have tricked you on a couple of details. The actual distance to the next 'key' is 'sum + 5': 00 represents a 1 byte encoding, not zero, so the minimum offset to the next 'key' is 5. Thus the maximum offset is actually 17, which means one can't depend on having two keys within a single 16 byte vector. I'm trying to figure out if there is some way to compensate for this without halving the performance.

Re: Reversing Bits in C

#87

Post by pbsd »

nkurz wrote: post #86
pbsd wrote: post #77

Earlier quoted context omitted.

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, x…

This is exciting, but I think I may have tricked you on a couple of details. The actual distance to the next 'key' is 'sum + 5': 00 represents a 1 byte encoding, not zero, so the minimum offset to the next 'key' is 5. Thus the maximum offset is actually 17, which means one can't depend on having two keys within a single 16 byte vector. I'm trying to figure out if there is some way to compensate for this without halvi…

Oh, I missed that. That makes things trickier, but I think we can still get away with something like

  vmovdqu xmm7, [rdi + rax + 5 - 1]
  vpinsrb xmm7, xmm7, [rdi + rax + 0], 0
without too much of a performance penalty. The adjustments to offsets then can be put into the shuffle tables, so there should be no further significant performance loss.

Re: Reversing Bits in C

#88

Post by nkurz »

pbsd wrote: post #87
nkurz wrote: post #86

Earlier quoted context omitted.

This is exciting, but I think I may have tricked you on a couple of details. The actual distance to the next 'key' is 'sum + 5': 00 represents a 1 byte encoding, not zero, so the minimum offset to the next 'key' is 5. Thus the maximum offset is actually 17, which means one can't depend on having two keys within a single 16 byte vector. I'm trying to figure out if there is some way to compensate for this without halvi…

Oh, I missed that. That makes things trickier, but I think we can still get away with something like vmovdqu xmm7, [rdi + rax + 5 - 1] vpinsrb xmm7, xmm7, [rdi + rax + 0], 0 without too much of a performance penalty. The adjustments to offsets then can be put into the shuffle tables, so there should be no further significant performance loss.

Yes, I think that should work to guarantee two per vector. I hadn't previously considered trying to do that, and appreciate the suggestion and the sketch. I think I have a slightly faster (7 cycle) approach doing one at at time using a 64-bit register as a lookup for the sum of the middle two fields, but this has good promise. Especially if we can get out one farther ahead, so instead of having the vector reload on the critical path, the unused portion of the current vector and a preload can be 'slid' into place. Do you know if there is a good way to simulate a PALIGN but with a non-immediate operand? This might get down to 9-10 cycles for two keys.

Re: Reversing Bits in C

#89

Post by pbsd »

nkurz wrote: post #85
pbsd wrote: post #73

Earlier quoted context omitted.

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.

Thanks for looking at this! This is wonderful and succinct (presuming it works, I'm still staring at it), but the 20+ latency of DIV makes it impractical. I think I can do it with multiply, and, multiply, shift, but even 3 cycle latency for the multiplies is too much: key *= 0x04040400UL; key &= 0x30C30C00UL; key *= 0x00041041UL; key >>= 28; Let me stare at your shuffling solution for a bit...

In the interest of achieving the simplest instruction sequence, I've also found (AVX2):

  key   = _pdep_u32(key, 0x03030303);
  key  *= 0x01010101;
  key >>= 24;

Re: Reversing Bits in C

#90

Post by pbsd »

nkurz wrote: post #88
pbsd wrote: post #87

Earlier quoted context omitted.

Oh, I missed that. That makes things trickier, but I think we can still get away with something like vmovdqu xmm7, [rdi + rax + 5 - 1] vpinsrb xmm7, xmm7, [rdi + rax + 0], 0 without too much of a performance penalty. The adjustments to offsets then can be put into the shuffle tables, so there should be no further significant performance loss.

Yes, I think that should work to guarantee two per vector. I hadn't previously considered trying to do that, and appreciate the suggestion and the sketch. I think I have a slightly faster (7 cycle) approach doing one at at time using a 64-bit register as a lookup for the sum of the middle two fields, but this has good promise. Especially if we can get out one farther ahead, so instead of having the vector reload on t…

I have no idea how to simulate a variable PALIGNR on Intel chips without making the loop extremely slow.

On AMD (with XOP), it can be done using VPPERM, which can shuffle from 2 sources. We can do variable alignment like this:

  vpperm xmm0, xmm1, xmm2, [[0..31] + offset]
On second thought, we can possibly do something similar on Intel using 2 pshufb and a blend.
Post reply on HN