3 ms·

I assume interrupts would be disabled or deferred during this section, so you get stronger guarantees on worst-case behavior; hence the bound on the number of c

I assume interrupts would be disabled or deferred during this section, so you get stronger guarantees on worst-case behavior; hence the bound on the number of cycles a thread is allowed to execute for. On one of the less common unixes (Sun's maybe? I don't totally remember), you could set a bit in some thread-specific part of memory to indicate that you were uninterruptible. If the OS saw that bit was set, it would set a "you need to yield" bit in the same part of memory and then allow the thread to continue (and penalize threads that abused the feature). As a practical matter, I suspect that the scheme proposed wouldn't have advantages over a careful use of HTM. I also suspect that the "lock two cachelines" thing is harder to implement than it sounds. The way Intel implements atomic operations that span cachelines now involves waiting for a interconnect quiescence period (taking O(microseconds)). What's proposed here is strictly more general.

pizlonator 10y ago
Disabling interrupts prevents you from using interrupt-unsafe logic inside the critical section, which is impractical in most cases. It would mean, for example, that you wouldn't be able to touch memory that had been swapped. It also doesn't actually improve performance. When people do this, it's because they want to edit process-local data structures. Unless you're in kernel, you probably don't want this. As a practical matter, HTM is dead. It's 2x slower than locking in the common cases: uncontended critical section or contended critical section that has a race. It also prevents you from doing effects outside of memory (it's just guaranteed to revert to locks in that case, so you pay all of the overhead of HTM and all of the overhead of locks). Interesting about the difficulty of locking two cache lines. To me the important thing to keep in mind when talking about concurrency alternatives to the status quo is: nobody has proved that contended-but-not-racy critical sections are common. According to my data, they are unicorns. This means that from a performance standpoint, any proposed concurrency protocol that is different from locking must justify how it plans to beat locks on the two things that they are super good at, which are uncontended critical sections (with locks you pay one or two CASes on cache lines you probably already own) and contended-and-racy critical sections (with locks you pay for some CASes but the lock will make threads contend as quietly as possible to allow the lock owner to proceed quickly). If a proposal is worse than locks on the two most common kinds of critical sections, then that's silly. AFAICT, all of these trasactions-or-better-CAS approaches would only help in the case of contended-but-not-racy critical sections, which are too rare to matter. The two cache line thing definitely sounds like it will be more expensive than locking in the uncontended case, and I don't see how it will help in the contended-but-racy case. EDIT: I said "contended-but-racy" when I meant "contended-but-not-racy" in one place, above. Fixed.
- gpderetta 10y ago
  Transactions compose and TM is potentially easier to use. Also some algorithms necessarily require locking multiple mutexes (think for example of a wait-for-any operation). HTM in principle would allow implementing them more efficiently.
  - pizlonator 10y ago
    Transactions don't compose with I/O or any OS side-effects that the TM system isn't in the loop on, while locks compose fine with those things. One module that uses locks is free to call another module that uses locks so long as the relationship is one-way like user->kernel, so locks compose also, just with different constraints. In short, transactions don't compose with I/O while locks don't compose with cyclic relationships. So, the statement that "transactions compose" is false in both directions: it's false because transactions don't compose in general, and it's false because it implies that locks don't, while they in fact do. The only empirical evidence about transactions being easier to use is actually contrary: even with the availability of HTM, it's not used nearly as widely as locks, because if you enable HTM for every lock then everything runs a lot slower (or doesn't run at all).
    - gpderetta 10y ago
      Under the proposed C++ TM, synchronised blocks can do i/o. They are not transactional, but do compose. If you have two locked data structures and you want an operation to manipulate both atomically you need to expose the locks. And if you want the operation itself to compose with others... well get hairy. TM is widely used I believe by least Haskel and Closure programmers, even with non hardware accelerated versions because of the ease of use. HTM is another story, it's availability is still relatively restricted. Time will tell.
      - pizlonator 10y ago
        Closure is indeed TM-based, but that's not an A/B test of ease-of-use. I don't think there exists evidence to suggest that transactions are easier to use. I think you are confused about the meaning of composability. The synchronized/atomic TM proposal for C++ is roughly single-global-lock. This means that you can still deadlock if you use synchronized to protect IPC with another process, which then does an IPC call back to you, which you service on another thread that also uses synchronized. Whenever these transactional proposals fall back on locking, they immediately bring in the pitfalls of locking. The C++ TM proposal is a joke. There's no good reason to use concurrency if you won't get a speed-up, and the current design of synchronized is sure to make it more difficult to get speed-ups.

