For this week, I read Language Support for Lightweight Transactions by Cambridge Researchers Harris and Fraser from 2003. The paper outlines the development of software transactional memory as a feature built into the Java Programming language. I had first read about STM as a feature of Haskell while reading Beautiful Code, which is what pulled me into this paper.

Concurrency is a big problem in modern computing. We've reached a point where processors aren't getting faster, but we're getting more cores. On one hand, this is great for multi-application environments, because each application can have full access to a core. In practice, this actually doesn't work, since on Intel chips, the cache is shared between all the cores (which works better for concurrent programs), and some applications really need to additional speed.

STM is an mechanism of defining small atomic operations that you can be assured of will be viewed by every other application as a single op. For a simple example:

        class Account
        {
            private int balance;
        
            Account(int intialValue)
            {
                balance = initialValue;
            }
        
            public int getBalance() { return balance; }
        
            public void deposit(int amount) 
            {
                balance += amount;
            }
        
            public void withdraw(int amount)
            {
                this.deposit(-amount);
            }
        
            public void transfer(int amount, Account toAccount)
            {
                this.withdraw(amount);
                toAccount.deposit(amount);
            }
        }
        

Now, in a multi-threaded environment, the above code could have problems, because deposit actually involves 3 instructions: read balance, add amount to balance, write balance, and if there are two deposits being made to an account, then they could both read at roughly the same time, which would cause their commits to be inaccurate.

With STM, you indicate somehow that they're 'atomic' functions, and it checks that the value in memory hasn't changed since you read it, to ensure that your changed amount it correct, if it has, the transaction aborts and can be retried again. It's a similar practice to transactions in a SQL database, and as such, it does add overhead to the operations. But so does traditional locking using mutexes and semaphores.

Which is where the findings of the paper were most interesting. In their trials, using a highly tuned hash-table implementation using traditional locking mechanisms, either a single lock for the entire table, or fine-grained locking, and a simple implementation using STM, they found that the overhead on each operation in the STM case was actually pretty small compared to the fact that it was essentially non-blocking, only needing to redo work on the off chance that the same records were being updated.

With language support, which in Java would look like this:

        class Account
        {
            private int balance;
        
            Account(int intialValue)
            {
                    balance = initialValue;
            }
        
            public int getBalance() { return balance; }
        
            public void deposit(int amount) 
            {
                atomic {
                    balance += amount;
                }
            }
        
            public void withdraw(int amount)
            {
                atomic {
                    this.deposit(-amount);
                }
            }
        
            public void transfer(int amount, Account toAccount)
            {
                atomic {
                    this.withdraw(amount);
                    toAccount.deposit(amount);
                }
            }
        }
        

The atomic keyword, at least in the research compiler that this paper was based on, who's source can be here, would handle the creation of the transaction, as well as the enforcement of it. With STM, deadlocks are basically impossible. If a transaction fails, it can be re-executed after waiting a random interval, and move on from there. Using mutexes, the transfer function could easily deadlock with a programmer error.

This paper was really interesting, because the Haskell version makes a really big deal about not allowing functions that perform IO inside of transactions, and the Beautiful Code discussion of the feature made it sound like STM practically required being used in a purely functional language, but this paper showed that clearly wasn't the case, and has made me very curious about other ways to use this technique.

Next weeks paper will be A Framework for Robust and Flexible Handling of Inputs with Uncertainty.