Optimize 128-bit decimal formatting
Maintainers usually reply within 9 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 48/100
- Issue type
- Refactor
- Clarity
- Mostly clear
- Activity status
- Active
- Tech stack
- cpp
- Domain
- performance
Research direction
Start by locating count_digits(native_uint128) and do_format_decimal, then trace how the 64-bit formatter returns the start of its output. Check the existing tests and benchmarks for 128-bit decimal formatting before changing the division path. Done means the proposed operations are removed or replaced without changing formatting results, and benchmarks confirm the performance impact.
Written by the indexing model from the issue text.
Description
Hi..
current 128-bit decimal formatting path uses division and modulo by 10^19 to reduce values into 64-bit chunks........ and GCC emits __udivti3 and __udivmodti4 calls for these operations.
During this i found two probably redundant operations - please correct me if i'm wrong or missed a point to review here :
count_digits(native_uint128)performs a second 128-bit division when the result is already known to have 39 digits.do_format_decimalcounts the remaining digits again, although the 64-bit formatter already returns the start of the formatted output.
so can we remove these redundant operations and replacing division by 10^19 with an exact three-multiply reciprocal implementation .... 10^19 = 2^19 * 5^19.
anyway in my testing GCC (12.2.0)benchmarks show a 14.6% improvement in fmt::format_to for uniformly distributed 128-bit values and 24.8% for the upper 39-digit range.
- Dominant language
- C++
- Stars
- 25.9k
- Forks
- 3.1k
- Avg merge
- 9d 5h
- Merged PRs (30d)
- 13
Getting set up
- No Dockerfile or Docker Compose file
- Has a pull request template
- Read the contributing 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.
More from fmtlib/fmt
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 9 days
-
Difficulty 3/5 1-2 days Newbie friendliness 63/100
Maintainers usually reply within 9 days
-
<stdfloat>May be free again @shreyas-s1403 claimed this 13 days ago, and no pull request is open. Open
Difficulty 4/5 3-5 days Newbie friendliness 45/100
fmtlib/fmt#4725 · 10 comments · 1 reaction ·
Maintainers usually reply within 9 days
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
fmtlib/fmt#4518 · 1 comment · 6 reactions ·
Maintainers usually reply within 9 days
-
failed to print error code `:s` fail on windows due to encoding errorMay be free again @shreyas-s1403 claimed this 13 days ago, and no pull request is open. Open
Difficulty 4/5 3-5 days Newbie friendliness 35/100
fmtlib/fmt#4436 · 11 comments ·
Maintainers usually reply within 9 days
Similar issues
-
Linux npm packaging leaves workspace files that block subsequent CI checkoutPossibly taken @Spockkk0225 claimed this today. Openci
Difficulty 2/5 1-3 hours Newbie friendliness 73/100
alibaba/neug#1195 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
Maintainers usually reply within 3 days
-
QA/No release-notes/exclude tests tests/missing-coverage tests/test-quality
Difficulty 2/5 1-3 hours Newbie friendliness 71/100
brave/brave-browser#61019 ·
Maintainers usually reply within 1 day
-
? - Needs Triage bug CUTLASS C++
Difficulty 1/5 Under an hour Newbie friendliness 88/100
Maintainers usually reply within 4 days