future/HTMtableRCU.tex

% future/HTMtableRCU.tex
% SPDX-License-Identifier: CC-BY-SA-3.0

\begin{table*}
\centering
\small
\input{future/HTMtableColor}
\setstretch{0.95}
\setlength{\tabcolsep}{4pt}\OneColumnHSpace{-.9in}
\ebresizewidth{
\resizebox{6.5in}{!}{
\begin{tabularx}{6.8in}{p{0.95in}cXcX}
\toprule
  &
    & \multicolumn{1}{c}{Locking with Userspace RCU or Hazard Pointers} &
      & \multicolumn{1}{c}{Hardware Transactional Memory} \\
\midrule
  Basic Idea &
    & Allow only one thread at a time to access a given set of objects. &
      & Cause a given operation over a set of objects to execute atomically. \\
\midrule
  Scope &
    & \Pl Handles all operations. &
      & \Pl Handles revocable operations. \\
\addlinespace[4pt]
  &
    & &
      & \Mn Irrevocable operations force fallback (typically to locking). \\
\midrule
  Composability &
    & \Pl Readers limited only by grace-period-wait operations. &
      & \Dw Limited by irrevocable operations, transaction size, and deadlock.
        (Assuming lock-based fallback code.)\\
\addlinespace[4pt]
  &
    & \Mn Updaters limited by deadlock.  Readers reduce deadlock. &
      & \\
\midrule
  Scalability \& Performance &
    & \Mn Data must be partitionable to avoid lock contention among updaters. &
      & \Mn Data must be partitionable to avoid conflicts. \\
\addlinespace[4pt]
  &
    & \Pl Partitioning not needed for readers. &
      & \\
\cmidrule{3-5}
  &
    & \Dw Partitioning for updaters must typically be fixed at design time. &
      & \Pl Dynamic adjustment of partitioning carried out automatically down
        to cacheline boundaries. \\
\cmidrule{3-5}
  &
    & \Pl Partitioning not needed for readers. &
      & \Mn Partitioning required for fallbacks (less important for rare
        fallbacks). \\
\cmidrule{3-5}
  &
    & \Dw Updater locking primitives typically result in expensive cache misses
      and memory-barrier instructions. &
      & \Mn Transactions begin/end instructions typically do not result in
        cache misses, but do have memory-ordering and overhead consequences. \\
\cmidrule{3-5}
  &
    & \Pl Update-side contention effects are focused on acquisition and release,
      so that the critical section runs at full speed. &
      & \Mn Contention aborts conflicting transactions, even if they have been
        running for a long time. \\
\addlinespace[4pt]
  &
    & \Pl Readers do not contend with updaters or with each other. &
      & \\
\cmidrule{3-5}
  &
    & \Pl Read-side primitives are typically bounded wait-free with low
      overhead.
      (Lock-free with low overhead for hazard pointers.) &
      & \Mn Read-only transactions subject to conflicts and rollbacks.
        No forward-progress guarantees other than those supplied by fallback
        code. \\
\cmidrule{3-5}
  &
    & \Pl Privatization operations are simple, intuitive, performant, and
      scalable when data is visible only to updaters. &
      & \Mn Privatized data contributes to transaction size. \\
\addlinespace[4pt]
  &
    & \Mn Privatization operations are expensive (though still intuitive
      and scalable) for reader-visible data. &
      & \\
\midrule
  Hardware Support &
    & \Pl Commodity hardware suffices. &
      & \Mn New hardware required (and is starting to become available). \\
\cmidrule{3-5}
  &
    & \Pl Performance is insensitive to cache-geometry details. &
      & \Mn Performance depends critically on cache geometry. \\
\midrule
  Software Support &
    & \Pl APIs exist, large body of code and experience, debuggers operate
      naturally. &
      & \Mn APIs emerging, little experience outside of DBMS, breakpoints
        mid-transaction can be problematic. \\
\midrule
  Interaction With Other Mechanisms &
    & \Pl Long experience of successful interaction. &
      & \Dw Just beginning investigation of interaction. \\
\midrule
  Practical Apps &
    & \Pl Yes. &
      & \Pl Yes. \\
\midrule
  Wide Applicability &
    & \Pl Yes. &
      & \Mn Jury still out. \\
\bottomrule
\end{tabularx}
}}
\caption{Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM
  (\colorbox{plus}{Advantage}, \colorbox{minus}{Disadvantage},
  \colorbox{down}{Strong Disadvantage})}
\label{tab:future:Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM}
\end{table*}