lambdaworks icon indicating copy to clipboard operation
lambdaworks copied to clipboard

Small perf adjustments for `ShortWeierstrassProjectivePoint` operations

Open tcoratger opened this issue 11 months ago • 4 comments

Small perf adjustments for ShortWeierstrassProjectivePoint operations

Description

  • In the double operation, the pull request implements an early return strategy to check if self is the neutral element before performing any further calculations. If self is indeed the neutral element, the function immediately returns a clone of self. This optimization enhances performance by avoiding unnecessary computations, resulting in faster execution.

  • The pull request optimizes the operate_with_affine function by reordering the sequence of operations. Previously, the function performed certain calculations before checking if self or other were neutral elements. This resulted in unnecessary computation overhead. The pull request rectifies this by placing the neutral element check at the beginning of the function. If either self or other is the neutral element, the function terminates early, saving computational costs and improving overall efficiency.

Type of change

Please delete options that are not relevant.

  • [X] Optimization

Checklist

  • [ ] Linked to Github Issue
  • [ ] Unit tests added
  • [ ] This change requires new documentation.
    • [ ] Documentation has been added/updated.
  • [X] This change is an Optimization
    • [ ] Benchmarks added/run

tcoratger avatar Mar 11 '24 10:03 tcoratger

I don't think the first optimization is right. The early return adds an additional branch, so it may make the average case slower, and we usually don't care about optimizing the neutral element case. You need to bench this and compare it, but I highly doubt the additional branch is worth.

MauroToscano avatar Mar 12 '24 18:03 MauroToscano

Codecov Report

Attention: Patch coverage is 87.50000% with 1 lines in your changes are missing coverage. Please review.

Project coverage is 72.32%. Comparing base (52042bf) to head (444379c).

Files Patch % Lines
math/src/elliptic_curve/short_weierstrass/point.rs 87.50% 1 Missing :warning:
Additional details and impacted files
@@            Coverage Diff             @@
##             main     #842      +/-   ##
==========================================
- Coverage   72.32%   72.32%   -0.01%     
==========================================
  Files         147      147              
  Lines       33820    33823       +3     
==========================================
+ Hits        24459    24461       +2     
- Misses       9361     9362       +1     

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

codecov-commenter avatar Mar 12 '24 18:03 codecov-commenter

I don't think the first optimization is right. The early return adds an additional branch, so it may make the average case slower, and we usually don't care about optimizing the neutral element case. You need to bench this and compare it, but I highly doubt the additional branch is worth.

Here is the benchmark for the double case (for the general situation):

  • Before:
point Projective Double | Lambdaworks
                        time:   [364.85 ns 364.97 ns 365.09 ns]
Found 7 outliers among 100 measurements (7.00%)
  5 (5.00%) high mild
  2 (2.00%) high severe
  • After:
point Projective Double | Lambdaworks
                        time:   [364.55 ns 365.17 ns 366.33 ns]
                        change: [-0.1313% +0.0010% +0.1993%] (p = 1.00 > 0.05)
                        No change in performance detected.
Found 10 outliers among 100 measurements (10.00%)
  4 (4.00%) high mild
  6 (6.00%) high severe

tcoratger avatar Mar 12 '24 19:03 tcoratger

@entropidelic Let me know if there is something to do here

tcoratger avatar Mar 27 '24 23:03 tcoratger