[Bug libstdc++/99277] New: C++2a synchronisation is inefficient in GCC 11 and can't be fixed later

[Bug libstdc++/99277] New: C++2a synchronisation is inefficient in GCC 11 and can't be fixed later

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

            Bug ID: 99277
           Summary: C++2a synchronisation is inefficient in GCC 11 and
                    can't be fixed later
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: thiago at kde dot org
  Target Milestone: ---

Requesting that this be treated as a blocker for GCC 11.

Detailed post:
https://gcc.gnu.org/pipermail/libstdc++/2021-February/052043.html

Summary:
Since everything in this implementation is inline and, once released, it will
tie our hands until the next ABI break (libstdc++.so.7). And no, inline
namespaces and ABI tags are no different than ABI breaks, they only make the
ABI break more or less silent in the process.

Here's a summary of the findings:

 1) everything is inline
 2) futex code is still behind a lot of code calling into std::_Hash_bytes
 3) other int-sized (incl. enums) atomics don't use futex
 4) std::latch and std::counting_semaphore defaults preclude from using
    futex on Linux
 5) std::barrier implementation also uses a type that futex(2) can't handle

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11 and can't be fixed later

[hjl.tools at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

H.J. Lu <hjl.tools at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0

[Bug libstdc++/99277] [11 Regression] C++2a synchronisation is inefficient in GCC 11 and can't be fixed later

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |ABI
            Summary|C++2a synchronisation is    |[11 Regression] C++2a
                   |inefficient in GCC 11 and   |synchronisation is
                   |can't be fixed later        |inefficient in GCC 11 and
                   |                            |can't be fixed later
           Priority|P3                          |P1
                 CC|                            |rguenth at gcc dot gnu.org

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Marking as regression so it's on the radar.  libstdc++ folks please discuss,
feel free to remove the regression marker in case you think we shouldn't block
GCC 11 for a solution.

[Bug libstdc++/99277] [11 Regression] C++2a synchronisation is inefficient in GCC 11 and can't be fixed later

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Regarding 32-bit vs. 64-bit futex, I guess it depends on what the 64-bit object
holds, if it holds a counter, the usual way how to handle it is to do futex on
the least significant half of the counter.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11 and can't be fixed later

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[11 Regression] C++2a       |C++2a synchronisation is
                   |synchronisation is          |inefficient in GCC 11 and
                   |inefficient in GCC 11 and   |can't be fixed later
                   |can't be fixed later        |

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I already replied on the mailing list. These are inline specifically so we
don't tie ourselves to symbols exported from the DSO before the features are
stable.

They aren't going to be considered stable for GCC 11 so your suggestion is to
disable everything, get no usage experience to help improve it, then at some
point re-enable it when it's no more mature than it is now. I don't see how
that helps anything.

We've done things this way for years. When C++20 support is no longer
experimental is when the ABI will be fixed.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #4 from Thiago Macieira <thiago at kde dot org> ---
(In reply to Jonathan Wakely from comment #3)
> We've done things this way for years. When C++20 support is no longer
> experimental is when the ABI will be fixed.

Based on the discussion, I've removed the "can't be fixed later" part of the
summary.

(In reply to Jakub Jelinek from comment #2)
> Regarding 32-bit vs. 64-bit futex, I guess it depends on what the 64-bit
> object holds, if it holds a counter, the usual way how to handle it is to do
> futex on the least significant half of the counter.

But if it holds a pointer value, then we can't do that trick. We'd need to do a
pointer+counter (generation) trick, which requires a 16-byte compare-exchange
to update, with the futex pointing to the lower half of the counter portion.
I'm just saying that we may have sufficient argument now to change Linus' mind
on having a 64-bit futex support. 

Whether that applies to 32-bit architectures or not, I don't know and is not in
my interest area to research.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[ville.voutilainen at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Ville Voutilainen <ville.voutilainen at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ville.voutilainen at gmail dot com

--- Comment #5 from Ville Voutilainen <ville.voutilainen at gmail dot com> ---
Look people, this just *CAN'T* be a blocker for GCC11. That's a tail wagging a
dog; yeah sure there may be an ABI break in a C++20 concurrency facility, but
to have that block the GCC 11 release is just.. ..unfathomable. Just my 0.02 on
the blocker-ness of this.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #6 from Thiago Macieira <thiago at kde dot org> ---
We don't have to delay the release. Either of these two patches give us one
more year to get it right:

--- libstdc++-v3/include/bits/atomic_wait.h
+++ libstdc++-v3/include/bits/atomic_wait.h
@@ -32,9 +32,9 @@

 #pragma GCC system_header

 #include <bits/c++config.h>
-#if defined _GLIBCXX_HAS_GTHREADS || defined _GLIBCXX_HAVE_LINUX_FUTEX
+#if defined _GLIBCXX_ENABLE_EXPERIMENTAL_ATOMIC_WAIT && (defined
_GLIBCXX_HAS_GTHREADS || defined _GLIBCXX_HAVE_LINUX_FUTEX)
 #include <bits/functional_hash.h>
 #include <bits/gthr.h>
 #include <ext/numeric_traits.h>

Or

--- libstdc++-v3/include/bits/atomic_base.h
+++ libstdc++-v3/include/bits/atomic_base.h
@@ -36,9 +36,9 @@
 #include <stdint.h>
 #include <bits/atomic_lockfree_defines.h>
 #include <bits/move.h>

-#if __cplusplus > 201703L
+#if __cplusplus > 201703L && defined _GLIBCXX_ENABLE_EXPERIMENTAL_ATOMIC_WAIT
 #include <bits/atomic_wait.h>
 #endif

 #ifndef _GLIBCXX_ALWAYS_INLINE

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.0                        |11.2

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.1 has been released, retargeting bugs to GCC 11.2.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #8 from Thiago Macieira <thiago at kde dot org> ---
This one is probably 12.0.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.2                        |12.0

--- Comment #9 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Agreed

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.0                        |12.2

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 12.1 is being released, retargeting bugs to GCC 12.2.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.3                        |12.4

--- Comment #12 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 12.3 is being released, retargeting bugs to GCC 12.4.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Thiago Macieira <thiago at kde dot org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|UNCONFIRMED                 |RESOLVED

--- Comment #13 from Thiago Macieira <thiago at kde dot org> ---
I believe this was fixed before release. Just the issue not closed.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|12.4                        |12.0

--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
For the record ...

(In reply to Thiago Macieira from comment #0)
> Here's a summary of the findings:
> 
>  1) everything is inline

No change here yet, it's intentional that nothing has been added to the library
for now.

>  2) futex code is still behind a lot of code calling into std::_Hash_bytes

That changed with r12-10-gb52aef3a8cbcc8

>  3) other int-sized (incl. enums) atomics don't use futex

So did that.

>  4) std::latch and std::counting_semaphore defaults preclude from using
>     futex on Linux

