modexp optimizations
Los mantenedores suelen responder en 1 día
Nadie ha tomado este issue todavía.
Evaluación
- Dificultad
- 5/5
- Tiempo estimado
- Más de una semana
- Aptitud para principiantes
- 18/100
- Tipo de issue
- Refactorización
- Claridad
- Necesita aclaración
- Estado de actividad
- Tranquilo
- Stack tecnológico
- cmake, cpp
- Área
- blockchain, cryptography, performance
Línea de trabajo
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.
Escrito por el modelo de indexación a partir del texto del issue.
Descripción
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
- Lenguaje dominante
- C++
- Estrellas
- 979
- Forks
- 340
- Merge medio
- 12 h 16 min
- PR fusionados (30 d)
- 25
Preparar el entorno
- Incluye un Dockerfile o un archivo de Docker Compose
- Sin plantilla de pull request
- Sin guía de contribución
Primeros pasos
- Lee el issue completo y luego la guía de contribución del proyecto.
- Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
- Haz un fork del repositorio y trabaja en una rama.
- Abre un pull request que haga referencia al número del issue.
Más de ipsilon/evmone
-
Dificultad 1/5 Menos de una hora Aptitud para principiantes 82/100
Los mantenedores suelen responder en 1 día
-
Dificultad 3/5 1-2 días Aptitud para principiantes 56/100
Los mantenedores suelen responder en 1 día
-
Dificultad 3/5 1-2 días Aptitud para principiantes 57/100
Los mantenedores suelen responder en 1 día
-
Dificultad 5/5 Más de una semana Aptitud para principiantes 12/100
Los mantenedores suelen responder en 1 día
-
Dificultad 4/5 3-5 días Aptitud para principiantes 52/100
Los mantenedores suelen responder en 1 día
Todos los issues de ipsilon/evmone
Issues similares
-
Dificultad 2/5 1-3 horas Aptitud para principiantes 71/100
ROCm/rocm-libraries#16108 ·
Los mantenedores suelen responder en 2 días
-
asr pass bug intrinsic low priority wrong result
Dificultad 2/5 1-3 horas Aptitud para principiantes 67/100
Los mantenedores suelen responder en 1 día
-
👀 needs triage enhancement
Dificultad 2/5 1-3 horas Aptitud para principiantes 72/100
rerun-io/rerun#13021 · 1 comentario ·
Los mantenedores suelen responder en 2 días
-
bug
Dificultad 2/5 1-3 horas Aptitud para principiantes 68/100
Los mantenedores suelen responder en 2 días
-
Reference check: findingsAbiertoaudit-reference-check
Dificultad 2/5 1-3 horas Aptitud para principiantes 78/100
Los mantenedores suelen responder en 1 día