ecmult_multi: reduce strauss memory usage by 30% #1761

1. 
   jonasnick commented at 2:28 pm on October 17, 2025: contributor

   This is a draft because I’m not sure about the cleanest way to implement it.
2. ecmult_multi: reduce strauss memory usage by 30% 26166c4f5f
3. real-or-random added the label performance on Oct 27, 2025
4. 
   real-or-random commented at 8:02 am on October 27, 2025: contributor

   This is a draft because I’m not sure about the cleanest way to implement it.

   The current approach looks clean. What other approaches do you have in mind?

5. real-or-random added the label tweak/refactor on Oct 27, 2025
6. in src/ecmult_impl.h:239 in 26166c4f5f

   236+}
   237+
   238 struct secp256k1_strauss_point_state {
   239-    int wnaf_na_1[129];
   240-    int wnaf_na_lam[129];
   241+    int8_t wnaf_na_1[129];
   

   ---

   ---

   

   real-or-random commented at 8:10 am on October 27, 2025:

   0    int_least8_t wnaf_na_1[129];
   

   This is technically better to retain support for platforms that don’t offer int8_t. I don’t think there are any relevant platforms of that kind, but why not… 🤷

   edit: Now that I think about it again, a platform that does not offer int8_t will most likely one for which CHAR_BITS != 8. And then it’s neither relevant nor it’s likely to offer int32_t or int64_t which we need anyway. So I guess there’s no difference between int8_t and int_least8_t.

   ---

   

   hebasto commented at 4:58 pm on October 27, 2025:

   This is technically better to retain support for platforms that don’t offer int8_t.

   int8_t is already used in src/assumptions.h.

7. 
   hebasto commented at 4:47 pm on October 27, 2025: member

   Concept ACK.
8. 
   hebasto commented at 6:00 pm on October 27, 2025: member

   On my x86_64 system, this PR reduces the memory allocated on the scratch space from 2224 bytes to 1452 bytes per point.

   Please ping me once it’s undrafted.

9. 
   jonasnick commented at 6:52 pm on October 27, 2025: contributor

   The current approach requires a temporary array int wnaf_tmp[256]; to provide to secp256k1_ecmult_wnaf which looks unclean. The alternatives are

   1. copy almost all of secp256k1_ecmult_wnaf into secp256k1_ecmult_wnaf_small, or
   2. remove secp256k1_ecmult_wnaf_small and write an secp256k1_ecmult macro.

   Both options seem to be worse.

10. 
    hebasto commented at 10:00 pm on October 27, 2025: member

    The current approach requires a temporary array int wnaf_tmp[256]; to provide to secp256k1_ecmult_wnaf which looks unclean. The alternatives are

    1. copy almost all of secp256k1_ecmult_wnaf into secp256k1_ecmult_wnaf_small, or

    2. remove secp256k1_ecmult_wnaf_small and write an secp256k1_ecmult macro.

    Both options seem to be worse.

    I might suggest a third option: https://github.com/hebasto/secp256k1/commit/5c0d6eeeb2ec9dc8de92f59cf7647a30e6826dcb.

Contributors
jonasnick real-or-random hebasto

Labels
performance tweak/refactor