4 ms·
8-bit number to binary string (2013)
- pitaj 4y agoWow that's really clever. I never considered that the 8 unicode bytes corresponding to the 8 bits of u8 would fit in a u64.
- sfblah 4y agoIt's a clever solution. For converting unsigned chars to strings, though, a lookup table is going to be the fastest solution, since there are only 256 possibilities.
- userbinator 4y agoPossibly fastest in a microbenchmark, but that's 2k of cache (at least) which the table will consume.
- mortenlarsen 4y agoAre you sure? A cache miss might be very expensive.
- dragontamer 4y agoLookup tables hit the load/store units, IIRC only 2 loads per clock tick on modern Intel or AMD-Zen chips (though if anyone remembers, correct me if I'm wrong). Modern bitshifts/add instructions can instead perform 3x per clock tick on Intel, and 4x per clock tick on AMD Zen. Multiplication is 5-cycles of latency, but at least 1-per-clock tick, maybe 2-per-clock-tick depending on architecture. The /128 is just a "bitshift-right 7". ------- EDIT: So you need 8x lookups (at least 4 clock ticks worth of resources, assuming the CPU can perform 2-lookups per clock tick) for your lookup table approach. But this "*(unsigned long long*)out = 3472328296227680304ULL + (((c * 9241421688590303745ULL) / 128) & 72340172838076673ULL)" operation only has 3x bit operations + 1x multiply, using 2-clock ticks worth of resources. The multiply and lookups have multiple clock-ticks of latency, but throughput tends to be the more important metric rather than latency in high-speed CPU code in my experience. (CPUs are very smart about rearranging code out-of-order to become throughput bound rather than latency bound)
- vardump 4y agoThose constants are somewhat obfuscated. 3472328296227680304 == 0x3030303030303030 9241421688590303745 == 0x8040201008040201 72340172838076673 == 0x0101010101010101 ... and suddenly things are a lot less mysterious. Similar tricks were used for poor man's SIMD in one 32-bit register before MMX, Altivec etc. You could for example do just one multiply RGB 5-5-5 bit alpha blending instead of 3! ("Cooked" / premultiplied alpha of course.)
- AdamH12113 4y agoThank you, that makes much more sense.
- glouwbug 4y agoIsn't that poor man SIMD an Abrash Black Book trick?
- vardump 4y agoPerhaps, although a lot of people invented these tricks independently. I think some of the first ones have been known since seventies.
- Twisol 4y agoHah. From the article: > Of course, the last thing I did was changing the constants to decimal - they look way more scary this way ;>
- dragontamer 4y agoTo truly understand this stuff... you have to study SIMD. But wait, what SIMD instructions? No no no. The 64-bit register here is being used as a 64-way 1-bit SIMD. You can see that addition and the "&" instructions are just simple SIMD. The multiplication instruction can be broken up into complex 64x bitshifts + 64x add instructions all into a single statement. In general, this is called SWAR (SIMD within a register). --------- The "popcount" trick is also SIMD/SWAR (bitshift and add the & 0xcccccccc / 0x33333333 / etc. etc.), and is in fact a "reduction" / "prefix sum" applied over 1-bit values in a 32-bit or 64-bit register applied in a 1-bit SIMD as well. ------------ This achieves very fast results because its innately parallel. A 64-bit processor after all, can be seen as a 64-way parallel 1-bit processor. Learning the parallelization techniques, and applying them in this fashion leads to this kind of super-fast code. Furthermore: PEXT / PDEP from Intel can be seen as "bitwise 64x way gather" and "bitwise 64x way scatter" bit-instructions. The 64-bit register as a 64-way parallel computer is truly a marvelous abstraction.
- stouset 4y agoIncidentally, I wish PEXT existed for other architectures. It's extremely useful for a chess engine technique called Magic Bitboards.
- mmphosis 4y agox86_64 no loop needed: movabsq $3472328296227680304, %rdx movzbl %dil, %eax movabsq $-9205322385119247871, %rdi imulq %rdi, %rax movabsq $72340172838076673, %rdi shrq $7, %rax andq %rdi, %rax addq %rdx, %rax movq %rax, (%rsi) 6502 with a loop: LDX #$08 loop LSR $EB LDA #$30 ADC #$00 DEX STA result,X BNE loop
- vanderZwan 4y agoIn the previous discussion someone lamented they wished they could do this in JavaScript[0]. Nowadays we have TextDecoder and BigInt64Array so I'm pretty sure we actually could do it[1][2]. I doubt it would be faster than calling <number>.toString(2), but in principle we could port this. [0] https://news.ycombinator.com/item?id=10517332 https://news.ycombinator.com/item?id=10517332 [1] https://developer.mozilla.org/en-US/docs/Web/API/TextDecoder https://developer.mozilla.org/en-US/docs/Web/API/TextDecoder [2] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/BigInt64Array https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- Mr_Modulo 4y ago<number>.toString(2) Wouldn't be quite right because the output needs to be padded out with zeros.
- vanderZwan 4y agoOh, right, good catch! So <number>.toString(2).padStart(8, "0") then. I still expect it to be faster than this clever hack though. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/padStart https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- vanderZwan 4y agoHere we go: const toBinary = (() => { const u64 = new BigUint64Array(1); const u8 = new Uint8Array(u64.buffer) u8[0] = 255; const decoder = new TextDecoder(); return (number) => { u64[0] = 0n; u8[0] = number; // We're assuming little-endian architectures u64[0] = (((u64[0] * 0x8040201008040201n) >> 7n) & 0x0101010101010101n) + 0x3030303030303030n return decoder.decode(u8) }; })()
- leni536 4y agoThe distribution of bits can also be achieved with a PDEP instruction, I wonder if that would make this somewhat practical on a modern CPU.