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

41–50 of 91 posts

Re: Reversing Bits in C

#41

Post by xymostech »

unoti wrote: post #20
kbojody wrote: post #19

Earlier quoted context omitted.

Endian is probably the most common.

Endian-ness would be reversing bytes, not bits within bytes, like 0x1234 -> 0x3412. What we're talking about here would be more along the lines of: 0b0010001 -> 0b1000100 The most obvious application I can think of for reversing bits within a byte would be for image processing applications, such as mirroring an image horizontally, or making kaleidoscopes. There are probably signal processing applications, too...

I don't even think that mirroring images would require reversing bytes, unless you want to mess up the color components also or something...

Re: Reversing Bits in C

#42

Post by zhemao »

robomartin wrote: post #14

If you've ever dealt with graphics file manipulation code chances are you've suffered the pain of changing the endian-ness of an image file. I never understood why some of these operations are not implemented as machine instructions that can run in one instruction cycle flat. There's nothing to them, I've done exactly that on FPGA's. Yes, they can be a little resource/routing intensive but not that bad.

Wait, why is it resource intensive? If all you need to do is reverse a fixed-size integer, wouldn't you just wire the inputs to the outputs backwards?

Re: Reversing Bits in C

#43

Post by drivers99 »

MichaelBurge wrote: post #40
stephencanon wrote: post #28

Earlier quoted context omitted.

If N is 8, then O(N) is O(1). For that matter, so is O(f(N)), for any function f.

Is that true? I would agree that the time is bounded by a constant, but Big O only makes sense at all as the size of the input increases without bound.

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).

Re: Reversing Bits in C

#44

Post by jandrewrogers »

stephencanon wrote: post #37
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…

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…

Both GCC and Clang are surprisingly mediocre at this kind of optimization. I write a lot of extreme performance integer algorithms and those compilers only seem to find "obvious" parallel instruction schedules about half the time even in isolated contexts.

Fortunately, it is pretty simple to induce the desired optimization from the C code without resorting to much cleverness. The compilers miss these optimizations often enough that I frequently double check if I care. Still, it requires fairly detailed knowledge of the microarchitecture.

I do not do microarchitecture optimization work very often. The last time I did, it was to design a faster, better hash function to replace Google's CityHash (and the result was faster and stronger). For most codes, memory behaviors dominate with respect to performance.

Re: Reversing Bits in C

#45

Post by robomartin »

picomancer wrote: post #24
robomartin wrote: post #14

If you've ever dealt with graphics file manipulation code chances are you've suffered the pain of changing the endian-ness of an image file. I never understood why some of these operations are not implemented as machine instructions that can run in one instruction cycle flat. There's nothing to them, I've done exactly that on FPGA's. Yes, they can be a little resource/routing intensive but not that bad.

> changing the endian-ness x86 has had the BSWAP instruction since the 486. gcc has a __builtin_bswap16, __builtin_bswap32, and __builtin_bswap64 which will presumably take advantage of these built-in instructions on x86 and any other gcc-supported architectures where similar instructions exist (and fall back to a reasonably fast and well-tested multi-instruction implementation where they don't). You should really RT…

Oh, I RTFM. Not always working on Intel platforms though. And still:

http://hardwarebug.org/2010/01/14/beware-the-builtins/

Re: Reversing Bits in C

#46

Post by robomartin »

zhemao wrote: post #42
robomartin wrote: post #14

If you've ever dealt with graphics file manipulation code chances are you've suffered the pain of changing the endian-ness of an image file. I never understood why some of these operations are not implemented as machine instructions that can run in one instruction cycle flat. There's nothing to them, I've done exactly that on FPGA's. Yes, they can be a little resource/routing intensive but not that bad.

Wait, why is it resource intensive? If all you need to do is reverse a fixed-size integer, wouldn't you just wire the inputs to the outputs backwards?

Depending on timing requirements, device type, operating speed and word width you have to add one or more layers of flip-flops to facilitate timing closure and avoid potential metastability issues.

Re: Reversing Bits in C

#47

Post by mrb »

robomartin wrote: post #14

If you've ever dealt with graphics file manipulation code chances are you've suffered the pain of changing the endian-ness of an image file. I never understood why some of these operations are not implemented as machine instructions that can run in one instruction cycle flat. There's nothing to them, I've done exactly that on FPGA's. Yes, they can be a little resource/routing intensive but not that bad.

Note that this post is about changing the order of bits within a byte (eg. x86-64 XOP instruction VPPERM with bit reversal option). Whereas you are talking about changing the order of bytes within a word (x86 instruction BSWAP).

Re: Reversing Bits in C

#48

Post by stephencanon »

jandrewrogers wrote: post #44
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…

Both GCC and Clang are surprisingly mediocre at this kind of optimization. I write a lot of extreme performance integer algorithms and those compilers only seem to find "obvious" parallel instruction schedules about half the time even in isolated contexts. Fortunately, it is pretty simple to induce the desired optimization from the C code without resorting to much cleverness. The compilers miss these optimizations of…

> Both GCC and Clang are surprisingly mediocre at this kind of optimization.

Clang, at least, has gotten significantly better in the past year (I haven’t used GCC for a while), but there’s certainly room for improvement. Please report bugs for cases that your compiler misses if you can spare a few minutes.

Re: Reversing Bits in C

#49

Post by chacham15 »

The difference here between the obvious method and the best method is 55ns. Is there a reason that this problem deserves this much attention for as little a difference in time? (I realize that it is 6.5x more, but if it isnt at the center of some core loop, the multiplicative factor doesnt really matter). What use cases are there for this?

Re: Reversing Bits in C

#50

Post by munificent »

> That’s one mathematical operation, but a large number of CPU instructions. CPU instructions are what matter here, though, as we see, not as much as cache coherency.

I thought it was also a single CPU instruction, but multiple clock cycles.

Post reply on HN