microsoft / microsoft/STL

`<charconv>`: faster parsing of integers

Open
#4,135 1 comment 0 reactions 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

Two things.

1) Everyone unfairly overlooks this beatiful series of posts:
https://johnnylee-sde.github.io/
namely:
Fast numeric string to int

There the author describes painfully simple algorithm for conversion from decimal characters to binary integers.
Here's a quick and dirty version for strings 8 decimal characters or less:

uint32_t charsToInt(std::string_view s) {
  uint64_t i = 0;
  const auto size = std::min(s.size(), static_cast<size_t>(8));
  std::memcpy(&i, s.data(), size);
  i <<= 8 * (8 - size);
  i = (i & 0x0F0F0F0F0F0F0F0Full) * 2561ull >> 8;
  i = (i & 0x00FF00FF00FF00FFull) * 6553601ull >> 16;
  i = (i & 0x0000FFFF0000FFFFull) * 42949672960001ull >> 32;
  return static_cast<uint32_t>(i);
}

All the credits go to the author of the post above, see explanation there also.
With proper data preparation you don't need the initial shift, so it's only 3 binary ANDs, 3 integer multiplications and 3 shifts per 8 decimal characters.

I believe it can be very easily SIMD-ified if one desires. I didn't try it.

E.g. simdjson uses this algorithm (again attributing the author above) here:
https://github.com/simdjson/simdjson/blob/master/include/simdjson/fallback/numberparsing_defs.h#L24

2) I have an idea that you can determine overflow relatively easily without doing all the work the result of which would be wasted anyway, and bail to "fast fail" route.

Suppose that we know how many decimal characters there are. Then, e.g. for uint64_t it's as easy as comparing strings:

uint64_t charsToInt(std::string_view s) {
  if (s.size() > 20)
    throw "nope"; // definitely overflows
  if (s.size() == 20 && s > "18446744073709551615"sv)
    throw "nope";
// ...

Otherwise using the algorithm from point 1) above one can easily check for overflow part-by-part like in this quick and dirty example:

uint64_t charsToInt(std::string_view s) {
  // ...
  if (s.size() <= 8) {
    // ...
  }
  if (s.size() <= 16) {
    // ...
  }
  const auto highSize = std::min(s.size() - 16, static_cast<size_t>(4));
  const uint64_t high = charsToInt(uint64Cast(s.data(), highSize) << (8 * (8 - highSize)));
  if (high > 1844ull)
    throw "nope";
  const uint64_t middle = charsToInt(uint64Cast(s.data() + highSize, 8));
  if (high == 1844ull && middle > 67440737ull)
    throw "nope";
  const uint64_t low = charsToInt(uint64Cast(s.data() + highSize + 8, 8));
  if (high == 1844ull && middle == 67440737ull && low > 9551615ull)
    throw "nope";

  // equivalently
  // if (std::tuple{high, middle, low} > std::tuple{1844ull, 67440737ull, 9551615ull})
  //   throw "nope"; // number > 1844'67440737'09551615

  return high * 10000000000000000ull + middle * 100000000ull + low;
}

Full example: https://godbolt.org/z/18azWhTo4


I did not benchmark any of it. The algorithm from point 1) gives very simple assembly so it looks very promising.

Hope this helps or gives you some ideas.

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 by reviewing the proposed integer-parsing algorithms and the linked simdjson number-parsing example. No STL implementation file, test, benchmark, or specific entry point is identified in the issue, so define those before implementation. Done would require an agreed scope plus benchmark and correctness evidence for the parsing change.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.