Hacker News Reader

Comment by mkchoi212 | Hacker News Reader

This looks a lot better than GCC’s asm. However, I can’t think of a good reason why one should use asm in their code instead of letting the compiler write the far superior asm for you.

View on HN

It's not always superior!

For example, I've been working on a big integer library. Addition is a bit annoying, because you need to add 3 numbers (the prior carry bit, and the two digits you're adding) and get out a new carry bit and a resulting digit. This is a bit cumbersome:

        let (res, carry1) = target_digit.overflowing_add(carry as u64);
        let (res, carry2) = res.overflowing_add(other_digit);
        *target_digit = res;
        carry = carry1 || carry2;

The resulting assembly is a fairly literal translation. We perform the addition using an add instruction, and extract the carry flag into a register using setb.

        addq    (%rdi,%rsi,8), %rcx
        setb    %r10b
        addq    (%rdx,%rsi,8), %rcx
        setb    %al
        movq    %rcx, (%rdi,%rsi,8)
        orb     %r10b, %al
        movzbl  %al, %eax

But there's a dedicated instruction for this, adc. adc adds two operands and the carry flag, while itself setting a carry flag. Manually unrolling the loop a bit, I wrote this assembly:

                shlb $8, {carry}
                adcq 0x00({y0}), {x0}
                adcq 0x08({y0}), {x1}
                adcq 0x10({y0}), {x2}
                adcq 0x18({y0}), {x3}
                adcq 0x20({y0}), {x4}
                adcq 0x28({y0}), {x5}
                setb {carry}

And got a 3x speedup.

What is Rust's policy for signed/unsigned int overflow? I assume that it's not modulo or else the complier should have generated ADC for you.

I assume you've been using Compiler Explorer a lot?

> What is Rust's policy for signed/unsigned int overflow?

Defined, by default checked in debug mode and unchecked in release, unsigned wraps and signed wraps as two's complement. This can be overridden by explicitly setting overflow-checks in the relevant profile.

It also, separately, has explicitly wrapping, saturating and checking versions of basic arithmetic operations.

overflowing_add, like I was using above, is explicitly wrapping.

I've found it very difficult to provoke rustc into emitting an ADC: the only case where it does so AFAICT is when adding u128s, which are implemented using u64s. Not sure why, except that the shortest function I could think of to emulate ADC is kind of baroque, and it's possible the compiler can't figure it out.

I've mostly been using cpuprofiler[1] and Vtune to simultaneously profile my code and show the assembly. In theory they both provide timing information per-instruction, but I don't really trust it. For the 6 adc instructions above, it shows the number of clock ticks as ranging from 22 million to 3 billion, which doesn't make sense to me. But at least it shows me the assembly!

[1] https://docs.rs/cpuprofiler/0.0.4/cpuprofiler/index.html

This will change your life!

https://godbolt.org/z/fntvYa

The article here:

https://news.ycombinator.com/item?id=23351007

specifically recommends against the carry variants of addition, because the instructions are still dependent on each other and don't pipeline well. In other words, it's using the same algorithm, just buried in a single instruction, and that doesn't necessarily make it faster.

Have you considered using a strategy similar to what the article suggests? I think the HN comments also had some additional suggestions.

The dependency is unavoidable due to the way addition works.

The approach in the article only works if you are adding a lot of numbers together, and then indeed doing carry propagation once at the end is obviously faster.

But of course there is no way that doing the carry propagation yourself on one addition can possibly be faster on a decent CPU that implements add-with-carry efficienly.

Maybe it's worth considering an interface to a big int library that can defer carry work across many operations, and then normalizing at the end?

That certainly sounds useful for, e.g., totaling an array of big integers.

> that doesn't necessarily make it faster

Did you miss the "And got a 3x speedup" part of the post you were replying to? Actual benchmarks of real code always trump theoretical deliberations.

Yikes. I was just trying to link to a relevant technique that the author might find helpful.

A big integer library may have many use cases; a benchmark only shows one data point. It's possible that by deferring carry work across more operations he'd see an even bigger improvement.

I was briefly very excited when I read that article, actually. But as devit points out in a sibling comment, that technique is only relevant to cases where you're adding more than 2 numbers.

Multiplication initially seemed like a very promising use case, since it's basically repeated addition. But I'm not super optimistic about that, because I think it's dominated by the alternate optimization of noticing that the product of two 64 bit numbers cannot saturate the high 64 bits of the resulting 128 bit number, which causes carries to be bounded [1].

[1] https://github.com/rocurley/bignum/blob/b45448a156fb9100ab06...

Thanks for this - its been many years since I've done anything touching assembly, and never outside of an academic context, so when I read conversations like this I'm always curious for concrete examples of how people are actually _using_ this stuff beyond something vague like interacting with VT-x or working on an experimental OS.

