Specialized double-SHA256 with 64 byte inputs with SSE4.1 and AVX2 #13191

pull sipa wants to merge 7 commits into bitcoin:master from sipa:201709_dsha256_64 changing 16 files +1347 −204
  1. sipa commented at 6:36 pm on May 8, 2018: member

    This introduces a framework for specialized double-SHA256 with 64 byte inputs. 4 different implementations are provided:

    • Generic C++ (reusing the normal SHA256 code)
    • Specialized C++ for 64-byte inputs, but no special instructions
    • 4-way using SSE4.1 intrinsics
    • 8-way using AVX2 intrinsics

    On my own system (AVX2 capable), I get these benchmarks for computing the Merkle root of 9001 leaves (supported lengths / special instructions / parallellism):

    • 7.2 ms with varsize/naive/1way (master, non-SSE4 hardware)
    • 5.8 ms with size64/naive/1way (this PR, non-SSE4 capable systems)
    • 4.8 ms with varsize/SSE4/1way (master, SSE4 hardware)
    • 2.9 ms with size64/SSE4/4way (this PR, SSE4 hardware)
    • 1.1 ms with size64/AVX2/8way (this PR, AVX2 hardware)
  2. Benchmark Merkle root computation 0df017889b
  3. Refactor SHA256 code 57f34630fb
  4. sipa force-pushed on May 8, 2018
  5. sipa force-pushed on May 8, 2018
  6. sipa force-pushed on May 8, 2018
  7. sipa force-pushed on May 8, 2018
  8. sipa force-pushed on May 8, 2018
  9. sipa force-pushed on May 8, 2018
  10. sipa force-pushed on May 8, 2018
  11. sipa force-pushed on May 8, 2018
  12. laanwj added the label Validation on May 9, 2018
  13. laanwj commented at 1:18 pm on May 9, 2018: member

    Looks like these whole chains of functions are unused after this, except in the merkle tests:

    0BlockMerkleBranch → ComputeMerkleBranch → MerkleComputation
1ComputeMerkleRootFromBranch

    Might want to move some functions there.

  14. in src/crypto/sha256_avx2.cpp:48 in 6904dc15cd outdated 
    43+    __m256i t2 = Add(Sigma0(a), Maj(a, b, c));
