ARMv8 getting atomic operations

By: Linus Torvalds (torvalds.delete@this.linux-foundation.org), December 4, 2014 12:05 pm
Room: Moderated Discussions
anon (anon.delete@this.anon.com) on December 3, 2014 5:08 pm wrote:
>
> We've talked about this before here, but LL/SC can guarantee progress (when it is limited
> like POWER does), and the LL of course always carries a load-for-store signal.

Both of these are "true", but not what I'm complaining about.

First off, "guaranteed forward progress" in LL/SC tends to be a global thing: you're guaranteeing not to livelock. That is not interesting from a performance standpoint, it's just interesting from a "minimal requirements" standpoint.

The thing is, the LL/SC model (and the load/cmpxchg model) does not guarantee that each thread makes forward progress, much less that each cache miss makes any progress.

Seriously, it's a real issue. The cmpxchg fails. Not just occasionally. Under real load (admittedly very high contention), it fails quite often. And each failure is basically an extra and unnecessary ping-pong of a cacheline, where some other CPU ended up winning a race, and causing the cache access on the losing CPU to be pure and utter useless work.

On x86 (which, again, is the only architecture you can actually compare these approaches), the numbers seem to be that if you update counters, the atomic RMW "add" model gets about twice the progress over a "load+add+cmpxchg" model. Twice.

And yes, that obviously ends up depending on cache coherency details etc, and how "sticky" a cacheline is to a CPU that got it. But that's actually a real potential issue too: being too sticky tends to improve throughput, but can cause some seriously excessive unfairness issues, where a node or a core that got exclusive access to the cacheline and keeps writing to it can get very unfair advantages wrt other cores.

And yes, we've very much seen that too especially in NUMA environments.

So LL/SC either fails a lot and causes ping-pong traffic while only making very slow progress (some progress, yes), or can try to avoid the failure case by making the cachelines very sticky and then become very unfair and amenable to imbalance.

A RMW model doesn't tend to have the same kind of issues. Once you got the cacheline, you will update it. There is no failure case and unnecessary cache transaction.

And yes, you can in theory make LL/SC or load/cmpxchg work like a RMW by noticing the pattern and basically turning the bad LL/SC model into an RMW model by generating macro-instructions. And I actually think it's not a bad idea. But even if you do that, you basically have to first admit the superiority of the RMW model.

As to the LL always implying write intent, I agree that it tends to make more sense. I'm not actually convinced everybody always does that. In the x86 world, where the pseudo-equivalent sequence is load/cmpxchg, we definitely have hit that issue.

