Inline hot functions in libcxx shared_ptr implementation.

[hxy9243]

Summary

This patch moves some existing functions from the memory.cpp to the memory header file, so that they could be properly inlined, which gives potential optimization opportunities and performance benefits.

[halyavin]

libcxx/include/atomic_support.h

1 ↗

(On Diff #72725)

Non-standard include files in the main include directory must start with __ to avoid collisions with application headers.

1 ↗

(On Diff #72725)

Does anyone know why this header exists and atomic header can't be used instead?

[hxy9243]

Addresses comments from @halyavin, rename "atomic_support.h" to "__atomic_support" to avoid collisions with application headers.

[mclow.lists]

How does this play with existing binaries? Applications that expect these functions to exist in the dylib?

[EricWF]

In D24991#565715, @mclow.lists wrote:

How does this play with existing binaries? Applications that expect these functions to exist in the dylib?

This patch is majorly ABI breaking, although we could probably find a formulation that wasn't.

@hxy9243 wrote:

which gives potential optimization opportunities and performance benefits.

Please provide benchmark tests which demonstrate that these benefits are concrete and not just "potential". Moving methods out of the dylib is no easy task so I would like hard evidence that it's worth while.

libcxx/include/memory

3684

Anonymous namespaces are a C++11 feature and this is C++03 code.

3689

• T and increment need to be reserved names.
• Never use __attribute__((always_inline)) directly, that's why we have visibility macros.

3693

Why add increment and decrement at all? Just manually inline __libcpp_atomic_add at the callsites.

3727

Why would you want to inline this?

[sebpop]

In D24991#565861, @EricWF wrote:

Please provide benchmark tests which demonstrate that these benefits are concrete and not just "potential". Moving methods out of the dylib is no easy task so I would like hard evidence that it's worth while.

With this patch we have seen the score of a proprietary benchmark going up by 20%, matching the performance we see with LLVM + libstdc++.
We will provide a testcase that shows the performance uplift.

[EricWF]

In D24991#566140, @sebpop wrote:

In D24991#565861, @EricWF wrote:

Please provide benchmark tests which demonstrate that these benefits are concrete and not just "potential". Moving methods out of the dylib is no easy task so I would like hard evidence that it's worth while.

With this patch we have seen the score of a proprietary benchmark going up by 20%, matching the performance we see with LLVM + libstdc++.
We will provide a testcase that shows the performance uplift.

20% sounds amazing! Thanks for working on this.

[hxy9243]

Thanks for pointing out. It's true that it may cause ABI breakage. It would be nice to keep compatibility while getting the performance benefits from inlining.

I've tested the patch with google-benchmark/util_smartptr_libcxx shipped with libcxx on x86_64 server, and attached the results as following:

BASE libcxx r283113:
$   taskset -c 23 ./util_smartptr.libcxx.out
Run on (24 X 1200 MHz CPU s)
2016-10-12 13:52:03
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
Benchmark                          Time           CPU Iterations
----------------------------------------------------------------
BM_SharedPtrCreateDestroy         54 ns         54 ns   12388755
BM_SharedPtrIncDecRef             37 ns         37 ns   19021739
BM_WeakPtrIncDecRef               38 ns         38 ns   18421053
 


libcxx with patch:
$   taskset -c 23 ./util_smartptr.libcxx.out
Run on (24 X 1200 MHz CPU s)
2016-10-12 13:48:38
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
Benchmark                          Time           CPU Iterations
----------------------------------------------------------------
BM_SharedPtrCreateDestroy         44 ns         44 ns   14730639
BM_SharedPtrIncDecRef             18 ns         18 ns   38888889
BM_WeakPtrIncDecRef               30 ns         30 ns   23648649

[sebpop]

In D24991#565861, @EricWF wrote:

In D24991#565715, @mclow.lists wrote:

How does this play with existing binaries? Applications that expect these functions to exist in the dylib?

This patch is majorly ABI breaking, although we could probably find a formulation that wasn't.

Eric, Marshall,
any suggestions on how to fix the backwards compatibility issue?

Thanks!

[hiraditya]

Marshall suggests using macro as we discussed offline. For some reason the reply does not appear here: http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20161010/173780.html

[sebpop]

In D24991#571056, @hiraditya wrote:

Marshall suggests using macro as we discussed offline. For some reason the reply does not appear here: http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20161010/173780.html

Ping.

[sebpop]

The patch also implements the idea that Marshall proposed in:
http://lists.llvm.org/pipermail/cfe-commits/Week-of-Mon-20161010/173780.html

I have an idea; it involves a macro that is sometimes "inline" and
sometimes not, and changes when you're building the library vs. when you're
just including the headers.

Tested on x86_64-linux.
The symbols for the functions that are now inlined still appear in the libc++.so.

Ok to commit?

[sebpop]

libcxx/include/memory

3693

I like the idea to manually inline the inc and dec functions.
What should we do with the NOTE: above?

NOTE: Relaxed and acq/rel atomics (for increment and decrement respectively)
should be sufficient for thread safety.
// See https://llvm.org/bugs/show_bug.cgi?id=22803

should we just go ahead and remove the note, or you want to have it where inc/dec are called? (about a dozen places.)

[hxy9243]

Looks good to me.
Notice that the performance gain can only be observed when compiled with the updated C++ header files.

[sebpop]

Ping: Eric, Marshall, could you please approve or comment on this patch?
Thanks!

[kubamracek]

Just a question: TSan intercepts on the dylib functions, namely __release_shared, to track the atomic accesses. Can you make sure this doesn't break? There's a few testcases for this in compiler-rt.

[sebpop]

In D24991#583877, @kubabrecka wrote:

Just a question: TSan intercepts on the dylib functions, namely __release_shared, to track the atomic accesses. Can you make sure this doesn't break? There's a few testcases for this in compiler-rt.

I just ran ninja check-all with and without this patch and there are no regressions in compiler-rt on an x86_64-linux machine.

[kubamracek]

In D24991#586219, @sebpop wrote:

I just ran ninja check-all with and without this patch and there are no regressions in compiler-rt on an x86_64-linux machine.

The TSan interceptors (and testcases) are Darwin-only at this point. I'll run the tests on my machine.

[hxy9243]

In D24991#586248, @kubabrecka wrote:

In D24991#586219, @sebpop wrote:

I just ran ninja check-all with and without this patch and there are no regressions in compiler-rt on an x86_64-linux machine.

The TSan interceptors (and testcases) are Darwin-only at this point. I'll run the tests on my machine.

Any updates on the testing? Thanks very much!

[kubamracek]

This passes TSan tests on Darwin. LGTM.

[sebpop]

@mclow.lists, @EricWF, ok to commit the patch?

Thanks,
Sebastian

[hxy9243]

Ping. @mclow.lists, @EricWF, any ideas on this patch?
Thanks very much!

[sebpop]

@mclow.lists could you please have a last look at this patch: the change is for a performance improvement (20% uplift on a proprietary benchmark), and all the issues mentioned in the review have been addressed.
The existing synthetic benchmark shows an overall improvement:

master:
Benchmark                          Time           CPU Iterations
----------------------------------------------------------------
BM_SharedPtrCreateDestroy         54 ns         54 ns   12388755
BM_SharedPtrIncDecRef             37 ns         37 ns   19021739
BM_WeakPtrIncDecRef               38 ns         38 ns   18421053
 
master + patch:
Benchmark                          Time           CPU Iterations
----------------------------------------------------------------
BM_SharedPtrCreateDestroy         44 ns         44 ns   14730639
BM_SharedPtrIncDecRef             18 ns         18 ns   38888889
BM_WeakPtrIncDecRef               30 ns         30 ns   23648649

[EricWF]

Added a bunch of inline comments.

The biggest requested change is removing the __atomic_support header. We only need one atomic call within the headers. It's overkill to add a new header.

libcxx/include/__atomic_support

1 ↗

(On Diff #75908)

I would greatly prefer if this patch didn't add another header, and simply defined __libcpp_atomic_increment and __libcpp_atomic_decrement in place of __atomic_inc_dec::increment/__atomic_inc_dec::decrement.

libcxx/include/memory

3693

Neremind about the manually inlining bit.

Please remove the __atomic_inc_dec namespace and rename increment to __libcpp_atomic_increment and decrement to __libcpp_atomic_decrement.

Please also remove the __atomic_support header and instead simply call __atomic_add_fetch from inside the functions.

3757–3758

Please apply _LIBCPP_FUNC_VIS to both of these methods.

3760

the inline in redundant if you define the function inside the class.

3794–3795

Please add _LIBCPP_FUNC_VIS to the three methods.

3797

inline is redundant here.

[hxy9243]

Move the header back in its place, and only copy over necessary parts. Now call __atomic_add_fetch from inside the functions.

[hxy9243]

Minor fix, remove redundant inlines.

[hxy9243]

Addressed previous issues in the comments. The patch still shows consistent perf uplift in proprietary benchmark on shared_ptr.

@EricWF @sebpop @hiraditya Any thoughts?

[kubamracek]

libcxx/include/memory

3702

I don't think this should be named __libcpp_atomic_increment, because it uses relaxed ordering and thus it's not a generic increment (same goes for decrement). Could we rename this to __libcpp_atomic_refcount_increment or something similar? That would suggest why we're using acq+rel on one side and relaxed on other side. Using these functions for non-refcount purposes will be wrong and the current names (__libcpp_atomic_increment) suggest that they're doing generic atomic operations.

[hxy9243]

Adresses comments from @kubabrecka: minor changes on function names. Rename __libcpp_atomic_* to __libcpp_atomic_refcount_*.

[EricWF]

Almost LGTM. Just a couple of inline comments left. Thanks for working on this!

libcxx/include/memory

3691

1. I would reduce these checks down to only what we need in the headers.
2. I would rename _LIBCPP_HAS_ATOMIC_BUILTINS to _LIBCPP_HAS_BUILTIN_ATOMIC_SUPPORT so it doesn't conflict with atomic_support.h and so we don't get it confused with all of the other _LIBCPP_ATOMIC configuration macros.
3. This is missing the configuration checks for GCC. Specifically #elif !defined(__clang__) && defined(_GNUC_VER) && _GNUC_VER >= 407

3701

inline _LIBCPP_INLINE_VISIBILITY

3759

_LIBCPP_FUNC_VIS goes before the return type.

3797

_LIBCPP_FUNC_VIS goes before the return type.

[hxy9243]

Addresses comments from @EricWF.

Thanks for reviewing, I know it takes a lot of energy. It helped me learn a lot.

[mclow.lists]

libcxx/include/memory

3700

template <class _Tp>, please.

Otherwise when some client code does #define T true (yes, I've seen that!) this breaks. _Tp is a reserved identifier, and if they use that, we can point at them and laugh.

3702

The parameter name needs to be reserved as well. __t, please.

3711

Same comment as L3700

3713

Same comment as L3702

[hxy9243]

Addresses comments from @mclow.lists.

[EricWF]

LGTM.

libcxx/include/memory

#ifndef _LIBCPP_NO_EXCEPTIONS
         throw;
     }
 #endif
 }
 
 
 #endif // _LIBCPP_STD_VER > 14
 
+// NOTE: Relaxed and acq/rel atomics (for increment and decrement respectively)
+// should be sufficient for thread safety.
+// See https://llvm.org/bugs/show_bug.cgi?id=22803
+#if defined(__clang__) && __has_builtin(__atomic_load_n)             \
+                       && __has_builtin(__atomic_store_n)            \
+                       && __has_builtin(__atomic_add_fetch)          \
+                       && __has_builtin(__atomic_compare_exchange_n) \
+                       && defined(__ATOMIC_RELAXED)                  \
+                       && defined(__ATOMIC_CONSUME)                  \
+                       && defined(__ATOMIC_ACQUIRE)                  \
+                       && defined(__ATOMIC_RELEASE)                  \
+                       && defined(__ATOMIC_ACQ_REL)                  \
+                       && defined(__ATOMIC_SEQ_CST)
+#   define _LIBCPP_HAS_ATOMIC_BUILTINS
+#endif
+
+template <class T>
+inline T
+__libcpp_atomic_refcount_increment(T& t) _NOEXCEPT
+{
+#if defined(_LIBCPP_HAS_ATOMIC_BUILTINS) && !defined(_LIBCPP_HAS_NO_THREADS)
+    return __atomic_add_fetch(&t, 1, __ATOMIC_RELAXED);
+#else
+    return t += 1;
+#endif
+}
+
+template <class T>
+inline T
+__libcpp_atomic_refcount_decrement(T& t) _NOEXCEPT
+{
+#if defined(_LIBCPP_HAS_ATOMIC_BUILTINS) && !defined(_LIBCPP_HAS_NO_THREADS)
+    return __atomic_add_fetch(&t, -1, __ATOMIC_ACQ_REL);
+#else
+    return t -= 1;
+#endif
+}
+
 class _LIBCPP_EXCEPTION_ABI bad_weak_ptr
     : public std::exception
 {
 public:
     virtual ~bad_weak_ptr() _NOEXCEPT;
     virtual const char* what() const  _NOEXCEPT;
 };
 
 _LIBCPP_NORETURN inline _LIBCPP_ALWAYS_INLINE
 void __throw_bad_weak_ptr()
 {
 #ifndef _LIBCPP_NO_EXCEPTIONS
     throw bad_weak_ptr();
 #else
protected:
     virtual ~__shared_count();
 private:
     virtual void __on_zero_shared() _NOEXCEPT = 0;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
     explicit __shared_count(long __refs = 0) _NOEXCEPT
         : __shared_owners_(__refs) {}
 
-    void __add_shared() _NOEXCEPT;
-    bool __release_shared() _NOEXCEPT;
+#ifdef _LIBCPP_BUILDING_MEMORY
+    void _LIBCPP_FUNC_VIS __add_shared() _NOEXCEPT;
+    bool _LIBCPP_FUNC_VIS __release_shared() _NOEXCEPT;
+#else
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_shared() _NOEXCEPT {
+      __libcpp_atomic_refcount_increment(__shared_owners_);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    bool __release_shared() _NOEXCEPT {
+      if (__libcpp_atomic_refcount_decrement(__shared_owners_) == -1) {
+        __on_zero_shared();
+        return true;
+      }
+      return false;
+    }
+#endif
     _LIBCPP_INLINE_VISIBILITY
     long use_count() const _NOEXCEPT {
         return __libcpp_relaxed_load(&__shared_owners_) + 1;
     }
 };
 
 class _LIBCPP_TYPE_VIS __shared_weak_count
     : private __shared_count
 {
     long __shared_weak_owners_;
 
 public:
     _LIBCPP_INLINE_VISIBILITY
     explicit __shared_weak_count(long __refs = 0) _NOEXCEPT
         : __shared_count(__refs),
           __shared_weak_owners_(__refs) {}
 protected:
     virtual ~__shared_weak_count();
 
 public:
-    void __add_shared() _NOEXCEPT;
-    void __add_weak() _NOEXCEPT;
-    void __release_shared() _NOEXCEPT;
+#ifdef _LIBCPP_BUILDING_MEMORY
+    void _LIBCPP_FUNC_VIS __add_shared() _NOEXCEPT;
+    void _LIBCPP_FUNC_VIS __add_weak() _NOEXCEPT;
+    void _LIBCPP_FUNC_VIS __release_shared() _NOEXCEPT;
+#else
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_shared() _NOEXCEPT {
+      __shared_count::__add_shared();
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    void __add_weak() _NOEXCEPT {
+      __libcpp_atomic_refcount_increment(__shared_weak_owners_);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    void __release_shared() _NOEXCEPT {
+      if (__shared_count::__release_shared())
+        __release_weak();
+    }
+#endif
     void __release_weak() _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     long use_count() const _NOEXCEPT {return __shared_count::use_count();}
     __shared_weak_count* lock() _NOEXCEPT;
 
     // Define the function out only if we build static libc++ without RTTI.
     // Otherwise we may break clients who need to compile their projects with
     // -fno-rtti and yet link against a libc++.dylib compiled

libcxx/src/memory.cpp

 #ifndef _LIBCPP_HAS_NO_THREADS
 #include "mutex"
 #include "thread"
 #endif
 #include "include/atomic_support.h"
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-namespace
-{
-
-// NOTE: Relaxed and acq/rel atomics (for increment and decrement respectively)
-// should be sufficient for thread safety.
-// See https://llvm.org/bugs/show_bug.cgi?id=22803
-template <class T>
-inline T
-increment(T& t) _NOEXCEPT
-{
-    return __libcpp_atomic_add(&t, 1, _AO_Relaxed);
-}
-
-template <class T>
-inline T
-decrement(T& t) _NOEXCEPT
-{
-    return __libcpp_atomic_add(&t, -1, _AO_Acq_Rel);
-}
-
-}  // namespace
-
 const allocator_arg_t allocator_arg = allocator_arg_t();
 
 bad_weak_ptr::~bad_weak_ptr() _NOEXCEPT {}
 
 const char*
 bad_weak_ptr::what() const _NOEXCEPT
 {
     return "bad_weak_ptr";
 }
 
 __shared_count::~__shared_count()
 {
 }
 
+__shared_weak_count::~__shared_weak_count()
+{
+}
+
 void
 __shared_count::__add_shared() _NOEXCEPT
 {
-    increment(__shared_owners_);
+    __libcpp_atomic_refcount_increment(__shared_owners_);
 }
 
 bool
 __shared_count::__release_shared() _NOEXCEPT
 {
-    if (decrement(__shared_owners_) == -1)
+    if (__libcpp_atomic_refcount_decrement(__shared_owners_) == -1)
     {
         __on_zero_shared();
         return true;
     }
     return false;
 }
 
-__shared_weak_count::~__shared_weak_count()
-{
-}
-
 void
 __shared_weak_count::__add_shared() _NOEXCEPT
 {
     __shared_count::__add_shared();
 }
 
 void
 __shared_weak_count::__add_weak() _NOEXCEPT
 {
-    increment(__shared_weak_owners_);
+    __libcpp_atomic_refcount_increment(__shared_weak_owners_);
 }
 
 void
 __shared_weak_count::__release_shared() _NOEXCEPT
 {
     if (__shared_count::__release_shared())
         __release_weak();
 }
__shared_weak_count::__release_weak() _NOEXCEPT
     // weak_ptr::lock() could read / modify the shared count.
     if (__libcpp_atomic_load(&__shared_weak_owners_, _AO_Acquire) == 0)
     {
         // no need to do this store, because we are about
         // to destroy everything.
         //__libcpp_atomic_store(&__shared_weak_owners_, -1, _AO_Release);
         __on_zero_shared_weak();
     }
-    else if (decrement(__shared_weak_owners_) == -1)
+    else if (__libcpp_atomic_refcount_decrement(__shared_weak_owners_) == -1)
         __on_zero_shared_weak();
 }
 
 __shared_weak_count*
 __shared_weak_count::lock() _NOEXCEPT
 {
     long object_owners = __libcpp_atomic_load(&__shared_owners_);
     while (object_owners != -1)