[WIP, Please benchmark] Use Co-Z in pippenger #1782

1. 
   peterdettman commented at 11:56 am on December 9, 2025: contributor

   Modifies the pippenger bucket-summing loop. Very early code, just here to get benchmarks of the basic concept.

   In short, we ensure running_sum always has the same z coordinate as the accumulator (“r”), so that adding running_sum to r can be done in 5M + 2S (with free update of running_sum for the new Co-Z coordinate); this is often called a ZADDU (or DBLU when it devolves to doubling). On the downside, when adding each bucket to the running_sum, we now need to also update r to keep them Co-Z; cost 3M + 1S. So a typical iteration of the summing loop costs 20M + 7S instead of 24M + 8S.

   I measure a few % overall improvement for pippenger_wnaf, depending on the number of points, although I would appreciate others sanity-checking that. Unfortunately it involves rather a lot of new code, not helped by the fact that there are special cases everywhere.

2. Prototype using CoZ arithmetic in pippenger_wnaf d95e48b089
3. peterdettman marked this as a draft on Dec 9, 2025
4. 
   john-moffett commented at 6:52 pm on December 9, 2025: contributor

   Apple M2 Max, default build. Master vs d95e48b089778de9ca992cc5dfbabd6674d8c2d4

    0secp256k1 configure summary
    1===========================
    2Build artifacts:
    3  library type ........................ Shared
    4Optional modules:
    5  ECDH ................................ ON
    6  ECDSA pubkey recovery ............... OFF
    7  extrakeys ........................... ON
    8  schnorrsig .......................... ON
    9  musig ............................... ON
   10  ElligatorSwift ...................... ON
   11Parameters:
   12  ecmult window size .................. 15
   13  ecmult gen table size ............... 86 KiB
   14Optional features:
   15  assembly ............................ OFF
   16  external callbacks .................. OFF
   17Optional binaries:
   18  benchmark ........................... ON
   19  noverify_tests ...................... ON
   20  tests ............................... ON
   21  exhaustive tests .................... ON
   22  ctime_tests ......................... OFF
   23  examples ............................ OFF
   24
   25Cross compiling ....................... FALSE
   26API visibility attributes ............. ON
   27Valgrind .............................. OFF
   28Preprocessor defined macros ........... ECMULT_WINDOW_SIZE=15 COMB_BLOCKS=43 COMB_TEETH=6
   29C compiler ............................ AppleClang 17.0.0.17000013, /usr/bin/cc
   30CFLAGS ................................ 
   31Compile options ....................... -Wall -pedantic -Wcast-align -Wconditional-uninitialized -Wextra -Wnested-externs -Wno-long-long -Wno-overlength-strings -Wno-unused-function -Wreserved-identifier -Wshadow -Wstrict-prototypes -Wundef
   32Build type:
   33 - CMAKE_BUILD_TYPE ................... RelWithDebInfo
   34 - CFLAGS ............................. -O2 -g 
   35 - LDFLAGS for executables ............ 
   36 - LDFLAGS for shared libraries ....... 
   

   Benchmark	Before Avg (us)	After Avg (us)	Δ Avg (us)	Δ Avg %
   ecmult_multi_79p_g	7.81	7.85	+0.04	+0.5%
   ecmult_multi_95p_g	7.47	7.32	-0.15	-2.0%
   ecmult_multi_111p_g	7.24	7.03	-0.21	-2.9%
   ecmult_multi_127p_g	7.15	6.87	-0.28	-3.9%
   ecmult_multi_159p_g	6.85	6.49	-0.36	-5.3%
   ecmult_multi_191p_g	6.57	6.25	-0.32	-4.9%
   ecmult_multi_223p_g	6.28	6.08	-0.20	-3.2%
   ecmult_multi_255p_g	6.23	5.99	-0.24	-3.9%
   ecmult_multi_319p_g	5.86	5.71	-0.15	-2.6%
   ecmult_multi_383p_g	5.71	5.59	-0.12	-2.1%
   ecmult_multi_447p_g	5.48	5.41	-0.07	-1.3%
   ecmult_multi_511p_g	5.35	5.28	-0.07	-1.3%
   ecmult_multi_639p_g	5.33	5.20	-0.13	-2.4%
   ecmult_multi_767p_g	5.04	5.06	+0.02	+0.4%
   ecmult_multi_895p_g	4.96	4.88	-0.08	-1.6%
   ecmult_multi_1023p_g	4.88	4.89	+0.01	+0.2%
   ecmult_multi_1279p_g	4.76	4.67	-0.09	-1.9%
   ecmult_multi_1535p_g	4.59	4.51	-0.08	-1.7%
   ecmult_multi_1791p_g	4.46	4.36	-0.10	-2.2%
   ecmult_multi_2047p_g	4.36	4.29	-0.07	-1.6%
   ecmult_multi_2559p_g	4.24	4.18	-0.06	-1.4%
   ecmult_multi_3071p_g	4.14	4.06	-0.08	-1.9%
   ecmult_multi_3583p_g	4.19	4.04	-0.15	-3.6%
   ecmult_multi_4095p_g	4.04	3.95	-0.09	-2.2%
   ecmult_multi_5119p_g	3.93	3.86	-0.07	-1.8%
   ecmult_multi_6143p_g	3.82	3.78	-0.04	-1.0%
   ecmult_multi_7167p_g	3.79	3.76	-0.03	-0.8%
   ecmult_multi_8191p_g	3.75	3.65	-0.10	-2.7%
   ecmult_multi_10239p_g	3.63	3.57	-0.06	-1.7%
   ecmult_multi_12287p_g	3.57	3.51	-0.06	-1.7%
   ecmult_multi_14335p_g	3.50	3.48	-0.02	-0.6%
   ecmult_multi_16383p_g	3.53	3.38	-0.15	-4.2%
   ecmult_multi_20479p_g	3.42	3.31	-0.11	-3.2%
   ecmult_multi_24575p_g	3.29	3.30	+0.01	+0.3%
   ecmult_multi_28671p_g	3.22	3.14	-0.08	-2.5%
   ecmult_multi_32767p_g	3.19	3.10	-0.09	-2.8%

Contributors
peterdettman john-moffett