Transactional Programming

Cleanup

If the program could be rolled back right to the beginning, no memory would ever be freed and eventually the program would run out of memory. So objects marked for deletion must actually be deleted at some point.

This can be done when the outermost transaction has completed. At this point, there is no possibility of roll back. So the entire transaction stack is scanned for deleted objects, which are deleted, and then the transaction stack is resized to 0.

If transactions are kept short, then the transaction stack will be small, and deleted objects will not be hanging around for very long. On the other hand, if the entire program is wrapped in a transaction, then the program will never free any memory!

Concurrent Access

Transactions in different threads should be independent. When one thread throws an exception and rolls back some containers, it should not interfere with another thread that is executing quite happily. This means that concurrent threads cannot share the same transaction stack.

There are basically two solutions to this problem.

• Provide a lock so that transactions in different threads are mutually exclusive. This is the only truly safe thing to do, and is easy for programmers who no longer need to write any locks in the program, because they are implicit in the transaction. But this reduces concurrency so it is not an ideal solution.
• Have one transaction stack per thread. But extreme care is required. Suppose a list contains two elements, a and b. If thread A deletes a, then thread B deletes b, then thread A rolls back the deletion, where does a get inserted? Its hint says that it should be inserted before b, but b is a deleted object! Such problems do not arise in a single-threaded program. It is not enough to lock just the operation, the destructor of the transaction must be protected by the mutex as well, in case rolling back interferes with another thread.

The general pattern is as follows:

{
 Lock lock(mutex);  
  // Destructor unlocks
 atomic::transaction tr;
  // Modify container
 tr.commit();
}

Performance

Transactions add around 5-15 percent of CPU time for insertion and deletion. The main overhead is logging each operation on the transaction stack. The extra memory used is proportional to the size of the transaction, not the size of the data. Provided that transactions are short, little extra memory is required. Object deletion is deferred until the end of the transaction.

Table 1 shows some performance comparisons of atomic containers compared to their std equivalents, in nonthrowing circumstances. The program used to generate these numbers is available online (see "Resource Center," page 5) and at calumgrant.net/atomic. These figures measure the same operation performed repeatedly on different types of containers. As you can see from these results, atomic containers do add some overhead, which is to be expected. The only container for which the overhead dominates the performance is for vector<int>, which is so efficient that the operations on the transaction stack are slower than the operations on the vector itself.

Conclusion

The problem with C++ exceptions is that they can occur at many points in a program, and if even a single exception is overlooked, the program is potentially unsafe. Database transactions don't suffer from this problem because atomic behavior is guaranteed by the transaction. By copying the database approach, C++ can also implement transactions. It provides guarantees of atomic behavior, helps in complex error-recovery situations, and allows smaller functions to be composed into larger transactions. Whichever exception strategy is used, it is an important part of the design and needs care, attention, and planning.

References

[1] Abrahams, D. "Exception-Safety in Generic Components," Generic Programming: Proceedings of a Dagstuhl Seminar, M. Jazayeri, R. Loos, and D. Musser, eds. (Springer Verlag, 1999).

[2] Alexandrescu, A., P. Marginean. "Change the Way You Write Exception-Safe Code—Forever." (www.cuj.com/ documents/s=8000/cujcexp1812alexandr/alexandr.htm).