44+    d = Add(d, t1);
45+    h = Add(t1, t2);
46+}
47+
48+__m256i inline Read8(const unsigned char* chunk, int offset) {
    laanwj commented at 1:33 pm on May 9, 2018:

    Read8 and Write8 appear to read and write values respectively in opposite order, I suppose this is intentional?

    unrelated: I also wonder if this could be done with a parallel instruction instead of calling into ReadBE32/WriteBE32 for each component, as we know the host endianness.

    sipa commented at 3:28 pm on May 9, 2018:
    Fixed! Indeed, there exist byte-shuffle intrinsics for SSE4 and AVX2; I’ve used those instead of individual byteswaps.
  15. sipa force-pushed on May 9, 2018
  16. in src/bench/crypto_hash.cpp:57 in b36eac01fc outdated 
    51@@ -52,6 +52,14 @@ static void SHA256_32b(benchmark::State& state)
52     }
53 }
54 
55+static void DSHA256_64b(benchmark::State& state)
56+{
57+    std::vector<uint8_t> in(64 * 1024,0);
    kristapsk commented at 5:06 pm on May 9, 2018:
    Shouldn’t there be a space between “1024,” and “0”?
  17. theuni commented at 7:54 pm on May 9, 2018: member
    Concept ACK! @sipa Please see the build-system comments on #13203, I didn’t realize this was a different PR. I’ll follow-up here for non-power changes.
  18. in src/crypto/sha256.cpp:500 in d473e1e0d0 outdated 
    481     if (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx >> 19) & 1) {
482         Transform = sha256_sse4::Transform;
483         TransformD64 = TransformD64Wrapper<sha256_sse4::Transform>;
484-        assert(SelfTest(Transform));
485-        return "sse4";
486+#if defined(ENABLE_SSE41) && !defined(BUILD_BITCOIN_INTERNAL)
    theuni commented at 8:30 pm on May 9, 2018:
    Just because libbitcoinconsensus doesn’t take advantage of 4way? Or some buildsystem limitation?
    sipa commented at 8:31 pm on May 9, 2018:

    Both.

    I didn’t feel like creating copies of all the architecture-specialized libs for use within libbitcoinconsensus - especially as it doesn’t benefit it.

  19. ghost commented at 6:35 am on May 10, 2018: none

    Great job! Any plans to add support for AVX512?

    I know there are not so many people with AVX512 CPU’s but why not add it from now?

    All Intel CPU’s will have support for AVX512 in coming months (mainstream + server).

  20. ghost commented at 6:36 am on May 10, 2018: none

    Some benchmarks numbers about AVX512 in the article below!

    https://hk.saowen.com/a/218fa211f2b705dc6ebc2691a2b21743ce7cd95585c781d181b3809352bffbe3

    https://github.com/intel/intel-ipsec-mb/blob/master/README

  21. laanwj commented at 6:58 am on May 10, 2018: member

    I know there are not so many people with AVX512 CPU’s but why not add it from now?

    That is not how open source development works. A PR is for reviewing the code. Future improvements can be done in future PRs. For example @TheBlueMatt adds support for POWER8 instructions in #13203. I might add ARM intrinsics support at some point.

  22. sipa commented at 7:46 pm on May 11, 2018: member
    @laanwj The algorithm in MerkleComputation is actually potentially more efficient (better memory locality) than the one in ComputeMerkleRoot now, apart from the fact that it doesn’t take advantage of multi-way hashing. I’d like to keep it around for a bit and see if I can adapt it to use multi-way instead, in which case it could be used for everything. I can also move it and move it back if used. What do you think? @Kick1986 AVX512 is cool, but it’s low-impact (even machines that support it right now do it with reduced clock rate), and I’m unable to benchmark it. Feel free to add in follow-up work yoursel, though.
  23. ghost commented at 0:47 am on May 12, 2018: none
    @sipa Thanks for answering me! You are right about AVX512 clock speed, it will go mainstream sometime 2020. I will do my best to add AVX512 to BTC code before that. Thanks
  24. sipa force-pushed on May 12, 2018
  25. sipa commented at 7:14 pm on May 12, 2018: member

    @laanwj I moved the unused Merkle branch functions to the test code. Also:

    I might add ARM intrinsics support at some point.

    :+1: That sounds far more impactful than POWER8, to be honest ;) @theuni I’ve addressed some of your build system comments from #13203, but left the ENABLE_AVX2 and ENABLE_SSE41 macros, because there isn’t a clean platform independent way to use compiler defines. __AVX2__ exists in both GCC and MSVC, but there is no __SSE4_1__ in MSVC (and worse, there is no way to test for SSE4 at all there; you have to test whether the FP code is x87 based or SSE based). @kristapsk Ok, I’ve added a space.

  26. gmaxwell commented at 7:00 pm on May 15, 2018: contributor

    Concept ACK. Lightly tested ACK.

    We should open a issue to track doing a specialized 1-way 64-byte SSE4 function for this later as that is a pretty much guaranteed performance gain (as the non-specialized 1-way SSE4 that does more work is faster than the specialized non-SSE4 1-way code) which can be done by someone who knows assembly but knows little about Bitcoin.

    We might want to add a note to explain the specialization along the lines of: the 64-byte input (and 32-byte input in the second SHA256 invocation) mean that most of the input to the message expansion is zeros, which lets us drop out a lot of additions.

  27. sipa commented at 0:25 am on May 17, 2018: member
    @gmaxwell Yes, perhaps. But the impact of that would be pretty low at best, as every system in which that optimized 1-way code can be used also supports 4-way 64-byte optimized code already; meaning such an implementation would only be used for up to 3 of the last hashes in each level of a Merkle tree.
  28. sipa commented at 7:29 pm on May 20, 2018: member
    @theuni Could you have a look at the build system changes again?
  29. theuni commented at 4:47 pm on May 29, 2018: member
    @sipa thanks for the fixups. utACK build-system changes.
  30. in src/consensus/merkle.cpp:133 in 0bc5ec3732 outdated 
    130@@ -131,9 +131,23 @@ static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot
