Hacker News Reader

Comment by jbk | Hacker News Reader

> but with modern compilers, what does assembly get you over just using C or another language [...] I was under the impression compilers nowadays have lots of optimizations that would take a lot of work for a human to do by hand

dav1d, the open source AV1 decoder, has now more asm than C code. It's one of the most recent open source projects with significant asm work ongoing.

The asm version outperforms the C version (full optimizations enabled) by 4,5x on AVX2.

We have similar results in SSSE3 (3,5x) and ARM64 (4x).

We're not talking about a few percents, we're talking about multiple times faster.

And AV1 is a standard, so there are no algo shortcuts that can be made: it is either compliant or it is not.

Sure, in most cases, it is not needed to write asm; but there are cases, notably for multimedia, where writing asm by hand is a lot faster, and that includes codecs and game engines.

View on HN

Well, video decoding is very adapted to ASM, I'd say. You can use vectorisation, you can optimize pipelined executions, etc. Things were compiler may not be so good (my experience is a bit dated). You also optimize a few tight loops, so you can really invest time in them with good ROI.

I'm not sure that operating systems are so suited to ASM optimization (in the sense that you may not reap so many benefits). Maybe one could optimize for size (so you can make super tiny OS) ?

    Maybe one could optimize for size (so you can make super tiny OS) ?

Yes, and remember... optimizing for code size is optimizing for speed. =)

Smaller code and data = more CPU cache hits, which are orders of magnitude faster than fetching from RAM. So even if "all" you do is make code smaller, you can get more speed...

> Yes, and remember... optimizing for code size is optimizing for speed. =)

Not always. I think loop-unrolling is a common perf-optimisation technique. Even if the perf-gain is positive in this case, I highly suspect that it doesn't outweigh the cost of maintaining asm code(vs C/other higher level code).

edit: formatting

Yep. I remember loop unrolling the skeletal animation code in libgdx way back resulted in a significant performance increase. And that was in Java

More so inlining. Much more than loop unrolling.

Optimizing for size is a local maximum in performance.

There are some LLVM optimization talks that show otherwise, where longer vectorized code actually runs faster than the smaller version, though.

...in microbenchmarks.

That's what created multi-kilobyte memcpy() implementations, which barely beat REP MOVSB but cause huge icache bloat.

Less code doesn't imply faster code. GCC coreutils have blasted through openbsd coreutils for years.

Now we have CPUs with 256KB instruction cache and up. You can compile your whole OS at insane optimizations.

I think one element of writing ASM by hand is the programmer subliminally changes the algorithm to be 'simpler' to write.

In Java, that might involve adding more classes and abstractions to make things conceptually simpler. In C, that might involve using structs to keep relevant data together. In C++, it might involve using a std::set to keep a list of 3 constants, Etc.

It turns out that when you have to write the asm by hand and you see that double pointer dereference is a pain, you avoid data structures with double dereferences (as C data structures often end up with). You avoid classes and abstractions (as are common in Java), because they involve a lot of boilerplate. You use compile time constants for that set of three things rather than any complex hashing that C++ would do, etc.

There are lots of small things like this, and it turns out the effect adds up significantly.

>> I think one element of writing ASM by hand is the programmer subliminally changes the algorithm to be 'simpler' to write.

I strongly disagree :-)

My experience is that optimizing assembler leads to reorganize your code or even your algorithm into a form that you'll CPU will be most efficient at executing which almost always translate to unbelievably intricate, super hard to modify code. I've done stuff on 6502, 80x86, MMX and the assembly parts, optimized for speed and ended up with impossibly tricky code. Worst, sometimes I have to adapt my data structures to allow optimization, which becomes even tougher. So, I prefer to leave assembly code at the "onyl if necessary" level

But now, to be honest, optimizing assembly code is incredibly satisfying to me :-) I've got the feeling to use a CPU to its maximum capacity. Also, using assembly comes after thorough algorithmic study. So once I'm at the ASM level, I've maxed out my own capabilities ! How happy me !

So if you have the chance to do that, just give it a try !

I suspect that this occurs for you exactly because you're aiming for optimization. This can happen in any language, really.

I'd assume that when you maintain larger codebases (i.e. full OS and application suite), that you start writing practical and maintainable code instead.

ahhh I'm biased. Your analysis is right :-)

But even so, I'd say that ASM doesn't help. Clumsy code in ASM is worse than clumsy code in high-level language :-)

If you write assembler in a maintainable way, do you still gain lots of benefits over a compiler?

>I think one element of writing ASM by hand is the programmer subliminally changes the algorithm to be 'simpler' to write.

It's not subliminal. It's packing a backpack that someone else has to carry, vs packing a backpack that _you're_ going to carry.

Compare a 512 byte boot sector game [1] to a ~1Gigabyte unity 'hello world'.

Until the day the compiler can smartly trim down all the unity framework to just 512 bytes because it notices I'm not using most of it, hand coding in asm will always work out smaller and faster, if one puts in enough effort.

