bytes.fromhex() is 1.3 times slower than binascii.a2b_hex()

[dgrisby]

Bug report

Bug description:

I was looking at modernising some old code that uses binascii.a2b_hex, and I was surprised to find that bytes.fromhex() is a lot slower:

>>> timeit.timeit('bytes.fromhex("abcd1234abcd1234")', number=10000000)
1.0542256180197
>>> timeit.timeit('binascii.a2b_hex("abcd1234abcd1234")', 'import binascii', number=10000000)
0.4072963949292898

I thought maybe it was a difference in the lookup of the bytes classmethod vs the module lookup. It appears that it is, to some extent, but not completely:

>>> timeit.timeit('fromhex("abcd1234abcd1234")', 'fromhex=bytes.fromhex', number=10000000)
0.6133267850382254
>>> timeit.timeit('a2b_hex("abcd1234abcd1234")', 'from binascii import a2b_hex', number=10000000)
0.3788172130007297

Of course, all these times are extremely small, so it probably does not matter in most situations, but still, I found it surprising.

CPython versions tested on:

3.13

Operating systems tested on:

Linux

[picnixz]

binascii.a2b_hex and bytes.fromhex do not do the same work. The docs say for a2b_hex:

hexstr must contain an even number of hexadecimal digits (which can be upper or lower case)
Similar functionality (accepting only text string arguments, but more liberal towards whitespace) is also accessible using the bytes.fromhex() class method.

So, I guess those additional checks are the reason why it's slower. I can investigate tomorrow though.

[picnixz]

I can confirm that bytes.fromhex is much slower, even on a PGO build:

$ ./python -m pyperf timeit -s 'fromhex=bytes.fromhex' 'fromhex("abcd1234abcd1234")'
.....................
Mean +- std dev: 52.1 ns +- 0.5 ns
$ ./python -m pyperf timeit -s 'from binascii import a2b_hex as fromhex' 'fromhex("abcd1234abcd1234")'
.....................
Mean +- std dev: 18.9 ns +- 0.7 ns

I'll see if we can do something to improve the performance though but I doubt it will be possible. However, we can indicate that unhexlify is a faster but stricter alternative.

[picnixz]

Ok, I've looked at the code and I don't think we can make it easily faster, unless we duplicate the code for binascii.unhexlify and have a fast path when the string does not contain any space (this is the additional feature that bytes.fromhex supports). However, for this fast path, we must first scan the entire string and check if there's a space using memchr. For small strings, maybe there will be some improvements.

Now, I guess that most of the time, inputs to bytes.fromhex do not contain spaces but this is just me guessing. Sometimes, hexstrings contain spaces just for the sake of clarity, but sometimes not. However, I usually worked with hexadecimal strings that do not have spaces. So maybe we could speed-up that case (again, at the cost of looking up for a space).

@vstinner The current code for bytes.fromhex uses the PyBytesWriter API. Do we gain much if we instead use raw allocation and manually fill the buffer, and then call PyBytes_FromStringAndSize ourselves? (namely, we would by-pass some checks and some ifs but I don't know if it's worth it).

[vstinner]

@vstinner The current code for bytes.fromhex uses the PyBytesWriter API. Do we gain much if we instead use raw allocation and manually fill the buffer, and then call PyBytes_FromStringAndSize ourselves?

I have no idea. Someone has to try and run a benchmark.

[plashchynski]

@picnixz @dgrisby the big difference in your experiments seems to stem from class method vs. module function call overhead. A class method invocation is slower, involves more lookups, checks, and allocations. To compare the actual performance of these two functions, you should benchmark them with bigger input and less invocations. So it spends more time in the function itself, rather than outside of it. So the invocation time makes less impact on the overall time. Hope it makes sense.

Here's my experiment and results:

# with small input (16 chars:
./python.exe -m timeit -n 10000000 -s 'import binascii; input="0123456789abcdef"' 'binascii.a2b_hex(input)'
10000000 loops, best of 5: 28.8 nsec per loop

./python.exe -m timeit -n 10000000 -s 'input="0123456789abcdef"' 'bytes.fromhex(input)'
10000000 loops, best of 5: 73.7 nsec per loop

bytes.fromhex 155.90% slower.

With larger input (1600 chars):

./python.exe -m timeit -n 100000 -s 'import binascii; input="0123456789abcdef" * 100' 'binascii.a2b_hex(input)'
100000 loops, best of 5: 571 nsec per loop

./python.exe -m timeit -n 100000 -s 'input="0123456789abcdef" * 100' 'bytes.fromhex(input)'
100000 loops, best of 5: 647 nsec per loop

bytes.fromhex only 13.31% slower.

[picnixz]

