Re: [PATCH] crypto: ecc - Optimize vli additive operations using compiler builtins

[Herbert Xu <herbert@gondor.apana.org.au>]

On Sun, Jun 07, 2026 at 01:24:35PM +0200, Fabian Blatter wrote:
> Replace the software carry flag emulation with compiler builtins.
> 
> Even the newest compilers struggle with taking advantage of the
> hardware carry flag. Compiler builtins allow the compiler to
> much more easily achieve this while still remaining constant-time.
> 
> This yields an approximately 6-7% performance improvement
> on the ecc_gen_privkey, ecc_make_pub_key and crypto_ecdh_shared_secret
> functions on x86_64 on all curve sizes.
> 
> Additionally, the code becomes much more readable.
> 
> Signed-off-by: Fabian Blatter <fabianblatter09@gmail.com>
> ---
> 
> Hi,
> 
> I'd like to expand on the benchmarks, compare the generated assembly,
> and clarify some things.
> 
> 
> Use of compiler builtins:
> 
> This patch uses __builtin_addcll, __builtin_subcll when available and
> otherwise __builtin_uaddll_overflow, __builtin_usubll_overflow. the
> latter have existed since ancient gcc versions, so no third fallback
> is needed.
> 
> I have put the add_carry and sub_borrow inline functions with the
> preprocessor logic for builtin selection directly in crypto/ecc.c.
> Please let me know if you would like them to be somewhere else.
> 
> They do not emit data-dependent branches, and so remain constant-time.
> 
> 
> Benchmarks:
> 
> All benchmarks were run single-threaded on my AMD 7700X CPU limited to
> 5.6Ghz. I have measured both nanoseconds and clock cycles, since their
> combination can hint at downclocking issues and allows calculation of
> the clock speed during the benchmark.
> 
> I have omitted the raw output from the benchmarking code, as they much
> exceed the 72 character limit.
> 
> I have calculated the percent differences, included clock speed
> calculations and relevant summaries.
> 
> 
> Macro benchmarks:
> 
> These were run in a virtualized environment using virtme-ng on the
> compiled linux kernel image compiled with default flags.
> 
> (the first value is the original time per operation, the second the
> patched one. cc is short for clock cycles)
> 
> Curve keypair generation (ecc_gen_privkey + ecc_make_pub_key):
> 
> P256:
>  - 646963ns/op -> 600632ns/op = -7.71%
>  - 2911300cc/op -> 2702854cc/op = -7.71%
>  - 4.4999Ghz -> 4.5000Ghz = no difference
> 
> P384:
>  - 1239160ns/op -> 1153940ns/op = -7.38%
>  - 5576250cc/op -> 5192749cc/op = -7.38%
>  - 4.5000Ghz -> 4.5000Ghz = no difference
> 
> Shared secret generation (crypto_ecdh_shared_secret):
> 
> P256:
>  - 320114ns/op -> 297548ns/op = -7.58%
>  - 1440521cc/op -> 1338972cc/op = -7.58%
>  - 4.5000Ghz -> 4.5000Ghz = no difference
> 
> P384:
>  - 620768ns/op -> 582560ns/op = -6.55%
>  - 2793467cc/op -> 2621529cc/op = -6.55%
>  - 4.5000Ghz -> 4.5000Ghz = no difference
> 
> The benchmarks clearly indicate a roughly 6-7% performance increase on
> the public API functions. It also appears that virtme-ng limited the
> clock speed to 4.5Ghz
> 
> 
> Micro benchmarks:
> 
> Since the vli additive functions only rely on u64 being defined, these
> were run without virtualization and with varying compilers and
> compiler flags.
> 
> The microbenchmarks show much more mixed results, depending
> heavily on the compiler and optimization level used.
> 
> For instance, on gcc and O2, the vli_add present in the
> patch is actually 25.3% slower than the original one. I have tracked
> this down to gcc using a weird way to restore the carry flag after
> each iteration, causing way more dependent instructions, preventing
> ILP from executing multiple at once.
> 
> This is quite interesting, since, as far as I know, the kernel compiles
> with gcc and O2 by default, yet the macro-level benchmarks still show a
> performance increase. The effect seems to be reversed when crypto/ecc.c
> gets compiled. Or maybe the linux kernel uses some additional
> optimization flags, I am unsure.
> 
> However, most of the time, the patched version outperforms the original
> one by a wide margin:
>  - On clang -O2 or -O3, vli_add and vli_uadd show a 4.074x and 5.384x
>    speedup.
>  - On gcc, vli_uadd shows a 74% performance increase at O2, 
>    and a 2.07x speedup at O3.
> 
> The performance profile of vli_sub and vli_usub is almost identical to
> that of vli_add and vli_uadd.
> 
> 
> Assembly comparison:
> 
> I have put together a piece of code on Compiler explorer, to make sure
> it compiles on old gcc versions, view instructions and play around with
> compiler settings.
> 
> If you would like, you can play around yourself here:
> https://godbolt.org/z/1jT5zesz8
> 
> When using clang 22.1 at -O3 -march=lunarlake, the difference between
> the patched and original version is particularly clear. The patched
> version produces this assembly in the unrolled vli_add loop:
> 
> mov     rax, qword ptr [rsi + 8*rcx + 16]
> adc     rax, qword ptr [rdx + 8*rcx + 16]
> mov     qword ptr [rdi + 8*rcx + 16], rax
> mov     rax, qword ptr [rsi + 8*rcx + 24]
> adc     rax, qword ptr [rdx + 8*rcx + 24]
> mov     qword ptr [rdi + 8*rcx + 24], rax
> mov     rax, qword ptr [rsi + 8*rcx + 32]
> adc     rax, qword ptr [rdx + 8*rcx + 32]
> mov     qword ptr [rdi + 8*rcx + 32], rax
> mov     rax, qword ptr [rsi + 8*rcx + 40]
> adc     rax, qword ptr [rdx + 8*rcx + 40]
> mov     qword ptr [rdi + 8*rcx + 40], rax
> mov     rax, qword ptr [rsi + 8*rcx + 48]
> adc     rax, qword ptr [rdx + 8*rcx + 48]
> 
> This is basically optimal for an inner loop. It's pure adc and mov
> instructions. The loop counting part is still nowhere near perfect,
> and still uses setc instructions. But it is still better than what
> the original version produces with the same compiler and flags:
> 
> mov     r10, qword ptr [rsi + 8*rcx]
> lea     r11, [r10 + rax]
> add     r11, qword ptr [rdx + 8*rcx]
> xor     ebx, ebx
> cmp     r11, r10
> setb    bl
> cmove   rbx, rax
> mov     qword ptr [rdi + 8*rcx], r11
> mov     rax, qword ptr [rsi + 8*rcx + 8]
> lea     r10, [rax + rbx]
> add     r10, qword ptr [rdx + 8*rcx + 8]
> xor     r11d, r11d
> cmp     r10, rax
> setb    r11b
> cmove   r11, rbx
> mov     qword ptr [rdi + 8*rcx + 8], r10
> mov     rax, qword ptr [rsi + 8*rcx + 16]
> lea     r10, [rax + r11]
> add     r10, qword ptr [rdx + 8*rcx + 16]
> xor     ebx, ebx
> cmp     r10, rax
> setb    bl
> cmove   rbx, r11
> mov     qword ptr [rdi + 8*rcx + 16], r10
> mov     rax, qword ptr [rsi + 8*rcx + 24]
> lea     r10, [rax + rbx]
> add     r10, qword ptr [rdx + 8*rcx + 24]
> xor     r11d, r11d
> cmp     r10, rax
> setb    r11b
> cmove   r11, rbx
> 
> This is downright horrendous. that entire block of processes only 4
> limbs, thats 8 instructions per limb! The add instructions
> are also not adc instructions, showing that the carry flag is
> being fully emulated. This demonstrates how even on the newest
> compilers and at the highest optimization level, still cannot
> generate hardware carry chains without explicit use of builtins.
> 
> I should note that not just clang 22.1.0 with -O3 -march=lunarlake
> does this. Gcc and clang show this behaviour on every version i have
> tested, regardless of target architecture.
> 
> I am not very familiar with ARM or RISC-V assembly, but looking at
> compiler explorer, the effect clearly persists, and in the case of
> RISC-V actually gets much worse.
> 
> This affects all architectures across all compilers and compiler
> flags.
> 
> 
> If you have gotten this far, thank you for reading this and I am looking
> forward to any feedback! If you would like any changes to this patch,
> I am very happy to send a v2.
> 
>  crypto/ecc.c | 98 ++++++++++++++++++++++++++++++++--------------------
>  1 file changed, 60 insertions(+), 38 deletions(-)

Patch applied.  Thanks.
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt