Transactions, which provide optimistic synchronization by avoiding
the use of blocking, greatly simplify multicore programming.
In fact, the programmer has simply to encapsulate sequential operations
or existing critical sections into transactions to obtain a
safe concurrent program. Programmers have thus started evaluating
transactional memory using data structures originally designed
for pessimistic (i.e., non-optimistic) synchronization, whose prominent
example is the red-black tree library developed by Oracle Labs
that is part of STAMP and microbench distributions.
Unfortunately, existing data structures are badly suited for optimistic
synchronization as they rely on strong structural invariants,
like logarithmic tree depth, to bound the step complexity of pessimistically
synchronized accesses. By contrast, this complexity
does not apply to optimistically synchronized accesses thus making
the invariants overly conservative. More dramatically, guaranteeing
such invariants tends to increase the probability of aborting
and restarting the same access before it completes.
In this talk, we introduce a concurrent binary search tree that
breaks transiently its balance structural invariants for efficiency, a
property we call transaction-friendly. We show that this new tree
outperforms the existing transaction-based version of the AVL and
the red-black trees. Its key novelty stems from the decoupling of
update operations: they are split into one transaction that modifies
the abstraction state and multiple ones that restructure its tree
implementation. The resulting transaction-friendly library trades
aborts for few additional access steps and, in particular, it speeds
up a transaction-based travel reservation application by up to 3:5 .