No conflict between theory and practice

By: NoSpammer (no.delete@this.spam.com), April 10, 2021 12:02 am
Room: Moderated Discussions
Aspect of Anonimity (aoa.delete@this.hjiffdhkoouggkl.com) on April 6, 2021 2:16 pm wrote:
> NoSpammer (no.delete@this.spam.com) on April 5, 2021 9:38 pm wrote:
> > Have you ever actually studied the relevant theory?
> >
>
> No.
>
> > So how can hardware assume, a priori, that software cannot cause a deadly
> > embrace under any circumstances?
>
> The crux is that HTM that aborts CANNOT do this! Fallback to normal locking always
> happens on abort, which undisputably can lock up. Even if all you do is retry a
> failed transaction, then congrats, you got a glorified spinlock in userspace!

Well, my point was that you cannot expect to have a workable transaction scheme without aborts or partial rollbacks. However, theoretically, one could devise a scheme that would not always abort to locking path but instead roll back more intelligently and retry.

> > And how would you resolve it?
>
> I suspected that it might be impossible, but:
>
> Use cache coherency to solve your memory coherency problem, and suspend tasks with
> potentially conflicting transactions. Detecting those is the difficult part.

I disagree. Detecting conflicting transactions is the easy part, resolving them in a close to optimal way in all possible circumstances is the difficult part.

> Start with the whole address space of a task and attempt to narrow it down because you
> care about concurrency. Thus you need to restrict the domain of potentially used memory
> for each transaction and provide that information in software at its start.
> If you end up with a taylor-made fit for each transaction,
> then congrats, you have converged to normal locking!

Well, let's think through it with a simplistic top-level view. Suppose you limit the transaction footprint to something reasonable the software and CPU can handle, and let's say you can even prove you have an algorithm that can roll back intelligently to guarantee forward progress and correctness of execution (with respect to ordering etc.). Now, let's say you have 2 threads with interlocking transactions. You need to have a protocol to resolve this, and the two CPU cores will have to exchange some information in order to roll back intelligently. This will take some time. Now suppose you have 3 threads on physically different CPUs that need some protocol to resolve interlocking transactions. Sound like a fine mathematical exercise. I guess it can be done. Now throw in some IRQ/NMI and maybe a couple non-transactional threads trying to read some lines locked by some of the transactions. I'm sure I have forgotten something more, like debugging features or any exceptions. If needed, maybe add just one more layer of nested transactions for more fun.

Can you see the combinatorial explosion of the state space? Can you easily envision a protocol to resolve all of possible situations correctly in a close to optimal way? Can you define a hardware test protocol for the implementation? Can you put timing estimates on resolution of transactions? What would be the waiting time for these to resolve vs. locking? I guess some advanced application of queuing theory could get you that far, with my post-grad math it would certainly take me quite some time to get anywhere near to correct analytical answers to these.

> It's only a subset of what's possible to do with locking primitives and maybe the sweet spot
> for you is some kind of memory segments and maybe you need lots of speculative execution for
> acceptable performance and maybe you want to also track pages besides cachlines to deal with
> overflow, regardless the outlook for superior performance combined with ease of use is grim.

