Consider the implementation of software transactional memory in Figure 13.19.

(a) How would you implement the read set, write map, and lock map data structures? You will want to minimize the cost not only of insert and lookup operations but also of (1) “zeroing out” the table at the end of a transaction, so it can be used again; and (2) extending the table if it becomes too full.

(b) The validate routine is called in two different places. Expand these calls in-line and customize them to the calling context. What optimizations can you achieve?

(c) Optimize the commit routine to exploit the fact that a final validation is unnecessary if no other transaction has committed since valid time.

(d) Further optimize commit by observing that the for loop in the finally clause really needs to iterate over orecs, not over addresses (there may be a difference, if more than one address hashes to the same orec). What data, ideally, should lock map hold?

Figure 13.9

shared count : integer := n shared sense : Boolean := true per-thread private local.sense : Boolean := true procedure central_barrier() local sense := not local-sense -- each thread toggles its own sense if fetch.and.decrementcount) = 1 -- last arriving thread count := n -- reinitialize for next iteration sense := local sense -- allow other threads to proceed else eat -- spin until sense = local.sense