modexp optimizations
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 18/100
- issue の種類
- リファクタリング
- 明瞭さ
- 説明が足りない
- 活発さ
- 静か
- 技術スタック
- cmake, cpp
調査の方向性
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.
索引モデルが issue の本文から書いたものです。
説明
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
- 主要言語
- C++
- スター
- 979
- フォーク
- 340
- 平均マージ
- 12時間 16分
- マージ済み PR(30日)
- 25
環境構築
- Dockerfile または Docker Compose ファイルあり
- プルリクエストのテンプレートなし
- コントリビューションガイドなし
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
ipsilon/evmone のほかの issue
-
難易度 1/5 1時間未満 初心者へのやさしさ 82/100
メンテナーはふだん 1 日以内に返信
-
難易度 3/5 1〜2日 初心者へのやさしさ 56/100
メンテナーはふだん 1 日以内に返信
-
難易度 3/5 1〜2日 初心者へのやさしさ 57/100
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 12/100
メンテナーはふだん 1 日以内に返信
-
難易度 4/5 3〜5日 初心者へのやさしさ 52/100
メンテナーはふだん 1 日以内に返信
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 71/100
ROCm/rocm-libraries#16108 ·
メンテナーはふだん 2 日以内に返信
-
asr pass bug intrinsic low priority wrong result
難易度 2/5 1〜3時間 初心者へのやさしさ 67/100
メンテナーはふだん 1 日以内に返信
-
👀 needs triage enhancement
難易度 2/5 1〜3時間 初心者へのやさしさ 72/100
rerun-io/rerun#13021 · コメント 1 件 ·
メンテナーはふだん 2 日以内に返信
-
bug
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
メンテナーはふだん 2 日以内に返信
-
audit-reference-check
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
メンテナーはふだん 1 日以内に返信