183 Commits

Author SHA1 Message Date
Martijn Vels 7ba045a430 Make basic_string::operator=() tail call properly
Summary: We discovered that the compiler may chose not to inline the operator=, which leads to an expensive extra stack frame. This change makes __assign_no_alias always tail called.

Reviewers: EricWF, #libc!

Subscribers: libcxx-commits

Tags: #libc

Differential Revision: https://reviews.llvm.org/D77913
2020-04-10 19:41:46 -04:00
Martijn Vels b019c5c037 Partially inline basic_string copy constructor in UNSTABLE
Summary:
    This is a recommit of https://reviews.llvm.org/D73223 where the added function accidentally ended up inside an idef block.

    This change splits the copy constructor up inlining short initialization, and explicitly outlining long initialization into __init_copy_ctor_external() which is the externally instantiated slow path.

    For unstable ABI, this has the following changes:

    remove basic_string(const basic_string&)
    remove basic_string(const basic_string&, const Allocator&)
    add __init_copy_ctor_external(const value_type*, size_type)
    Quick local benchmark for Copy:

    Master
    ```
    ---------------------------------------------------------------
    Benchmark                    Time             CPU   Iterations
    ---------------------------------------------------------------
    BM_StringCopy_Empty       3.50 ns         3.51 ns    199326720
    BM_StringCopy_Small       3.50 ns         3.51 ns    199510016
    BM_StringCopy_Large       15.7 ns         15.7 ns     45230080
    BM_StringCopy_Huge        1503 ns         1503 ns       464896
    ```
    With this change
    ```
    ---------------------------------------------------------------
    Benchmark                    Time             CPU   Iterations
    ---------------------------------------------------------------
    BM_StringCopy_Empty       1.99 ns         2.00 ns    356471808
    BM_StringCopy_Small       3.29 ns         3.30 ns    203425792
    BM_StringCopy_Large       13.3 ns         13.3 ns     52948992
    BM_StringCopy_Huge        1472 ns         1472 ns       475136
    ```

    Subscribers: libcxx-commits

    Tags: #libc

    Differential Revision: https://reviews.llvm.org/D75639
2020-03-04 17:52:46 -05:00
Martijn Vels 3712edb152 Revert "Partially inline basic_string copy constructor in UNSTABLE"
This reverts commit 8cf76e913b.

We are investigating why this causes compilation issues under -O3
2020-03-04 14:52:17 -05:00
Eric Fiselier 5891e7302f [libc++] Move std::string extern template declarations to end of class.
They need to appear before any member functions are ODR used, because
they change the visibility of many of these functions and otherwise
they could end up with hidden visibility in the DSO.
2020-03-04 13:57:29 -05:00
Martijn Vels 8cf76e913b Partially inline basic_string copy constructor in UNSTABLE
his change splits the copy constructor up inlining short initialization, and explicitly outlining long initialization into __init_copy_ctor_external() which is the externally instantiated slow path.

For unstable ABI, this has the following changes:

remove basic_string(const basic_string&)
remove basic_string(const basic_string&, const Allocator&)
add __init_copy_ctor_external(const value_type*, size_type)
Quick local benchmark for Copy:

Master
```
---------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
---------------------------------------------------------------
BM_StringCopy_Empty       3.50 ns         3.51 ns    199326720
BM_StringCopy_Small       3.50 ns         3.51 ns    199510016
BM_StringCopy_Large       15.7 ns         15.7 ns     45230080
BM_StringCopy_Huge        1503 ns         1503 ns       464896
```

```
---------------------------------------------------------------
Benchmark                    Time             CPU   Iterations
---------------------------------------------------------------
BM_StringCopy_Empty       1.99 ns         2.00 ns    356471808
BM_StringCopy_Small       3.29 ns         3.30 ns    203425792
BM_StringCopy_Large       13.3 ns         13.3 ns     52948992
BM_StringCopy_Huge        1472 ns         1472 ns       475136
```

Author: Martijn Vels <martijn.vels@gmail.com>

Reviewers: EricWF, mclow.list

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D73223
2020-03-03 17:49:25 -05:00
Martijn Vels 675326466b Add flag _LIBCPP_ABI_STRING_OPTIMIZED_EXTERNAL_INSTANTIATIONS for basic_string ABI
Summary: This review is a mostly trivial change to use an explicit ABI flag for the unstable external template list. This follows the practice for an ABI flag per feature, and provides a spot for the rational / motivation for the flag.

Reviewers: EricWF, ldionne

Subscribers: dexonsmith, libcxx-commits

Tags: #libc

Differential Revision: https://reviews.llvm.org/D75457
2020-03-02 10:26:37 -05:00
Martijn Vels f87d30cba2 Partially inline basic_string::operator=(const basic_string&)
Summary:
This change partially inlines operator=(const basic_string&) where both the input and current instance are short strings, making the assignment a fixed length inlined memcpy.