pizlonator 10y ago

Disabling interrupts prevents you from using interrupt-unsafe logic inside the critical section, which is impractical in most cases. It would mean, for example, that you wouldn't be able to touch memory that had been swapped. It also doesn't actually improve performance. When people do this, it's because they want to edit process-local data structures. Unless you're in kernel, you probably don't want this. As a practical matter, HTM is dead. It's 2x slower than locking in the common cases: uncontended critical section or contended critical section that has a race. It also prevents you from doing effects outside of memory (it's just guaranteed to revert to locks in that case, so you pay all of the overhead of HTM and all of the overhead of locks). Interesting about the difficulty of locking two cache lines. To me the important thing to keep in mind when talking about concurrency alternatives to the status quo is: nobody has proved that contended-but-not-racy critical sections are common. According to my data, they are unicorns. This means that from a performance standpoint, any proposed concurrency protocol that is different from locking must justify how it plans to beat locks on the two things that they are super good at, which are uncontended critical sections (with locks you pay one or two CASes on cache lines you probably already own) and contended-and-racy critical sections (with locks you pay for some CASes but the lock will make threads contend as quietly as possible to allow the lock owner to proceed quickly). If a proposal is worse than locks on the two most common kinds of critical sections, then that's silly. AFAICT, all of these trasactions-or-better-CAS approaches would only help in the case of contended-but-not-racy critical sections, which are too rare to matter. The two cache line thing definitely sounds like it will be more expensive than locking in the uncontended case, and I don't see how it will help in the contended-but-racy case. EDIT: I said "contended-but-racy" when I meant "contended-but-not-racy" in one place, above. Fixed.

gpderetta 10y ago
Transactions compose and TM is potentially easier to use. Also some algorithms necessarily require locking multiple mutexes (think for example of a wait-for-any operation). HTM in principle would allow implementing them more efficiently.
- pizlonator 10y ago
  Transactions don't compose with I/O or any OS side-effects that the TM system isn't in the loop on, while locks compose fine with those things. One module that uses locks is free to call another module that uses locks so long as the relationship is one-way like user->kernel, so locks compose also, just with different constraints. In short, transactions don't compose with I/O while locks don't compose with cyclic relationships. So, the statement that "transactions compose" is false in both directions: it's false because transactions don't compose in general, and it's false because it implies that locks don't, while they in fact do. The only empirical evidence about transactions being easier to use is actually contrary: even with the availability of HTM, it's not used nearly as widely as locks, because if you enable HTM for every lock then everything runs a lot slower (or doesn't run at all).
  - gpderetta 10y ago
    Under the proposed C++ TM, synchronised blocks can do i/o. They are not transactional, but do compose. If you have two locked data structures and you want an operation to manipulate both atomically you need to expose the locks. And if you want the operation itself to compose with others... well get hairy. TM is widely used I believe by least Haskel and Closure programmers, even with non hardware accelerated versions because of the ease of use. HTM is another story, it's availability is still relatively restricted. Time will tell.
    - pizlonator 10y ago
      Closure is indeed TM-based, but that's not an A/B test of ease-of-use. I don't think there exists evidence to suggest that transactions are easier to use. I think you are confused about the meaning of composability. The synchronized/atomic TM proposal for C++ is roughly single-global-lock. This means that you can still deadlock if you use synchronized to protect IPC with another process, which then does an IPC call back to you, which you service on another thread that also uses synchronized. Whenever these transactional proposals fall back on locking, they immediately bring in the pitfalls of locking. The C++ TM proposal is a joke. There's no good reason to use concurrency if you won't get a speed-up, and the current design of synchronized is sure to make it more difficult to get speed-ups.