microsoft / microsoft/STL

<charconv>: for integer to hex conversion instead of looping you can convert digits in parallel using bitwise operations

Open
#1,115 0 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

performance
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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.