Assignments where either of the strings are long are delegate to __assign_no_alias<__is_short>(), which is templated for the long / short branch already observed in the caller.

Stable:
```
--------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
--------------------------------------------------------------------------------
BM_StringAssignStr_Empty_Opaque            2.65 ns         2.66 ns    263745536
BM_StringAssignStr_Empty_Transparent       2.95 ns         2.96 ns    236494848
BM_StringAssignStr_Small_Opaque            2.93 ns         2.94 ns    237301760
BM_StringAssignStr_Small_Transparent       2.69 ns         2.69 ns    265809920
BM_StringAssignStr_Large_Opaque            19.6 ns         19.6 ns     35573760
BM_StringAssignStr_Large_Transparent       19.1 ns         19.1 ns     36716544
BM_StringAssignStr_Huge_Opaque             1901 ns         1901 ns       364544
BM_StringAssignStr_Huge_Transparent        1889 ns         1889 ns       360448
```

Unstable
```
--------------------------------------------------------------------------------
Benchmark                                     Time             CPU   Iterations
--------------------------------------------------------------------------------
BM_StringAssignStr_Empty_Opaque            1.29 ns         1.29 ns    540454912
BM_StringAssignStr_Empty_Transparent       1.11 ns         1.12 ns    628482048
BM_StringAssignStr_Small_Opaque            1.29 ns         1.29 ns    541216768
BM_StringAssignStr_Small_Transparent       1.11 ns         1.11 ns    629469184
BM_StringAssignStr_Large_Opaque            15.6 ns         15.6 ns     44945408
BM_StringAssignStr_Large_Transparent       14.9 ns         14.9 ns     46764032
BM_StringAssignStr_Huge_Opaque             1713 ns         1713 ns       401408
BM_StringAssignStr_Huge_Transparent        1704 ns         1704 ns       397312

```

Subscribers: libcxx-commits

Tags: #libc

Differential Revision: https://reviews.llvm.org/D75211
2020-03-02 09:58:11 -05:00
Martijn Vels d260ea7199 Inline basic_string::erase for fastpath where __n == npos
Summary:
This change checks for the case where people want to erase a string to the end, i.e., __n == npos, and inlines the call if so.

This also demonstrates keeping the ABI intact for V1, but inlining the erase() method for unstable.

Reviewers: EricWF, mclow.lists, ldionne

Reviewed By: EricWF, ldionne

Subscribers: smeenai, dexonsmith, christof, libcxx-commits

Tags: #libc

Differential Revision: https://reviews.llvm.org/D73743
2020-02-26 13:37:45 -05:00
Martijn Vels d8969a1cb9 Split _LIBCPP_STRING_EXTERN_TEMPLATE_LIST up into a V1 and UNSTABLE version.
This change splits the _LIBCPP_STRING_EXTERN_TEMPLATE_LIST up into a _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST containing the stable ABI, and a _LIBCPP_STRING_UNSTABLE_EXTERN_TEMPLATE_LIST containing the unstable ABI.

The purpose is to explicitly define and maintain the two lists, where the unstable ABI allows for ABI breaking changes for purposes such as optimization while offering a strong guarantee that any change inside the unstable ABI does not affect the stable ABI.

As per the comment in the __string header, we do still allow etries to be added to the stable ABI list as the c++ versions and corresponding c++ std API changes.
2020-02-20 23:21:14 -05:00
Martijn Vels 282b803b62 White space only change: reflow a comment in basic_string
Summary: This change reflows a comment line. This change serves as a no-op test commit

Reviewers: mclow.lists, ldionne, EricWF

Subscribers: dexonsmith, christof, libcxx-commits

Tags: #libc

Differential Revision: https://reviews.llvm.org/D73552
2020-01-30 19:55:48 -05:00
Eric Fiselier fa40b41168 Revert "[libc++] Optimize / partially inline basic_string copy constructor"
This reverts commit a8a9c8e0a1.

There are multiple reported failures caused by this change.
Each failure is really weird, but it makes sense to revert
while investigating.
2020-01-20 21:41:58 -05:00
Eric Fiselier a8a9c8e0a1 [libc++] Optimize / partially inline basic_string copy constructor
Splits copy constructor up inlining short initialization, outlining long
initialization into __init_long() which is the externally instantiated slow
path initialization.

Subsequently changing the copy ctor to be inlined (not externally instantiated)
provides significant speed ups for short string initialization.

Generated code given:

void StringCopyCtor(void* mem, const std::string& s) {
    std::string*p = new(mem) std::string{s};
}

