<charconv>: for integer to hex conversion instead of looping you can convert digits in parallel using bitwise operations
Nobody has claimed this yet.
- Dominant language
- C++
- Stars
- 11.1k
- Forks
- 1.7k
- Avg merge
- 4d 15h
- Merged PRs (30d)
- 22
Description
For conversion of integers to hexadecimal (and I believe to base power of two in general) you can use bitwise operations as described here:
https://johnnylee-sde.github.io/Fast-unsigned-integer-to-hex-string/
The current implementation uses a loop, e.g. like here:
https://github.com/microsoft/STL/blob/550713eba27c5803addb6f615d3526400cb2df37/stl/inc/charconv#L115-L120
Here is my quick and dirty implementation (click to expand)
#include <cstddef>
#include <cstring>
#ifdef _MSVC
#include <intrin.h>
#else
#include <x86intrin.h>
#endif
uint32_t log2(uint32_t i) {
#ifdef _MSVC
return 32u - __lzcnt(i);
#else
return 32u - __builtin_clz(i);
#endif
}
void writeHexNumber(char *s, uint32_t number)
{
// inspired by https://johnnylee-sde.github.io/Fast-unsigned-integer-to-hex-string/
// convert to 64 bit: 0x00000000'1234abcd
uint64_t digits = number;
// send low part to high 32 bits, high part to low 16 bit: 0x0000abcd'00001234
digits = (digits << 32) | (digits >> 16);
// spread bytes to higher bytes: 0x00cd00ab'00340012
digits = ((digits & 0x0000ff00'0000ff00) >> 8) | ((digits & 0x000000ff'000000ff) << 16);
// move high hex digits to separate bytes: 0x0d0c0b0a'04030201
digits = ((digits & 0x00f000f0'00f000f0) >> 4) | ((digits & 0x000f000f'000f000f) << 8);
// make mask for byte values larger than '9' by overflowing into neighbor bits
const uint64_t mask = ((digits + 0x06060606'06060606) >> 4) & 0x01010101'01010101;
// convert to ASCII by adding value of '0' which is '48' of '0x30'
digits |= 0x30303030'30303030;
// fix up large value by adding value of ('A' - ('9' + 1)) which is '7'
digits += mask * 0x7;
// we got 'digits' containing ASCII codes for each byte
// we have to memcpy data to formally avoid UB
//memcpy(s, &digits, 8);
// skip leading zeros
const auto size = (log2(number | 1) + 3) / 4;
memcpy(s, reinterpret_cast<const std::byte*>(&digits) + (8 - size), size);
}
With MSVC it works faster than to_chars except in the case with only one hex digit (i.e. for values <= 0xf) where it works slightly slower (like 4 ns vs. 3 ns, I would ignore it, honestly).
With Clang on Windows it is as fast or (almost always) faster than to_chars.
I haven't thoroughly tested it on linux, here is a quick benchmark:
https://quick-bench.com/q/xFxgWRFB6GQg2yw5clVwXJzONvE
Leading zeros fixup takes roughly fourth to third of the whole runtime, if you don't need it (want leading zeros in the output) it is noticeably faster.
Hope this helps.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in stl/inc/charconv around the integer-to-hex conversion linked in the issue, then review the proposed bitwise approach and the quick-bench benchmark. Compare correctness and performance with the existing conversion across relevant integer values and supported platforms; done means the implementation is demonstrably faster without changing to_chars behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100