[1]: https://www.youtube.com/watch?v=1UzTf0Qo37A

Unity isn't.. what? And the problem there is using an ill-suited framework, not the language.

If you compile hello world in C, it's not going to be very big either.

> if one puts in enough effort

"enough effort" is a cheat. I can replace almost any program with a smaller javascript version, if I put in "enough effort". It's not a reasonable way to compare anything.

>If you compile hello world in C, it's not going to be very big either.

You should actually try that, and compare sizes with the asm hello world.

The problem not in the language per se, but in the linker settings. By tweaking it, you can achieve almost same size as the assembler version has.

You say that, but I still haven't seen any compilers link in only parts of libc. Use any of it and it all comes in.

Hello world in C becomes anywhere from 120KB to 1.2MB even if just using puts. Even setting the entry point to a function with no arguments doesn't help.

A tiny hello world ends up needing to ignore the standard library and use a console output function from the OS.

Just checked on a Ubuntu machine. Hello world takes 6Kb. Uses printf.

That's because it links dynamically to the standard library.

Is that a problem? It's there whether you use it or not, and it's not like the asm is running in a vacuum either.

If you go to an embedded point of view where there is nothing already supplied, you can get a hello world, even with a basic printf, down to that size.

Especially since you use external libraries to do the bulk of the work, 6KB is a lot.

It is an order of magnitude bigger than the assembly version.

After some manipulations with the linker, I was able to cut the size down to 750 bytes. You cannot go below this, without hacking the ELF file format.

I got my asm one down to 268 without even trying.

It prints (via write syscall) "hello world.\n" and then calls exit(0).

Assembled with fasm, linked with ld -n, then stripped.

Ok fine, I've used the tool called sstrip from a suite called ELFKickers. Now my hello_world.cpp (yes, c++) is 380 bytes long. I could not make it any shorter, so yeah, it is 120 bytes (50%) bigger than yours.

Regarding sstrip, I am familiar with it. Be careful that you know what it actually does.

So, not order of magnitude then?

Yes, just look into how much effort you had to put vs my five minutes attempt.

The difference is between just using asm, or going out of the way to try to coerce a C toolchain to minimize the bloat.

Yea, large effort (objcopy, strip, sstrip), that I need to do only once, after that I already know how to do this an can just put it in a shell script. Now, I would like to know how quickly you'll be able to write a quicksort implementaion, that would outperform my C code, while being at least 25% smaller . Yeah, and how big your binary will become, once you link libc or opengl or whatever to make it able to do actual work.

95KB using MinGW's GCC on Windows using default compilation.

When I tell it to emit the assembly with "-S" I get 28 lines of code when I have a feeling assembly is much shorter.

I agree that Unity is bloated and should take way less constant storage, but that's an invalid comparison. They are not the same domains, they don't use the same APIs, the don't on the same environment, they don't talk to the same hardware, they don't have the same functionality, etc.

> I'm not sure that operating systems are so suited to ASM optimization

I do not know, to be honest.

I was just pointing that multimedia and game engines can get a lot of helps on ASM by hand.

I’m wondering if they time spent in writing asm for av1 could also be spend in writing an optimising pass for the c compiler? So that any optimisations can be applied by the compiler while the readability of the C language is retained.

The compiler knows nothing about your program and its data layout, which is were all of that speedup comes from.

There are some SIMD constructs that you can efficiently express in C by writing intrinsics, but that isn't substantially different from writing ASM.

Then there are some trivial cases where a loop can be unrolled and packed into SIMD instructions automagically, which retains readability, but greatly limits what you can write. You'll need to read the generated machine code to make sure you didn't mess up.

The benefit of just writing ASM is to not have such a translation layer between you and the processor. That same code that you carefully wrote to make it through the optimization passes for one compiler will likely get messed up in another compiler.

You mean like intrinsics? Sure.

> I’m wondering if they time spent in writing asm for av1 could also be spend in writing an optimising pass for the c compiler?

Frankly, no.

Improving the compiler could get a few dozen of %, which is huge already. But 300%+, no.

All of the performance wins you’re referencing come from vectorization, you typically can’t vectorize OS code since it isn’t ALU bound, which makes your point moot.

> you typically can’t vectorize OS code since it isn’t ALU bound

The answer and parent were in no way only talking about OS.

The parent was definitely talking about the applicability of using assembly in the context of this project. Vectorization is irrelevant here.

> by 4,5x on AVX2

I would expect a much smaller gap as AVX2 is also available through intrinsics on C ?!

CPU intrinsics are just another way of doing inline Assembly.

False or vacuously true

IANA C/C++/ASM expert, but one thing I've been thinking of would greatly benefit from type-punning (overlaying 2 kinds of data and interpreting one as the other) because it can use a 64-bit register to parallelise 4 ops at once where speed really, really matters.

That's trivial in ASM I believe, but don't know how well it's possible in C/C++, if at all.

