Hacker News Reader

Comment by jdsully | Hacker News Reader

The assembly is not bad for a beginner but far from optimal. A few things that stand out from a quick glance:

1) Try to load things sequentially don’t load from offset 32, then 0, then 16.

2) Don’t use the loop instruction

3) this code:

  dec  n
  cmp  n, 0
  jne  1b

Can be replaced with:

  sub n, 1
  jnz 1b

Which will actually be executed by the processor as a single instruction (macro-op fusion).

4) Interleave your expensive instructions with less expensive ones. Try to interleave multiple dependency chains to let the processor see more of the parallelism.

Your two divisions one after another will be limited by available execution units capable of doing the divide.

5) Lastly align your loop labels to 16-byte offsets. The assembler will do this for you with the ALIGN directive.

View on HN

Doing most of your changes made essentially no difference X)

I suspect the assembly generated by the compiler is pretty fancy.

Edit: Just briefly looking at the objdump again, gcc is using a lot of scalar variants of instructions, instead of vector. Maybe this is giving the CPU better hints?

Maybe my code would run better on a more modern CPU (while still constraining the original C program to SSE3 only) ?

Strength reduction and algorithmic changes will make the most difference, but that requires a much deeper look at the code. I wouldn’t be surprised if the compiler found a way to reduce the number of divisions.

If you have a lot of practice the compiler is not difficult to beat. But it definitely takes some effort and study of the optimization manuals.

Hand written 294 lines vs. gcc -O3 526 lines. https://godbolt.org/z/yEcMKf

At a first glance, it seems the compiler version is better at hiding the latency of some of the div instructions. It might be hiding memory access latency, too. But that's more involved analysis.

I don't know why you're using objdump instead of -S to have gcc generate assembly directly.

You get named constants and named labels that way, and you can even choose the sane Intel syntax with -masm=intel which you can also do with objdump.

I like -Wa,-adhlns=foo.lst -g to see the C, asm, and machine code all together.

For x86-64 compilers will use intrinsic instructions which will automatically optimize for that processor. Unless you're really good at knowing the processor you're almost always better off doing it like this. It's almost no benefit writing assembly because of these optimizations these days.

Are there linters that will overlay compiler-tier optimization hints on top of handwritten assembly?

This would be cool. I usually write up some C snippets and compare what different compilers do with what I have. The compiler explorer makes this really easy

Huh, yeah, that'd be neat. Specifically just ripping out the peephole optimizer from a backend just for matching would be a great start with a decent amount of value and not a god tier amount of work.

That being said, you're not going to see the really crazy optimizations that compilers can do, because they need a bit of a higher level view of what you're trying to do.

You could try to use one of the c language reversers to get c source code and then ask gcc/clang.

Don't know of anything that works on the source code level but static analysis in profilers does that for the object code (ones I use are proprietary but I imagine something like V-Tune does this as well).

The closest thing would be the Godbolt Compiler Explorer:

https://godbolt.org/

It is nice tool for online exploration, but not as V-Tune.

I have not looked at it in many years, but Intel's VTune tool was designed to help coders analyze and hand-tune code.

not precisely what you're asking, but there are two tools that annotate machine instructions with results from throughput and latency analysis, which helps with loop microoptimisation.

the original from intel, iaca: https://software.intel.com/en-us/articles/intel-architecture...

newer clone, shipped with llvm: https://llvm.org/docs/CommandGuide/llvm-mca.html

Shouldn't a superscalar CPU figure out concurrent execution chains by itself with register renaming

It will do a bit of that, but remember it has to work in real time and and can only look ahead so far. Give it a fighting chance by helping out whenever you can.

Tangent, but this reminds me of this great talk by Matt Godbolt from CppCon 2017: “What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid”

https://youtu.be/bSkpMdDe4g4.

And the follow up https://youtu.be/nAbCKa0FzjQ.

It's comments like these that make me realize I have a lot to learn about computers, I understand those words separately but together it sounds like a line from star trek.

CPUs can execute multiple instructions per clock cycle (recent x86_64 can do 4-5). However, instructions can take 1 or (commonly) several clock cycles to complete, before their results are available for any instructions depending on said result to start executing. Such dependencies are the babe of superscalar parallelism.

But sometimes things that look like dependencies are fake.

XMM0 = XMM1 + XMM2 XMM3 = XMM0 + XMM4 XMM0 = XMM5 + XMM6 XMM7 = XMM0 + XMM8

At first glance it may look like you have to calculate these instructions serially. But, by renaming the last two `XMM0` you eliminate the dependency on the specific register, and can calculate instructions 1 and 3 in parallel, followed by 2 and 4 in parallel.

Except all those times it fails miserably. Like doing this to AVX SIMD.

Cpus are designed with compiler optimizer experts in the loop. If the compiler can do it the cpu won't try. Instead the cpu does things that the optimizer can't do. Note that this goes both ways, if an optimizer won't use something the cpu won't do it, if the optimizer wants something the cpu will do it. (obviously within the limits of what is possible, and all the other trade offs)

Regiser renaming is designed assuming the optimizer

4. is interesting fact I didn't know. I learned in modern hardware, the simple data structure actually runs faster(linked node vs contiguous storage), but in assembly level, it's still quite opposite I guess.

Under what circumstances to non-contiguous data structures run faster? I know of circumstances where structures with pointers make it easier to get better asymptotic behavior with a large amount of data, but none where a linked structure out-performs the analogous contiguous one on moderate amounts (a few cache lines) of data.

I wondered when he learned that. I learned the same thing in 1996, but modern cpus were not yet (the the knowledge of the class, I'm sure they were doing it...) dining prediction in the cache to load the next required memory before it was required. This optimization changed things such that linear search often is faster than binary search (unless n is very large of course)

Where could I read about advanced assembly optimization techniques like this?

In the data sheets for your cpu. Note that this is cpu specific, even when the instruction set is shared that doesn't mean that the same optimization applies.

https://www.agner.org/optimize/ is the best.

in any other language it would be something like if (x-1) != 0

Reply on news.ycombinator.com