modexp optimizations
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
- Lĩnh vực
- blockchain, cryptography, performance
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 ofbit_width()— branchcrypto/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 inmul_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 spanmul()andaddmul()from mulmod.hpp. At -O3 it calls the genericaddmul()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_pow2in 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 inprecompiles_bench.cpp.
Benchmarking follow-ups
- Revert the codspeed-cpp fork pin in
test/CMakeLists.txtonce 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_256does not show there - Move
TODO(cmake-3.26)intest/CMakeLists.txttoFetchContent_Declare(SYSTEM)when the CMake floor reaches 3.26 — the keyword is not stripped before being forwarded toExternalProject_Add()in 3.25.1, which is what Debian 12 and thegcc-minimage 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
- Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
- 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.
- Fork repository và làm thay đổi trên một nhánh.
- Mở pull request có tham chiếu số hiệu của issue.
Issue khác của ipsilon/evmone
-
Độ khó 1/5 Dưới một giờ Mức phù hợp với người mới 82/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 56/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 3/5 1-2 ngày Mức phù hợp với người mới 57/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 5/5 Hơn một tuần Mức phù hợp với người mới 12/100
Maintainer thường phản hồi trong vòng 1 ngày
-
Độ khó 4/5 3-5 ngày Mức phù hợp với người mới 52/100
Maintainer thường phản hồi trong vòng 1 ngày
Tất cả issue của ipsilon/evmone
Issue tương tự
-
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 71/100
ROCm/rocm-libraries#16108 ·
Maintainer thường phản hồi trong vòng 2 ngày
-
asr pass bug intrinsic low priority wrong result
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 67/100
Maintainer thường phản hồi trong vòng 1 ngày
-
👀 needs triage enhancement
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 72/100
rerun-io/rerun#13021 · 1 bình luận ·
Maintainer thường phản hồi trong vòng 2 ngày
-
bug
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 68/100
Maintainer thường phản hồi trong vòng 2 ngày
-
Reference check: findingsĐang mởaudit-reference-check
Độ khó 2/5 1-3 giờ Mức phù hợp với người mới 78/100
Maintainer thường phản hồi trong vòng 1 ngày