This is an archive of the discontinued LLVM Phabricator instance.

Partially inline basic_string::assign(__s [, __n]) methods.
ClosedPublic

Authored by mvels on Mar 3 2020, 11:39 AM.

Details

Summary

This change adds constant value detection to the assign methods, which optimizes the assigment of compile time known constant string values.

The compiler elides either to the non-constant or constant code execution. The assign() methods are removed from the external template for the unstable ABI.

All assignment calls now fallback to the __assign_inlined() implementation code, which allows future changes where we do not call into the 'grow_by_and_replace' but specialize for SSO --> non SSO and non SSO --> non SSO growths.

Notice that this change does NOT take an early branch in the assign() methods. We may consider adding early branches, however, the compiler's inlining heuristics then go negative on inlining the code even as the constant optimization should be pretty clean cut. (this is likely only an issue for non FDO builds, but for now we use a single external implementation).

Benchmark STABLE / V1:

-----------------------------------------------------------------------------------
Benchmark                                        Time             CPU   Iterations
-----------------------------------------------------------------------------------
BM_StringAssignAsciiz_Empty_Opaque            6.61 ns         6.62 ns    105451520
BM_StringAssignAsciiz_Empty_Transparent       6.43 ns         6.43 ns    108793856
BM_StringAssignAsciiz_Small_Opaque            8.61 ns         8.61 ns     81317888
BM_StringAssignAsciiz_Small_Transparent       8.33 ns         8.33 ns     84029440
BM_StringAssignAsciiz_Large_Opaque            19.7 ns         19.7 ns     35692544
BM_StringAssignAsciiz_Large_Transparent       19.2 ns         19.2 ns     36343808
BM_StringAssignAsciiz_Huge_Opaque             1696 ns         1696 ns       401408
BM_StringAssignAsciiz_Huge_Transparent        1743 ns         1743 ns       397312
BM_StringAssignAsciizMix_Opaque               11.8 ns         11.8 ns     59224064
BM_StringAssignAsciizMix_Transparent          11.9 ns         11.9 ns     58802176

Benchmark UNSTABLE / V2 without this change:

-----------------------------------------------------------------------------------
Benchmark                                        Time             CPU   Iterations
-----------------------------------------------------------------------------------
BM_StringAssignAsciiz_Empty_Opaque            6.24 ns         6.25 ns    109424640
BM_StringAssignAsciiz_Empty_Transparent       5.92 ns         5.93 ns    118013952
BM_StringAssignAsciiz_Small_Opaque            7.60 ns         7.60 ns     92065792
BM_StringAssignAsciiz_Small_Transparent       7.80 ns         7.81 ns     89632768
BM_StringAssignAsciiz_Large_Opaque            19.9 ns         19.9 ns     35254272
BM_StringAssignAsciiz_Large_Transparent       19.1 ns         19.1 ns     36786176
BM_StringAssignAsciiz_Huge_Opaque             1717 ns         1717 ns       389120
BM_StringAssignAsciiz_Huge_Transparent        1723 ns         1722 ns       397312
BM_StringAssignAsciizMix_Opaque               11.2 ns         11.2 ns     62922752
BM_StringAssignAsciizMix_Transparent          11.1 ns         11.1 ns     62586880

Benchmark UNSTABLE / V2 with this change:

-----------------------------------------------------------------------------------
Benchmark                                        Time             CPU   Iterations
-----------------------------------------------------------------------------------
BM_StringAssignAsciiz_Empty_Opaque            4.92 ns         4.93 ns    136773632
BM_StringAssignAsciiz_Empty_Transparent      0.834 ns        0.835 ns    837238784
BM_StringAssignAsciiz_Small_Opaque            7.02 ns         7.03 ns     99655680
BM_StringAssignAsciiz_Small_Transparent       1.10 ns         1.10 ns    634368000
BM_StringAssignAsciiz_Large_Opaque            18.3 ns         18.3 ns     38576128
BM_StringAssignAsciiz_Large_Transparent       14.3 ns         14.3 ns     48939008
BM_StringAssignAsciiz_Huge_Opaque             1716 ns         1716 ns       393216
BM_StringAssignAsciiz_Huge_Transparent        1688 ns         1688 ns       409600
BM_StringAssignAsciizMix_Opaque               9.96 ns         9.95 ns     70467584
BM_StringAssignAsciizMix_Transparent          4.34 ns         4.34 ns    164167680

Diff Detail

Event Timeline

mvels created this revision.Mar 3 2020, 11:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 3 2020, 11:39 AM
ldionne requested changes to this revision.Mar 3 2020, 1:24 PM
ldionne added inline comments.
libcxx/include/string
2291

I don't quite understand why we don't also call __assign_maybe_alias(__s, __n); in this case?

This revision now requires changes to proceed.Mar 3 2020, 1:24 PM
mvels updated this revision to Diff 248052.Mar 3 2020, 3:03 PM
mvels marked 2 inline comments as done.

Fixed bug / omitting __n parameter

libcxx/include/string
2291

That is a bug (the checks actually fail on it) resulting from some lazy copy-paste from my side :\ Fixed.

mvels updated this revision to Diff 248053.Mar 3 2020, 3:06 PM

Diff to HEAD

Harbormaster completed remote builds in B47987: Diff 248053.
ldionne requested changes to this revision.Mar 4 2020, 6:17 AM
ldionne added inline comments.
libcxx/include/string
1585

Nitpick: and__assign_maybe_alias is missing a space

1591

nitpick typo: that the it fits

2288

We could call __assign_maybe_alias(__s, traits_type::length(__s)) instead to avoid code duplication?

2293

Just to confirm my understanding: at this point we don't know whether *this is short or long, however we do know [__s, __s + __n) is going to fit in whatever string we have, cause __n would fit in the short string.

However, why do we know there's no aliasing (which __assign_in_place assumes)?

2481

Why don't we instead do:

if (_LIBCPP_BUILTIN_CONSTANT_P(__s[0])) {
    assign(__s, traits_type::length(__s));
} else {
    __assign_maybe_alias(__s);
}

I think both are equivalent, but we duplicate less code.

This revision now requires changes to proceed.Mar 4 2020, 6:17 AM
mvels updated this revision to Diff 248329.Mar 4 2020, 2:51 PM

New diff after rebase

This revision was not accepted when it landed; it landed in state Needs Review.Mar 4 2020, 3:14 PM
This revision was automatically updated to reflect the committed changes.