* [PATCH 0/2] future: Update Locking and HTM comparison tables
@ 2017-12-06 15:00 Akira Yokosawa
2017-12-06 15:01 ` [PATCH 1/2] " Akira Yokosawa
` (3 more replies)
0 siblings, 4 replies; 9+ messages in thread
From: Akira Yokosawa @ 2017-12-06 15:00 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From d6497dadbc973d7d94591f48730c4c0ce1c129a8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Wed, 6 Dec 2017 23:40:04 +0900
Subject: [PATCH 0/2] future: Update Locking and HTM comparison tables
Hi Paul,
I have tackled the remaining two tables of old style in Section 17.3.
"Advantage", "Disadvantage", and "Strong Disadvantage" can be indicated
by background colors, and their structures can be simplified.
This scheme is inspired by Table 12.4, with using lower saturation
colors.
Patch #1 modifies the tables.
Patch #2 adds a merged table of the two as a sidewaystable.
Background colors are chosen so that they can be distinguished
when they are printed in grayscale.
Thoughts?
Thanks, Akira
--
Akira Yokosawa (2):
future: Update Locking and HTM comparison tables
future: Add merged table of locking & HTM comparison
appendix/styleguide/styleguide.tex | 6 -
future/HTMtable.tex | 201 ++++++++++++++---------------
future/HTMtableColor.tex | 9 ++
future/HTMtableFull.tex | 148 +++++++++++++++++++++
future/HTMtableRCU.tex | 254 +++++++++++++++++--------------------
future/htm.tex | 6 +
perfbook.tex | 1 +
7 files changed, 370 insertions(+), 255 deletions(-)
create mode 100644 future/HTMtableColor.tex
create mode 100644 future/HTMtableFull.tex
--
2.7.4
^ permalink raw reply [flat|nested] 9+ messages in thread* [PATCH 1/2] future: Update Locking and HTM comparison tables 2017-12-06 15:00 [PATCH 0/2] future: Update Locking and HTM comparison tables Akira Yokosawa @ 2017-12-06 15:01 ` Akira Yokosawa 2017-12-06 15:05 ` [PATCH 2/2] future: Add merged table of locking & HTM comparison Akira Yokosawa ` (2 subsequent siblings) 3 siblings, 0 replies; 9+ messages in thread From: Akira Yokosawa @ 2017-12-06 15:01 UTC (permalink / raw) To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa From c0970ece95821d54891cb5491873ae4c33c9b7ec Mon Sep 17 00:00:00 2001 From: Akira Yokosawa <akiyks@gmail.com> Date: Wed, 6 Dec 2017 23:38:01 +0900 Subject: [PATCH 1/2] future: Update Locking and HTM comparison tables By using background colors to indicate Advantage/Disadvantage, these tables can be simplified. As with other tables, rules of "booktabs" are used. Skips between rows are controlled by using \midrule, \cmidrule, and \addlinespace. In order to put HTMtableRCU.tex within a size of A4 paper, baseline skip is slightly reduced locally by \setstretch command (provided by "setspace" package) and the overall table is further reduced by \resizebox. Background colors are defined in a separate file HTMtableColor.tex for ease of color tuning. Colors used at the moment are chosen so that they can be distinguished when printed in grayscale. Color names "plus", "minus", "down" reflect the symbols used before this change. To place gaps between columns, extra columns are added and \tabcolsep is narrowed. Also fix a couple of typo (partionable -> partitionable, partioning -> partitioning). Signed-off-by: Akira Yokosawa <akiyks@gmail.com> --- appendix/styleguide/styleguide.tex | 6 - future/HTMtable.tex | 201 ++++++++++++++--------------- future/HTMtableColor.tex | 9 ++ future/HTMtableRCU.tex | 254 +++++++++++++++++-------------------- perfbook.tex | 1 + 5 files changed, 216 insertions(+), 255 deletions(-) create mode 100644 future/HTMtableColor.tex diff --git a/appendix/styleguide/styleguide.tex b/appendix/styleguide/styleguide.tex index 11f539b..0337fbb 100644 --- a/appendix/styleguide/styleguide.tex +++ b/appendix/styleguide/styleguide.tex @@ -797,12 +797,6 @@ IBM~Q & $0.015$ \label{tab:app:styleguide:Refrigeration Power Consumption} \end{table} -Most tables in the text have been converted to this format. -Tables~\ref{tab:future:Comparison of Locking and HTM} -and~\ref{tab:future:Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM} -are the exceptions. They are complex and require an alternative -approach.\footnote{Any suggestion is welcome!!!} - \subsubsection{Position of Caption} \label{sec:app:styleguide:Position of Caption} diff --git a/future/HTMtable.tex b/future/HTMtable.tex index d317f94..31d4802 100644 --- a/future/HTMtable.tex +++ b/future/HTMtable.tex @@ -4,114 +4,97 @@ \begin{table*}[p] \centering % \scriptsize -\small\OneColumnHSpace{-.8in} -\begin{tabular}{p{1.0in}||c|p{2.0in}||c|p{2.0in}} -& \multicolumn{2}{c||}{Locking} & \multicolumn{2}{c}{Hardware Transactional Memory} \\ -\hline -\hline -Basic Idea - & \multicolumn{2}{p{2.2in}||}{ - Allow only one thread at a time to access a given set of objects.} - & \multicolumn{2}{p{2.2in}}{ - Cause a given operation over a set of objects to execute - atomically.} \\ -\hline -\hline -Scope - & $+$ - & Handles all operations. - & $+$ - & Handles revocable operations. \\ -\cline{4-5} - & & - & $-$ - & Irrevocable operations force fallback (typically - to locking). \\ -\hline -Composability - & $\Downarrow$ - & Limited by deadlock. - & $\Downarrow$ - & Limited by irrevocable operations, transaction size, - and deadlock (assuming lock-based fallback code). \\ -\hline -Scalability \& Performance - & $-$ - & Data must be partitionable to avoid lock contention. - & $-$ - & Data must be partionable to avoid conflicts. \\ -\cline{2-5} - & $\Downarrow$ - & Partioning must typically be fixed at design time. - & $+$ - & Dynamic adjustment of partitioning carried out - automatically down to cacheline boundaries. \\ -\cline{4-5} - & - & - & $-$ - & Partitioning required for fallbacks (less important - for rare fallbacks). \\ -\cline{2-5} - & $\Downarrow$ - & Locking primitives typically result in expensive cache misses - and memory-barrier instructions. - & $-$ - & Transactions begin/end instructions typically do not - result in cache misses, but do have memory-ordering - consequences. \\ -\cline{2-5} - & $+$ - & Contention effects are focused on acquisition and release, so - that the critical section runs at full speed. - & $-$ - & Contention aborts conflicting transactions, even - if they have been running for a long time. \\ -\cline{2-5} - & $+$ - & Privatization operations are simple, intuitive, performant, - and scalable. - & $-$ - & Privatized data contributes to transaction size. \\ -\hline -Hardware Support - & $+$ - & Commodity hardware suffices. - & $-$ - & New hardware required (and is starting to become - available). \\ -\cline{2-5} - & $+$ - & Performance is insensitive to cache-geometry details. - & $-$ - & Performance depends critically on cache geometry. \\ -\hline -Software Support - & $+$ - & APIs exist, large body of code and experience, debuggers operate - naturally. - & $-$ - & APIs emerging, little experience outside of DBMS, - breakpoints mid-transaction can be problematic. \\ -\hline -Interaction With Other Mechanisms - & $+$ - & Long experience of successful interaction. - & $\Downarrow$ - & Just beginning investigation of interaction. \\ -\hline -Practical Apps - & $+$ - & Yes. - & $+$ - & Yes. \\ -\hline -Wide Applicability - & $+$ - & Yes. - & $-$ - & Jury still out, but likely to win significant use. \\ -\end{tabular} -\caption{Comparison of Locking and HTM (``$+$'' is Advantage, ``$-$'' is Disadvantage, ``$\Downarrow$'' is Strong Disadvantage)} +\small +\input{future/HTMtableColor} +\setlength{\tabcolsep}{4pt}\OneColumnHSpace{-.9in} +\begin{tabularx}{6.5in}{p{0.95in}cXcX} +\toprule + & + & \multicolumn{1}{c}{Locking} & + & \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 & + & \Dw Limited by deadlock. & + & \Dw Limited by irrevocable operations, transaction size, + and deadlock (assuming lock-based fallback code). \\ +\midrule + Scalability \& Performance & + & \Mn Data must be partitionable to avoid lock contention. & + & \Mn Data must be partitionable to avoid conflicts. \\ +\cmidrule{3-5} + & + & \Dw Partioning must typically be fixed at design time. & + & \Pl Dynamic adjustment of partitioning carried out automatically down + to cacheline boundaries. \\ +\addlinespace[4pt] + & + & & + & \Mn Partitioning required for fallbacks (less important for rare + fallbacks). \\ +\cmidrule{3-5} + & + & \Dw 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 consequences. \\ +\cmidrule{3-5} + & + & \Pl 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. \\ +\cmidrule{3-5} + & + & \Pl Privatization operations are simple, intuitive, performant, + and scalable. & + & \Mn Privatized data contributes to transaction size. \\ +\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, but likely to win significant use. \\ +\bottomrule +\end{tabularx} +\IfTwoColumn{ +\caption{Comparison of Locking and HTM (\colorbox{plus}{Advantage}, + \colorbox{minus}{Disadvantage}, \colorbox{down}{Strong Disadvantage})} +}{ +\caption{Comparison of Locking and HTM (\colorbox{plus}{Advantage}, + \colorbox{minus}{Disadvantage}, + \colorbox{down}{Strong} \colorbox{down}{Disadvantage})} +} \label{tab:future:Comparison of Locking and HTM} \end{table*} diff --git a/future/HTMtableColor.tex b/future/HTMtableColor.tex new file mode 100644 index 0000000..94a7c2f --- /dev/null +++ b/future/HTMtableColor.tex @@ -0,0 +1,9 @@ +% future/HTMtableColor.tex +% SPDX-License-Identifier: CC-BY-SA-3.0 + +\definecolor{plus}{cmyk}{0.1,0,0,0} +\definecolor{minus}{cmyk}{0,0.05,0.2,0.05} +\definecolor{down}{cmyk}{0,0.15,0.15,0.1} +\newcommand{\Pl}{\cellcolor{plus}} +\newcommand{\Mn}{\cellcolor{minus}} +\newcommand{\Dw}{\cellcolor{down}} diff --git a/future/HTMtableRCU.tex b/future/HTMtableRCU.tex index 4c51fa3..c7a59d8 100644 --- a/future/HTMtableRCU.tex +++ b/future/HTMtableRCU.tex @@ -3,145 +3,119 @@ \begin{table*}[p] \centering -\small\OneColumnHSpace{-.8in} -%\raggedright -\begin{tabular}{p{1.0in}||c|p{2.0in}||c|p{2.0in}} -& \multicolumn{2}{c||}{Locking with Userspace RCU or Hazard Pointers} & \multicolumn{2}{c}{Hardware Transactional Memory} \\ -\hline -\hline -Basic Idea - & \multicolumn{2}{p{2.2in}||}{ - Allow only one thread at a time to access a given set of objects.} - & \multicolumn{2}{p{2.2in}}{ - Cause a given operation over a set of objects to execute - atomically.} \\ -\hline -\hline -Scope - & $+$ - & Handles all operations. - & $+$ - & Handles revocable operations. \\ -\cline{4-5} - & & - & $-$ - & Irrevocable operations force fallback (typically - to locking). \\ -\hline -Composability - & $+$ - & Readers limited only by grace-period-wait operations. - & $\Downarrow$ - & Limited by irrevocable operations, transaction size, - and deadlock. \\ -\cline{2-3} - & $-$ - & Updaters limited by deadlock. Readers reduce deadlock. - & - & (Assuming lock-based fallback code.) \\ -\hline -Scalability \& Performance - & $-$ - & Data must be partitionable to avoid lock contention among - updaters. - & $-$ - & Data must be partionable to avoid conflicts. \\ -\cline{2-3} - & $+$ - & Partitioning not needed for readers. - & - & \\ -\cline{2-5} - & $\Downarrow$ - & Partioning for updaters must typically be fixed at design time. - & $+$ - & Dynamic adjustment of partitioning carried out - automatically down to cacheline boundaries. \\ -\cline{2-5} - & $+$ - & Partitioning not needed for readers. - & $-$ - & Partitioning required for fallbacks (less important - for rare fallbacks). \\ -\cline{2-5} - & $\Downarrow$ - & Updater locking primitives typically result in expensive cache - misses and memory-barrier instructions. - & $-$ - & Transactions begin/end instructions typically do not - result in cache misses, but do have memory-ordering - consequences. \\ -\cline{2-5} - & $+$ - & Update-side contention effects are focused on acquisition and - release, so that the critical section runs at full speed. - & $-$ - & Contention aborts conflicting transactions, even - if they have been running for a long time. \\ -\cline{2-3} - & $+$ - & Readers do not contend with updaters or with each other. - & - & \\ -\cline{2-5} - & $+$ - & Read-side primitives are typically wait-free with low - overhead. (Lock-free for hazard pointers.) - & $-$ - & Read-only transactions subject to conflicts and rollbacks. - No forward-progress guarantees other than those supplied - by fallback code. \\ -\cline{2-5} - & $+$ - & Privatization operations are simple, intuitive, performant, - and scalable when data is visible only to updaters. - & $-$ - & Privatized data contributes to transaction size. \\ -\cline{2-3} - & $-$ - & Privitization operations are expensive (though still intuitive - and scalable) for reader-visible data. - & - & \\ -\hline -Hardware Support - & $+$ - & Commodity hardware suffices. - & $-$ - & New hardware required (and is starting to become - available). \\ -\cline{2-5} - & $+$ - & Performance is insensitive to cache-geometry details. - & $-$ - & Performance depends critically on cache geometry. \\ -\hline -Software Support - & $+$ - & APIs exist, large body of code and experience, debuggers operate - naturally. - & $-$ - & APIs emerging, little experience outside of DBMS, - breakpoints mid-transaction can be problematic. \\ -\hline -Interaction With Other Mechanisms - & $+$ - & Long experience of successful interaction. - & $\Downarrow$ - & Just beginning investigation of interaction. \\ -\hline -Practical Apps - & $+$ - & Yes. - & $+$ - & Yes. \\ -\hline -Wide Applicability - & $+$ - & Yes. - & $-$ - & Jury still out, but likely to win significant use. \\ -\end{tabular} -\caption{Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM (``$+$'' is Advantage, ``$-$'' is Disadvantage, ``$\Downarrow$'' is Strong Disadvantage)} +\small +\input{future/HTMtableColor} +\setstretch{0.95} +\setlength{\tabcolsep}{4pt}\OneColumnHSpace{-.9in} +\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 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 wait-free with low overhead. + (Lock-free 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 Privitization 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, but likely to win significant use. \\ +\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*} diff --git a/perfbook.tex b/perfbook.tex index 32f0e6d..e4bba02 100644 --- a/perfbook.tex +++ b/perfbook.tex @@ -31,6 +31,7 @@ % \usepackage{breakurl} \usepackage{graphicx} \usepackage{rotating} +\usepackage{setspace} \usepackage{enumitem} \setlist[description]{style=unboxed} %\usepackage{enumerate} -- 2.7.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 2/2] future: Add merged table of locking & HTM comparison 2017-12-06 15:00 [PATCH 0/2] future: Update Locking and HTM comparison tables Akira Yokosawa 2017-12-06 15:01 ` [PATCH 1/2] " Akira Yokosawa @ 2017-12-06 15:05 ` Akira Yokosawa 2017-12-06 16:11 ` [PATCH 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney 2017-12-06 22:19 ` [PATCH v2 " Akira Yokosawa 3 siblings, 0 replies; 9+ messages in thread From: Akira Yokosawa @ 2017-12-06 15:05 UTC (permalink / raw) To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa From d6497dadbc973d7d94591f48730c4c0ce1c129a8 Mon Sep 17 00:00:00 2001 From: Akira Yokosawa <akiyks@gmail.com> Date: Wed, 6 Dec 2017 23:38:41 +0900 Subject: [PATCH 2/2] future: Add merged table of locking & HTM comparison Tables of HTMtable.tex and HTMtableRCU.tex can be merged into a single large table in a "sidewaystable" environment. To reduce the height of the table, font size of footnotesize is used in addition to commands \setstretch{} and \resizebox{}. The additional paragraph in the text citing the table is tentative and need some rewording. Signed-off-by: Akira Yokosawa <akiyks@gmail.com> --- future/HTMtableFull.tex | 148 ++++++++++++++++++++++++++++++++++++++++++++++++ future/htm.tex | 6 ++ 2 files changed, 154 insertions(+) create mode 100644 future/HTMtableFull.tex diff --git a/future/HTMtableFull.tex b/future/HTMtableFull.tex new file mode 100644 index 0000000..eb2886c --- /dev/null +++ b/future/HTMtableFull.tex @@ -0,0 +1,148 @@ +% future/HTMtableFull.tex +% SPDX-License-Identifier: CC-BY-SA-3.0 + +\begin{sidewaystable*}[htbp] +\input{future/HTMtableColor} +\centering +\caption{Comparison of Locking (Plain and Augmented) and HTM + (\colorbox{plus}{Advantage}, \colorbox{minus}{Disadvantage}, + \colorbox{down}{Strong Disadvantage})} +\label{tab:future:Comparison of Locking (Plain and Augmented) and HTM} +\footnotesize +\setstretch{0.95} +%\renewcommand*{\arraystretch}{1.4} +\setlength{\tabcolsep}{3pt} +\resizebox{8in}{!}{ +\begin{tabularx}{8.5in}{p{.85in}cXcXcX} +\toprule + & + & \multicolumn{1}{c}{Locking} & + & \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. & + & 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 all operations. & + & \Pl Handles revocable operations. \\ +\addlinespace[4pt] + & + & & + & & + & \Mn Irrevocable operations force fallback (typically to locking). \\ +\midrule + Composability & + & \Dw Limited by deadlock. & + & \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. & + & \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-7} + & + & \Dw Partitioning must typically be fixed at design time. & + & \Dw Partitioning for updaters must typically be fixed at design time. & + & \Pl Dynamic adjustment of partitioning carried out automatically + down to cacheline boundaries. \\ +\addlinespace[4pt] + & + & & + & \Pl Partitioning not needed for readers. & + & \Mn Partitioning required for fallbacks (less important for rare + fallbacks). \\ +\cmidrule{3-7} + & + & \Dw Locking primitives typically result in expensive cache misses and + memory-barrier instructions.& + & \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 consequences. \\ +\cmidrule{3-7} + & + & \Pl Contention effects are focused on acquisition and release, so that + the critical section runs at full speed. & + & \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-7} + & + & & + & \Pl Read-side primitives are typically wait-free with low overhead. + (Lock-free 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-7} + & + & \Pl Privatization operations are simple, intuitive, performant, + and scalable. & + & \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. & + & \Pl Commodity hardware suffices. & + & \Mn New hardware required (and is starting to become available). \\ +\cmidrule{3-7} + & + & \Pl Performance is insensitive to cache-geometry details. & + & \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. & + & \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. & + & \Pl Long experience of successful interaction. & + & \Dw Just beginning investigation of interaction. \\ +\midrule + Practical Apps & + & \Pl Yes. & + & \Pl Yes. & + & \Pl Yes. \\ +\midrule + Wide Applicability & + & \Pl Yes. & + & \Pl Yes. & + & \Mn Jury still out, but likely to win significant use. \\ +\bottomrule +\end{tabularx} +} +\end{sidewaystable*} diff --git a/future/htm.tex b/future/htm.tex index 7c9f610..6667cd0 100644 --- a/future/htm.tex +++ b/future/htm.tex @@ -918,6 +918,12 @@ A summary of the differences between the two tables is as follows: straightforward. \end{enumerate} +\input{future/HTMtableFull} + +For those who want to see the comparison at one view, +Table~\ref{tab:future:Comparison of Locking (Plain and Augmented) and HTM} +shows the merged comparison. + Of course, it is also possible to augment HTM, as discussed in the next section. -- 2.7.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 0/2] future: Update Locking and HTM comparison tables 2017-12-06 15:00 [PATCH 0/2] future: Update Locking and HTM comparison tables Akira Yokosawa 2017-12-06 15:01 ` [PATCH 1/2] " Akira Yokosawa 2017-12-06 15:05 ` [PATCH 2/2] future: Add merged table of locking & HTM comparison Akira Yokosawa @ 2017-12-06 16:11 ` Paul E. McKenney 2017-12-06 22:16 ` Akira Yokosawa 2017-12-06 22:19 ` [PATCH v2 " Akira Yokosawa 3 siblings, 1 reply; 9+ messages in thread From: Paul E. McKenney @ 2017-12-06 16:11 UTC (permalink / raw) To: Akira Yokosawa; +Cc: perfbook On Thu, Dec 07, 2017 at 12:00:02AM +0900, Akira Yokosawa wrote: > >From d6497dadbc973d7d94591f48730c4c0ce1c129a8 Mon Sep 17 00:00:00 2001 > From: Akira Yokosawa <akiyks@gmail.com> > Date: Wed, 6 Dec 2017 23:40:04 +0900 > Subject: [PATCH 0/2] future: Update Locking and HTM comparison tables > > Hi Paul, > > I have tackled the remaining two tables of old style in Section 17.3. > "Advantage", "Disadvantage", and "Strong Disadvantage" can be indicated > by background colors, and their structures can be simplified. > This scheme is inspired by Table 12.4, with using lower saturation > colors. > > Patch #1 modifies the tables. > Patch #2 adds a merged table of the two as a sidewaystable. > > Background colors are chosen so that they can be distinguished > when they are printed in grayscale. > > Thoughts? Very nice!!! I very much like the use of colors instead of symbols, and I say that as someone who is red-green colorblind. ;-) I queued both commits and added the commit below. If you are OK with the below change, I will push all three. If not, please let me know what needs to change. Thanx, Paul ------------------------------------------------------------------------ commit 76dacd546e9e1ad1153ef5b3ef6ad0dfd9985246 Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> Date: Wed Dec 6 08:07:10 2017 -0800 future/htm: Reword sentence referencing the new Table 17.3 Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> diff --git a/future/htm.tex b/future/htm.tex index 6667cd0ce8f0..908166bc0768 100644 --- a/future/htm.tex +++ b/future/htm.tex @@ -920,9 +920,11 @@ A summary of the differences between the two tables is as follows: \input{future/HTMtableFull} -For those who want to see the comparison at one view, +For those with good eyesight, Table~\ref{tab:future:Comparison of Locking (Plain and Augmented) and HTM} -shows the merged comparison. +combines +Tables~\ref{tab:future:Comparison of Locking and HTM} +and~\ref{tab:future:Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM}. Of course, it is also possible to augment HTM, as discussed in the next section. ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH 0/2] future: Update Locking and HTM comparison tables 2017-12-06 16:11 ` [PATCH 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney @ 2017-12-06 22:16 ` Akira Yokosawa 0 siblings, 0 replies; 9+ messages in thread From: Akira Yokosawa @ 2017-12-06 22:16 UTC (permalink / raw) To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa On 2017/12/06 08:11:59 -0800, Paul E. McKenney wrote: > On Thu, Dec 07, 2017 at 12:00:02AM +0900, Akira Yokosawa wrote: >> >From d6497dadbc973d7d94591f48730c4c0ce1c129a8 Mon Sep 17 00:00:00 2001 >> From: Akira Yokosawa <akiyks@gmail.com> >> Date: Wed, 6 Dec 2017 23:40:04 +0900 >> Subject: [PATCH 0/2] future: Update Locking and HTM comparison tables >> >> Hi Paul, >> >> I have tackled the remaining two tables of old style in Section 17.3. >> "Advantage", "Disadvantage", and "Strong Disadvantage" can be indicated >> by background colors, and their structures can be simplified. >> This scheme is inspired by Table 12.4, with using lower saturation >> colors. >> >> Patch #1 modifies the tables. >> Patch #2 adds a merged table of the two as a sidewaystable. >> >> Background colors are chosen so that they can be distinguished >> when they are printed in grayscale. >> >> Thoughts? > > Very nice!!! I very much like the use of colors instead of symbols, > and I say that as someone who is red-green colorblind. ;-) > > I queued both commits and added the commit below. If you are OK with > the below change, I will push all three. If not, please let me know > what needs to change. Sounds nice! Such a casual expression never occurs to me. Acked-by: Akira Yokosawa <akiyks@gmail.com> But I found another typo in the table. (Privitization) I'm sending v2 of the patch set containing the fix. Please apply it instead. Thanks, Akira > > Thanx, Paul > > ------------------------------------------------------------------------ > > commit 76dacd546e9e1ad1153ef5b3ef6ad0dfd9985246 > Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com> > Date: Wed Dec 6 08:07:10 2017 -0800 > > future/htm: Reword sentence referencing the new Table 17.3 > > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com> > > diff --git a/future/htm.tex b/future/htm.tex > index 6667cd0ce8f0..908166bc0768 100644 > --- a/future/htm.tex > +++ b/future/htm.tex > @@ -920,9 +920,11 @@ A summary of the differences between the two tables is as follows: > > \input{future/HTMtableFull} > > -For those who want to see the comparison at one view, > +For those with good eyesight, > Table~\ref{tab:future:Comparison of Locking (Plain and Augmented) and HTM} > -shows the merged comparison. > +combines > +Tables~\ref{tab:future:Comparison of Locking and HTM} > +and~\ref{tab:future:Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM}. > > Of course, it is also possible to augment HTM, > as discussed in the next section. > > ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH v2 0/2] future: Update Locking and HTM comparison tables 2017-12-06 15:00 [PATCH 0/2] future: Update Locking and HTM comparison tables Akira Yokosawa ` (2 preceding siblings ...) 2017-12-06 16:11 ` [PATCH 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney @ 2017-12-06 22:19 ` Akira Yokosawa 2017-12-06 22:20 ` [PATCH v2 1/2] " Akira Yokosawa ` (2 more replies) 3 siblings, 3 replies; 9+ messages in thread From: Akira Yokosawa @ 2017-12-06 22:19 UTC (permalink / raw) To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa From 0525a99211ea5bce67be8f5137c4abde142d8e8e Mon Sep 17 00:00:00 2001 From: Akira Yokosawa <akiyks@gmail.com> Date: Thu, 7 Dec 2017 07:05:32 +0900 Subject: [PATCH v2 0/2] future: Update Locking and HTM comparison tables Hi Paul, I found another typo in HTMtableRCU.tex. This is a respin including the fix. Please apply this set instead. Change since v1: Fix typo (Privitization -> Privatization) Thanks, Akira -- Akira Yokosawa (2): future: Update Locking and HTM comparison tables future: Add merged table of locking & HTM comparison appendix/styleguide/styleguide.tex | 6 - future/HTMtable.tex | 201 ++++++++++++++--------------- future/HTMtableColor.tex | 9 ++ future/HTMtableFull.tex | 148 +++++++++++++++++++++ future/HTMtableRCU.tex | 254 +++++++++++++++++-------------------- future/htm.tex | 6 + perfbook.tex | 1 + 7 files changed, 370 insertions(+), 255 deletions(-) create mode 100644 future/HTMtableColor.tex create mode 100644 future/HTMtableFull.tex -- 2.7.4 ^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH v2 1/2] future: Update Locking and HTM comparison tables 2017-12-06 22:19 ` [PATCH v2 " Akira Yokosawa @ 2017-12-06 22:20 ` Akira Yokosawa 2017-12-06 22:22 ` [PATCH v2 2/2] future: Add merged table of locking & HTM comparison Akira Yokosawa 2017-12-06 22:54 ` [PATCH v2 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney 2 siblings, 0 replies; 9+ messages in thread From: Akira Yokosawa @ 2017-12-06 22:20 UTC (permalink / raw) To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa From 54dfd3f357164a1d170943284e3ed2486d8841e2 Mon Sep 17 00:00:00 2001 From: Akira Yokosawa <akiyks@gmail.com> Date: Wed, 6 Dec 2017 23:38:01 +0900 Subject: [PATCH v2 1/2] future: Update Locking and HTM comparison tables By using background colors to indicate Advantage/Disadvantage, these tables can be simplified. As with other tables, rules of "booktabs" are used. Skips between rows are controlled by using \midrule, \cmidrule, and \addlinespace. In order to put HTMtableRCU.tex within a size of A4 paper, baseline skip is slightly reduced locally by \setstretch command (provided by "setspace" package) and the overall table is further reduced by \resizebox. Background colors are defined in a separate file HTMtableColor.tex for ease of color tuning. Colors used at the moment are chosen so that they can be distinguished when printed in grayscale. Color names "plus", "minus", "down" reflect the symbols used before this change. To place gaps between columns, extra columns are added and \tabcolsep is narrowed. Also fix a couple of typo (partionable -> partitionable, partioning -> partitioning, privitization -> privatization). Signed-off-by: Akira Yokosawa <akiyks@gmail.com> --- appendix/styleguide/styleguide.tex | 6 - future/HTMtable.tex | 201 ++++++++++++++--------------- future/HTMtableColor.tex | 9 ++ future/HTMtableRCU.tex | 254 +++++++++++++++++-------------------- perfbook.tex | 1 + 5 files changed, 216 insertions(+), 255 deletions(-) create mode 100644 future/HTMtableColor.tex diff --git a/appendix/styleguide/styleguide.tex b/appendix/styleguide/styleguide.tex index 11f539b..0337fbb 100644 --- a/appendix/styleguide/styleguide.tex +++ b/appendix/styleguide/styleguide.tex @@ -797,12 +797,6 @@ IBM~Q & $0.015$ \label{tab:app:styleguide:Refrigeration Power Consumption} \end{table} -Most tables in the text have been converted to this format. -Tables~\ref{tab:future:Comparison of Locking and HTM} -and~\ref{tab:future:Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM} -are the exceptions. They are complex and require an alternative -approach.\footnote{Any suggestion is welcome!!!} - \subsubsection{Position of Caption} \label{sec:app:styleguide:Position of Caption} diff --git a/future/HTMtable.tex b/future/HTMtable.tex index d317f94..31d4802 100644 --- a/future/HTMtable.tex +++ b/future/HTMtable.tex @@ -4,114 +4,97 @@ \begin{table*}[p] \centering % \scriptsize -\small\OneColumnHSpace{-.8in} -\begin{tabular}{p{1.0in}||c|p{2.0in}||c|p{2.0in}} -& \multicolumn{2}{c||}{Locking} & \multicolumn{2}{c}{Hardware Transactional Memory} \\ -\hline -\hline -Basic Idea - & \multicolumn{2}{p{2.2in}||}{ - Allow only one thread at a time to access a given set of objects.} - & \multicolumn{2}{p{2.2in}}{ - Cause a given operation over a set of objects to execute - atomically.} \\ -\hline -\hline -Scope - & $+$ - & Handles all operations. - & $+$ - & Handles revocable operations. \\ -\cline{4-5} - & & - & $-$ - & Irrevocable operations force fallback (typically - to locking). \\ -\hline -Composability - & $\Downarrow$ - & Limited by deadlock. - & $\Downarrow$ - & Limited by irrevocable operations, transaction size, - and deadlock (assuming lock-based fallback code). \\ -\hline -Scalability \& Performance - & $-$ - & Data must be partitionable to avoid lock contention. - & $-$ - & Data must be partionable to avoid conflicts. \\ -\cline{2-5} - & $\Downarrow$ - & Partioning must typically be fixed at design time. - & $+$ - & Dynamic adjustment of partitioning carried out - automatically down to cacheline boundaries. \\ -\cline{4-5} - & - & - & $-$ - & Partitioning required for fallbacks (less important - for rare fallbacks). \\ -\cline{2-5} - & $\Downarrow$ - & Locking primitives typically result in expensive cache misses - and memory-barrier instructions. - & $-$ - & Transactions begin/end instructions typically do not - result in cache misses, but do have memory-ordering - consequences. \\ -\cline{2-5} - & $+$ - & Contention effects are focused on acquisition and release, so - that the critical section runs at full speed. - & $-$ - & Contention aborts conflicting transactions, even - if they have been running for a long time. \\ -\cline{2-5} - & $+$ - & Privatization operations are simple, intuitive, performant, - and scalable. - & $-$ - & Privatized data contributes to transaction size. \\ -\hline -Hardware Support - & $+$ - & Commodity hardware suffices. - & $-$ - & New hardware required (and is starting to become - available). \\ -\cline{2-5} - & $+$ - & Performance is insensitive to cache-geometry details. - & $-$ - & Performance depends critically on cache geometry. \\ -\hline -Software Support - & $+$ - & APIs exist, large body of code and experience, debuggers operate - naturally. - & $-$ - & APIs emerging, little experience outside of DBMS, - breakpoints mid-transaction can be problematic. \\ -\hline -Interaction With Other Mechanisms - & $+$ - & Long experience of successful interaction. - & $\Downarrow$ - & Just beginning investigation of interaction. \\ -\hline -Practical Apps - & $+$ - & Yes. - & $+$ - & Yes. \\ -\hline -Wide Applicability - & $+$ - & Yes. - & $-$ - & Jury still out, but likely to win significant use. \\ -\end{tabular} -\caption{Comparison of Locking and HTM (``$+$'' is Advantage, ``$-$'' is Disadvantage, ``$\Downarrow$'' is Strong Disadvantage)} +\small +\input{future/HTMtableColor} +\setlength{\tabcolsep}{4pt}\OneColumnHSpace{-.9in} +\begin{tabularx}{6.5in}{p{0.95in}cXcX} +\toprule + & + & \multicolumn{1}{c}{Locking} & + & \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 & + & \Dw Limited by deadlock. & + & \Dw Limited by irrevocable operations, transaction size, + and deadlock (assuming lock-based fallback code). \\ +\midrule + Scalability \& Performance & + & \Mn Data must be partitionable to avoid lock contention. & + & \Mn Data must be partitionable to avoid conflicts. \\ +\cmidrule{3-5} + & + & \Dw Partioning must typically be fixed at design time. & + & \Pl Dynamic adjustment of partitioning carried out automatically down + to cacheline boundaries. \\ +\addlinespace[4pt] + & + & & + & \Mn Partitioning required for fallbacks (less important for rare + fallbacks). \\ +\cmidrule{3-5} + & + & \Dw 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 consequences. \\ +\cmidrule{3-5} + & + & \Pl 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. \\ +\cmidrule{3-5} + & + & \Pl Privatization operations are simple, intuitive, performant, + and scalable. & + & \Mn Privatized data contributes to transaction size. \\ +\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, but likely to win significant use. \\ +\bottomrule +\end{tabularx} +\IfTwoColumn{ +\caption{Comparison of Locking and HTM (\colorbox{plus}{Advantage}, + \colorbox{minus}{Disadvantage}, \colorbox{down}{Strong Disadvantage})} +}{ +\caption{Comparison of Locking and HTM (\colorbox{plus}{Advantage}, + \colorbox{minus}{Disadvantage}, + \colorbox{down}{Strong} \colorbox{down}{Disadvantage})} +} \label{tab:future:Comparison of Locking and HTM} \end{table*} diff --git a/future/HTMtableColor.tex b/future/HTMtableColor.tex new file mode 100644 index 0000000..94a7c2f --- /dev/null +++ b/future/HTMtableColor.tex @@ -0,0 +1,9 @@ +% future/HTMtableColor.tex +% SPDX-License-Identifier: CC-BY-SA-3.0 + +\definecolor{plus}{cmyk}{0.1,0,0,0} +\definecolor{minus}{cmyk}{0,0.05,0.2,0.05} +\definecolor{down}{cmyk}{0,0.15,0.15,0.1} +\newcommand{\Pl}{\cellcolor{plus}} +\newcommand{\Mn}{\cellcolor{minus}} +\newcommand{\Dw}{\cellcolor{down}} diff --git a/future/HTMtableRCU.tex b/future/HTMtableRCU.tex index 4c51fa3..2d25502 100644 --- a/future/HTMtableRCU.tex +++ b/future/HTMtableRCU.tex @@ -3,145 +3,119 @@ \begin{table*}[p] \centering -\small\OneColumnHSpace{-.8in} -%\raggedright -\begin{tabular}{p{1.0in}||c|p{2.0in}||c|p{2.0in}} -& \multicolumn{2}{c||}{Locking with Userspace RCU or Hazard Pointers} & \multicolumn{2}{c}{Hardware Transactional Memory} \\ -\hline -\hline -Basic Idea - & \multicolumn{2}{p{2.2in}||}{ - Allow only one thread at a time to access a given set of objects.} - & \multicolumn{2}{p{2.2in}}{ - Cause a given operation over a set of objects to execute - atomically.} \\ -\hline -\hline -Scope - & $+$ - & Handles all operations. - & $+$ - & Handles revocable operations. \\ -\cline{4-5} - & & - & $-$ - & Irrevocable operations force fallback (typically - to locking). \\ -\hline -Composability - & $+$ - & Readers limited only by grace-period-wait operations. - & $\Downarrow$ - & Limited by irrevocable operations, transaction size, - and deadlock. \\ -\cline{2-3} - & $-$ - & Updaters limited by deadlock. Readers reduce deadlock. - & - & (Assuming lock-based fallback code.) \\ -\hline -Scalability \& Performance - & $-$ - & Data must be partitionable to avoid lock contention among - updaters. - & $-$ - & Data must be partionable to avoid conflicts. \\ -\cline{2-3} - & $+$ - & Partitioning not needed for readers. - & - & \\ -\cline{2-5} - & $\Downarrow$ - & Partioning for updaters must typically be fixed at design time. - & $+$ - & Dynamic adjustment of partitioning carried out - automatically down to cacheline boundaries. \\ -\cline{2-5} - & $+$ - & Partitioning not needed for readers. - & $-$ - & Partitioning required for fallbacks (less important - for rare fallbacks). \\ -\cline{2-5} - & $\Downarrow$ - & Updater locking primitives typically result in expensive cache - misses and memory-barrier instructions. - & $-$ - & Transactions begin/end instructions typically do not - result in cache misses, but do have memory-ordering - consequences. \\ -\cline{2-5} - & $+$ - & Update-side contention effects are focused on acquisition and - release, so that the critical section runs at full speed. - & $-$ - & Contention aborts conflicting transactions, even - if they have been running for a long time. \\ -\cline{2-3} - & $+$ - & Readers do not contend with updaters or with each other. - & - & \\ -\cline{2-5} - & $+$ - & Read-side primitives are typically wait-free with low - overhead. (Lock-free for hazard pointers.) - & $-$ - & Read-only transactions subject to conflicts and rollbacks. - No forward-progress guarantees other than those supplied - by fallback code. \\ -\cline{2-5} - & $+$ - & Privatization operations are simple, intuitive, performant, - and scalable when data is visible only to updaters. - & $-$ - & Privatized data contributes to transaction size. \\ -\cline{2-3} - & $-$ - & Privitization operations are expensive (though still intuitive - and scalable) for reader-visible data. - & - & \\ -\hline -Hardware Support - & $+$ - & Commodity hardware suffices. - & $-$ - & New hardware required (and is starting to become - available). \\ -\cline{2-5} - & $+$ - & Performance is insensitive to cache-geometry details. - & $-$ - & Performance depends critically on cache geometry. \\ -\hline -Software Support - & $+$ - & APIs exist, large body of code and experience, debuggers operate - naturally. - & $-$ - & APIs emerging, little experience outside of DBMS, - breakpoints mid-transaction can be problematic. \\ -\hline -Interaction With Other Mechanisms - & $+$ - & Long experience of successful interaction. - & $\Downarrow$ - & Just beginning investigation of interaction. \\ -\hline -Practical Apps - & $+$ - & Yes. - & $+$ - & Yes. \\ -\hline -Wide Applicability - & $+$ - & Yes. - & $-$ - & Jury still out, but likely to win significant use. \\ -\end{tabular} -\caption{Comparison of Locking (Augmented by RCU or Hazard Pointers) and HTM (``$+$'' is Advantage, ``$-$'' is Disadvantage, ``$\Downarrow$'' is Strong Disadvantage)} +\small +\input{future/HTMtableColor} +\setstretch{0.95} +\setlength{\tabcolsep}{4pt}\OneColumnHSpace{-.9in} +\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 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 wait-free with low overhead. + (Lock-free 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, but likely to win significant use. \\ +\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*} diff --git a/perfbook.tex b/perfbook.tex index 32f0e6d..e4bba02 100644 --- a/perfbook.tex +++ b/perfbook.tex @@ -31,6 +31,7 @@ % \usepackage{breakurl} \usepackage{graphicx} \usepackage{rotating} +\usepackage{setspace} \usepackage{enumitem} \setlist[description]{style=unboxed} %\usepackage{enumerate} -- 2.7.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH v2 2/2] future: Add merged table of locking & HTM comparison 2017-12-06 22:19 ` [PATCH v2 " Akira Yokosawa 2017-12-06 22:20 ` [PATCH v2 1/2] " Akira Yokosawa @ 2017-12-06 22:22 ` Akira Yokosawa 2017-12-06 22:54 ` [PATCH v2 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney 2 siblings, 0 replies; 9+ messages in thread From: Akira Yokosawa @ 2017-12-06 22:22 UTC (permalink / raw) To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa From 0525a99211ea5bce67be8f5137c4abde142d8e8e Mon Sep 17 00:00:00 2001 From: Akira Yokosawa <akiyks@gmail.com> Date: Wed, 6 Dec 2017 23:38:41 +0900 Subject: [PATCH v2 2/2] future: Add merged table of locking & HTM comparison Tables of HTMtable.tex and HTMtableRCU.tex can be merged into a single large table in a "sidewaystable" environment. To reduce the height of the table, font size of footnotesize is used in addition to commands \setstretch{} and \resizebox{}. The additional paragraph in the text citing the table is tentative and need some rewording. Signed-off-by: Akira Yokosawa <akiyks@gmail.com> --- future/HTMtableFull.tex | 148 ++++++++++++++++++++++++++++++++++++++++++++++++ future/htm.tex | 6 ++ 2 files changed, 154 insertions(+) create mode 100644 future/HTMtableFull.tex diff --git a/future/HTMtableFull.tex b/future/HTMtableFull.tex new file mode 100644 index 0000000..5001497 --- /dev/null +++ b/future/HTMtableFull.tex @@ -0,0 +1,148 @@ +% future/HTMtableFull.tex +% SPDX-License-Identifier: CC-BY-SA-3.0 + +\begin{sidewaystable*}[htbp] +\input{future/HTMtableColor} +\centering +\caption{Comparison of Locking (Plain and Augmented) and HTM + (\colorbox{plus}{Advantage}, \colorbox{minus}{Disadvantage}, + \colorbox{down}{Strong Disadvantage})} +\label{tab:future:Comparison of Locking (Plain and Augmented) and HTM} +\footnotesize +\setstretch{0.95} +%\renewcommand*{\arraystretch}{1.4} +\setlength{\tabcolsep}{3pt} +\resizebox{8in}{!}{ +\begin{tabularx}{8.5in}{p{.85in}cXcXcX} +\toprule + & + & \multicolumn{1}{c}{Locking} & + & \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. & + & 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 all operations. & + & \Pl Handles revocable operations. \\ +\addlinespace[4pt] + & + & & + & & + & \Mn Irrevocable operations force fallback (typically to locking). \\ +\midrule + Composability & + & \Dw Limited by deadlock. & + & \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. & + & \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-7} + & + & \Dw Partitioning must typically be fixed at design time. & + & \Dw Partitioning for updaters must typically be fixed at design time. & + & \Pl Dynamic adjustment of partitioning carried out automatically + down to cacheline boundaries. \\ +\addlinespace[4pt] + & + & & + & \Pl Partitioning not needed for readers. & + & \Mn Partitioning required for fallbacks (less important for rare + fallbacks). \\ +\cmidrule{3-7} + & + & \Dw Locking primitives typically result in expensive cache misses and + memory-barrier instructions.& + & \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 consequences. \\ +\cmidrule{3-7} + & + & \Pl Contention effects are focused on acquisition and release, so that + the critical section runs at full speed. & + & \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-7} + & + & & + & \Pl Read-side primitives are typically wait-free with low overhead. + (Lock-free 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-7} + & + & \Pl Privatization operations are simple, intuitive, performant, + and scalable. & + & \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. & + & \Pl Commodity hardware suffices. & + & \Mn New hardware required (and is starting to become available). \\ +\cmidrule{3-7} + & + & \Pl Performance is insensitive to cache-geometry details. & + & \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. & + & \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. & + & \Pl Long experience of successful interaction. & + & \Dw Just beginning investigation of interaction. \\ +\midrule + Practical Apps & + & \Pl Yes. & + & \Pl Yes. & + & \Pl Yes. \\ +\midrule + Wide Applicability & + & \Pl Yes. & + & \Pl Yes. & + & \Mn Jury still out, but likely to win significant use. \\ +\bottomrule +\end{tabularx} +} +\end{sidewaystable*} diff --git a/future/htm.tex b/future/htm.tex index 7c9f610..6667cd0 100644 --- a/future/htm.tex +++ b/future/htm.tex @@ -918,6 +918,12 @@ A summary of the differences between the two tables is as follows: straightforward. \end{enumerate} +\input{future/HTMtableFull} + +For those who want to see the comparison at one view, +Table~\ref{tab:future:Comparison of Locking (Plain and Augmented) and HTM} +shows the merged comparison. + Of course, it is also possible to augment HTM, as discussed in the next section. -- 2.7.4 ^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [PATCH v2 0/2] future: Update Locking and HTM comparison tables 2017-12-06 22:19 ` [PATCH v2 " Akira Yokosawa 2017-12-06 22:20 ` [PATCH v2 1/2] " Akira Yokosawa 2017-12-06 22:22 ` [PATCH v2 2/2] future: Add merged table of locking & HTM comparison Akira Yokosawa @ 2017-12-06 22:54 ` Paul E. McKenney 2 siblings, 0 replies; 9+ messages in thread From: Paul E. McKenney @ 2017-12-06 22:54 UTC (permalink / raw) To: Akira Yokosawa; +Cc: perfbook On Thu, Dec 07, 2017 at 07:19:02AM +0900, Akira Yokosawa wrote: > >From 0525a99211ea5bce67be8f5137c4abde142d8e8e Mon Sep 17 00:00:00 2001 > From: Akira Yokosawa <akiyks@gmail.com> > Date: Thu, 7 Dec 2017 07:05:32 +0900 > Subject: [PATCH v2 0/2] future: Update Locking and HTM comparison tables > > Hi Paul, > > I found another typo in HTMtableRCU.tex. > This is a respin including the fix. > Please apply this set instead. > > Change since v1: > > Fix typo (Privitization -> Privatization) > > Thanks, Akira Ah, good catch! I queued and pushed your updated patches and my wording change, thank you! Thanx, Paul > -- > Akira Yokosawa (2): > future: Update Locking and HTM comparison tables > future: Add merged table of locking & HTM comparison > > appendix/styleguide/styleguide.tex | 6 - > future/HTMtable.tex | 201 ++++++++++++++--------------- > future/HTMtableColor.tex | 9 ++ > future/HTMtableFull.tex | 148 +++++++++++++++++++++ > future/HTMtableRCU.tex | 254 +++++++++++++++++-------------------- > future/htm.tex | 6 + > perfbook.tex | 1 + > 7 files changed, 370 insertions(+), 255 deletions(-) > create mode 100644 future/HTMtableColor.tex > create mode 100644 future/HTMtableFull.tex > > -- > 2.7.4 > > ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2017-12-06 22:54 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2017-12-06 15:00 [PATCH 0/2] future: Update Locking and HTM comparison tables Akira Yokosawa 2017-12-06 15:01 ` [PATCH 1/2] " Akira Yokosawa 2017-12-06 15:05 ` [PATCH 2/2] future: Add merged table of locking & HTM comparison Akira Yokosawa 2017-12-06 16:11 ` [PATCH 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney 2017-12-06 22:16 ` Akira Yokosawa 2017-12-06 22:19 ` [PATCH v2 " Akira Yokosawa 2017-12-06 22:20 ` [PATCH v2 1/2] " Akira Yokosawa 2017-12-06 22:22 ` [PATCH v2 2/2] future: Add merged table of locking & HTM comparison Akira Yokosawa 2017-12-06 22:54 ` [PATCH v2 0/2] future: Update Locking and HTM comparison tables Paul E. McKenney
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.