This is an archive of the discontinued LLVM Phabricator instance.

Paths

Table of Contentst

-
libcxx/include/
-
include/
16/16
charconv

Differential D97705

[libc++] Improve std::to_chars for base != 10.
ClosedPublic

Authored by Mordante on Mar 1 2021, 10:13 AM.

Download Raw Diff

Details

Reviewers

EricWF
ldionne
mclow.lists
miscco
curdeius
• Quuxplusone

Group Reviewers

Restricted Project

Commits

rG6c11aebd302d: [libc++] Improve std::to_chars for base != 10.

Summary

This improves the speed of to_chars for bases 2, 8, and 16.
These bases are common and used in <format>. This change
uses a lookup table, like done in base 10 and causes an increase
in code size. The change has a small overhead for the other bases.

Benchmark                             Time             CPU      Time Old      Time New       CPU Old       CPU New
------------------------------------------------------------------------------------------------------------------
BM_to_chars_good/2                 -0.9476         -0.9476           252            13           252            13
BM_to_chars_good/3                 +0.0018         +0.0018           145           145           145           145
BM_to_chars_good/4                 +0.0108         +0.0108           104           105           104           105
BM_to_chars_good/5                 +0.0159         +0.0160            89            91            89            91
BM_to_chars_good/6                 +0.0162         +0.0162            80            81            80            81
BM_to_chars_good/7                 +0.0117         +0.0117            72            73            72            73
BM_to_chars_good/8                 -0.8643         -0.8643            64             9            64             9
BM_to_chars_good/9                 +0.0095         +0.0095            60            60            60            60
BM_to_chars_good/10                +0.0540         +0.0540             6             6             6             6
BM_to_chars_good/11                +0.0299         +0.0299            55            57            55            57
BM_to_chars_good/12                +0.0060         +0.0060            48            49            49            49
BM_to_chars_good/13                +0.0102         +0.0102            48            48            48            48
BM_to_chars_good/14                +0.0184         +0.0185            47            48            47            48
BM_to_chars_good/15                +0.0269         +0.0269            44            45            44            45
BM_to_chars_good/16                -0.8207         -0.8207            37             7            37             7
BM_to_chars_good/17                +0.0241         +0.0241            37            38            37            38
BM_to_chars_good/18                +0.0221         +0.0221            37            38            37            38
BM_to_chars_good/19                +0.0222         +0.0223            37            38            37            38
BM_to_chars_good/20                +0.0317         +0.0317            38            39            38            39
BM_to_chars_good/21                +0.0342         +0.0341            38            39            38            39
BM_to_chars_good/22                +0.0336         +0.0336            36            38            36            38
BM_to_chars_good/23                +0.0222         +0.0222            34            35            34            35
BM_to_chars_good/24                +0.0185         +0.0185            31            32            31            32
BM_to_chars_good/25                +0.0157         +0.0157            32            32            32            32
BM_to_chars_good/26                +0.0181         +0.0181            32            32            32            32
BM_to_chars_good/27                +0.0153         +0.0153            32            32            32            32
BM_to_chars_good/28                +0.0179         +0.0179            32            32            32            32
BM_to_chars_good/29                +0.0189         +0.0189            32            33            32            33
BM_to_chars_good/30                +0.0212         +0.0212            32            33            32            33
BM_to_chars_good/31                +0.0221         +0.0221            32            33            32            33
BM_to_chars_good/32                +0.0292         +0.0292            32            33            32            33
BM_to_chars_good/33                +0.0319         +0.0319            32            33            32            33
BM_to_chars_good/34                +0.0411         +0.0410            33            34            33            34
BM_to_chars_good/35                +0.0515         +0.0515            33            34            33            34
BM_to_chars_good/36                +0.0502         +0.0502            32            34            32            34
BM_to_chars_bad/2                  -0.8752         -0.8752            40             5            40             5
BM_to_chars_bad/3                  +0.1952         +0.1952            21            26            21            26
BM_to_chars_bad/4                  +0.3626         +0.3626            16            22            16            22
BM_to_chars_bad/5                  +0.2267         +0.2268            17            21            17            21
BM_to_chars_bad/6                  +0.3560         +0.3559            14            19            14            19
BM_to_chars_bad/7                  +0.4599         +0.4600            12            18            12            18
BM_to_chars_bad/8                  -0.5074         -0.5074            11             5            11             5
BM_to_chars_bad/9                  +0.4814         +0.4814            10            15            10            15
BM_to_chars_bad/10                 +0.7761         +0.7761             2             4             2             4
BM_to_chars_bad/11                 +0.3948         +0.3948            12            16            12            16
BM_to_chars_bad/12                 +0.3203         +0.3203            10            13            10            13
BM_to_chars_bad/13                 +0.3067         +0.3067            11            14            11            14
BM_to_chars_bad/14                 +0.2235         +0.2235            12            14            12            14
BM_to_chars_bad/15                 +0.2675         +0.2675            11            14            11            14
BM_to_chars_bad/16                 -0.1801         -0.1801             7             5             7             5
BM_to_chars_bad/17                 +0.5651         +0.5651             7            11             7            11
BM_to_chars_bad/18                 +0.5407         +0.5406             7            11             7            11
BM_to_chars_bad/19                 +0.5593         +0.5593             8            12             8            12
BM_to_chars_bad/20                 +0.5823         +0.5823             8            13             8            13
BM_to_chars_bad/21                 +0.6032         +0.6032             9            15             9            15
BM_to_chars_bad/22                 +0.6407         +0.6408             9            14             9            14
BM_to_chars_bad/23                 +0.6292         +0.6292             7            12             7            12
BM_to_chars_bad/24                 +0.5784         +0.5784             6            10             6            10
BM_to_chars_bad/25                 +0.5784         +0.5784             6            10             6            10
BM_to_chars_bad/26                 +0.5713         +0.5713             7            10             7            10
BM_to_chars_bad/27                 +0.5969         +0.5969             7            11             7            11
BM_to_chars_bad/28                 +0.6131         +0.6131             7            11             7            11
BM_to_chars_bad/29                 +0.6937         +0.6937             7            11             7            11
BM_to_chars_bad/30                 +0.7655         +0.7656             7            12             7            12
BM_to_chars_bad/31                 +0.8939         +0.8939             6            12             6            12
BM_to_chars_bad/32                 +1.0157         +1.0157             6            13             6            13
BM_to_chars_bad/33                 +1.0279         +1.0279             7            14             7            14
BM_to_chars_bad/34                 +1.0388         +1.0388             7            14             7            14
BM_to_chars_bad/35                 +1.0990         +1.0990             7            15             7            15
BM_to_chars_bad/36                 +1.1503         +1.1503             7            15             7            15

