4 ms·
The code in the blog post does not match what is actually benchmarked. The reason `u256_full_mul` is so much faster than the inline assembly version is that it
by pbsd 8y ago
The code in the blog post does not match what is actually benchmarked. The reason `u256_full_mul` is so much faster than the inline assembly version is that it omits the upper part of the result, due to how the benchmark is done (cf. https://github.com/paritytech/bigint/blob/44a3133030306d9fcc9865b2e8e8368f6992cc98/benches/bigint.rs#L114-L115 https://github.com/paritytech/bigint/blob/44a3133030306d9fcc...). There should be 16 full 64x64->128 multiplications (unless you're doing Karatsuba, which is not the case here) in a full 256-bit multiplication, but I only count 6 in the benchmark's inner loop (plus 4 64x64->64 multiplications). No wonder it's faster.
The disassembly for the Rust output of `u256_full_mul` at the end is also terrible, and it looks like the output of a debug build. There's no reason an optimizing compiler should be outputting `pushfd` and `popfd` in performant code. The benchmarked loop does not have those instructions.
- nonsince 8y agoIt's possible that `pushfq`+`popfq` get turned into a `mov` from the flag register into a the output register due to microcode-level optimisations.
- pbsd 8y agoThat is not the case. On a Skylake chip, a pushfd + popfd roundtrip costs 24 cycles.
- feikname 8y agoJust out of curiosity, how do you know this? Is it some kind of measurement you made yourself, written on Intel docs somewhere or something else? I've been wondering about how much instructions cost lately and would like to be able to know this without the need of asking others.
- pbsd 8y agoAgner's instruction listings [1] and InstLatX64 [2] are good sources for a variety of chips. The 24 cycle figure above can be seen at https://github.com/InstLatx64/InstLatx64/blob/ee13abcfb1e2bb8207737a362daa73d7c9ed66a8/GenuineIntel00506E3_Skylake2_InstLatX64.txt#L625-L628 https://github.com/InstLatx64/InstLatx64/blob/ee13abcfb1e2bb... [1] http://www.agner.org/optimize/#manuals http://www.agner.org/optimize/#manuals [2] https://github.com/InstLatx64 https://github.com/InstLatx64
- koverstreet 8y agoThere's also the intel optimization manuals.
- ajross 8y agoPUSH/POPF* instructions push the flags register to save comparison results when you need to reuse the registers containing the original comparison arguments. They're well-pipelined, integrated with the stack engine and very fast on modern CPUs, and I've definitely seen the compiler emit them (more on i686 than x86_64 to be fair). I won't speak to the quality of the generated code otherwise, but this bit of evidence by itself doesn't seem persuasive. (edit: pbsd is right: per Agner Fog, these guys are slow. It's likely that the L/SAHF trick is the one I was remembering.)
- pbsd 8y agoWhere are you getting that from? `pushfd` is OK-ish, but `popfd` is microcoded, requires 9 uops, and can only be issued once every ~20 cycles. That's not what I would call well-pipelined. You could probably achieve the same result (assuming you want to avoid adc instructions, for some reason) by using setc r8 plus shr r8, 1 to get the carry back.
- nonsince 8y agoIf you use `-C target-cpu=native` (Rust's equivalent of `-march=native`) you get code that uses `mulxq` in order to avoid `pushf`/`popf`. https://gist.github.com/Vurich/5cb83c773e90fc7a463ccb58e1dad4e3 https://gist.github.com/Vurich/5cb83c773e90fc7a463ccb58e1dad...
- pbsd 8y agoIt's still doing it, but now it uses `lahf` + `sahf` instead to (re)store the flags. These are better than pushf + popf for sure, but they cannot be used in general code because some early x86_64 chips forgot to implement them.
- deaddodo 8y agoIf your general code is only intended to be used on newer versions of Windows, you can. Windows has required it since 8.1.