17 ms·
Reversing Bits in C
- KaeseEs 13y agoGreat analysis, although I'm curious how the idea that doing a bunch of 64 bit ops in order to accomplish byte arithmetic came about to begin with - was the function in question not written by a firmware guy?
- groby_b 13y agoOr the programmer was a firmware hacker, and she knew that RBIT is ARMv6T2, which IIRC wasn't available until the iPhone 3GS. (Not 100% certain, and I don't have my manuals handy)
- stephencanon 13y ago... in which case she would have used a lookup table, unless she was a really old-school firmware hacker and still believed that you couldn’t justify 256B for the table. (FWIW, you’re right about ARMv6T2).
- groby_b 13y agoI am. 256 bytes pain me :) (I've worked on systems with that much RAM total) Kidding aside, I'd probably not go for the lookup table unless the whole thing was necessary in an inner loop - the cache miss cost is high. And since it's in a function, it better not be in an inner loop :)
- nly 13y ago256B 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?)
- groby_b 13y ago8 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 blows out one entry in your return stack - which makes a more costly mispredict later on likely. Why yes, yes I do miss fiddling around with low level details. :)
- saalweachter 13y ago... don't C++ people always tell us that inlining is the single easiest optimization for a compiler to perform?
- groby_b 13y agoYeah. 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" ;)
- caf 13y agoSurely there is an argument that if it's called infrequently enough that cache misses on the LUT are a problem, then it's also called so infrequently that its performance is irrelevant.
- zwieback 13y agoI think this one goes back to PDP days and wasn't necessarily written to be the fastest possible implementation. The PDP could do 36*36 multiply into 72 bits. Not sure how the modulo instruction performed but there was a DIV instruction.
- binarymax 13y agoDown the rabbit hole says this came from HAKMEM No. 239 in 1972! http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item167 http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item167
- _ihaque 13y agoAlong the same vein, Andrew Dalke wrote up an interesting series of blog posts benchmarking different implementations of population count (counting the number of set bits in a word): http://dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html http://dalkescientific.com/writings/diary/archive/2008/07/03... http://dalkescientific.com/writings/diary/archive/2008/07/05/bitslice_and_popcount.html http://dalkescientific.com/writings/diary/archive/2008/07/05... http://dalkescientific.com/writings/diary/archive/2011/11/02/faster_popcount_update.html http://dalkescientific.com/writings/diary/archive/2011/11/02... The Stanford Bit Hacks page linked in the original article is also very interesting reading for folks into this sort of stuff.
- cnvogel 13y agoInterestingly, while x86-64 does not seem to have a single opcode for reversing bits in a byte, it has a function to arbitrarily shuffle around the 16 bytes in a 128bit SSE register [PSHUFB]. It just blows my mind how much data those SIMD instructions process or move around in relatively few clock-cycles. http://stackoverflow.com/a/9040426 http://stackoverflow.com/a/9040426 http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html http://www.intel.com/content/www/us/en/processors/architectu... (it's on page 1256 of 3251).
- stephencanon 13y agoIt’s actually shocking how long it took Intel to add PSHUFB to SSE. Altivec (PPC) had the even-more-powerful vperm (arbitrary shuffle mapping 32B to 16B) way back in 1999.
- chacham15 13y agoThe VAX (circa 1977) had polynomial evaluation as an instruction[1]. What is your point? [1] http://en.wikipedia.org/wiki/VAX http://en.wikipedia.org/wiki/VAX
- nhaehnle 13y agoThe point is that bit twiddling can be much more efficient to implement in hardware because all you're doing is placing wires somewhere. The RBIT instruction in the article significantly speeds up an operation at very low hardware cost. Polynomial evaluation does not fit into this pattern, because you need actual arithmetic operations to do it, and so a hardware polynomial evaluation instruction has no significant benefit over the corresponding sequence of explicit multiplications and additions.
- stephencanon 13y agoLike my sibling posted, the crazy CISCy instructions aren’t comparable because in general they were no faster than an equivalent sequence of simpler instructions. That’s not the case for permute; there are no “simpler” instructions that let you build an efficient permute. It’s one the fundamental building blocks for efficient vector code -- that’s why it’s shocking that it was added to SSE so late.
- rainforest 13y agoThe 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-with-a-single-multiplication/14551792#14551792 http://stackoverflow.com/questions/14547087/extracting-bits-...
- nkurz 13y agoThat'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 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-four-2-bit-bitfields-in-a-single-8-bit-byte/ http://stackoverflow.com/questions/17880178/how-do-i-sum-the...
- pbsd 13y agoWe 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.
- pbsd 13y agoThinking 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 <= 12, we already have the next sum in the vector! ; xmm7[0] = xmm8[xmm8[0]] vpaddb xmm8, xmm8, xmm7 ; add it vpextrb eax, xmm8, 0 vmovdqu xmm7, [rdi + rax] add rdi, rax sub esi, 2 jnz _loop_body This is likely extendable to 32-byte vectors with AVX2; have not thought much about that case.
- daniel-cussen 13y agoIn 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, using inclusive or and variants of the shuffle instruction.
- keenerd 13y agoThis does an 18 bit word, right?
- daniel-cussen 13y agoYep. 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.
- Scaevolus 13y agoI'm glad they noted that the lookup table's speed relies on it being in cache, which most "benchmark magic bit-fiddling operations" posts ignore. (Although it's temporal locality, not cache coherence, that's important for this.)
- robomartin 13y agoIf 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.
- picomancer 13y ago> 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 RTFM every couple years, just to know what your processor [1] and compiler [2] can do. [1] http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html http://www.intel.com/content/www/us/en/processors/architectu... [2] http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
- robomartin 13y agoOh, I RTFM. Not always working on Intel platforms though. And still: http://hardwarebug.org/2010/01/14/beware-the-builtins/ http://hardwarebug.org/2010/01/14/beware-the-builtins/
- zhemao 13y agoWait, 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?
- robomartin 13y agoDepending 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.
- applecore 13y agoInteresting. What's the purpose of reversing the bits in a byte?
- kbojody 13y agoEndian is probably the most common.
- unoti 13y agoEndian-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...
- xymostech 13y agoI don't even think that mirroring images would require reversing bytes, unless you want to mess up the color components also or something...
- ErsatzVerkehr 13y ago> mirroring an image horizontally ...but only a 2-color image.
- to3m 13y agoIt was at one time standard to store each bitplane separately. If you had a 4-color 320x200 image, for example, you'd have one page of VRAM that stored a 320x200 1-bit image, holding all the bit 0s, and another, exactly the same, holding all the bit 1s. And so on up to as many bit planes as required. (That was one usual arrangement, but there are other options - e.g., interleaved bitplanes and/or no video RAM as such.) Separate bitplanes were very annoying in many respects, and the demise of the approach was probably regretted by only a few. But storing each bitplane separately does have one major advantage: you can just write all your algorithms to operate on 1-bit images, and they automatically run at any bit depth. Just run the routine once for each bitplane you're interested in processing. (That may also mean the hardware is simpler to implement - one plausible excuse for its ubiquity. Not my field of expertise though...)
- kibwen 13y ago"Intel x86/x64 processors don’t have this instruction, so this is definitely not a portable solution." This stuck out to me. I know that RISC vs CISC is basically a meaningless distinction nowadays, but I still naively expected that x86 would be more-or-less a strict superset of ARM.
- pbsd 13y agoStrictly speaking, AMD's XOP extensions do have an instruction that is close enough: VPPERM. It allows to not only shuffle bytes, like the already mentioned PSHUFB, but also reverse bits within each byte. Therefore, a single VPPERM instruction can reverse up to 128 bits at a time.
- stephencanon 13y agoModern ARM has lots of instructions that don’t have direct x86 equivalents. Most are in the vector domain, but there are plenty of non-vector examples too: BFI, BFC, BIC, ORN, RSB, saturating arithmetic, numerous multiply-add variants, etc.
- Symmetry 13y agoVery interesting, though you shouldn't be surprised by small differences between O(1) and O(N) algorithms when N is only 8.
- stephencanon 13y agoIf N is 8, then O(N) is O(1). For that matter, so is O(f(N)), for any function f.
- MichaelBurge 13y agoIs 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.
- drivers99 13y agoIf 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).
- millstone 13y agoSo 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 complexity is irrelevant.
- Dylan16807 13y agoI 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.
- fjarlq 13y agoA great companion to this sort of thing is the book Hacker's Delight by Henry S. Warren, Jr: http://www.hackersdelight.org/ http://www.hackersdelight.org/ http://www.amazon.com/Hackers-Delight-2nd-Edition-ebook/dp/B009GMUMTM/ http://www.amazon.com/Hackers-Delight-2nd-Edition-ebook/dp/B...
- deleted 13y ago[deleted]
- jandrewrogers 13y agoThis 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 same time. For most algorithms, particularly those that are not carefully designed, multiple execution ports may be sitting idle for a given clock cycle. (Hyper-threads work by opportunistically using these unused execution ports.) Consequently, algorithms with a few extra operations but more operation parallelism will frequently be faster than an equivalent algorithm where the operations are necessarily serialized in the CPU. Furthermore, the compiler and CPU may have a difficult time discerning when instructions in some algorithms can be executed in parallel across execution ports. Seemingly null changes to the implementation of such algorithms, such as using splitting the algorithm across two accumulator variables and combining them at the end when any normal programmer would just use one variable to achieve the same thing can have a large impact on performance. I once doubled the performance of a bit-twiddling algorithm simply by taking the algorithm and using three variables instead of one. The algorithm was identical but the use of three registers exposed the available parallelism to the CPU.
- carterschonwald 13y agoVery very good points! Relatedly: for any performance sensitive code, reading the relevant version of the Intel Optimization manual + a book like Hacker's Delight will lead to a lot of good understanding of these trick. (admission: i'm spending a lot of my time staring at ways to make it really really easy to write fast numerical codes, so thinking about the ports on modern CPUs is very very helpful)
- stephencanon 13y agoThis 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 as you note, hyper threading will take advantage of them too). Third, even though there are six ports (actually, 8 ports and 4 ALUs in Haswell![1]), that i7 can still only retire 4 fused uops per cycle, so in practice one thread cannot saturate all of the execution ports, no matter how cleverly it is optimized. All of this combines to mean that the fastest bit-reversal in isolation may not be the fastest bit-reversal in situ, which is much more important. Actually evaluating that is much more complex, but it does tend to tip things away from chasing too much ILP slightly more than isolated timing does. [1] http://www.anandtech.com/show/6355/intels-haswell-architecture/8 http://www.anandtech.com/show/6355/intels-haswell-architectu...
- mgraczyk 13y agoThe author seems to misunderstand the idea of asymptotic complexity. All of the reversal operations are O(1) because the number of bits being flipped is a constant. If he were concerned with flipping the bits in an arbitrary precision number, then his different solutions might deserve "Big-O" classifications. Second point: The reason that the original solution is slow is because a mod operation by a number that is not a power of two involves a floating point divide, or several multiply accumulates at extended precision. Either of those two operations are slower than any of the other methods.
- chacham15 13y agoThe 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?
- Renaud 13y agoI suppose the point was to show that it's pretty bad to resort to copy/pasting clever bit hacks into libraries without taking care of how they work. The fact that the code isn't necessarily obvious makes me think that whoever used it was hoping for an optimisation of sorts. Terseness can lead to obfuscation, and that's the wrong sort of optimisation. So we can hope that the developer was going for speed instead, but the results show that was a huge failure. Maybe this won't affect performance in this particular library, maybe it's called once or twice and it doesn't matter, but if this is part of the innards of a game or a cryptographic function or some low-level network stack, it could have very detrimental consequences on performance.
- munificent 13y ago> 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.
- twoodfin 13y agoThe article makes the point that the lookup table version is fast because the table fits in D$, and that if the table were evicted it would be slower. This is true, but the more interesting point is that by loading this table into D$, you're potentially slowing down other operations. It's an important conundrum of optimization that if you had 20 similarly complex functions in a critical path, implementing and benchmarking each individually with a lookup table could show excellent performance while globally performance is terrible. And worse, it's uniformly terrible, with no particular function seeming to be consuming an inordinate amount of the runtime or, for that matter, D$ misses.
- stephencanon 13y agoIf you had 20 similar functions, the tables would occupy 5k in total, using only 1/6th of the L1 D$ on a typical "big" CPU. In actuality, temporal locality is such that you don't often stride through all table entries uniformly, so the actual cache pressure is even less. The point that you're going after is a good one, but its important to keep in mind how enormous modern memory hierarchies are. It often is very reasonable to trade memory and cache pressure for speed.
- mzs 13y agoOh man this is one of my nits. I've written code like this. For example in some bit counting code I have a block comment in front of all that with 57 lines that are not blank. I have a copy of Hacker's Delight on my bookshelf, but will the person after me know what and how that code works? I really hope that there was a comment before that pointing to one of the hack web pages at least.
- barbs 13y agoAck! Light grey on white background! My eyes!! Seriously, that's really annoying.
- duedl0r 13y agoWhy on earth does this article have so many upvotes? Running time analysis is completely wrong... O(n) vs O(1) and such...tss..don't get me started..