Oh thanks for that. I'll also try to check the differences between those two by simply benchmarking the two algorithms instead. It's a bit sad that calling a classmethod is a bit slower in this case :( (and significantly drops performance). If isolated algorithms also behave similarly, then I don't think we can do anything in particular.

[vstinner]

If you get the function in the timeit setup statement, the difference is lower:

$ python -m timeit -n 10000000 -s 'import binascii; input="0123456789abcdef"; a2b_hex=binascii.a2b_hex' 'a2b_hex(input)'
10000000 loops, best of 5: 42.3 nsec per loop
$ python -m timeit -n 10000000 -s 'input="0123456789abcdef"; fromhex=bytes.fromhex' 'fromhex(input)'
10000000 loops, best of 5: 66.6 nsec per loop

[picnixz]

On my machine, the difference is still quite significant (PGO+LTO build):

./python -m timeit -s 's = "abcd1234abcd1234"; fromhex=bytes.fromhex' 'fromhex(s)'
5000000 loops, best of 5: 51 nsec per loop
./python -m timeit -s 'import binascii; s = "abcd1234abcd1234"; fromhex=binascii.a2b_hex' 'fromhex(s)'
20000000 loops, best of 5: 17.9 nsec per loop

In my case, it's almost a 3x difference, while in your case it's a 1.5x diff. So there might be something at play (or is it just because of my laptop specs?) I didn't have time yet to investigate but I'll try to do it by the end of the week.

[picnixz]

So, I've tried to use different implementations with different heuristics. However, because we need to detect first if a space exists within the given string before using a fast implementation (same as binascii.fromhex), it gets worse for longer strings. Benchmark script is:

import binascii
import random
import string
import time
from itertools import product

import pyperf

def bench_ref_fromhex(loops, value):
    range_it = range(loops)
    t0 = time.perf_counter()
    for _ in range_it:
        bytes.fromhex(value)
    return time.perf_counter() - t0

def bench_new_fromhex(loops, value):
    range_it = range(loops)
    t0 = time.perf_counter()
    for _ in range_it:
        bytes.fromhex2(value)
    return time.perf_counter() - t0

def bench_ref_a2b_hex(loops, value):
    range_it = range(loops)
    t0 = time.perf_counter()
    for _ in range_it:
        binascii.unhexlify(value)
    return time.perf_counter() - t0

def make_value(n, p=0):
    # n = q + s with even q and s; p = fraction of whitespaces
    # q = 2 * k = n * (1 - p)
    # s = n * p
    assert n % 2 == 0
    assert 0 <= p <= 1
    s = int(n * p)
    if s % 2 == 1:
        s = min(n, s + 1)
    q = max(0, n - s)
    assert s % 2 == 0
    assert q % 2 == 0
    # choose the random characters that will form the pairs
    chars = random.choices(string.hexdigits.lower(), k=q)
    terms = [''.join(chars[i:i + 2]) for i in range(0, q, 2)]
    terms.extend(random.choices(string.whitespace, k=s))
    random.shuffle(terms)
    return ''.join(terms), s

def bench(runner, name, func, ns=(16, 128, 1024), ps=(0,)):
    for n, p in product(ns, ps):
        value, n_ws = make_value(n, p)
        runner.bench_time_func(f'{name}[{n}]+space[{n_ws}]', func, value)

def add_cmdline_args(cmd, args):
    cmd.append(args.implementation)

if __name__ == '__main__':
    runner = pyperf.Runner(add_cmdline_args=add_cmdline_args)
    runner.argparser.add_argument('implementation', choices=['ref', 'new'])
    args = runner.parse_args()

    if args.implementation == 'ref':
        fromhex = bench_ref_fromhex
    else:
        fromhex = bench_new_fromhex
    bench(runner, 'fromhex', fromhex, ps=[0, 0.1, 0.5, 0.9])
    if args.implementation == 'ref':
        bench(runner, 'a2b_hex', bench_ref_a2b_hex)

The reason why we're still slow is because we need to remove all whitespaces and not just regular spaces.

• Use strpbrk for detecting all whitespaces and fall back to a fast path -> very slow for large inputs.
• Use strspn instead of skipping using do { } while loops -> still slower than the naive skip
• Use multiple calls to memchr -> haven't tested, but even with just simple whitespaces \x20 and nothing more, we're barely faster than bytes.fromhex and don't reach the speed of binascii.unhexlify.

I didn't test memchr to locate all possible whitespaces as with just one whitespace it's already not convincing, so I don't think we can do better unfortunately. We also cannot just strip the string of its whitespaces before using the fast algorithm as we would lose the exact error location if needs arise.

If others want to continue investigating, they can try (I didn't optimize all algorithms, maybe I made some errors) but they can use my benchmark script to check their implementations. I'll check one more time this w-e but I don't think I'm going to see something better for all inputs (maybe we could micro-optimize depending on the length of the input, but I don't think it's worth the code complication).