Performance Optimizations

[sfluhrer]

This is a proposed performance optimization; the improvements I see (measured on my Xeon) are:

• For F-ref parameter sets, I see a fairly consistent 4% speed-up
• For S-ref parameter sets, I don't see much (perhaps a 1% speed-up)
• For Haraka-AES_NI and SHAKE256-AVX2 parameter sets, I see a 10%-20% speed-up
• For SHA256-AVX2 parameter sets, I see a 20-35% speed-up (with 128s getting the 30+%)

Now, as for a summary of the changes:

• The largest change is I reorganized how the x4 and x8 (AVX2 and AES_NI) implementations worked. In the old code, it would process 4 or 8 FORS trees in parallel; however since the number of FORS trees in not a multiple of 4 or 8, that means that for the last couple FORS trees, it would ignore several of the parallel tracks. What I did is work on one FORS tree at a time; I would generate 4 or 8 leaf nodes at once, and then in the FORS tree itself, combine 4 or 8 nodes at a time (see fors_gen_leafx[48] and treehashx[48]). That way, except for the top 2 or 3 FORS levels, I use every track to compute something useful
• Similarly, in the old code, the previous code would process 4 or 8 WOTS chains in parallel; however the number of chains is not a multiple of 4 or 8. The new code generates 4 or 8 WOTS+ public keys in parallel (wots_gen_leafx[48]), and then uses the same logic to compute the Merkle tree.
• I also combined the wots signature and the Merkle tree signature together. That is, as a side effect of generating the Merkle tree, I would notice when we were visiting the 'active' WOTS+ public key, and when we were, extracting the WOTS+ signature values as we computed them (rather than recomputing the WOTS chains a second time). I believe that's responsible for the 4% speed-up on the reference F implementations (which use short trees, hence the WOTS signature was a significant part of the computation).
• In addition, instead of treating the x4 and x8 versions as a 'special case', I unified that with the reference implementation (which has x1 routines)
• Finally, I modified the benchmark.c routine, and removed test/wots.c from the Makefile (as the API it tested no longer exists)

Enjoy!

[bwesterb]

Oh, btw, did you check that test vectors didn't change? (As this changes both ref and the optimised versions.)

[sfluhrer]

Yes, I did verify the test vectors, for both the reference and the optimized versions. A diff between the current version and the new version showed no differences.

From: Bas Westerbaan notifications@github.com Sent: Monday, October 05, 2020 7:58 AM To: sphincs/sphincsplus sphincsplus@noreply.github.com Cc: Scott Fluhrer (sfluhrer) sfluhrer@cisco.com; Author author@noreply.github.com Subject: Re: [sphincs/sphincsplus] Performance Optimizations (#16)

Oh, btw, did you check that test vectors didn't change? (As this changes both ref and the optimised versions.)

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHubhttps://github.com/sphincs/sphincsplus/pull/16#issuecomment-703584209, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB5KPWUR6ATWBMGICAGWHYTSJGYD5ANCNFSM4RSQ33SA.