modexp optimizations

オープン
#1,665 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 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 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
主要言語
C++
スター
979
フォーク
340
平均マージ
12時間 16分
マージ済み PR(30日)
25

環境構築

  • Dockerfile または Docker Compose ファイルあり
  • プルリクエストのテンプレートなし
  • コントリビューションガイドなし

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

ipsilon/evmone のほかの issue

ipsilon/evmone の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。