Type punning in general would be somewhat difficult to do here in a way that vectorized but was still defined by the standard. You’d need to put a branch with undefined behavior in it when alignment wasn’t satisfied, then do a memcpy into a vector type, and hope that the compiler understands what you’re doing and doesn’t deoptimize it.

I fail to see why not just use a __m64 variable and do the conversion.

https://software.intel.com/sites/landingpage/IntrinsicsGuide...

You can also try to make a union whose one field is a __m64, but beware not to trigger UB conditions.

That is still writing asm. You need to write it, the compiler cannot do it by itself.

When using Clang org CC (possibly other compilers, too), you don’t need to use intrinsics. These compilers have some support for vector types (https://clang.llvm.org/docs/LanguageExtensions.html#vectors-..., https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html)

One can, for example, write:

  typedef int v4si __attribute__ ((vector_size (16)));

  v4si a, b, c;
  […]
  b += 3; // add 3 to each of b’s elements
  c = a + b; // pairwise addition

Using this gives up some control over assembly; it doesn’t guarantee vector instructions get used, but it makes it easier for the compiler to generate them.

Also, I’m fairly sure there are vector instructions not covered by this extension.

Video coding is one of the few outliers where compilers are not very good at the kind of optimisations that really help. Any experiences with that kind of code does not generalise to other types of code.

How much would something like Halide help with writing optimized code for AV1? It's originally designed for image manipulation, but I imagine encoding/decoding to be a little bit more demanding of expressiveness.

https://halide-lang.org/

When I worked with Halide, on a thing that is relatively close to the image decoding (transform a series of angle-amplitude pairs (radioastronomy) to the image, a lot of sprite-with-opaqueness painting), I was perplexed to find out how hard it is to work in Halide with non-constant offsets. The functionality was essentially non-existent back then (2015, I assume).

In fact, any scatter-gather operations were non-existent in Halide.

From what I remember these operations were introduced at some point, but we moved away from Halide.

Also, it was not quite simple to transform a loop that draws sprites over the entire image into a loop that draw sprites over part of image and draws many parts of image in parallel (change nesting). Hand-written CUDA version of the algorithm ended up with exactly that.

Thus, if you need some partial-derivatives-numerical-kernel, Halide is good for you. If you are working on the video decoding, Halide is not that good for you. If you are working on video encoding, Halide will be more of a nuisance than a helping hand (early exits from loops, computable access ranges, etc).

That is all very interesting. If you were drawing sprites, why not use straight openGL?

Do you think it would have worked to organize tiles and threads outside of halide and use halide for isolated parts that are already organized into arrays?

I suppose Halide was mainly involved for this part:

> transform a series of angle-amplitude pairs (radioastronomy) to the image

We would like to be relatively target-agnostic. OpenGL could be one of targets, but not only one. We also would like to work on regular and/or GPU-equipped cluster machines, etc.

On the suggestion in your second part: why use Halide then? Should it be responsibility of Halide to work out the best loop nesting and best use of threads?

Again, Halide was put aside and we used CUDA for final version, exactly because of inability of Halide to do good work in our case.

> Should it be responsibility of Halide to work out the best loop nesting and best use of threads?

I don't know about "should", but it seems to me that it would still be valuable, even if working out the threading and organization.of the data into an array.

> Again, Halide was put aside and we used CUDA for final version, exactly because of inability of Halide to do good work in our case

I didn't say anything about that. I'm not sure why you are restating it.

> We're not talking about a few percents, we're talking about multiple times faster.

I wonder how long it will take for compilers close that gap. I assume compilers will eventually produce assembly code that outperforms anything written by human.

These aren't necessarily the typical use cases that compiler writers are trying to optimize, either. So, compilers for general purpose languages may never close that gap.

Have you seen a non asm low level language that could fit hardware better than C ? Not starting a flamewar, just that it seems that you're in a context where you may have reviewed things we might not know of.

I hear tell that a lot of the places where modern Fortran shows up are contexts where faster-than-C performance is desirable.

But that's plausibly the compiler doing its magic. Or is there anything in Fortran language/semantics that maps close to vectorized ISAs ?

A company I used to work for has spent 30 years trying to migrate FORTRAN code to C. I was not involved in the project, so I don't know the details, but the gist of what I was told is that there are edge cases where FORTRAN stomps C in every performance metric. So you can make decent progress for a while, but you'll eventually hit a major roadblock that halts progress.

I think of the BLAS algos as being very Fortran friendly, and the Fortran references never _out_perform the C implementations. (The asm implementations are of course the best.)

Be curious to know what you're thinking of here.

I've no personal experience, but people historically point to pointer aliasing as the primary thing that speeds up Fortran code vs C.

https://en.wikipedia.org/wiki/Pointer_aliasing

No personal experience either but discussing with people invested in high perf C, they said that `restrict` was enough to avoid aliasing issues.

ISPC in this case is exactly that. It makes vectorization fairly easy and very fast.

I've done some bare-metal development in Ada. It was originally designed for embedded systems, so it has features that fit this niche very well. It's definitely not as simple as C, it has a much more modern design however.

Reply on news.ycombinator.com