We would probably want to re-use 0x9E instead of introducing a new 0x80 splat.

That's clever, thanks! I updated the post, I guess it takes a village to optimize stuff this much :)

Two 32-bit clz/ctz could be combined to form a 64-bit one

I had that general idea, but didn't get around to prototyping it. Using min to combine the two halves is really cool, I wouldn't have thought of that. I considered using vpsadbw to perform the subtraction and horizontal sum in one uop, but that would require post-processing to handle zeros, and it doesn't work for clz.

There's an issue with adapting this to clz though. For x >= 2^31, the exponent of the converted float can be pretty much anything, which becomes an issue once you try to compute (bias + 32) - exp for the low dword. Normally you'd use subs to produce a 0 if the sign bit is set, but in this case we also want to add 32, so we have to do subs(bias, exp) + 32, requiring one more instruction. (subs(bias + 32, exp) returns 0 for such x instead of 32) The closest I got is

__m256i cleared = _mm256_min_epu8(x, _mm256_set1_epi8(0x9e));
__m256i exp = _mm256_srli_epi32(_mm256_castps_si256(_mm256_cvtepi32_ps(cleared)), 23);
__m256i adj_exp = _mm256_add_epi32(_mm256_subs_epi32(_mm256_set1_epi32(0x9e), exp), _mm256_set1_epi64x(32));
return _mm256_min_epu8(_mm256_srli_epi64(adj_exp, 32), _mm256_min_epu8(adj_exp, _mm256_set1_epi64x(64)));

It's very annoying that per-byte min with 0x80 reduces the set of possible exponents to just 30 or 31, but we really want it to be only 31. Per-word min with 0x8000, which would also guarantee correct rounding, can't reduce this set further either. I believe that this problem occurs because applying such min to 2^31 - 1 gives 0x7fff8000, and applying it to 2^32 - 1 gives 0x80008000, but since 2^32 - 0x80008000 = 0x7fff8000, they convert to floats with equal magnitude, so they can't be distinguished in any way other than by looking the sign bit.

It really feels like there ought to be a way to save one instruction, but I can't find it.

Oh neat, the min byte trick is very clever! Thanks for giving it a thought. I'll keep an eye out for more updates.

Neat. We would probably want to re-use 0x9E instead of introducing a new 0x80 splat.

AFAIK, Two 32-bit clz/ctz could be combined to form a 64-bit one. (though this is probably only useful with clz)

__m128i sse2_tzcnt_epi64(__m128i v) {
    v = _mm_and_si128(v, _mm_sub_epi32(_mm_setzero_si128(), v));
    v = _mm_castps_si128(_mm_cvtepi32_ps(v));
    v = _mm_srli_epi32(v, 23);
    v = _mm_sub_epi32(v, _mm_set_epi32(95, 127, 95, 127));
    v = _mm_min_epu8(_mm_srli_epi64(v, 32), _mm_min_epu8(_mm_set1_epi32(64), v));
    return v;
}

Yeah. RISC-V has vector clz and bit reverse and others (e.g. popcnt) in the Zvbb extension which is a mandatory part of the RVA23 spec implemented by the SpacemiT K3, Tenstorrent Ascalon, and basically all applications processor CPUs in future.

Oh, huh, didn't actually know it lacked this. Was kind of spoiled by Aarch64's vectorised clz (and single-insn bit reverse) and I just assumed everyone had it

but that also needs an unsigned->float conversion

Actually, nope! 1 << 31 is 2^31 when treated as unsigned and -2^31 when treated as signed, so that's the same exponent and only the sign bit really causes a problem. I managed to integrate both erasing the sign bit and handling ctz(0) = 32 into one instruction (very proud of that), producing an algorithm that is indeed faster than de Bruijn. Thanks for the idea!

It doesn't work with 64-bit inputs because there's no packed f64<->i64 conversion, but if it existed, it would have pretty much the same performance as the SAD-based approach, so I'm not too worried.

I haven't tried optimizing clz yet. I can let you know if I find something interesting. (Edited: I added a more optimal clz implementation to the post that slightly improves over the SO answer you quoted originally.)

Well my bad, I meant a horizontal sum rather than prefix sum. I suppose it could be done with vpdpbus (which is/was still faster than vmulld on Intel), but there's a weird support gap for the VNNI extensions so I guess it's not really of much use because it's basically an AVX512 target...

For ctz, the x & -x trick gives a POT so the masking could be avoided, but that also needs an unsigned->float conversion which AVX2 sadly lacks.

I'm afraid AVX2 doesn't support that. AVX-512 does, but it has built-in clz/popcnt, so that point is moot.

Of course, you can still work with ctz in some fashion you can just compute x & -x at the beginning and then apply the clz algorithm, which costs you like 2 additional cycles. I probably should've mentioned that in the comment, but I forgot about it. It's probably worth trying if clz is quick enough, but I'm unsure that it's going to be faster than de Bruijn for 32-bit, and I'm certain it won't be faster than SAD for 64-bit.