And that.

>  5) std::barrier implementation also uses a type that futex(2) can't handle

barrier still uses a 1-byte enum for the atomic waits.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #15 from Thiago Macieira <thiago at kde dot org> ---
> >  5) std::barrier implementation also uses a type that futex(2) can't handle

> barrier still uses a 1-byte enum for the atomic waits.

That can only now be fixed for libstdc++.so.7, then.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[rodgertq at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #16 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
(In reply to Thiago Macieira from comment #15)
> > >  5) std::barrier implementation also uses a type that futex(2) can't handle
> 
> > barrier still uses a 1-byte enum for the atomic waits.
> 
> That can only now be fixed for libstdc++.so.7, then.

The original implementation came from Olvier Giroux and is part of libc++. The
libc++ implementation also does not use a type that futex or ulock_wait/wake
(uint64_t) can handle. I have discussed this in the past with Olivier, the
choice of char was deliberate on his part. The implementation has been tested
on a number of platforms (including time on ORNL's Summit). The following
comment, preserved from libc++ should be considered carefully before any change
here -

" 2. A great deal of attention has been paid to avoid cache line thrashing
    by flattening the tree structure into cache-line sized arrays, that
    are indexed in an efficient way."

It is my opinion that the bar for making a change here is high. I would need to
see benchmark numbers that illustrate the performance differences under various
contention scenarios vs impact on caches by being able to fit the entire tree
in a single cache line using char, vs four or eight cache lines using the type
favored by futex or ulock_wait/wake.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #17 from Thiago Macieira <thiago at kde dot org> ---
(In reply to Thomas Rodgers from comment #16)
> The original implementation came from Olvier Giroux and is part of libc++.
> The libc++ implementation also does not use a type that futex or
> ulock_wait/wake (uint64_t) can handle. I have discussed this in the past
> with Olivier, the choice of char was deliberate on his part. The
> implementation has been tested on a number of platforms (including time on
> ORNL's Summit). 

I remember our discussion on this. But libc++ isn't trying to be optimal and it
never supports direct futex. The fact that they chose this path does not mean
libstdc++ must too.


> The following comment, preserved from libc++ should be
> considered carefully before any change here -
> 
> " 2. A great deal of attention has been paid to avoid cache line thrashing
>     by flattening the tree structure into cache-line sized arrays, that
>     are indexed in an efficient way."
> 
> It is my opinion that the bar for making a change here is high. I would need
> to see benchmark numbers that illustrate the performance differences under
> various contention scenarios vs impact on caches by being able to fit the
> entire tree in a single cache line using char, vs four or eight cache lines
> using the type favored by futex or ulock_wait/wake.

Indeed. My other $DAYJOB involves a lot of cacheline thrashing up to and
including current 480-core machines, so I appreciate the thought there.

In any case, we can't change the design even if we turn up new data showing
that there's benefit or a bottleneck somewhere.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #18 from Jonathan Wakely <redi at gcc dot gnu.org> ---
We have not committed to a stable ABI for C++20 yet.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #19 from Thiago Macieira <thiago at kde dot org> ---
(In reply to Jonathan Wakely from comment #18)
> We have not committed to a stable ABI for C++20 yet.

That was my argument when creating this bug report two years ago: if it's
available in the standard headers to be used without explicit, opt-in actions
by the users, it's committed. The change may not break the ABI inside of
libstdc++.so.6, but so long as it breaks ABI of some library, it's an ABI
break. I understand that's not what your current policy says, but it doesn't
change reality. So please don't do it.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #20 from Jonathan Wakely <redi at gcc dot gnu.org> ---
We've already done it with other C++20 types, and we did it with C++17 types
before that.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[thiago at kde dot org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #21 from Thiago Macieira <thiago at kde dot org> ---
I understand that. I don't think it's a reason to repeat the policy, though.

Anyway, I don't have any new arguments than when we discussed this two years
ago, so I won't pursue this matter further.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #22 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Thiago Macieira from comment #19)
> (In reply to Jonathan Wakely from comment #18)
> > We have not committed to a stable ABI for C++20 yet.
> 
> That was my argument when creating this bug report two years ago: if it's
> available in the standard headers to be used without explicit, opt-in
> actions by the users, it's committed.

N.B. explicit opt-in is required: -std=c++20 or similar.

The default mode does not provide std::barrier etc.

[Bug libstdc++/99277] C++2a synchronisation is inefficient in GCC 11

[rodgertq at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99277

--- Comment #23 from Thomas Rodgers <rodgertq at gcc dot gnu.org> ---
(In reply to Thiago Macieira from comment #21)
> I understand that. I don't think it's a reason to repeat the policy, though.
> 
> Anyway, I don't have any new arguments than when we discussed this two years
> ago, so I won't pursue this matter further.

(Un)fortunately, the entire implementation detail in the headers will change,
most likely with GCC14 (ideally moving most of the implementation into the
.so). As Jonathan points out, this hardly the only experimental feature area
within libstdc++ that has undergone such changes.