modexp optimizations

Abierto
#1,665 1 comentario 0 reacciones 0 asignados Ver en GitHub

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

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 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
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

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de ipsilon/evmone

Todos los issues de ipsilon/evmone

Issues similares

Más issues de C++

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.