Diff Detail

Repository: rG LLVM Github Monorepo

Event Timeline

Mordante requested review of this revision.Mar 1 2021, 10:13 AM

Mordante created this revision.

Herald added a project: Restricted Project. · View Herald TranscriptMar 1 2021, 10:13 AM

Herald added a reviewer: Restricted Project. · View Herald Transcript

Herald added a subscriber: libcxx-commits. · View Herald Transcript

Mordante planned changes to this revision.Mar 1 2021, 10:14 AM

Harbormaster completed remote builds in B91375: Diff 327170.Mar 1 2021, 12:46 PM

I think it would make sense to have a general implementation that works for all bases, and then have a few common bases (likely 2, 8, 10, 16 as you say) be compiled in the library. I think the top-level could look something like:

if (base == 2) // then dispatch to the implementation for base 2 in the library
else if (base == 8) // dispatch to base 8
else if (base == 10) // dispatch to base 10
else if (base == 16) // dispatch to base 16
else // general implementation

I'm not saying use if over switch or whatever -- I'm just saying IMO it would make sense to check for the base, optimize for a few common bases (for a modest increase in code size in the dylib), and then fallback to a general implementation available as templates that will be compiled in the user's binaries. WDYT?

So if that wasn't clear, I think I'm saying I agree with you that (3) seems like what we want to do.

In D97705#2689775, @ldionne wrote:

So if that wasn't clear, I think I'm saying I agree with you that (3) seems like what we want to do.

Thanks for your feedback! Then I'll proceed with method 3. I'll make a separate review to fix the bug and then use this review to do the optimization for bases 2, 8, and 16.

Mordante mentioned this in D100722: [libc++] Fixes std::to_chars for bases != 10..Apr 18 2021, 5:30 AM

Mordante mentioned this in rG9393060f908b: [libc++] Fixes std::to_chars for bases != 10..Apr 29 2021, 10:56 AM

A new version testing some different optimizations options.
Test to see whether it passes a CI run.

Mordante planned changes to this revision.May 19 2021, 10:56 AM

Harbormaster completed remote builds in B105272: Diff 346512.May 19 2021, 11:33 AM

Remove tabs. The CI failed on this the last run.