131 }
132 
133 uint256 ComputeMerkleRoot(const std::vector<uint256>& leaves, bool* mutated) {
    theuni commented at 4:55 pm on May 29, 2018:
    Nit: pass leaves by value. It can be std::move’d from BlockMerkleRoot.
    sipa commented at 9:22 pm on May 29, 2018:
    Done.
  31. in src/crypto/sha256.cpp:64 in 57f34630fb outdated 
    126-        Round(f, g, h, a, b, c, d, e, 0x8cc70208, w11 += sigma1(w9) + w4 + sigma0(w12));
127-        Round(e, f, g, h, a, b, c, d, 0x90befffa, w12 += sigma1(w10) + w5 + sigma0(w13));
128-        Round(d, e, f, g, h, a, b, c, 0xa4506ceb, w13 += sigma1(w11) + w6 + sigma0(w14));
129-        Round(c, d, e, f, g, h, a, b, 0xbef9a3f7, w14 + sigma1(w12) + w7 + sigma0(w15));
130-        Round(b, c, d, e, f, g, h, a, 0xc67178f2, w15 + sigma1(w13) + w8 + sigma0(w0));
131+        Round(a, b, c, d, e, f, g, h, 0x428a2f98 + (w0 = ReadBE32(chunk + 0)));
    theuni commented at 5:31 pm on May 29, 2018:
    Since there’s arithmetic involved now and not just a simple cast, please give the constants an ‘ul’ suffix just to be explicit.
    sipa commented at 9:22 pm on May 29, 2018:
    Fixed (also in SSE4 and AVX2 code).
  32. in src/crypto/sha256.cpp:158 in 0150c8d85e outdated 
    153+    uint32_t g = 0x1f83d9abul;
154+    uint32_t h = 0x5be0cd19ul;
155+
156+    uint32_t w0, w1, w2, w3, w4, w5, w6, w7, w8, w9, w10, w11, w12, w13, w14, w15;
157+
158+    Round(a, b, c, d, e, f, g, h, 0x428a2f98 + (w0 = ReadBE32(in + 0)));
    theuni commented at 5:32 pm on May 29, 2018:
    ‘ul’ suffix for these as well.
  33. theuni approved
  34. theuni commented at 6:07 pm on May 29, 2018: member

    utACK, nothing major to complain about. Admittedly I’m relying on tests to check the new sha2 code itself, I only glanced. Very nice work :)

    Might it be helpful to add a non-double 4way/8way function as well? That would allow (for example) batched txid calculations where the first iteration is lazy and variable-sized as it is now, but 4way/8way could be used for the fixed-size second iterations.

  35. Specialized double sha256 for 64 byte inputs d0c9632883
  36. Use SHA256D64 in Merkle root computation 1f0e7ca09c
  37. 4-way SSE4.1 implementation for double SHA256 on 64-byte inputs 230294bf5f
  38. 8-way AVX2 implementation for double SHA256 on 64-byte inputs 4437d6e1f3
  39. [MOVEONLY] Move unused Merkle branch code to tests 4defdfab94
  40. sipa force-pushed on May 29, 2018
  41. sipa commented at 9:28 pm on May 29, 2018: member

    Addressed @theuni’s nits.

    Also:

    Might it be helpful to add a non-double 4way/8way function as well? That would allow (for example) batched txid calculations where the first iteration is lazy and variable-sized as it is now, but 4way/8way could be used for the fixed-size second iterations.

    Yes, but it’s significantly more complicated. You need to schedule multiple variable length things in groups of 64 bytes, interspersed with padding. Not going to do that in this PR. Also, @jl2012 suggested writing an optimized 32-byte-input single-SHA256 for use in the second half of double-SHA256 computations, which could help there as well.

  42. in src/bench/merkle_root.cpp:1 in 4defdfab94 
    0@@ -0,0 +1,26 @@
1+// Copyright (c) 2016 The Bitcoin Core developers
    Empact commented at 0:25 am on May 30, 2018:
    2018
  43. in src/bench/merkle_root.cpp:5 in 4defdfab94 
    0@@ -0,0 +1,26 @@
