`<charconv>`: faster parsing of integers
Nobody has claimed this yet.
- 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
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 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