Mordante planned changes to this revision.May 20 2021, 10:52 AM

Harbormaster completed remote builds in B105448: Diff 346769.May 20 2021, 1:08 PM

Rebased and using the fastest solution.

Mordante edited the summary of this revision. (Show Details)Jan 21 2022, 8:50 AM

Mordante added a reviewer: • Quuxplusone.

In D97705#2689772, @ldionne wrote:

I think it would make sense to have a general implementation that works for all bases, and then have a few common bases (likely 2, 8, 10, 16 as you say) be compiled in the library. I think the top-level could look something like:

I think moving code to the library will only be temporary. It seems the direction is to make these functions constexpr in C++23. https://wg21.link/p2291r3

libcxx/include/charconv
548–557	Run 1 -> `#if 0` Run 2 -> `#if 1`

Harbormaster completed remote builds in B144844: Diff 402002.Jan 21 2022, 8:57 AM

Still some scattered #if 0/1s left to remove.

libcxx/include/charconv
329	The red flag here was the `: unsigned` (I was like, "why does the signedness matter? better study closer") but actually, why do we need an enumerator for this at all? It's used only twice, and in contexts like _VSTD::memcpy(__p, &__base_2_lut[4 * __c], 4); ~~~ unsigned __c = __value % _Base; __value /= _Base; *--__p = "01"[__c]; The number `2` is hard-coded so many places here, two more won't make a difference (and will save two lines and eliminate a red flag). Ditto in the `8` and `16` cases. (If this was to appease clang-tidy: Don't appease it. :))
334	I'd remove `noexcept` from line 331, as it's just noise. (Nobody relies on the noexceptness of this function.) Ditto throughout — I assume there will be other redundant `noexcept`s.
358	Is Clang smart enough to optimize this into `'0' + __c`? Would the latter be more readable anyway? (Note there is no issue with EBCDIC here; all charsets must have `'0'+1 == '1'` according to the standard.) Ditto line 413.
363	Either `constexpr` if this is C++11-and-later, or `_LIBCPP_CONSTEXPR const`, surely?
490	`__enable_if_t<sizeof(_Tp) >= sizeof(unsigned)>* = nullptr` is the more traditional libc++ism. (`enable_if_t` if this is C++14-and-later.)

Thanks for the review! The patch is still RFC to see whether this is the direction we want to go. Hence the remaining #if and the lack of polish.

In D97705#3262177, @Mordante wrote:

Thanks for the review! The patch is still RFC to see whether this is the direction we want to go. Hence the remaining #if and the lack of polish.

Just to make sure I understand (the review summary is difficult to read for me due to formatting issues), we have a base implementation using __to_chars_itoa, and then we also have implementations specific to other bases that use __to_chars_integral<2> and friends. When those base-specific implementations are enabled, we get roughly 3x performance improvement on those bases, at the cost of < 256 bytes of size for a lookup table. That's right?

If so, I'd say make the optimization non-customizeable and always use it.

Mordante mentioned this in D121223: [libc++][NFC] Cleanups in <charconv>..Mar 8 2022, 8:41 AM

In D97705#3349302, @ldionne wrote:

In D97705#3262177, @Mordante wrote:

Just to make sure I understand (the review summary is difficult to read for me due to formatting issues), we have a base implementation using __to_chars_itoa, and then we also have implementations specific to other bases that use __to_chars_integral<2> and friends. When those base-specific implementations are enabled, we get roughly 3x performance improvement on those bases, at the cost of < 256 bytes of size for a lookup table. That's right?

The size of the lookup table differs, 64-bytes for base 2, 128-bytes for base 8, and 512-bytes for base 16.
The speedup is 14 times for base 2, 3 times for base 8, and 2 times for base 16.

libcxx/include/charconv
329	No it had nothing to do with clang-tidy ;-) This was from an earlier experiment it had a generic form for other integral values. However there the size/speed benefit wasn't great so most of that was removed. Now this is also gone.
358	The entire file uses this style, including places are _Base > 10. So I prefer to keep it as is.
363	This was copy-pasted from another part of this file. D121223 addresses these places.
490	This is the same as other places in this file, so I prefer to keep it. Note the `enable_if` specifies the type as `int` so `nullptr` isn't an option.

Herald added a project: Restricted Project. · View Herald TranscriptMar 8 2022, 8:48 AM

• Quuxplusone added inline comments.Mar 8 2022, 9:50 AM

