Modular arithmetic: compile-time modulus and per-modulus strategy selection
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
- 難易度
- 5/5
- 見積もり時間
- 1週間以上
- 初心者へのやさしさ
- 18/100
- issue の種類
- リファクタリング
- 明瞭さ
- おおむね明確
- 活発さ
- 静か
- 技術スタック
- cpp
調査の方向性
Start from lib/evmone_precompiles/modarith.hpp and the already-landed steps listed in the issue (#1652, #1657, #1659, #1663). Follow the remaining checklist: rename ModArith/to_mont (#1666), take the modulus as an NTTP (#1664), drop FpSpec for FieldElement<Mod>, then ArithFor and backends. Done means the two-layer design, concept, and backends land with the listed multiplication counts beaten in the precompiles benchmark disassembly; resolve the CodSpeed vs hardware-counter mismatch before treating regressions as real.
索引モデルが issue の本文から書いたものです。
説明
Rework the modular arithmetic in lib/evmone_precompiles/modarith.hpp into two layers: a
FieldElement value type over an arithmetic backend picked per modulus. Both keyed by a
const auto& reference to the modulus, so a backend can classify the modulus itself and no
per-curve tagging is needed:
template <const auto& Mod>
using ArithFor = std::conditional_t<pseudo_mersenne_c(Mod) != 0,
PseudoMersenneArith<Mod>, MontgomeryArith<Mod>>;
Steps
- Move
evmmaxintoevmone::crypto(#1652) - Rename
modinvtomodinv_pow2(#1657) - Extract
modadd/modsub/modinv_scaledas free functions (#1659) - Fix the modarith benchmarks measuring dead code (#1663)
- Rename
ModArithtoMontgomeryArith,to_monttoto_internal(#1666) - Take the modulus as a template parameter (#1664)
- Drop
FpSpec:FieldElement<Mod>instead ofFieldElement<Spec>. The specs hold only
ORDER, and binding a reference NTTP to astatic constexprmember of the enclosing class
works in both GCC and Clang, so the curve headers keep their shape -
FieldArithconcept andArithForselection - Pseudo-Mersenne backend for secp256k1 (p = 2²⁵⁶ − 2³² − 977, plain representation, so the
conversions are identity) -
sqrin the concept, withmul(x, x)as the fallback - Sparse-modulus refinement in
MontgomeryArith:if constexprdeletes the carry tracking.
Requires extracting the multiplication out of the class - Asm kernels with constructor-based cpuid dispatch. Also fixes the latent SIGILL on
crypto/modexp_asm, wheremul_amm_256usestarget("bmi2,adx")guarded only by
#ifdef __x86_64__ -
SolinasArithfor p256, only if it beats the baseline below
Baseline to beat
Multiplications per 256-bit Montgomery multiplication, counted in the disassembly of the linked
precompiles benchmark (GCC 15.2, -O3, x86-64-v2):
| modulus | multiplications | of which imul |
body |
|---|---|---|---|
| bn254 Fp | 36 | 4 | 319 insns |
| secp256k1 Fp | 28 | 4 | 300 insns |
| secp256k1 Fr | 36 | 4 | 317 insns |
| secp256r1 Fp | 28 | 0 | 289 insns |
| secp256r1 n | 36 | 4 | 319 insns |
secp256k1 loses 8 multiplications to its three all-ones limbs, secp256r1 loses 8 to its zero limb
and all four imul because N′ == 1. Both come from constant folding alone, so a hand-written
strategy has to beat 28, not 36.
GCC already clones the multiplication per modulus. Before #1664 it also kept one unspecialised copy
with the modulus loaded from memory, called from secp256k1_ecdsa_recover (8 sites),
secp256r1::verify (7), ecpairing_execute (6), ecadd_execute (6), ecmul_execute (4) and
add_affine<bn254> (4).
Open
- Distinct backend types plus
ArithFor, or one template dispatching internally with
if constexpr? The internal representation differs per strategy, so the conversions branch too. - Redundant limb layouts (5×52) are out of scope.
- CodSpeed simulation reports 2–10% regressions on #1664 where hardware counters show ≤2% change in
instructions and a flat wall clock. #1666 has byte-identical.textand CodSpeed reports no
change on it, so the baseline is not stale. Worth resolving before the gate drives decisions here.
- 主要言語
- 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 日以内に返信