Merge bitcoin/bitcoin#29458: refactor: Preallocate result in TryParseHex to avoid resizing

a19235c14b3dc02de30b5d769de29d1752c23dbd Preallocate result in `TryParseHex` to avoid resizing (Lőrinc)
b7489ecb52c1f99facb7c81c5e46963394d0620d Add benchmark for TryParseHex (Lőrinc)

Pull request description:

  This pull request introduces optimizations to the `TryParseHex` function, focusing primarily on the ideal case (valid hexadecimal input without spaces).
  A new benchmark, `HexParse` was introduced in a separate commit.

  The main optimization preallocates the result vector based on the input string's length. This aims to completely avoid costly dynamic reallocations when no spaces are present.

  ------------

  Before:
  ```
  |           ns/base16 |            base16/s |    err% |     total | benchmark
  |--------------------:|--------------------:|--------:|----------:|:----------
  |                1.60 |      623,238,893.11 |    0.3% |      0.01 | `HexParse`
  |                1.65 |      606,747,566.34 |    0.6% |      0.01 | `HexParse`
  |                1.60 |      626,149,544.07 |    0.3% |      0.01 | `HexParse`
  ```

  After:
  ```
  |           ns/base16 |            base16/s |    err% |     total | benchmark
  |--------------------:|--------------------:|--------:|----------:|:----------
  |                0.68 |    1,465,555,976.27 |    0.8% |      0.01 | `HexParse`
  |                0.68 |    1,472,962,920.18 |    0.3% |      0.01 | `HexParse`
  |                0.68 |    1,476,159,423.00 |    0.3% |      0.01 | `HexParse`
  ```

ACKs for top commit:
  achow101:
    ACK a19235c14b3dc02de30b5d769de29d1752c23dbd
  hebasto:
    ACK a19235c14b3dc02de30b5d769de29d1752c23dbd.
  andrewtoth:
    Re-ACK a19235c14b3dc02de30b5d769de29d1752c23dbd
  Empact:
    Re-ACK https://github.com/bitcoin/bitcoin/pull/29458/commits/a19235c14b3dc02de30b5d769de29d1752c23dbd

Tree-SHA512: e09a59791104be3fd1026862ce98de9efafa1f949626fa01e3b7d58e6a2ef02a11f0de55ddba5c43230a53effd24e6d368c1e12848b17e8ce91d7908a59333f0

1 files changed, 36 insertions, 0 deletions

diff --git a/src/bench/parse_hex.cpp b/src/bench/parse_hex.cpp
new file mode 100644
index 0000000000..db3ead043c
--- /dev/null
+++ b/src/bench/parse_hex.cpp
@@ -0,0 +1,36 @@
+// Copyright (c) 2024- The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <bench/bench.h>
+#include <random.h>
+#include <stddef.h>
+#include <util/strencodings.h>
+#include <cassert>
+#include <optional>
+#include <vector>
+
+std::string generateHexString(size_t length) {
+    const auto hex_digits = "0123456789ABCDEF";
+    FastRandomContext rng(/*fDeterministic=*/true);
+
+    std::string data;
+    while (data.size() < length) {
+        auto digit = hex_digits[rng.randbits(4)];
+        data.push_back(digit);
+    }
+    return data;
+}
+
+static void HexParse(benchmark::Bench& bench)
+{
+    auto data = generateHexString(130); // Generates 678B0EDA0A1FD30904D5A65E3568DB82DB2D918B0AD8DEA18A63FECCB877D07CAD1495C7157584D877420EF38B8DA473A6348B4F51811AC13C786B962BEE5668F9 by default
+
+    bench.batch(data.size()).unit("base16").run([&] {
+        auto result = TryParseHex(data);
+        assert(result != std::nullopt); // make sure we're measuring the successful case
+        ankerl::nanobench::doNotOptimizeAway(result);
+    });
+}
+
+BENCHMARK(HexParse, benchmark::PriorityLevel::HIGH);