libcxx/include/charconv
490	This is the same as other places in this file, so I prefer to keep it. OK. Note the enable_if specifies the type as int so nullptr isn't an option. FWIW: The existing `enable_if` comes out to `int = 0`, but in my suggested "more traditional libc++ism" rewrite, the `__enable_if_t` would come out to `void* = nullptr` instead. I don't see a problem there, so either I'm missing something or you were. (The rewrite would change the mangling, but this is hide-from-abi so we shouldn't care.)

Mordante mentioned this in rG3925f98de4ac: [libc++][NFC] Cleanups in <charconv>..Mar 9 2022, 8:52 AM

Mordante marked 5 inline comments as done.Mar 12 2022, 4:29 AM

Mordante added inline comments.

libcxx/include/charconv
490	I prefer to keep them in this style to keep the file uniform. It indeed shouldn't be an ABI break, but I rather keep them as-is, just in case there is an issue.

Rebase and address review comments.

Harbormaster completed remote builds in B153902: Diff 414823.Mar 12 2022, 5:52 AM

Mordante retitled this revision from [RFC][libc++] Improve std::to_chars for base != 10. to [libc++] Improve std::to_chars for base != 10..Mar 22 2022, 12:03 PM

Mordante edited the summary of this revision. (Show Details)

This looks sensible to me.

libcxx/include/charconv
508	I don't think we need `_LIBCPP_AVAILABILITY_TO_CHARS` here, since this is all implemented in the headers. Or did I miss a dependency on the dylib?

This revision is now accepted and ready to land.May 13 2022, 11:54 AM

philnik added a subscriber: philnik.May 13 2022, 12:46 PM

philnik added inline comments.

libcxx/include/charconv
546	Does this `[[likely]]` make any difference?

Rebased and address review comments.
Will land when the build passes.

Harbormaster completed remote builds in B164441: Diff 429426.May 14 2022, 3:56 AM

Mordante marked 2 inline comments as done.May 14 2022, 3:59 AM

Mordante added inline comments.

libcxx/include/charconv
508	Good catch!
546	Yes I've measured in the benchmarks that it makes improvements. However I plan to refactor this file to prepare for https://wg21.link/p2291r3 "Add Constexpr Modifiers to Functions to_chars and from_chars for Integral Types in <charconv>" and 128-bit support. When the base 10 implementation moves to the header this attribute may have less benefit. But that requires another round of profiling.

Closed by commit rG6c11aebd302d: [libc++] Improve std::to_chars for base != 10. (authored by Mordante). · Explain WhyMay 14 2022, 4:01 AM

This revision was automatically updated to reflect the committed changes.

Mordante marked 2 inline comments as done.

Mordante added a commit: rG6c11aebd302d: [libc++] Improve std::to_chars for base != 10..

Revision Contents

Path

Size

libcxx/

include/

charconv

202 lines

Diff 429436

libcxx/include/charconv

Show First 20 Lines • Show All 313 Lines • ▼ Show 20 Lines __to_chars_integral(char* __first, char* __last, _Tp __value, int __base,

{ {

*__first++ = '-'; *__first++ = '-';

__x = __complement(__x); __x = __complement(__x);

} }

return __to_chars_integral(__first, __last, __x, __base, false_type()); return __to_chars_integral(__first, __last, __x, __base, false_type());

} }