asm:
        cmp     byte ptr [rsi + 23], 0
        js      .LBB0_2
        mov     rax, qword ptr [rsi + 16]
        mov     qword ptr [rdi + 16], rax
        movups  xmm0, xmmword ptr [rsi]
        movups  xmmword ptr [rdi], xmm0
        ret
.LBB0_2:
        jmp     std::basic_string::__init_long # TAILCALL

Benchmark:
BM_StringCopy_Empty                                           5.19ns ± 6%             1.50ns ± 8%  -71.02%        (p=0.000 n=10+10)
BM_StringCopy_Small                                           5.14ns ± 8%             1.53ns ± 7%  -70.17%        (p=0.000 n=10+10)
BM_StringCopy_Large                                           18.9ns ± 0%             19.3ns ± 0%   +1.92%        (p=0.000 n=10+10)
BM_StringCopy_Huge                                             309ns ± 1%              316ns ± 5%     ~            (p=0.633 n=8+10)

Patch from Martijn Vels (mvels@google.com)
Reviewed as D72160.
2020-01-17 16:53:54 -05:00
Eric Fiselier 59919c4d6b [libc++] Fix Windows DLL build for string.
We need to mark string::npos with _LIBCPP_FUNC_VIS on the first
in-class declaration, otherwise it might get ignored
2020-01-16 15:01:12 -05:00
Eric Fiselier 313d89724c [libc++] Fix parsing <string> in C++03.
Specifically, add a space between >> when closing templates.
2020-01-15 17:29:55 -05:00
Eric Fiselier 58c7fa5ade [libc++] Optimize basic_string::operator=(const basic_string&) for SSO assignments
This change optimizes the operator=() assignment for short strings by direcly
copying the raw data from the source into the current instance. This creates an
optimized / inlined mempcy up to over 2X faster for short string assignments.
With inlining enabled for operator=, performance is up to 6X faster.

Benchmarks 'as is':
name                                    old time/op   new time/op    delta
BM_StringAssignStr_Empty_Opaque         6.05ns ± 2%   3.59ns ± 0%  -40.67%
BM_StringAssignStr_Empty_Transparent    5.15ns ± 0%   3.08ns ± 0%  -40.12%
BM_StringAssignStr_Small_Opaque         7.71ns ± 0%   3.59ns ± 0%  -53.45%
BM_StringAssignStr_Small_Transparent    7.66ns ± 0%   3.09ns ± 0%  -59.66%
BM_StringAssignStr_Large_Opaque         24.1ns ± 0%   24.9ns ± 0%   +3.22%
BM_StringAssignStr_Large_Transparent    22.2ns ± 0%   22.8ns ± 0%   +2.77%
BM_StringAssignStr_Huge_Opaque           315ns ± 6%    320ns ± 5%     ~
BM_StringAssignStr_Huge_Transparent      318ns ± 5%    321ns ± 4%     ~

Benchmarks with partial inlining operator=():
name                                    old time/op   new time/op    delta
BM_StringAssignStr_Empty_Opaque         5.94ns ± 2%   1.95ns ± 0%  -67.21%
BM_StringAssignStr_Empty_Transparent    5.14ns ± 0%   1.04ns ± 1%  -79.73%
BM_StringAssignStr_Small_Opaque         7.69ns ± 0%   1.96ns ± 0%  -74.48%
BM_StringAssignStr_Small_Transparent    7.65ns ± 0%   1.04ns ± 0%  -86.40%
BM_StringAssignStr_Large_Opaque         24.1ns ± 0%   24.5ns ± 0%   +1.61%
BM_StringAssignStr_Large_Transparent    22.2ns ± 0%   21.1ns ± 0%   -4.70%
BM_StringAssignStr_Huge_Opaque           317ns ± 5%    323ns ± 4%     ~
BM_StringAssignStr_Huge_Transparent      318ns ± 5%    320ns ± 5%     ~

Patch by Martijn Vels (mvels@google.com)
Reviewed as https://reviews.llvm.org/D72704
2020-01-15 17:27:10 -05:00
Eric Fiselier 288a143639 [libc++] Explicitly enumerate std::string external instantiations - Attempt 2
The GCC build failures have been addressed, and the LLDB failures were
  fixed by LLDB.

   I have also verified that the apple-clang 9.0 segfault no longer
   occurs.

Original Message:

 The external instantiation of std::string is a problem for libc++.
    Additions and removals of inline functions in string can cause ABI
    breakages, including introducing new symbols.

    This patch aims to:
      (1) Make clear which functions are explicitly instatiated.
      (2) Prevent new functions from being accidentally instantiated.
      (3) Allow a migration path for adding or removing functions from the
      explicit instantiation over time.

    Although this new formulation is uglier, it is preferable from a
    maintainability and readability standpoint because it explicitly
    enumerates the functions we've chosen to expose in our ABI. Changing
    this list is non-trivial and requires thought and planning.

    (3) is achieved by making it possible to control the extern template declaration
    separately from it's definition. Meaning we could add a new definition to
    the dylib, wait for it to roll out, then add the extern template
    declaration to the header. Similarly, we could remove existing extern
    template declarations while still keeping the definition to prevent ABI
    breakages.