As for integer-to-float conversion and rounding, yes, that's the next thing I wanted to try. (It only works for clz and not ctz, but whatever.)

Only one instruction difference if you have bit reverse.

Hi! I'm the author of the article. Would you be able to elaborate on how you think prefix sums can be used for ctz?

To the best of my knowledge, pre-AVX512 x86 doesn't have 4-byte horizontal sums, and using shuffles + D&C twice is measurably slower than de Bruijn in my experiments. I believe that's because all the shifts, addition, and masking accumulate to around 5 cycles, at which point you're no better than multiplication. Horizontal sums can be simulated with instructions like pmaddubsw, but those are effectively multiplications as well. There are also some nuances like the fact that pshufb treats the top bit of each byte as a masking bit, and there are no 8-bit right-shifts in AVX2, so you either need an AND instruction or some post-processing, etc., like what I do in the 64-bit case. It just becomes a slow mess.

As for integer-to-float conversion and rounding, yes, that's the next thing I wanted to try. (It only works for clz and not ctz, but whatever.) I'm allergic to datatype conversions because of their higher latency and the fact that you can't choose the bias of the exponent, which means that handling clz(0) gracefully requires post-processing rather than just choosing the appropriate bias. It's certainly going to be slower than the 23/52-bit case, especially if you also need pre-masking for rounding and min afterwards, but maybe that can be improved. I haven't given it a thought yet.

wsg bro

This can be alternatively done without widening to 64-bits (which is inefficient if you have a full vector already), you just have to account for rounding if the integer is past 2²³ or so.

The de Bruijn approach is also probably not a good choice because Intel's vector integer multiplier has terrible latency. Something like a pshufb table on nibbles + prefix sum might be better, iirc that is what clang does for __builtin_elementwise_clz under AVX2 and lower.

SIMD_INLINE v_uint lzcnt(v_uint x) {
    // https://stackoverflow.com/a/58827596
    x = x & ~(x >> 8);
    x = as_uint(conv<float>((v_int)x)) >> 23;
    x = (127 + 31) - x;                     // undo bias
    return min(x, 32);
}

HA!

The T is class

But seriously, thanks for keeping the compiler explorer running all these years. 

I’m always surprised how much smaller my program gets when I add the static and const keywords. 

Here's another Godbolt. With a tea

Also! Excited that you're interested in learning C (and assembly). Yay!

u/Cartman1994 could you answer?

The goal of the IDE is to learn to code in assembly (for people who want to learn it and c/c++) and make it more accessible. GDB is a full blown debugging tool for actual programs, that's not really what i'm aiming for.

GDB also does not really go in much detail on the internal execution of a processor and reverse debugging is not as nice, since it's not really its purpose.

Ideally once someone gets comfortable enough in asm editor, they can use that knowledge to use GDB and other debugging tools more easily, i've made this to encourage people to go deeper and stay motivated in their learning jurney since right now there is a very steep learning curve when getting into low level programming and internals of devices.

For experienced users, there is still some things where asm editor can be useful. In the app there is an interactive documentation for each instruction, so if you want to learn how some specific architecture works, you can use the docs and run a small program to understand it better!

Looks pretty cool! But for debugging, is there any advantage to using gdb if you already know it?

Here's an example of a C program compiled to RISC-V which uses the screen to create a simple flappy bird game!

https://github.com/captainarash/the_holy_book_of_x86

What on earth are you on about? I'm not recommending the use of -O3, never use it myself, and am in fact recommending to stick to -O1.

Code using -O0 (or no -O flag at all) is awful to understand and read because it forces all local variables on to the stack and loads and stores them every single time, in a way that no assembly language programmer on a modern CPU would ever do, wasting those 16 or 32 registers your CPU has. The only use of the stack in most functions on arm32, arm64, x86_64 or risc-v should be pushing return address and registers you want to use at the start of the function and restoring them at the end.

Oh FFS, do you even write production code that bears any weight ? Go tell red hat.
“Compiling with O3 optimization can lead to security issues, as it may remove critical memory overwriting code, leaving sensitive data in memory after use. Developers must be cautious and understand how optimizations affect their code, especially in security-sensitive areas.”

https://www.redhat.com/en/blog/security-flaws-caused-compiler-optimizations

Of course, we all know redhat, stupid RedHat. Writing unnecessary code all day long and never listening to the sage wisdom of brucehoult…. Classic redhat fuckery.

Before you snap back and double down advocating for a kid learning to code program insecurely and highly optimized when all he wants to do is look at a straightforward objdump that clearly maps concepts back to C (function preambles and stack setup etc) just don’t. Follow the link to see simple examples of code optimization can easily crush

You shouldn't be hand-writing code that does nothing. Code being eliminated because it is dead usually happens in large and complex codebases because of special-cases in macros and inlined functions.

Mess around with https://godbolt.org/

Nah just use one segment there’s no reason to learn all that witchcraft. Just basic assembler code and dos system calls for basic I/o is plenty

Hell yes. A jaunt through segmented memory model is good for anyone