search

zcash / pasta_curves

Rust implementation for zcash/pasta
Other
80 stars 49 forks source link

replace double with bit shift #50

Open str4d opened 1 year ago

str4d commented 1 year ago

Extracted from https://github.com/zcash/pasta_curves/pull/44.

codecov-commenter commented 1 year ago

Codecov Report

Base: 66.15% // Head: 60.44% // Decreases project coverage by -5.71% :warning:

Coverage data is based on head (9b4bfa5) compared to base (682a0e6). Patch coverage: 100.00% of modified lines in pull request are covered.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## main #50 +/- ## ========================================== - Coverage 66.15% 60.44% -5.72% ========================================== Files 12 10 -2 Lines 1427 1221 -206 ========================================== - Hits 944 738 -206 Misses 483 483 ``` | [Impacted Files](https://codecov.io/gh/zcash/pasta_curves/pull/50?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash) | Coverage Δ | | |---|---|---| | [src/fields/fp.rs](https://codecov.io/gh/zcash/pasta_curves/pull/50/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash#diff-c3JjL2ZpZWxkcy9mcC5ycw==) | `76.28% <100.00%> (-4.00%)` | :arrow_down: | | [src/fields/fq.rs](https://codecov.io/gh/zcash/pasta_curves/pull/50/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash#diff-c3JjL2ZpZWxkcy9mcS5ycw==) | `76.28% <100.00%> (-3.43%)` | :arrow_down: | | [src/lib.rs](https://codecov.io/gh/zcash/pasta_curves/pull/50/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash#diff-c3JjL2xpYi5ycw==) | `0.00% <0.00%> (-100.00%)` | :arrow_down: | | [src/macros.rs](https://codecov.io/gh/zcash/pasta_curves/pull/50/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash#diff-c3JjL21hY3Jvcy5ycw==) | `51.61% <0.00%> (-1.73%)` | :arrow_down: | | [src/vesta.rs](https://codecov.io/gh/zcash/pasta_curves/pull/50/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash#diff-c3JjL3Zlc3RhLnJz) | | | | [src/pallas.rs](https://codecov.io/gh/zcash/pasta_curves/pull/50/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash#diff-c3JjL3BhbGxhcy5ycw==) | | | Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=zcash)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

str4d commented 1 year ago

Hmm, this implementation does not appear to be more efficient. I ran:

$ rustc +stable --version
rustc 1.64.0 (a55dd71d5 2022-09-19)
$ cargo +stable asm --lib "<pasta_curves::fields::fp::Fp as ff::Field>::double"

once on current main and again on this PR, and got the following assembly:

Current main ```asm .section ".text.::double","ax",@progbits .globl ::double .p2align 4, 0x90 .type ::double,@function ::double: .cfi_startproc mov rax, rdi mov rdx, qword ptr [rsi] mov r11, qword ptr [rsi + 8] lea r10, [rdx + rdx] mov r9, qword ptr [rsi + 16] xor edi, edi movabs r8, 7409212017489215487 add r8, r10 adc rdi, -1 shrd rdx, r11, 63 sar rdi, 63 add rdx, rdi adc rdi, 0 movabs r10, -2469829653914515739 add r10, rdx adc rdi, -1 shrd r11, r9, 63 sar rdi, 63 add r11, rdi adc rdi, 0 mov rdx, qword ptr [rsi + 24] sar rdi, 63 shld rdx, r9, 1 add rdx, rdi adc rdi, 0 movabs r9, -4611686018427387904 add r9, rdx adc rdi, -1 movabs rdx, -7409212017489215487 and rdx, rdi movabs rsi, 2469829653914515739 and rsi, rdi movabs rcx, 4611686018427387904 and rcx, rdi add rdx, r8 adc rsi, r10 adc r11, 0 adc rcx, r9 mov qword ptr [rax], rdx mov qword ptr [rax + 8], rsi mov qword ptr [rax + 16], r11 mov qword ptr [rax + 24], rcx ret .size ::double, .Lfunc_end50-::double ```
Current main ```asm .section ".text.::double","ax",@progbits .globl ::double .p2align 4, 0x90 .type ::double,@function ::double: .cfi_startproc push rbx .cfi_def_cfa_offset 16 .cfi_offset rbx, -16 mov rax, rdi mov rdx, qword ptr [rsi] mov rbx, qword ptr [rsi + 8] mov rcx, rbx shld rcx, rdx, 1 add rdx, rdx mov r8, qword ptr [rsi + 16] shrd rbx, r8, 63 mov r9, qword ptr [rsi + 24] shld r9, r8, 1 xor esi, esi movabs r8, 7409212017489215487 add r8, rdx adc rsi, -1 sar rsi, 63 add rcx, rsi adc rsi, 0 movabs r10, -2469829653914515739 add r10, rcx adc rsi, -1 sar rsi, 63 add rbx, rsi adc rsi, 0 sar rsi, 63 add r9, rsi adc rsi, 0 movabs r11, -4611686018427387904 add r11, r9 adc rsi, -1 movabs rdx, -7409212017489215487 and rdx, rsi movabs rcx, 2469829653914515739 and rcx, rsi movabs rdi, 4611686018427387904 and rdi, rsi add rdx, r8 adc rcx, r10 adc rbx, 0 adc rdi, r11 mov qword ptr [rax], rdx mov qword ptr [rax + 8], rcx mov qword ptr [rax + 16], rbx mov qword ptr [rax + 24], rdi pop rbx .cfi_def_cfa_offset 8 ret .size ::double, .Lfunc_end50-::double ```

It looks to me like rustc and LLVM are able to optimise the self.add(self) implementation down to basically the same assembly as the manual bitshifting implementation, while the latter causes a couple of additional assembly instructions to be generated.