2020-01-15 17:12:49 -05:00
Eric Fiselier 2d8f23f571 [libc++] Explicitly mark basic_string<...>::npos with default
visibility.

This ensures that the version compiled into the library isn't
accidentally hidden.
2020-01-15 17:02:17 -05:00
Eric Fiselier 24d2a015ea [libc++] Make SFINAE'd member functions in string mutually exclusive.
This patch is needed in order to work around a GCC bug that fails to
explicitly instantiate a non-template function of a class template when
there is another overload that's a function template.
(See https://godbolt.org/z/4bUQ_b)

This patch SFINAE's away the function templates when the argument is
a basic_string.
2020-01-15 17:00:26 -05:00
Oliver Stannard 6a634a5dba Revert "[libc++] Explicitly enumerate std::string external instantiations."
This is causing failures for multiple buildbots and bootstrap builds,
details at https://reviews.llvm.org/rG61bd1920.

This reverts commit 61bd19206f.
2020-01-13 13:54:04 +00:00
Eric Fiselier 61bd19206f [libc++] Explicitly enumerate std::string external instantiations.
The external instantiation of std::string is a problem for libc++.
    Additions and removals of inline functions in string can cause ABI
    breakages, including introducing new symbols.

    This patch aims to:
      (1) Make clear which functions are explicitly instatiated.
      (2) Prevent new functions from being accidentally instantiated.
      (3) Allow a migration path for adding or removing functions from the
      explicit instantiation over time.

    Although this new formulation is uglier, it is preferable from a
    maintainability and readability standpoint because it explicitly
    enumerates the functions we've chosen to expose in our ABI. Changing
    this list is non-trivial and requires thought and planning.

    (3) is achieved by making it possible to control the extern template declaration
    separately from it's definition. Meaning we could add a new definition to
    the dylib, wait for it to roll out, then add the extern template
    declaration to the header. Similarly, we could remove existing extern
    template declarations while still keeping the definition to prevent ABI
    breakages.
2020-01-09 15:51:02 -05:00
Eric Fiselier a53534a9f6 [libc++] Add __default_init_tag to basic_string constructors
This removes unneeded zero initialization of string data.

For example, given the below code:

void Init(void *mem) {
    new (mem) std::string("Hello World");
}

Assembly before:

Init(void*):
        xorps   xmm0, xmm0
        movups  xmmword ptr [rdi], xmm0
        mov     qword ptr [rdi + 16], 0
        mov     byte ptr [rdi], 22
        movabs  rax, 8022916924116329800
        mov     qword ptr [rdi + 1], rax
        mov     dword ptr [rdi + 8], 1684828783
        mov     byte ptr [rdi + 12], 0
        ret

Assembly after:

Init():
        mov     byte ptr [rdi], 22
        movabs  rax, 8022916924116329800
        mov     qword ptr [rdi + 1], rax
        mov     dword ptr [rdi + 8], 1684828783
        mov     byte ptr [rdi + 12], 0
        ret

Patch by Martijn Vels (mvels@google.com)
Reviewed as https://reviews.llvm.org/D70621
2019-12-16 19:04:09 -05:00
Eric Fiselier 549545b64a [libc++] Rework compressed pair constructors.
This patch de-duplicates most compressed pair constructors
to use the same code in C++11 and C++03.

Part of doing that is deleting the "__second_tag()" and replacing
it with a "__value_init_tag()" which has the same effect, but
allows for the removal of the special "one-arg" first element
constructor.

This patch is intended to have no semantic change.
2019-12-16 18:38:58 -05:00
marshall 703c26f03b Optimize and fix basic_string move assignment operator. Reviewed as https://reviews.llvm.org/D68623. Thanks to mvels for the patch. 2019-11-27 07:13:32 -08:00
Eric Fiselier f82dba0192 Rename __is_foo_iterator traits to reflect their Cpp17 nature.
With the upcoming introduction of iterator concepts in ranges,
the meaning of "__is_contiguous_iterator" changes drastically.

Currently we intend it to mean "does it have this iterator category",
but it could now also mean "does it meet the requirements of this
concept", and these can be different.
2019-11-18 01:49:32 -05:00
Eric Fiselier 0068c59139 [libc++] Rename __to_raw_pointer to __to_address.
This function has the same behavior as the now-standand std::to_address.
Re-using the name makes the behavior more clear, and in the future it
will allow us to correctly get the raw pointer for user provided pointer
types.
2019-11-16 17:16:09 -05:00