Linus
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
ARMv8 getting atomic operationsdmcq2014/12/02 05:32 PM
  ARMv8 getting atomic operationsMaynard Handley2014/12/02 07:33 PM
    ARMv8 getting atomic operationsDoug S2014/12/02 10:30 PM
      ARMv8 getting atomic operationsdmcq2014/12/03 03:16 AM
      ARMv8 getting atomic operationsMaynard Handley2014/12/03 09:20 AM
      ARMv8 getting atomic operationsBrett2014/12/03 04:46 PM
    ARMv8 getting atomic operationsAndreas2014/12/03 06:51 AM
      ARMv8 getting atomic operationsLinus Torvalds2014/12/03 11:15 AM
        ARMv8 getting atomic operationsanon2014/12/03 05:08 PM
          Guaranteed transactionsPaul A. Clayton2014/12/03 08:04 PM
            Guaranteed transactionsanon2014/12/03 08:38 PM
              Avoiding ping pongPaul A. Clayton2014/12/04 09:11 AM
                Avoiding ping ponganon2014/12/04 10:15 AM
                  OoO window is limitedPaul A. Clayton2014/12/04 01:06 PM
                Avoiding ping pongAaron Spink2014/12/04 12:01 PM
                  Avoiding ping pongKonrad Schwarz2014/12/04 01:10 PM
                    Avoiding ping pongAaron Spink2014/12/04 02:31 PM
                    Avoiding ping pongGabriele Svelto2014/12/04 02:49 PM
                      Avoiding ping pongKonrad Schwarz2014/12/04 11:08 PM
                        Avoiding ping pongGabriele Svelto2014/12/05 12:04 AM
                          Avoiding ping pongEric Bron nli2014/12/05 02:28 AM
                            Avoiding ping pongKonrad Schwarz2014/12/05 03:37 AM
                              Avoiding ping pongEric Bron nli2014/12/05 04:23 AM
                                Avoiding ping pongKlimax2014/12/05 05:47 AM
                                  Avoiding ping pongEric Bron2014/12/05 06:24 AM
                              Avoiding ping pongGabriele Svelto2014/12/05 10:38 AM
                                Avoiding ping pongKonrad Schwarz2014/12/07 02:28 PM
                                  Avoiding ping pongGabriele Svelto2014/12/08 07:10 PM
                                    Avoiding ping pongKonrad Schwarz2014/12/09 05:12 AM
                                      Avoiding ping pongGabriele Svelto2014/12/09 07:31 AM
                                        Avoiding ping ponganon2014/12/09 11:24 PM
                            Avoiding ping pongGabriele Svelto2014/12/05 10:17 AM
                              Avoiding ping pongEric Bron2014/12/05 10:32 AM
                                Avoiding ping pongGabriele Svelto2014/12/05 12:45 PM
                                  Avoiding ping pongEric Bron2014/12/06 02:20 AM
                                    Avoiding ping pongnksingh2014/12/06 03:42 AM
                                      Avoiding ping pongEric Bron2014/12/06 04:04 AM
                                        Avoiding ping pongGiGNiC2014/12/06 06:27 AM
                                          Avoiding ping pongEric Bron nli2014/12/06 06:44 AM
                                          Avoiding ping pongEric Bron2014/12/06 07:07 AM
                                            Avoiding ping pongnksingh2014/12/07 04:06 PM
                                              Avoiding ping pongEric Bron2014/12/08 04:17 AM
                                                Avoiding ping pongGiGNiC2014/12/08 11:53 AM
                                                Avoiding ping pongnksingh2014/12/08 05:53 PM
                                                  Avoiding ping pongEric Bron2014/12/09 01:33 AM
                                    Avoiding ping pongdmsc2014/12/06 04:12 AM
                                      Avoiding ping pongEric Bron2014/12/06 04:25 AM
                                        Avoiding ping pongKlimax2014/12/06 05:49 AM
                                          Avoiding ping pongrwessel2014/12/07 02:34 AM
                                        Avoiding ping pongdmsc2014/12/06 07:39 AM
                                        Avoiding ping pongKonrad Schwarz2014/12/07 02:37 PM
                                          Avoiding ping pongMichael S2014/12/07 04:37 PM
                                            Avoiding ping pongKonrad Schwarz2014/12/08 04:35 AM
                          Avoiding ping pongKonrad Schwarz2014/12/05 03:30 AM
                        Avoiding ping pongLinus Torvalds2014/12/05 12:58 PM
                          Avoiding ping pongEric Bron2014/12/06 02:42 AM
                            Avoiding ping pongnksingh2014/12/06 03:51 AM
                              Avoiding ping pongEric Bron2014/12/06 04:08 AM
                            Avoiding ping pongLinus Torvalds2014/12/06 01:25 PM
                              Avoiding ping pongnksingh2014/12/07 03:26 PM
                                Avoiding ping pongEric Bron2014/12/08 04:35 AM
                                  Avoiding ping pongBrett2014/12/08 10:00 AM
                                    Avoiding ping pongEric Bron2014/12/08 10:48 AM
                                    Avoiding ping pongrwessel2014/12/08 12:52 PM
                                      Avoiding ping pongBrett2014/12/08 01:58 PM
                                      Avoiding ping pongDoug S2014/12/08 02:04 PM
                              Avoiding ping pongJouni Osmala2014/12/08 02:45 AM
                                Avoiding ping ponganon2014/12/08 05:44 AM
                                  Avoiding ping pongJouni Osmala2014/12/08 01:10 PM
                                    Avoiding ping pongLinus Torvalds2014/12/08 01:34 PM
                                      Avoiding ping pongJouni Osmala2014/12/08 03:47 PM
                                        Avoiding ping pongLinus Torvalds2014/12/08 08:08 PM
                                          Avoiding ping pongGabriele Svelto2014/12/09 07:48 AM
                                            Avoiding ping pongMaynard Handley2014/12/09 11:41 AM
                                              Avoiding ping pongPatrick Chase2014/12/09 01:06 PM
                                              Avoiding ping pongGabriele Svelto2014/12/09 01:52 PM
                                                Avoiding ping pongPatrick Chase2014/12/09 02:08 PM
                                            Why read RWT or Reddit when you can get journalists to do it for you?Rob Thorpe2015/01/02 08:20 AM
                                              Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/02 11:21 AM
                                                Why read RWT or Reddit when you can get journalists to do it for you?EduardoS2015/01/02 11:37 AM
                                                  Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/03 12:00 PM
                                                Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron nli2015/01/02 02:28 PM
                                                  Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/03 12:02 PM
                                                    Why read RWT or Reddit when you can get journalists to do it for you?Michael S2015/01/03 12:36 PM
                                                      Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/03 01:11 PM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Michael S2015/01/03 01:30 PM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/03 02:57 PM
                                                            KNL cacheDavid Kanter2015/01/03 07:36 PM
                                                              KNL cacheEric Bron2015/01/04 03:34 AM
                                                                KNL cacheMichael S2015/01/04 04:11 AM
                                                                  KNL cacheEric Bron2015/01/04 04:57 AM
                                                                    KNL cacheMichael S2015/01/04 05:21 AM
                                                                      KNL cacheEric Bron2015/01/04 05:58 AM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/07 05:47 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Michael S2015/01/07 08:27 AM
                                                              Manycores vs multicoresjuanrga2015/01/10 04:10 PM
                                                                Manycores vs multicoresAaron Spink2015/01/10 05:32 PM
                                                                  Manycores vs multicoresjuanrga2015/01/10 06:32 PM
                                                                    Manycores vs multicoresExophase2015/01/10 06:49 PM
                                                                      Manycores vs multicoresjuanrga2015/01/10 08:21 PM
                                                                        Manycores vs multicoresExophase2015/01/10 08:51 PM
                                                                        Manycores vs multicoresAaron Spink2015/01/10 09:03 PM
                                                                    Manycores vs multicoresAaron Spink2015/01/10 07:21 PM
                                                                      Manycores vs multicoresjuanrga2015/01/10 08:25 PM
                                                                        Manycores vs multicoresAaron Spink2015/01/10 09:11 PM
                                                                          Manycores vs multicoresJouni Osmala2015/01/11 04:50 AM
                                                                            Manycores vs multicoresjuanrga2015/01/11 08:58 AM
                                                                            Manycores vs multicorescoppice2015/01/12 10:01 PM
                                                                              Manycores vs multicoresJouni Osmala2015/01/13 04:38 AM
                                                                        Manycores vs multicoresanon2015/01/11 03:19 AM
                                                                      Manycores vs multicoresMichael S2015/01/11 05:44 AM
                                                                        Manycores vs multicoresAaron Spink2015/01/11 05:55 PM
                                                                          Manycores vs multicoresMichael S2015/01/12 04:41 AM
                                                                            Manycores vs multicoresEric Bron2015/01/12 06:29 AM
                                                                              Manycores vs multicoresEric Bron2015/01/12 06:30 AM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/03 02:54 PM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/07 05:48 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/07 07:41 AM
                                                              Manycores vs multicoresjuanrga2015/01/10 04:14 PM
                                                    Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/03 02:42 PM
                                                      Why read RWT or Reddit when you can get journalists to do it for you?juanrga2015/01/07 06:03 AM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/07 07:45 AM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Linus Torvalds2015/01/08 03:09 PM
                                                          Pink unicorns for salejuanrga2015/01/10 05:09 PM
                                                        Intentionally picking a competitors slow part is cheating ...Mark Roulo2015/01/08 06:37 PM
                                                          Intentionally picking a competitors slow part is cheating ...coppice2015/01/08 11:38 PM
                                                            Intentionally picking a competitors slow part is cheating ...Mark Roulo2015/01/09 09:13 AM
                                                              Intentionally picking a competitors slow part is cheating ...Anon2015/01/10 02:00 AM
                                                              Intentionally picking a competitors slow part is cheating ...David Hess2015/01/11 01:03 PM
                                                            Intentionally picking a competitors slow part is cheating ...someone2015/01/09 10:31 AM
                                                              Intentionally picking a competitors slow part is cheating ...coppice2015/01/12 09:45 PM
                                                                Intentionally picking a competitors slow part is cheating ...coppice2015/01/12 09:47 PM
                                                                  Intentionally picking a competitors slow part is cheating ...Michael S2015/01/13 07:53 AM
                                                                    Intentionally picking a competitors slow part is cheating ...coppice2015/01/13 09:44 AM
                                                                      Intentionally picking a competitors slow part is cheating ...Michael S2015/01/13 10:01 AM
                                                                        Intentionally picking a competitors slow part is cheating ...coppice2015/01/13 08:35 PM
                                                                      Core sizesjuanrga2015/01/13 12:28 PM
                                                          NVIDIA'S FIRST CPU IS A WINNER (Linley Gwennap)juanrga2015/01/10 04:34 PM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?Patrick Chase2015/01/08 07:02 PM
                                                        Why read RWT or Reddit when you can get journalists to do it for you?coppice2015/01/08 10:18 PM
                                                          Why read RWT or Reddit when you can get journalists to do it for you?Patrick Chase2015/01/09 11:54 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Mark Roulo2015/01/09 12:59 PM
                                                              Why read RWT or Reddit when you can get journalists to do it for you?Patrick Chase2015/01/09 03:20 PM
                                                                Why read RWT or Reddit when you can get journalists to do it for you?Eric Bron2015/01/09 03:30 PM
                                                            Alternatives to OOOE (again)juanrga2015/01/10 04:50 PM
                                                              Alternatives to OOOE (again)David Kanter2015/01/11 12:10 AM
                                                                Alternatives to OOOE (again)juanrga2015/01/11 08:30 AM
                                                            Why read RWT or Reddit when you can get journalists to do it for you?Gabriele Svelto2015/01/11 12:53 AM
                                              Why read RWT or Reddit when you can get journalists to do it for you?Fake Linus Torvalds2015/01/03 12:14 PM
                                                Why read RWT or Reddit when you can get journalists to do it for you?Rob Thorpe2015/01/03 08:25 PM
                                          Avoiding ping pongMaynard Handley2014/12/09 11:33 AM
                                            Avoiding ping pongPatrick Chase2014/12/09 01:54 PM
                                              Avoiding ping pongMaynard Handley2014/12/09 06:56 PM
                                      Avoiding ping pongSalvatore De Dominicis2014/12/09 08:51 AM
                                        Avoiding ping pongPatrick Chase2014/12/09 02:00 PM
                                      Avoiding ping pongook2014/12/11 03:31 AM
                                      Avoiding ping pongArt Scott2014/12/19 10:19 PM
                                        Avoiding ping pongEric Bron nli2014/12/20 04:05 AM
                                      What about specialization?Troll?2015/01/02 07:55 AM
                                        What about specialization?Ungo2015/01/04 03:27 PM
                                      Avoiding ping pongfewwef2015/01/05 08:16 PM
                                      Avoiding ping pongV.Krishn2015/01/08 06:11 AM
                                    Avoiding ping pongGabriele Svelto2014/12/08 07:32 PM
                                    Avoiding ping ponganon2014/12/08 11:37 PM
                            Avoiding ping pongKonrad Schwarz2014/12/10 06:23 AM
                              Avoiding ping pongLinus Torvalds2014/12/10 11:56 AM
                          Object reference lockingDavid W2014/12/08 11:36 PM
                            Object reference lockingPatrick Chase2014/12/09 04:52 PM
                              Object reference lockingDavid W2014/12/11 05:18 AM
                    ISA != interface for "most programmers"Paul A. Clayton2014/12/04 03:34 PM
                      ISA != interface for "most programmers"rwessel2014/12/04 07:50 PM
                  Interesting! (exporting hot lines/cache-aware ISA); "Please sir, I want some more" (NT)Paul A. Clayton2014/12/04 02:26 PM
                  Avoiding ping pongMichael S2014/12/06 03:48 PM
          ARMv8 getting atomic operationsLinus Torvalds2014/12/04 12:05 PM
            LL/SC idiom recognition is not admitting RMW superiorityPaul A. Clayton2014/12/04 02:34 PM
            ARMv8 getting atomic operationsanon2014/12/04 10:17 PM
    ARMv8 getting atomic operationsPatrick Chase2014/12/03 12:09 PM
  limited ordernksingh2014/12/04 10:17 PM
    I didn't understand this either. (NT)Konrad Schwarz2014/12/04 10:32 PM
    limited orderdmcq2014/12/05 02:13 AM
    limited orderbakaneko2014/12/05 09:11 AM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell green?