Well in theory much is possible. In theory you can argue that you can even avoid a deadly embrace caused by rookie programmers or random compiled code memory access ordering by intelligently rolling back and retrying transactions. That might even work alright far small transactions that interact rarely. Personally, I'd love that for some of my code. But in practice when not targeted to specifically designed transaction patterns it seems it's not so difficult to get into the territory Linus is rambling about.
< Previous Post in ThreadNext Post in Thread >
TopicPosted ByDate
Armv9 officially announcedJon Masters2021/03/30 11:41 AM
  Armv9 officially announcedGabriele Svelto2021/03/30 01:27 PM
    HTM and TLEFoo_2021/03/30 01:31 PM
      HTM and TLEdmcq2021/03/30 03:03 PM
      Intel RTM and HLE is a successGanon2021/03/30 05:22 PM
        Intel RTM and HLE is a success (is it?)Foo_2021/03/31 01:16 AM
          Intel RTM and HLE was an abject failureanonymou52021/03/31 03:04 AM
          Intel RTM and HLE is a success (is it?)Andrey2021/03/31 05:27 AM
            Intel RTM and HLE is a success (is it?)Foo_2021/03/31 05:58 AM
              Intel RTM and HLE is a success (is it?)Andrey2021/03/31 07:45 AM
                Intel RTM and HLE is a success (is it?)Foo_2021/03/31 09:32 AM
                  Intel RTM and HLE is a success (is it?)Andrey2021/03/31 09:57 AM
                    Intel RTM and HLE is a success (is it?)anonymou52021/03/31 10:39 AM
                      ^ feel free to delete this one -- broken HTML there (NT)anonymou52021/03/31 10:40 AM
                      Intel RTM and HLE is a success (is it?)Andrey2021/03/31 10:47 AM
                    Intel RTM and HLE is a success (is it?)anonymou52021/03/31 10:40 AM
                Intel RTM and HLE is a success (is it?)Ganon2021/03/31 09:58 AM
                  Intel RTM and HLE is a success (is it?)anonymou52021/03/31 10:42 AM
                  Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 11:54 AM
                    Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 12:00 PM
                      Any idea about IBM?Mark Roulo2021/03/31 12:15 PM
                        Any idea about IBM?Linus Torvalds2021/03/31 12:37 PM
                          Any idea about IBM?dmcq2021/03/31 03:04 PM
                            Any idea about IBM?Linus Torvalds2021/03/31 04:44 PM
                              A non straw man view of hardware transactional memoryGanon2021/03/31 07:52 PM
                                A non straw man view of hardware transactional memoryanon22021/03/31 11:03 PM
                                  A non straw man view of hardware transactional memoryCarson2021/04/02 01:11 AM
                                    A non straw man view of hardware transactional memoryanon22021/04/02 05:28 AM
                              IBM zArch TM - guaranteed progressDavid Kanter2021/03/31 08:37 PM
                              Any idea about IBM?Andrey2021/03/31 11:31 PM
                                Any idea about IBM?Linus Torvalds2021/04/01 10:54 AM
                                  Any idea about IBM?Andrey2021/04/02 12:50 PM
                        Any idea about IBM?someone2021/04/01 12:02 AM
                      Intel RTM and HLE is a success (is it?)anon22021/03/31 03:46 PM
                        Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 05:08 PM
                          Leaving it to software is tricky!David Kanter2021/03/31 08:41 PM
                            And a hardware predicttor needs access to fallback timingCarson2021/04/01 11:13 PM
                              Hardware fallback pathAnon2021/04/02 10:51 AM
                              And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 10:41 AM
                                And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 11:11 AM
                                  And a hardware predicttor needs access to fallback timingsr2021/04/03 11:30 AM
                                    And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 12:14 PM
                                      And a hardware predicttor needs access to fallback timingsr2021/04/03 12:39 PM
                                        And a hardware predicttor needs access to fallback timingAnon2021/04/03 02:08 PM
                                          And a hardware predicttor needs access to fallback timingsr2021/04/03 02:33 PM
                                            And a hardware predicttor needs access to fallback timingdmcq2021/04/04 05:35 AM
                                        And a hardware predicttor needs access to fallback timingLinus Torvalds2021/04/03 02:22 PM
                                          Transactional memory isn't exclusive to lockingsr2021/04/04 12:17 AM
                                            Transactional memory isn't exclusive to lockingAspect of Anonimity2021/04/04 03:49 AM
                                            Transactional memory isn't exclusive to lockingAndrey2021/04/04 04:58 AM
                                              Transactional memory isn't exclusive to lockingsr2021/04/04 10:10 AM
                                                Transactional memory isn't exclusive to lockingAndrey2021/04/04 10:33 AM
                                                  Transactional memory isn't exclusive to lockingsr2021/04/05 02:41 AM
                                      And a hardware predicttor needs access to fallback timingGeertB2021/04/04 07:08 PM
                            Leaving it to software is tricky!Andrey2021/04/02 03:00 PM
                          Intel RTM and HLE is a success (is it?)@never_released2021/04/01 08:21 AM
                            Intel RTM and HLE is a success (is it?)@never_released2021/04/01 08:30 AM
                            Intel RTM and HLE is a success (is it?)Linus Torvalds2021/04/01 10:00 AM
                              Intel RTM and HLE is a success (is it?)dmcq2021/04/01 10:35 AM
                                Intel RTM and HLE is a success (is it?)Linus Torvalds2021/04/01 10:59 AM
                                  Is HTM actually in ARMv9?dncq2021/04/01 11:26 AM
                                    Is HTM actually in ARMv9?Linus Torvalds2021/04/01 12:13 PM
                              Intel RTM and HLE is a success (is it?)Jörn Engel2021/04/01 09:15 PM
                          Intel RTM and HLE is a success (is it?)---2021/04/02 10:00 AM
                      Intel RTM and HLE is a success (is it?)Jon Masters2021/04/01 10:56 AM
                        RockMichael S2021/04/01 12:29 PM
            Intel RTM and HLE is a success (is it?)Linus Torvalds2021/03/31 11:50 AM
              Intel RTM and HLE is a success (is it?)anon22021/03/31 03:57 PM
                Intel RTM and HLE is a success (is it?)anon32021/03/31 04:09 PM
          Intel RTM and HLE is a success (is it?)someone2021/03/31 11:56 PM
            Intel RTM and HLE is a success (is it?)someone2021/04/01 12:21 AM
              Intel RTM and HLE is a success (is it?)none2021/04/01 04:31 AM
                Intel RTM and HLE is a success (is it?)anonymou52021/04/01 09:24 AM
                  Intel RTM and HLE is a success (is it?)anony2021/04/01 10:26 AM
                  Intel RTM and HLE is a success (is it?)none2021/04/01 11:20 AM
                Intel RTM and HLE is a success (is it?)Brendan2021/04/01 05:23 PM
                  Intel RTM and HLE is a success (is it?)Adrian2021/04/02 01:03 AM
      Transactional memory similarity to garbage collectionPaul A. Clayton2021/04/05 01:53 PM
        Maybe notMark Roulo2021/04/05 03:07 PM
        Transactional memory similarity to garbage collectionAnon2021/04/05 03:14 PM
        No conflict between theory and practiceAspect of Anonimity2021/04/05 07:57 PM
          No conflict between theory and practiceNoSpammer2021/04/05 09:38 PM
            No conflict between theory and practicedmcq2021/04/06 07:05 AM
              No conflict between theory and practicesr2021/04/06 09:22 AM
                No conflict between theory and practiceBen LaHaise2021/04/06 03:43 PM
                  No conflict between theory and practicesr2021/04/07 09:42 AM
                    No conflict between theory and practiceAnon2021/04/07 10:06 AM
                    No conflict between theory and practiceLinus Torvalds2021/04/07 10:35 AM
                      No conflict between theory and practicesr2021/04/07 12:34 PM
                        If HTM were well implemented, nobody would complain (NT)Anon2021/04/07 12:54 PM
                          If HTM were well implemented, nobody would complaindmcq2021/04/07 03:36 PM
                            If HTM were well implemented, nobody would complainAnon2021/04/07 04:04 PM
                          If HTM were well implemented, nobody would complain---2021/04/08 09:37 AM
                        No conflict between theory and practiceLinus Torvalds2021/04/07 01:20 PM
                          No conflict between theory and practiceAndrey2021/04/07 02:32 PM
                            No conflict between theory and practicedmcq2021/04/07 03:32 PM
                              No conflict between theory and practiceanonymou52021/04/07 04:26 PM
                              No conflict between theory and practiceAndrey2021/04/07 05:54 PM
                                No conflict between theory and practiceLinus Torvalds2021/04/08 08:41 AM
                                  No conflict between theory and practiceAndrey2021/04/08 09:12 AM
                                  No conflict between theory and practiceRobert Williams2021/04/08 09:15 AM
                                    No conflict between theory and practiceLinus Torvalds2021/04/08 09:56 AM
                                      No conflict between theory and practiceRobert Williams2021/04/08 07:50 PM
                                        No conflict between theory and practiceLinus Torvalds2021/04/09 09:25 AM
                                          TSX for all?Robert Williams2021/04/09 12:46 PM
                                            It helps adoption when developers can run the code an their machines.Mark Roulo2021/04/09 12:54 PM
                                              It helps adoption when developers can run the code an their machines.me2021/04/09 02:21 PM
                                                It helps adoption when developers can run the code an their machines.Andrey2021/04/10 07:08 AM
                                                  It helps adoption when developers can run the code an their machines.me2021/04/10 12:43 PM
                                                    It helps adoption when developers can run the code an their machines.Robert Williams2021/04/10 07:05 PM
                                                      It helps adoption when developers can run the code an their machines.Andrey2021/04/11 01:42 AM
                                                        It helps adoption when developers can run the code an their machines.Michael S2021/04/11 04:23 AM
                                              It helps adoption when developers can run the code an their machines.Robert Williams2021/04/10 08:24 AM
                                                It helps adoption when developers can run the code an their machines.Andrey2021/04/10 10:36 AM
                                                  It helps adoption when developers can run the code an their machines.Michael S2021/04/10 10:58 AM
                                                    It helps adoption when developers can run the code an their machines.Robert Williams2021/04/10 11:42 AM
                                                    It helps adoption when developers can run the code an their machines.Brendan2021/04/10 11:27 PM
                                                      It helps adoption when developers can run the code an their machines.Michael S2021/04/11 03:34 AM
                                                        It helps adoption when developers can run the code an their machines.Brendan2021/04/11 04:18 PM
                                            TSX for all?wumpus2021/04/09 01:10 PM
                                            TSX for all?Linus Torvalds2021/04/09 03:03 PM
                                              [CLICK BAIT?] Torvalds to recommend arm64!anonymous22021/04/09 03:17 PM
                                              TSX for all?Linus Torvalds2021/04/09 03:22 PM
                                                amen! (NT)anonymou52021/04/09 05:42 PM
                                            TSX for all?Emil Briggs2021/04/10 05:52 AM
                                              TSX for all?Michael S2021/04/10 11:13 AM
                                                TSX for all?Brendan2021/04/10 11:05 PM
                                          No conflict between theory and practiceanonymouse2021/04/09 03:02 PM
                            No conflict between theory and practiceLinus Torvalds2021/04/07 05:12 PM
                              No conflict between theory and practiceAndrey2021/04/07 05:33 PM
                                No conflict between theory and practiceanon22021/04/07 08:12 PM
                                  No conflict between theory and practiceAndrey2021/04/08 12:29 AM
                                    No conflict between theory and practiceAnon2021/04/08 12:50 AM
                                    No conflict between theory and practiceanon22021/04/08 12:52 AM
                                      No conflict between theory and practiceAndrey2021/04/08 02:41 AM
                                        No conflict between theory and practiceAdrian2021/04/08 03:09 AM
                                          No conflict between theory and practiceAndrey2021/04/08 03:50 AM
                                            No conflict between theory and practiceAdrian2021/04/08 05:07 AM
                                            No conflict between theory and practiceanon22021/04/08 05:18 AM
                                              No conflict between theory and practiceAndrey2021/04/08 08:18 AM
                                                No conflict between theory and practiceanon22021/04/08 09:11 AM
                                                  No conflict between theory and practiceAndrey2021/04/08 09:48 AM
                                                    No conflict between theory and practiceanon22021/04/08 04:10 PM
                                            No conflict between theory and practice---2021/04/08 08:30 PM
                                              No conflict between theory and practicedmcq2021/04/09 02:25 AM
                                                No conflict between theory and practiceLinus Torvalds2021/04/09 09:44 AM
                                        No conflict between theory and practiceanon22021/04/08 04:09 AM
                                          No conflict between theory and practicesr2021/04/10 01:22 AM
                                            No conflict between theory and practiceAnon2021/04/10 04:00 AM
                                              No conflict between theory and practiceEtienne Lorrain2021/04/12 12:56 AM
                                                No conflict between theory and practiceAnon2021/04/12 01:54 AM
                                                  No conflict between theory and practicedmcq2021/04/12 01:44 PM
                              No conflict between theory and practiceGabriele Svelto2021/04/08 01:03 AM
                                No conflict between theory and practicedmcq2021/04/12 01:53 PM
                                  No conflict between theory and practicedmcq2021/04/14 04:50 AM
                      transactional memory = memory lock/unlocksr2021/04/10 12:56 AM
                        transactional memory = memory lock/unlockAnon2021/04/10 04:05 AM
                    No conflict between theory and practiceanon22021/04/07 05:19 PM
                No conflict between theory and practicedmcq2021/04/07 01:16 PM
            No conflict between theory and practiceAnon2021/04/06 10:46 AM
            No conflict between theory and practiceAspect of Anonimity2021/04/06 02:16 PM
              No conflict between theory and practiceNoSpammer2021/04/10 12:02 AM
                No conflict between theory and practicesr2021/04/10 01:47 AM
                No conflict between theory and practiceAspect of Anonimity2021/04/10 11:30 PM
                  No conflict between theory and practiceAndrey2021/04/11 05:05 AM
                    HmAspect of Anonimity2021/04/12 07:29 PM
                      Special internal SRAM to store Mutex?Etienne Lorrain2021/04/13 01:01 AM
                        Special internal SRAM to store Mutex?Anon2021/04/13 01:26 AM
                        Special internal SRAM to store Mutex?Linus Torvalds2021/04/13 09:53 AM
                        Special internal SRAM to store Mutex?Dan Fay2021/04/13 12:03 PM
                          Special internal SRAM to store Mutex?Ben LaHaise2021/04/13 03:32 PM
                          Special internal SRAM to store Mutex?Gabriele Svelto2021/04/13 11:43 PM
                        Special internal SRAM to store Mutex?Carson2021/04/13 10:19 PM
          No conflict between theory and practicesr2021/04/06 07:12 AM
            No conflict between theory and practiceAnon2021/04/06 10:43 AM
            No conflict between theory and practiceAspect of Anonimity2021/04/06 03:20 PM
              No conflict between theory and practicesr2021/04/07 10:09 AM
                No conflict between theory and practiceanon22021/04/07 08:53 PM
  Armv9 officially announceddmcq2021/03/30 03:28 PM
    Totally backwads logic on compatibilityHeikki Kultala2021/03/30 03:44 PM
      Totally backwads logic on compatibilityDoug S2021/03/31 12:09 PM
        Totally backwads logic on compatibilitydmcq2021/03/31 03:15 PM
  Armv9 officially announcedv92021/04/12 03:57 PM
    Armv9 officially announcedj2021/04/13 05:07 AM
      Armv9 officially announcedDoug S2021/04/13 10:21 AM
        Armv9 officially announcedanonymou52021/04/13 11:06 AM
          Armv9 officially announcedDoug S2021/04/13 01:01 PM
        Armv9 officially announceddmcq2021/04/13 03:20 PM
Reply to this Topic
Name:
Email:
Topic:
Body: No Text
How do you spell avocado?