Compilers are great, but they don't always produce optimal code. You can quite often produce faster code if you're prepared to hand roll the assembly code, but it's rarely something most people will need to do. The time it takes to produce often outweighs any advantage you'd get, but having it as an option is going to be very important.

Just within the rust world, https://www.nickwilcox.com/blog/autovec2/ from a few weeks ago talks about the limitations with the compiler around vectorisation, demonstrating that with hand-rolled assembly they were able to cut the runtime in half, vs what the compiler was able to produce.

Outside of the rust world, you'll often see hand-rolled assembly in performance critical code across a spectrum of uses, e.g. OpenSSL uses it extensively for performance reasons, Go has it in a number of places in their libraries, with a pure go fall-back, and so on.

Ah gotcha. I guess I just haven’t come across a situation that calls for hand written ASM yet :p

I definitely haven't for the things I'm working on. Good enough is good enough.

edit: Thinking about it, that's not true. I was dealing with some hot code running on some MIPS architecture stuff a while back and the compiler's generated ASM was merely "okay", for the standard library. Alternative libraries with hand-rolled ASM ran significantly faster and we were going to leverage those, when another team came up with architectural changes that allowed us to take that away from the MIPS part of the stack.

Compilers kind of suck at filling branch delay slots :(

I used to work on compilers and run-time libraries for embedded systems; our preference when we sub-optimally compiled the standard library was to teach the compiler how to generate the optimal code :).

Most application developers don't need assembly, but it's still necessary for the people writing Rust and its stdlib itself, embedded developers, people writing libraries that use very specialised optimisations, SIMD, etc.

You can't explore undocumented CPU instructions, like this guy is doing: https://youtu.be/jmTwlEh8L7g

One niche case where you need assembly is if you write a green threads library. At the yield points, you need to save all necessary registers of the current thread, and restore the registers of the thread you're switching to. There's no way you can do this without assembly, because you a) you need to control exactly which machine instructions are emitted in which order, and b) you need to read and write actual registers, not variables or memory locations.

Sometimes the compiler generates worse ASM (rarely, but it can happen, especially with vector instructions). Sometimes you want to use ASM instructions there are no intrinsics for. Sometimes you want to write some extremely low-level startup code for an OS or microcontroller and simply need assembly since the C/Rust/whatever runtime can't operate yet (eg main memory needs to be initialized).

Concerning vector instructions, it's not rare at all for compilers to generate worse code. That's something they still suck at, for the most part.

Yes, I suppose I phrased it poorly. For non-vector instructions it's rare, but auto-vectorization is often poor (though Rust seems to be pretty good at it, it's still far from perfect).

One example is authoring USDT probes. This is done by writing inline assembly comments [1] that the kernel can then trace when instructed to.

Also people doing cryptography things occasionally need access to specific ASM instructions for their work. I believe AES has specialized instructions, but there are more cases.

You're not wrong that writing inline ASM is a fairly specialized need, but for those who require it this will come in incredibly useful.

[1]: I still need to try using this, so I might be wrong. I was waiting on inline assembly to be available before trying tho, so quite excited it's now available.

Yeah true. But doesn’t Rust provide an equivalent to C’s intrinsic functions like popcount?

Yes:

https://doc.rust-lang.org/core/intrinsics/fn.ctpop.html

https://doc.rust-lang.org/std/?search=count_ones

There are still use cases for raw assembly untouched by the optimizer - e.g. constant time cryptography functions designed to thwart timing attacks might desire control over the exact instruction stream. Although, most of that can be tackled with out-of-line assembly - as one must do with x64 MSVC for example.

Because compilers almost never write better code than humans ?

There are literally tens of thousands of bugs in the GCC and LLVM/Clang bug trackers about that.

I don't remember the last time I read some compiler-generated asm and thought "wow, that's great code".

> Because compilers almost never write better code than humans

Compilers almost always write better code than most humans.

Really? Citation needed.

Compilers are programmed by humans. You are claiming that somehow compilers have learned to produce better assembly than the humans that programmed them.

I am a compiler writer, and know many compiler writers. I have yet to find one that would stand by your claim. When I look at the output of LLVM or GCC, I am ashamed.

I wish I had more time to make LLVM much better, but actually, 99% of my time is spent in fixing bugs filled by users that are neither compiler writers nor assembly programmers, and they too realized how bad the machine code emitted by these tools is.

So sure, a compiler emits better assembly than a human that hasn't learn assembly programming. It also emits better assembly than all humans that do not know how to program.

But no, it does not produce _by far_ better assembly than any programmer that actually cares about machine code enough to just take a look at it and check it.

Reply on news.ycombinator.com