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?