Add ASM optimizations for MuHash3072 #19181
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code CoverageFor detailed information about the code coverage, see the test coverage report. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update. ConflictsNo conflicts as of last run. |
|
Awesome, thanks for working on this. Given how good compilers are nowadays it's somewhat surprising to me that there's still something to gain with implementing things manually in assembly without use of any special instruction sets. |
|
Concept ACK. Description needs an update. And this still needs a rebase. |
8ca82da to
915ef08
Compare
|
Thanks for the nudge @Sjors and @DrahtBot ! I have only done a plain rebase so far, i.e. I have not checked whether further optimizations may be interesting to look into. But while I ran the benchmarks again I noticed that it currently appears that this has slower benchmarks than master on my machine. Results with this PR
Results on master
|
|
With This: Master: |
|
@MarcoFalke Well, that's expected at least. There are only x86_64 asm implementations here. @fjahr What kind of system/compiler/flags? |
|
Benchmark on Ryzen 5950X, Ubuntu 21.10, GCC 11.2.0, default configure flags. master:
This PR:
|
I wish I could read asm. 😅 |
Hmm, this was with Intel Core i5-6287U, darwin 21.2.0 (macOS 12.1), clang 13.0.0, default configure flags except for skipping the GUI. |
|
@fjahr Did you disable frequency scaling? Mobile CPUs by default will change frequency all the time in response to load, leading to unreliable benchmarks. |
915ef08 to
82d4c7e
Compare
There was a problem hiding this comment.
Results using gcc 11.3.0 and default configuration on a AMD EPYC 7702P (running Ubuntu 22.04):
master:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 6,810.64 | 146,829.16 | 2.5% | 0.01 | MuHash |
| 5,947.59 | 168,135.40 | 1.0% | 0.01 | MuHashDiv |
| 5,756.02 | 173,731.09 | 0.8% | 0.01 | MuHashMul |
| 838.00 | 1,193,321.69 | 0.4% | 0.01 | MuHashPrecompute |
PR:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 5,457.87 | 183,221.54 | 0.4% | 0.01 | MuHash |
| 4,605.19 | 217,146.38 | 0.9% | 0.01 | MuHashDiv |
| 4,615.33 | 216,669.07 | 0.7% | 0.01 | MuHashMul |
| 848.51 | 1,178,540.85 | 0.7% | 0.01 | MuHashPrecompute |
For a more practical test, I ran gettxoutset muhash without coinstatsindex on mainnet height 765184 both on master and the PR (started with -nolisten -noconnect to avoid distractions for the benchmark), showing a nice ~18% speedup:
master:
$ time ./src/bitcoin-cli gettxoutsetinfo muhash
{
"height": 765184,
"bestblock": "00000000000000000006923ee26b9b3d271035b5cdf79f4915d8453cb3a6f305",
"txouts": 83195150,
"bogosize": 6203273828,
"muhash": "b645663cd8a7a4b6083a84940199f17125232ab4b126602ed2aa054844503393",
"total_amount": 19219692.16624067,
"transactions": 49805302,
"disk_size": 5992277808
}
real 6m28.066s
user 0m0.003s
sys 0m0.001s
PR:
$ time ./src/bitcoin-cli gettxoutsetinfo muhash
{
"height": 765184,
"bestblock": "00000000000000000006923ee26b9b3d271035b5cdf79f4915d8453cb3a6f305",
"txouts": 83195150,
"bogosize": 6203273828,
"muhash": "b645663cd8a7a4b6083a84940199f17125232ab4b126602ed2aa054844503393",
"total_amount": 19219692.16624067,
"transactions": 49805302,
"disk_size": 5991699018
}
real 5m28.506s
user 0m0.003s
sys 0m0.000s
I seem to get consistently better results than master on GCC but also consistently worst results on clang.
Interesting, will als repeat the above test runs using clang in a bit to see if I can observe the same effect.
There was a problem hiding this comment.
I seem to get consistently better results than master on GCC but also consistently worst results on clang.
I can confirm that the MuHash performance with this PR is worse than on master when compiling using clang 14.0.0 (default configuration on a AMD EPYC 7702P, running Ubuntu 22.04). Benchmark results:
master:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 5,476.23 | 182,607.35 | 1.8% | 0.01 | MuHash |
| 4,570.74 | 218,782.88 | 1.0% | 0.01 | MuHashDiv |
| 4,547.88 | 219,882.44 | 0.9% | 0.01 | MuHashMul |
| 814.77 | 1,227,343.46 | 0.8% | 0.01 | MuHashPrecompute |
PR:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 5,799.24 | 172,436.30 | 0.6% | 0.01 | MuHash |
| 5,022.26 | 199,113.39 | 1.3% | 0.01 | MuHashDiv |
| 4,954.25 | 201,847.07 | 0.3% | 0.01 | MuHashMul |
| 828.04 | 1,207,671.75 | 0.8% | 0.01 | MuHashPrecompute |
And the gettxoutsetinfo muhash tests for mainnet block 765184:
master:
$ time ./src/bitcoin-cli gettxoutsetinfo muhash
{
"height": 765184,
"bestblock": "00000000000000000006923ee26b9b3d271035b5cdf79f4915d8453cb3a6f305",
"txouts": 83195150,
8000
"bogosize": 6203273828,
"muhash": "b645663cd8a7a4b6083a84940199f17125232ab4b126602ed2aa054844503393",
"total_amount": 19219692.16624067,
"transactions": 49805302,
"disk_size": 5991686963
}
real 5m36.934s
user 0m0.002s
sys 0m0.002s
PR:
$ time ./src/bitcoin-cli gettxoutsetinfo muhash
{
"height": 765184,
"bestblock": "00000000000000000006923ee26b9b3d271035b5cdf79f4915d8453cb3a6f305",
"txouts": 83195150,
"bogosize": 6203273828,
"muhash": "b645663cd8a7a4b6083a84940199f17125232ab4b126602ed2aa054844503393",
"total_amount": 19219692.16624067,
"transactions": 49805302,
"disk_size": 5991686963
}
real 5m52.723s
user 0m0.004s
sys 0m0.000s
(Sorry for the long double-posts, I should summarize both on them on a small summary table)
Based on those results, if at all, those optimizations should probably only be enabled if GCC is used? (Not sure if it's worth the review and maintenance burden though.)
Some of the code changes here conflict with #21590, and given that clang 14 is better than this ASM, we should maybe get benchmarks on a recent GCC (like 12.2) and see if it's faster. If not, I also wonder if there's a better way to convince GCC to output good code. @theStack Can you re-benchmark with GCC 12 ? I can also try to get some numbers on my machine. |
|
Maybe even with gcc 13.1, now that it is about to be released? |
|
I finally got another amd64 machine with which I can test again. I confirmed the clang-14 results others have seen and I tested with GCC 13.1. The results still look good there for me but would be great if someone else could confirm. (using Master: This PR: I guess it makes sense to only use this when GCC is used which should work with this but I would also be curious if there is another way to tell GCC to do the same optimizations clang seems to be doing. I will also try to combine the changes here with #21590 to see what the combined impact is. |
If it's that niche, it's a bit unclear to me whether it's worth the hassle. I feel we should look at #21590 first. I expect this to be a much larger improvement (and since it's algorithmic, it will apply to all targets). Perhaps we don't care about this optimization here so much after #21590. |
|
I have now tested SafeGCD vs SafeGCD+ASM (see https://github.com/fjahr/bitcoin/tree/pr21590-safegcd-asm) and the gains from including the ASM code are still substantial. GCC 13.1 - SafeGCD only: GCC 13.1 - SafeGCD + ASM: @real-or-random while this change here is niche in terms of the tooling+architecture it targets, the SafeGCD change only impacts the finalize operation and that has a much smaller impact on the overall computation time because of how we use MuHash in practice. When a new block comes in we do a div of all the spent TXOs and a mul of all the new UTXOs and then at the end we finalize once. So I still have a hard time deciding which one is the more valuable change. Also, while ASM might be a bit intimidating, #21590 has 10x the LOC changed and requires some understanding of the underlying theory. |
Okay, thanks for the numbers. I agree then, we shouldn't neglect this one.
Yeah, they both have their merits then, and I don't think any should be prioritized over the other. Let's do (first) whatever PR we get the ACKs on. (And yes, I expect #21590 to be harder to review...)
That would be ideal. I'll try to have a look at this. |
I played around with this a bit, and I don't see any obvious trick to make that work. If someone else wants to give it a try, https://gcc.godbolt.org/z/hhGfeEoKq could be a nice starting point. |
|
There hasn't been much activity lately. What is the status here? Finding reviewers may take time. However, if the patch is no longer relevant, please close this pull request. If the author lost interest or time to work on this, please close it and mark it 'Up for grabs' with the label, so that it can be picked up in the future. |
Still relevant... How good is your ASM, @DrahtBot ? 😁 |
|
It's a rather unsatisfying situation that a compiler produces better code than hand-written assembly. One possibility is just taking the asm generated by clang 14 and including that as asm blocks in the C++ code? |
Yes, but what would be a proper way of reviewing such a PR? Just comparing with the clang output? If we think that's sufficient, then that's a possible way forward. |
|
There's a lot of activity recently in GCC towards generating adc instructions on x86(_64): https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79173 But the current GCC trunk (14) so far hasn't improved over GCC 13 for over code. The GCC trhead also has some hints at possible other implementations such as GCC builtins, which may be simpler to review. I don't know. Checking the asm annotations is not trivial and not many people are familiar with inline asm. But on the other hand, I'm not saying that this PR is a huge review effort. It's just a handful of small functions, and someone needs to take the time. |
Seems like we should do that. |
|
Closing as up for grabs due to lack of activity. |
In general i really dislike the idea of copy/pasting assembly output from a compiler into the source code. It's already hard enough to review human-generated asm code but at least you can ask the author about the reasoning how and why. In the case of compiler output, well, it'd be a matter of waiting for gcc to improve 🙂 |
|
Removing "up for grabs" for now. I don't think anyone will review asm, regardless of where it came from? If there are reviewers who would review it, they should speak up first, no? |
|
To be clear, I'm happy to review asm if there's 1) a very clear performance win in an important part of the code 2) it's human-written and well commented 3) it's only small and relatively straightforward, self-contained operations. |
Adds assembly optimizations for
MuHash3072which is used for themuhashcalculation of the UTXO set hash.