PyPy Status Blog - STM update: back to threads?

If you use a sufficiently advanced STM, and have an atomic region, then two threads can enter the same region, as long as they don't use each other's memory. You may think, why synchronise if they're not using each other's memory? Well it can be extremely hard to work out a priori if two threads are using the same memory or not. In fact for some problems, such as many graph problems, working out what memory they're going to use is the same problem as the problem that you're trying to solve in the first place.

STM is like having a single lock for every single word in your memory, and then magically always acquiring every lock that you will need at the start of the transaction in a determinate order, so that you don't get deadlock.

If two threads enter an atomic region, but do access each other's memory, then the transaction is silently aborted and restarted. Ideally these aborts are rare and the program runs very much in parallel.

A more concrete example - in Java if you have a hash table you will usually lock during all reads and writes. If you used STM, and two writes accessed different buckets of the table, then there's no need to lock. The STM works this out for you.