1+// Copyright (c) 2016 The Bitcoin Core developers
2+// Distributed under the MIT software license, see the accompanying
3+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4+
5+#include "bench.h"
    Empact commented at 0:25 am on May 30, 2018:
    #include <
  44. DesWurstes commented at 1:29 pm on June 2, 2018: contributor

    In the future, please don’t spend time coding AVX/AVX2 SHA256. SHA-NI specialized instruction set has SHA2 opcodes, which is the possible most efficient way. Besides, it was released before SSE4.2 and AVX, so there are compatible more processors.

    If anyone is interested: https://github.com/01org/isa-l_crypto/blob/master/sha256_mb/sha256_ni_x2.asm

    Thanks pwuille. I guess you’re right.

  45. sipa commented at 2:21 pm on June 2, 2018: member
    @DesWurstes I’m perfectly capable of deciding for myself what I find interesting, thanks. Hardly any systems today support SHA-NI (only very recent low-power Intel CPUs, and AMD Ryzen), while AVX2 is available on all Intel chips since 2013 and AMD chips since 2015.
  46. laanwj commented at 3:41 pm on June 2, 2018: member
    @DesWurstes Apparently you didn’t bother to read the posts at all before replying, as this came up before. People decide for themselves what to work on. If you think something else is more important, you can submit your own pull request.
  47. sipa commented at 11:42 pm on June 3, 2018: member
    @DesWurstes https://github.com/bitcoin/bitcoin/pull/13386
  48. laanwj commented at 10:08 am on June 4, 2018: member
    utACK 4defdfab94504018f822dc34a313ad26cedc8255 Verified that FreeBSD+OpenBSD builds still pass.
  49. laanwj merged this on Jun 4, 2018
  50. laanwj closed this on Jun 4, 2018
  51. laanwj referenced this in commit 0de7cc848e on Jun 4, 2018
  52. droark commented at 6:44 pm on June 6, 2018: contributor

    After-the-fact tACK

    The code’s running nicely on my AVX2-enabled machine. Good job!

    I do have one question. Is this going to affect Gitian builds for people who are on older machines? Maybe I’m missing something silly but it seems like this could cause mismatches. I remember that the SSE4-enabled SHA-256 code initially required --enable-experimental-asm and was eventually enabled by default.

    Thanks.

  53. sipa commented at 6:53 pm on June 6, 2018: member
    @droark It does require an AVX2 compatible compiler, but GCC 4.7 is sufficient for that (which we already required for release builds). You can perfectly well build AVX2 code even if your own hardware doesn’t support AVX2.
  54. droark commented at 7:20 pm on June 6, 2018: contributor
    @sipa - Thanks. I had a bad understanding of compilers from long ago that I somehow never shook.
  55. laanwj referenced this in commit a607d23ae8 on Jun 12, 2018
  56. laanwj referenced this in commit 450055bdbd on Jun 18, 2018
  57. laanwj referenced this in commit 3a3eabef40 on Jul 9, 2018
  58. sipa added the label Needs release notes on Aug 14, 2018
  59. fanquake removed the label Needs release note on Mar 20, 2019
  60. rollmeister commented at 7:51 pm on April 13, 2019: contributor
    Can you please provide any documentation as to how you calculated the custom constants in Transform 2? I would like to adapt it for a 112 byte input. Could it be made to work if Transform 1 uses the state calculated from the first 64 bytes and the remaining 48 bytes (with appropriate padding) as the input message digest along with said calculated custom constants for Transform 2?
  61. codablock referenced this in commit 1fe1d86a06 on Oct 1, 2019
  62. codablock referenced this in commit 136765cfa8 on Oct 1, 2019
  63. codablock referenced this in commit 84194ace4a on Oct 1, 2019
  64. codablock referenced this in commit dda04a300e on Oct 1, 2019
  65. codablock referenced this in commit 5a23934df1 on Oct 1, 2019
  66. codablock referenced this in commit e44b6c7e58 on Oct 1, 2019
  67. codablock referenced this in commit 1df17c02e5 on Oct 1, 2019
  68. codablock referenced this in commit 1b2252c28c on Oct 1, 2019
  69. barrystyle referenced this in commit 23187a4b35 on Jan 22, 2020
  70. barrystyle referenced this in commit b2c9a95587 on Jan 22, 2020
  71. barrystyle referenced this in commit 1eee3932e0 on Jan 22, 2020
  72. barrystyle referenced this in commit 9be0431b4c on Jan 22, 2020
  73. DrahtBot locked this on Dec 16, 2021


sipa laanwj kristapsk theuni ghost gmaxwell Empact DesWurstes droark rollmeister

Labels
Validation

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-18 21:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me