Use SIMD?

[Raimo33]

Ever thought about using SIMD intrinsics to speed up some functions?

https://github.com/sipa/secp256k1/blob/master/src%2Ffield_10x26_impl.h

This code for example is full of cases were SIMD would offer great benefit

[Raimo33]

I'm open to implement it myself if it gets decided

[Raimo33]

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

[real-or-random]

Ever thought about using SIMD intrinsics to speed up some functions?

Does this issue answer your question? #1110

sipa/secp256k1@master/src%2Ffield_10x26_impl.h

By the way, this link points to a 10 year old version of the library code (because it points to the the wrong repo).

I'm open to implement it myself if it gets decided

I would be happy to see experimentation with SIMD, and I think we're in general open to the idea, but be aware that we have very high coding and reviewing standards, and not a lot of bandwidth. Reviewing such code will take a long time, and no one can give you a "decision" right now.

[Raimo33]

Ok I will experiment then. do you think I should make separate files or put #ifndefs blocks and embed the SSE2, AVX2, AVX512 versions directly along the already existing functions?

[real-or-random]

I'd start with #ifdef blocks for experimentation. This gets you started quicker if some functions use intrinsics and some don't because you won't need to care about organizing files so that you'll have all the right functions included.

[Raimo33]

hey, quick question:
are the VERIFY blocks for debugging or not? in other words, should I optimize them?
for example:

#ifdef VERIFY
static void secp256k1_fe_impl_verify(const secp256k1_fe *a) {
    const uint64_t *d = a->n;
    int m = a->normalized ? 1 : 2 * a->magnitude;
   /* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
    VERIFY_CHECK(d[0] <= 0xFFFFFFFFFFFFFULL * m);
    VERIFY_CHECK(d[1] <= 0xFFFFFFFFFFFFFULL * m);
    VERIFY_CHECK(d[2] <= 0xFFFFFFFFFFFFFULL * m);
    VERIFY_CHECK(d[3] <= 0xFFFFFFFFFFFFFULL * m);
    VERIFY_CHECK(d[4] <= 0x0FFFFFFFFFFFFULL * m);
    if (a->normalized) {
        if ((d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
            VERIFY_CHECK(d[0] < 0xFFFFEFFFFFC2FULL);
        }
    }
}
#endif
`

[real-or-random]

Yes, essentially. The VERIFY blocks and the VERIFY_CHECK macros are for assertions enabled only in the tests. No need to add SIMD there.

[Raimo33]

I've added SIMD to field_5x52_impl.h
Please share feedback and let me know if I should continue with the other files.

I ran the benchmarks (both with avx2 enabled, to see difference between auto-generated simd and manual simd). I ran benchmarks thoroughly to ensure every change was meaningful.
I don't have an avx512 CPU so I'm unable to run some tests & benchmarks for the secp256k1_fe_impl_get_b32 function. But it should be much faster as well.

Code: https://github.com/Raimo33/secp256k1/blob/simd/src/field_5x52_impl.h
Benchmarks:

bench_diff.pdf
bench.zip

Keep in mind that the only file I changed was field_5x52_impl.h, Imagine the possible speedup by applying simd to all other files as well. I see a lot of room for improvement and I would have a lot of fun implementing it.

[Raimo33]

As a side note, if you decide to integrate SIMD you'd need to change the CI pipeline and tests to compile with different flags. And ensure that the running machine supports avx intrinsics. Or maybe use some emulator if there is

[Raimo33]

it seems that no function of field_10x26_impl.h ever get's compiled in the final binaries and it's never tested. I can add garbage to field_10x26_impl.h, run the ctest . and everything still passes.

I'm avoiding optimization of field_10x26_impl.h as I see no way to test correctness.

[real-or-random]

We have two finite implementations:

• One that represents a field element by 5 limbs of uint64_t, where 52 bits are used if elements are reduced (5x52). This is used on 64-bit platforms.
• One that represents a field element by 10 limbs of uint32_t where 26 bits are used if elements are fully reduced (10x26). This is used on 32-bit platforms.

When using cmake, create a build32 dir and run CC="$CC -m32" cmake -B build32. This should set up a 32-bit build on x86_64.

[real-or-random]

Oh, but in case this was not obvious: You won't find an x86 (32-bit) CPU with AVX...

[Raimo33]

Not a problem for compiling, I can still set the -avx2 flag. But I guess problem for running. I'm not familiar to how my 64bit CPU runs 32bit programs, but I thought it still used AVX2.

But at this point do you think I should avoid adding SIMD to the whole field_10x26?

[real-or-random]

I've added SIMD to field_5x52_impl.h Please share feedback and let me know if I should continue with the other files.

I think it would be better to open a draft pull request. This makes it easier for people to look at the changes.

I ran the benchmarks (both with avx2 enabled, to see difference between auto-generated simd and manual simd). I ran benchmarks thoroughly to ensure every change was meaningful. I don't have an avx512 CPU so I'm unable to run some tests & benchmarks for the secp256k1_fe_impl_get_b32 function. But it should be much faster as well.

Code: Raimo33/secp256k1@simd/src/field_5x52_impl.h Benchmarks:

bench_diff.pdf

Hm, that doesn't draw a very consistent picture. Did you disable turbo boost? Do you know that you can increase the number of benchmark iterations by setting SECP256K1_BENCH_ITERS?

Keep in mind that the only file I changed was field_5x52_impl.h, Imagine the possible speedup by applying simd to all other files as well. I see a lot of room for improvement and I would have a lot of fun implementing it.

I'm not sure. I assume this is the file with the biggest potential. Bigger improvements might be possible by changing the algorithms or even the data structure so that they're more amenable to vectorization. (No idea if this is possible; I haven't thought about this or read up on it.)