9 ms·
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 fro
by jdsully 6y ago
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.
- heeen2 6y agoShouldn't a superscalar CPU figure out concurrent execution chains by itself with register renaming
- jdsully 6y agoIt 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.
- manaskarekar 6y agoTangent, 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 https://youtu.be/bSkpMdDe4g4. And the follow up https://youtu.be/nAbCKa0FzjQ https://youtu.be/nAbCKa0FzjQ.
- battery_cowboy 6y agoIt'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.
- celrod 6y agoCPUs 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.
- vardump 6y agoExcept all those times it fails miserably. Like doing this to AVX SIMD.
- bluGill 6y agoCpus 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
- _bxg1 6y agoAre there linters that will overlay compiler-tier optimization hints on top of handwritten assembly?
- sesuximo 6y agoThis 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
- monocasa 6y agoHuh, 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.
- emidln 6y agoYou could try to use one of the c language reversers to get c source code and then ask gcc/clang.
- pandaman 6y agoDon'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).
- CalChris 6y agoThe closest thing would be the Godbolt Compiler Explorer: https://godbolt.org/ https://godbolt.org/
- pjmlp 6y agoIt is nice tool for online exploration, but not as V-Tune.
- dbcurtis 6y ago
- ezoe 6y ago4. 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.
- chas 6y agoUnder 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.
- bluGill 6y agoI 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)
- jjdredd 6y agoWhere could I read about advanced assembly optimization techniques like this?
- bluGill 6y agoIn 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.
- drivebycomment 6y agohttps://www.agner.org/optimize/ https://www.agner.org/optimize/ is the best.
- fallat 6y agoDoing 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) ?
- jdsully 6y agoStrength 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.
- alecco 6y agoHand written 294 lines vs. gcc -O3 526 lines. https://godbolt.org/z/yEcMKf 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.
- msla 6y agoI 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.
- kragen 6y agoI like -Wa,-adhlns=foo.lst -g to see the C, asm, and machine code all together.
- Phylter 6y agoFor 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.
- OrgNet 6y agoin any other language it would be something like if (x-1) != 0