modexp optimizations

Đang mở
#1,665 1 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
18/100
Loại issue
Tái cấu trúc
Độ rõ ràng
Cần làm rõ
Mức độ hoạt động
Ít trao đổi
Công nghệ
cmake, cpp

Hướng nghiên cứu

This is a tracking issue, not a single change: remaining work lives on named branches such as crypto/modexp-opt, crypto/modexp-redc, and crypto/modexp-fixed-cost, plus open PR #1662. Start from the merged modexp/modarith work and the TODOs in precompiles_bench.cpp and test/CMakeLists.txt (CodSpeed pin, cmake-3.26). Done means landing one of the listed follow-ups after rebase, with benchmarks still registered uniformly.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Tracking issue to resume the modexp optimization work and the benchmarking infrastructure it depends on.

Merged

  • #1618 crypto: Use fixed-window exponentiation in modexp
  • #1631 crypto: Use a sliding window in modexp
  • #1619 Build the cryptography code with -O1 in Debug configurations
  • #1654 crypto: Keep the trimmed exponent bytes in a span
  • #1657 crypto: Rename modinv to modinv_pow2
  • #1659 crypto: Extract the representation-independent modular operations
  • #1658 test: Register the precompile benchmarks uniformly
  • #1660 build: Require CMake 3.25
  • #1661 build: Fetch google/benchmark instead of using Hunter
  • #1653 ci: Add CodSpeed continuous benchmarking
  • #1663 test: Fix the modarith benchmarks measuring dead code
  • #1662 crypto: Reduce the exponent for the power-of-two modulus part
  • #1707 crypto: Assert the Montgomery multiplication invariants
  • #1708 crypto: Fold the Montgomery carries into a single addition
  • #1797 crypto: Fix the modexp AMM comment and explain the bound
  • #1803 crypto: Use unsigned __int128 in multiply-accumulate with GCC
  • #1794 crypto: Use INTX_REQUIRE for modexp preconditions
  • #1798 ci: Run CodSpeed with GCC 15 on Ubuntu 26.04

Open

  • #1743 ci: Benchmark the walltime on CodSpeed — draft
  • #1697 ci: Ask CodSpeed for allocation measurements too — draft

To open

Ready, applies to master without conflicts (the full suite last passed on top of #1662):

  • crypto: Convert out of the Montgomery form without multiplying by one (REDC) — branch crypto/modexp-redc

Small and independent, applies to master without conflicts:

  • crypto: Define Exponent::empty() in terms of bit_width() — branch crypto/modexp-exponent-span, follow-up to #1654

Need rebasing or rework first, all on bases 110+ commits behind master:

  • crypto: Fuse the multiply and reduce passes in mul_amm (FIOS) — branch crypto/modexp-opt; conflicts with #1708 in mul_amm
  • crypto: Instantiate the modexp loop for one to three word moduli — branch crypto/modexp-fixed-cost; carries a second Montgomery-exit commit that collides with REDC, so rebase after it
  • test: Cover the modexp window bands and the RSA shape in benchmarks — branch test/modexp-bench-coverage, partly superseded by the sweep now in CodSpeed
  • crypto: Add a plain modexp path for square exponents — branch crypto/modexp-small-exp, base 190 commits behind, effectively a redo

No branch yet:

  • crypto: Force inlining of the multiply-accumulate loops into mul_amm_256 — clang 19 does not inline the span mul() and addmul() from mulmod.hpp. At -O3 it calls the generic addmul() 7 times and keeps the accumulator in memory, on x86-64 and aarch64 alike. GCC 14 and clang 22 inline and unroll them. In Erigon's MODEXP benchmark on amd64, a clang 19 build of evmone is 42–79% slower than a GCC build for a 256-bit modulus, and slower than Go's uint256 loop up to 128-bit exponents. This probably explains the arm64 data point below, which was built with Apple clang. With [[gnu::always_inline]] on both functions, clang 19 emits no calls and the same multiplies as GCC; the speed is not measured yet.
  • crypto: Reduce the modexp fixed per-call cost — the largest remaining lever. Work per gas peaks at ~59 instructions/gas for 2-bit exponents against ~19 for wide ones, because setup, CRT recombination and the conversions are not charged proportionally. Unlike the exponent reduction, this would lower the adversarial maximum rather than only benign inputs.
  • crypto: Handle the even modulus path — follow-up to #1618
  • test: Cover the even base path of modexp_pow2 in the benchmarks — the base is always odd today, so the branch carrying the largest win (up to -75% at k=254) is unbenchmarked. TODO is in precompiles_bench.cpp.

Benchmarking follow-ups

  • Revert the codspeed-cpp fork pin in test/CMakeLists.txt once CodSpeedHQ/codspeed-cpp#55 and #56 land upstream
  • Decide the CodSpeed regression threshold — 1% produced 6 false positives out of 129 benchmarks on #1662
  • Report the CodSpeed misattribution upstream — the flagged regressions are deterministic and reproduce exactly across runs, while instructions, data reads and writes, cache misses, branches and mispredicts are all flat or better; mul_amm's absolute cost is bit-identical and only its percentage share moves
  • Benchmark a clang build too — CodSpeed builds with GCC 15 only (#1798), so the clang 19 inlining gap in mul_amm_256 does not show there
  • Move TODO(cmake-3.26) in test/CMakeLists.txt to FetchContent_Declare(SYSTEM) when the CMake floor reaches 3.26 — the keyword is not stripped before being forwarded to ExternalProject_Add() in 3.25.1, which is what Debian 12 and the gcc-min image ship
Ngôn ngữ chính
C++
Star
979
Fork
340
Merge trung bình
12 giờ 16 phút
Pull request đã merge (30 ngày)
25

Chuẩn bị môi trường

  • Có Dockerfile hoặc tệp Docker Compose
  • Không có mẫu pull request
  • Không có hướng dẫn đóng góp

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của ipsilon/evmone

Tất cả issue của ipsilon/evmone

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.