namespace __itoa {

static constexpr char __base_2_lut[64] = {

'0', '0', '0', '0',

'0', '0', '0', '1',

'0', '0', '1', '0',

'0', '0', '1', '1',

'0', '1', '0', '0',

QuuxplusoneUnsubmitted

Done

The red flag here was the : unsigned (I was like, "why does the signedness matter? better study closer") but actually, why do we need an enumerator for this at all? It's used only twice, and in contexts like

      _VSTD::memcpy(__p, &__base_2_lut[4 * __c], 4);
~~~
      unsigned __c = __value % _Base;
      __value /= _Base;
      *--__p = "01"[__c];

The number 2 is hard-coded so many places here, two more won't make a difference (and will save two lines and eliminate a red flag). Ditto in the 8 and 16 cases.

(If this was to appease clang-tidy: Don't appease it. :))

Quuxplusone: The red flag here was the `: unsigned` (I was like, "why does the signedness matter? better…

MordanteAuthorUnsubmitted

Done

No it had nothing to do with clang-tidy ;-) This was from an earlier experiment it had a generic form for other integral values. However there the size/speed benefit wasn't great so most of that was removed. Now this is also gone.

Mordante: No it had nothing to do with clang-tidy ;-) This was from an earlier experiment it had a…

'0', '1', '0', '1',

'0', '1', '1', '0',

'0', '1', '1', '1',

'1', '0', '0', '0',

'1', '0', '0', '1',

QuuxplusoneUnsubmitted

Done

// If value == 0 still need one digit. If the value != this has no

- // effect since the code scans for the most significat bit set. (Note

+ // effect since the code scans for the most significant bit set. (Note

// that __libcpp_clz doesn't work for 0.)

I'd remove noexcept from line 331, as it's just noise. (Nobody relies on the noexceptness of this function.) Ditto throughout — I assume there will be other redundant noexcepts.

Quuxplusone: I'd remove `noexcept` from line 331, as it's just noise. (Nobody relies on the noexceptness of…

'1', '0', '1', '0',

'1', '0', '1', '1',

'1', '1', '0', '0',

'1', '1', '0', '1',

'1', '1', '1', '0',

'1', '1', '1', '1'

};

static constexpr char __base_8_lut[128] = {

'0', '0', '0', '1', '0', '2', '0', '3', '0', '4', '0', '5', '0', '6', '0', '7',

'1', '0', '1', '1', '1', '2', '1', '3', '1', '4', '1', '5', '1', '6', '1', '7',

'2', '0', '2', '1', '2', '2', '2', '3', '2', '4', '2', '5', '2', '6', '2', '7',

'3', '0', '3', '1', '3', '2', '3', '3', '3', '4', '3', '5', '3', '6', '3', '7',

'4', '0', '4', '1', '4', '2', '4', '3', '4', '4', '4', '5', '4', '6', '4', '7',

'5', '0', '5', '1', '5', '2', '5', '3', '5', '4', '5', '5', '5', '6', '5', '7',

'6', '0', '6', '1', '6', '2', '6', '3', '6', '4', '6', '5', '6', '6', '6', '7',

'7', '0', '7', '1', '7', '2', '7', '3', '7', '4', '7', '5', '7', '6', '7', '7'

};

static constexpr char __base_16_lut[512] = {

'0', '0', '0', '1', '0', '2', '0', '3', '0', '4', '0', '5', '0', '6', '0', '7', '0', '8', '0', '9', '0', 'a', '0', 'b', '0', 'c', '0', 'd', '0', 'e', '0', 'f',

'1', '0', '1', '1', '1', '2', '1', '3', '1', '4', '1', '5', '1', '6', '1', '7', '1', '8', '1', '9', '1', 'a', '1', 'b', '1', 'c', '1', 'd', '1', 'e', '1', 'f',

'2', '0', '2', '1', '2', '2', '2', '3', '2', '4', '2', '5', '2', '6', '2', '7', '2', '8', '2', '9', '2', 'a', '2', 'b', '2', 'c', '2', 'd', '2', 'e', '2', 'f',

'3', '0', '3', '1', '3', '2', '3', '3', '3', '4', '3', '5', '3', '6', '3', '7', '3', '8', '3', '9', '3', 'a', '3', 'b', '3', 'c', '3', 'd', '3', 'e', '3', 'f',

QuuxplusoneUnsubmitted

Done

Is Clang smart enough to optimize this into '0' + __c? Would the latter be more readable anyway? (Note there is no issue with EBCDIC here; all charsets must have '0'+1 == '1' according to the standard.)
Ditto line 413.

Quuxplusone: Is Clang smart enough to optimize this into `'0' + __c`? Would the latter be more readable…

MordanteAuthorUnsubmitted

Done

The entire file uses this style, including places are _Base > 10. So I prefer to keep it as is.

Mordante: The entire file uses this style, including places are _Base > 10. So I prefer to keep it as is.

'4', '0', '4', '1', '4', '2', '4', '3', '4', '4', '4', '5', '4', '6', '4', '7', '4', '8', '4', '9', '4', 'a', '4', 'b', '4', 'c', '4', 'd', '4', 'e', '4', 'f',

'5', '0', '5', '1', '5', '2', '5', '3', '5', '4', '5', '5', '5', '6', '5', '7', '5', '8', '5', '9', '5', 'a', '5', 'b', '5', 'c', '5', 'd', '5', 'e', '5', 'f',

'6', '0', '6', '1', '6', '2', '6', '3', '6', '4', '6', '5', '6', '6', '6', '7', '6', '8', '6', '9', '6', 'a', '6', 'b', '6', 'c', '6', 'd', '6', 'e', '6', 'f',

'7', '0', '7', '1', '7', '2', '7', '3', '7', '4', '7', '5', '7', '6', '7', '7', '7', '8', '7', '9', '7', 'a', '7', 'b', '7', 'c', '7', 'd', '7', 'e', '7', 'f',

'8', '0', '8', '1', '8', '2', '8', '3', '8', '4', '8', '5', '8', '6', '8', '7', '8', '8', '8', '9', '8', 'a', '8', 'b', '8', 'c', '8', 'd', '8', 'e', '8', 'f',

QuuxplusoneUnsubmitted

Done

Either constexpr if this is C++11-and-later, or _LIBCPP_CONSTEXPR const, surely?

Quuxplusone: Either `constexpr` if this is C++11-and-later, or `_LIBCPP_CONSTEXPR const`, surely?

MordanteAuthorUnsubmitted

Done

This was copy-pasted from another part of this file. D121223 addresses these places.

Mordante: This was copy-pasted from another part of this file. D121223 addresses these places.

'9', '0', '9', '1', '9', '2', '9', '3', '9', '4', '9', '5', '9', '6', '9', '7', '9', '8', '9', '9', '9', 'a', '9', 'b', '9', 'c', '9', 'd', '9', 'e', '9', 'f',

'a', '0', 'a', '1', 'a', '2', 'a', '3', 'a', '4', 'a', '5', 'a', '6', 'a', '7', 'a', '8', 'a', '9', 'a', 'a', 'a', 'b', 'a', 'c', 'a', 'd', 'a', 'e', 'a', 'f',

'b', '0', 'b', '1', 'b', '2', 'b', '3', 'b', '4', 'b', '5', 'b', '6', 'b', '7', 'b', '8', 'b', '9', 'b', 'a', 'b', 'b', 'b', 'c', 'b', 'd', 'b', 'e', 'b', 'f',

'c', '0', 'c', '1', 'c', '2', 'c', '3', 'c', '4', 'c', '5', 'c', '6', 'c', '7', 'c', '8', 'c', '9', 'c', 'a', 'c', 'b', 'c', 'c', 'c', 'd', 'c', 'e', 'c', 'f',

'd', '0', 'd', '1', 'd', '2', 'd', '3', 'd', '4', 'd', '5', 'd', '6', 'd', '7', 'd', '8', 'd', '9', 'd', 'a', 'd', 'b', 'd', 'c', 'd', 'd', 'd', 'e', 'd', 'f',

'e', '0', 'e', '1', 'e', '2', 'e', '3', 'e', '4', 'e', '5', 'e', '6', 'e', '7', 'e', '8', 'e', '9', 'e', 'a', 'e', 'b', 'e', 'c', 'e', 'd', 'e', 'e', 'e', 'f',

'f', '0', 'f', '1', 'f', '2', 'f', '3', 'f', '4', 'f', '5', 'f', '6', 'f', '7', 'f', '8', 'f', '9', 'f', 'a', 'f', 'b', 'f', 'c', 'f', 'd', 'f', 'e', 'f', 'f'

};

template <unsigned _Base>

struct _LIBCPP_HIDDEN __integral;

template <>

struct _LIBCPP_HIDDEN __integral<2> {

template <typename _Tp>

_LIBCPP_HIDE_FROM_ABI static constexpr int __width(_Tp __value) noexcept {

// If value == 0 still need one digit. If the value != this has no

// effect since the code scans for the most significant bit set. (Note

// that __libcpp_clz doesn't work for 0.)

return numeric_limits<_Tp>::digits - std::__libcpp_clz(__value | 1);

}

template <typename _Tp>

_LIBCPP_HIDE_FROM_ABI static to_chars_result __to_chars(char* __first, char* __last, _Tp __value) {

ptrdiff_t __cap = __last - __first;

int __n = __width(__value);

if (__n > __cap)

return {__last, errc::value_too_large};

__last = __first + __n;

char* __p = __last;

const unsigned __divisor = 16;

while (__value > __divisor) {

unsigned __c = __value % __divisor;

__value /= __divisor;

__p -= 4;

std::memcpy(__p, &__base_2_lut[4 * __c], 4);

}

do {

unsigned __c = __value % 2;

__value /= 2;

*--__p = "01"[__c];

} while (__value != 0);

return {__last, errc(0)};

}

};

template <>

struct _LIBCPP_HIDDEN __integral<8> {

template <typename _Tp>

_LIBCPP_HIDE_FROM_ABI static constexpr int __width(_Tp __value) noexcept {

// If value == 0 still need one digit. If the value != this has no

// effect since the code scans for the most significat bit set. (Note

// that __libcpp_clz doesn't work for 0.)

return ((numeric_limits<_Tp>::digits - std::__libcpp_clz(__value | 1)) + 2) / 3;

}

template <typename _Tp>

_LIBCPP_HIDE_FROM_ABI static to_chars_result __to_chars(char* __first, char* __last, _Tp __value) {

ptrdiff_t __cap = __last - __first;

int __n = __width(__value);

if (__n > __cap)

return {__last, errc::value_too_large};

__last = __first + __n;

char* __p = __last;

unsigned __divisor = 64;

while (__value > __divisor) {

unsigned __c = __value % __divisor;

__value /= __divisor;

__p -= 2;

std::memcpy(__p, &__base_8_lut[2 * __c], 2);

}

do {

unsigned __c = __value % 8;

__value /= 8;

*--__p = "01234567"[__c];

} while (__value != 0);

return {__last, errc(0)};

}

};

template <>

struct _LIBCPP_HIDDEN __integral<16> {

template <typename _Tp>

_LIBCPP_HIDE_FROM_ABI static constexpr int __width(_Tp __value) noexcept {

// If value == 0 still need one digit. If the value != this has no

// effect since the code scans for the most significat bit set. (Note

// that __libcpp_clz doesn't work for 0.)

return (numeric_limits<_Tp>::digits - std::__libcpp_clz(__value | 1) + 3) / 4;

}

template <typename _Tp>

_LIBCPP_HIDE_FROM_ABI static to_chars_result __to_chars(char* __first, char* __last, _Tp __value) {

ptrdiff_t __cap = __last - __first;

int __n = __width(__value);

if (__n > __cap)

return {__last, errc::value_too_large};

__last = __first + __n;

char* __p = __last;

unsigned __divisor = 256;

while (__value > __divisor) {

unsigned __c = __value % __divisor;

__value /= __divisor;

__p -= 2;

std::memcpy(__p, &__base_16_lut[2 * __c], 2);

}

if (__first != __last)

do {

unsigned __c = __value % 16;

__value /= 16;

*--__p = "0123456789abcdef"[__c];

} while (__value != 0);

return {__last, errc(0)};

}

};

} // namespace __itoa

template <unsigned _Base, typename _Tp,

typename enable_if<(sizeof(_Tp) >= sizeof(unsigned)), int>::type = 0>

_LIBCPP_HIDE_FROM_ABI int

__to_chars_integral_width(_Tp __value) {

return __itoa::__integral<_Base>::__width(__value);

}

QuuxplusoneUnsubmitted

Done

__enable_if_t<sizeof(_Tp) >= sizeof(unsigned)>* = nullptr is the more traditional libc++ism. (enable_if_t if this is C++14-and-later.)

Quuxplusone: `__enable_if_t<sizeof(_Tp) >= sizeof(unsigned)>* = nullptr` is the more traditional libc++ism.

MordanteAuthorUnsubmitted

Done

This is the same as other places in this file, so I prefer to keep it.
Note the enable_if specifies the type as int so nullptr isn't an option.

Mordante: This is the same as other places in this file, so I prefer to keep it. Note the `enable_if`…

QuuxplusoneUnsubmitted

Done

This is the same as other places in this file, so I prefer to keep it.

OK.

Note the enable_if specifies the type as int so nullptr isn't an option.

FWIW: The existing enable_if comes out to int = 0, but in my suggested "more traditional libc++ism" rewrite, the __enable_if_t would come out to void* = nullptr instead. I don't see a problem there, so either I'm missing something or you were. (The rewrite would change the mangling, but this is hide-from-abi so we shouldn't care.)

Quuxplusone: > This is the same as other places in this file, so I prefer to keep it. OK. > Note the…

MordanteAuthorUnsubmitted

Done

I prefer to keep them in this style to keep the file uniform. It indeed shouldn't be an ABI break, but I rather keep them as-is, just in case there is an issue.

Mordante: I prefer to keep them in this style to keep the file uniform. It indeed shouldn't be an ABI…

template <unsigned _Base, typename _Tp,

typename enable_if<(sizeof(_Tp) < sizeof(unsigned)), int>::type = 0>

_LIBCPP_HIDE_FROM_ABI int

__to_chars_integral_width(_Tp __value) {

return std::__to_chars_integral_width<_Base>(static_cast<unsigned>(__value));

}

template <unsigned _Base, typename _Tp,

typename enable_if<(sizeof(_Tp) >= sizeof(unsigned)), int>::type = 0>

_LIBCPP_HIDE_FROM_ABI to_chars_result

__to_chars_integral(char* __first, char* __last, _Tp __value) {

return __itoa::__integral<_Base>::__to_chars(__first, __last, __value);

}

template <unsigned _Base, typename _Tp,

typename enable_if<(sizeof(_Tp) < sizeof(unsigned)), int>::type = 0>

_LIBCPP_HIDE_FROM_ABI to_chars_result

ldionneUnsubmitted

Done

I don't think we need _LIBCPP_AVAILABILITY_TO_CHARS here, since this is all implemented in the headers. Or did I miss a dependency on the dylib?

ldionne: I don't think we need `_LIBCPP_AVAILABILITY_TO_CHARS` here, since this is all implemented in…

MordanteAuthorUnsubmitted

Done

Good catch!

Mordante: Good catch!

__to_chars_integral(char* __first, char* __last, _Tp __value) {

return std::__to_chars_integral<_Base>(__first, __last, static_cast<unsigned>(__value));

}

template <typename _Tp> template <typename _Tp>

_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_HIDE_FROM_ABI int _LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_HIDE_FROM_ABI int

__to_chars_integral_width(_Tp __value, unsigned __base) { __to_chars_integral_width(_Tp __value, unsigned __base) {

_LIBCPP_ASSERT(__value >= 0, "The function requires a non-negative value."); _LIBCPP_ASSERT(__value >= 0, "The function requires a non-negative value.");

unsigned __base_2 = __base * __base; unsigned __base_2 = __base * __base;

unsigned __base_3 = __base_2 * __base; unsigned __base_3 = __base_2 * __base;

unsigned __base_4 = __base_2 * __base_2; unsigned __base_4 = __base_2 * __base_2;

Show All 17 Lines

} }

template <typename _Tp> template <typename _Tp>

_LIBCPP_AVAILABILITY_TO_CHARS _LIBCPP_AVAILABILITY_TO_CHARS

inline _LIBCPP_HIDE_FROM_ABI to_chars_result inline _LIBCPP_HIDE_FROM_ABI to_chars_result

__to_chars_integral(char* __first, char* __last, _Tp __value, int __base, __to_chars_integral(char* __first, char* __last, _Tp __value, int __base,

false_type) false_type)

{ {

if (__base == 10) if (__base == 10) [[likely]]

philnikUnsubmitted

Done

Does this [[likely]] make any difference?

philnik: Does this `[[likely]]` make any difference?

MordanteAuthorUnsubmitted

Done

Yes I've measured in the benchmarks that it makes improvements. However I plan to refactor this file to prepare for https://wg21.link/p2291r3 "Add Constexpr Modifiers to Functions to_chars and from_chars for Integral Types in <charconv>" and 128-bit support. When the base 10 implementation moves to the header this attribute may have less benefit. But that requires another round of profiling.

Mordante: Yes I've measured in the benchmarks that it makes improvements. However I plan to refactor this…

return __to_chars_itoa(__first, __last, __value, false_type()); return __to_chars_itoa(__first, __last, __value, false_type());

switch (__base) {

case 2:

return __to_chars_integral<2>(__first, __last, __value);

case 8:

return __to_chars_integral<8>(__first, __last, __value);

case 16:

return __to_chars_integral<16>(__first, __last, __value);

}

MordanteAuthorUnsubmitted

Done

Run 1 -> #if 0
Run 2 -> #if 1

Mordante: Run 1 -> `#if 0` Run 2 -> `#if 1`

ptrdiff_t __cap = __last - __first; ptrdiff_t __cap = __last - __first;

int __n = __to_chars_integral_width(__value, __base); int __n = __to_chars_integral_width(__value, __base);

if (__n > __cap) if (__n > __cap)

return {__last, errc::value_too_large}; return {__last, errc::value_too_large};

__last = __first + __n; __last = __first + __n;

char* __p = __last; char* __p = __last;

do { do {

▲ Show 20 Lines • Show All 276 Lines • Show Last 20 Lines

This is an archive of the discontinued LLVM Phabricator instance.

[libc++] Improve std::to_chars for base != 10.ClosedPublic

Details

Diff Detail

Event Timeline

Revision Contents

Diff 429436

libcxx/include/charconv

[libc++] Improve std::to_chars for base != 10.
ClosedPublic