Update table layout
cover Update table layout
From d224db4bfed5d4ce0639062a920bafc6f9442e16 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:55:49 +0900
Subject: [PATCH 0/5] Update table layout
Hi Paul,
My first idea was to add a make target for "table captions at the top". But I changed my mind and promoted the layout as default. Instead, I added a target "perfbook-tcb.pdf" (tcb: Table Caption Bottom), which keeps the caption at the bottom.
Patch #1 does the change in perfbook.tex and Makefile.
Patches #2 and #3 are minor fixes I noticed while updating tables.
Patch #4 updates most tables to use the new table layout experimented in Style Guide for a while. It contains changes to use "S" column specifier provided by the "siunitx" package.
Patch #5 converts a table into a figure drawn by tabular.
There remains several tables not yet touched. They are complex and large ones. They need extra work to use the new scheme.
NOTE: Table 13.1 does not contain legends and does not use subscripts as shown in Table D.5 at the moment. In the text, it looks OK to me.
Thoughts?
Thanks, Akira
--
Akira Yokosawa (5):
Move caption of table to top
Define \twocolumnwidth for 1c layout
Use \O{} macro for 'order-of'
Update tables using booktabs and alternate-row coloring scheme
datastruct: Convert 'NUMA Topology of System Under Test' to figure
Makefile | 6 ++- SMPdesign/SMPdesign.tex | 10 +++-- advsync/rt.tex | 8 ++-- appendix/questions/after.tex | 25 +++++++++---- appendix/styleguide/styleguide.tex | 20 ++++++---- count/count.tex | 54 ++++++++++++++++----------- cpu/overheads.tex | 76 +++++++++++++++++--------------------- datastruct/datastruct.tex | 23 ++++++++---- defer/rcuapi.tex | 16 ++++---- defer/rcufundamental.tex | 16 ++++---- defer/rcuusage.tex | 10 +++-- defer/whichtochoose.tex | 27 +++++--------- formal/spinhint.tex | 68 +++++++++++++++++----------------- future/QC.tex | 75 +++++++++++++++++++------------------ memorder/memorder.tex | 8 ++-- perfbook.tex | 17 +++++++++ together/refcnt.tex | 25 +++++++------ 17 files changed, 266 insertions(+), 218 deletions(-)
Signature · 1 line
2.7.4
PATCH 1/5 Move caption of table to top
From a816ec3f6407f3de0b194dbf61498bca650ee818 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 20:18:54 +0900
Subject: [PATCH 1/5] Move caption of table to top
For those who prefer caption of tables at the bottom, add a make target "perfbook-tcb.pdf" (abbr. tcb: Table Caption Bottom).
Help message displayed by "make help" is updated accordingly.
--- Makefile | 6 +++++- appendix/styleguide/styleguide.tex | 6 ++++-- perfbook.tex | 12 ++++++++++++ 3 files changed, 21 insertions(+), 3 deletions(-)
Makefile +5 -1
@@ -10,7 +10,7 @@ LATEXSOURCES = \ LATEXGENERATED = autodate.tex qqz.tex contrib.tex origpub.tex -ABBREVTARGETS := 1c hb msns mss mstx msr msn msnt 1csf +ABBREVTARGETS := tcb 1c hb msns mss mstx msr msn msnt 1csf PDFTARGETS := perfbook.pdf $(foreach v,$(ABBREVTARGETS),perfbook-$(v).pdf)
@@ -101,6 +101,9 @@ contrib.tex: perfbook_flat.tex qqz.tex origpub.tex: perfbook_flat.tex sh utilities/extractorigpub.sh < $< > $@ +perfbook-tcb.tex: perfbook.tex + sed -e 's/{tblcptop}{true}/{tblcptop}{false}/' < $< > $@ + perfbook-1c.tex: perfbook.tex sed -e 's/,twocolumn//' -e 's/setboolean{twocolumn}{true}/setboolean{twocolumn}{false}/' < $< > $@
@@ -179,6 +182,7 @@ help: @echo "Official targets (Latin Modern Typewriter for monospace font):" @echo " Full, Abbr." @echo " perfbook.pdf, 2c: (default) 2-column layout" + @echo " perfbook-tcb, tct: 2-column layout with table caption at bottom" @echo " perfbook-1c.pdf, 1c: 1-column layout" @echo " perfbook-hb.pdf, hb: For hardcover books (2-column)" @echo
appendix/styleguide/styleguide.tex +4 -2
@@ -915,11 +915,12 @@ look ugly.\footnote{ Vertical lines should be avoided and horizontal lines should be used sparingly, especially in tables of simple structure. +\IfTblCpTop{}{ \floatstyle{plaintop} \restylefloat{table} -\captionsetup[table]{hangindent=30pt} \setlength{\abovetopsep}{-2pt} \addtolength{\abovecaptionskip}{-2.5pt} +} For example, Table~\ref{tab:future:Refrigeration Power Consumption}
@@ -1381,11 +1382,12 @@ have been recently converted to the scheme presented in this section. Refer to \path{memorder/memorder.tex} for examples of tables with complex headings. +\IfTblCpTop{}{ \floatstyle{plain} \restylefloat{table} -\captionsetup[table]{hangindent=0pt} \addtolength{\abovecaptionskip}{2.5pt} \setlength{\abovetopsep}{0pt} +} \subsubsection{Miscellaneous Candidates} \label{sec:app:styleguide:Miscellaneous Candidates}
perfbook.tex +12 -0
@@ -79,6 +79,9 @@ \newboolean{lmttforcode} \setboolean{lmttforcode}{true} \newcommand{\IfLmttForCode}[2]{\ifthenelse{\boolean{lmttforcode}}{#1}{#2}} +\newboolean{tblcptop} +\setboolean{tblcptop}{true} +\newcommand{\IfTblCpTop}[2]{\ifthenelse{\boolean{tblcptop}}{#1}{#2}} \newcommand{\OneColumnHSpace}[1]{\IfTwoColumn{}{\hspace*{#1}}}
@@ -107,6 +110,15 @@ \AtBeginEnvironment{listing}{\renewcommand{\ttdefault}{lmtt}} }{} +\IfTblCpTop{ +\floatstyle{plaintop} +\restylefloat{table} +\addtolength{\abovecaptionskip}{-2.5pt} +\setlength{\abovetopsep}{-2pt} +}{} +\captionsetup{hangindent=20pt} +\captionsetup[listing]{hangindent=20pt} + \begin{document} %%HTMLSKIP
Signature · 1 line
2.7.4
PATCH 2/5 Define \twocolumnwidth for 1c layout
In reply to Akira YokosawaFrom d04822df9b8f292309ca6b176a8e1c37da84eb11 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 20:25:28 +0900
Subject: [PATCH 2/5] Define \twocolumnwidth for 1c layout
Using \columnwidth in \resizebox{} and tabularx environment causes several figures and a table to be too wide in 1c layout. By defining and using a length \twocolumnwidth for both 2c and 1c layouts, the problem can be avoided.
--- SMPdesign/SMPdesign.tex | 2 +- memorder/memorder.tex | 8 ++++---- perfbook.tex | 4 ++++ 3 files changed, 9 insertions(+), 5 deletions(-)
SMPdesign/SMPdesign.tex +1 -1
@@ -1350,7 +1350,7 @@ Table~\ref{fig:app:questions:Schematic of Real-World Parallel Allocator}. \centering \renewcommand*{\arraystretch}{1.25} \setlength\tabcolsep{4pt} -\begin{tabularx}{\columnwidth}{l|l|>{\raggedright\arraybackslash}X} +\begin{tabularx}{\twocolumnwidth}{l|l|>{\raggedright\arraybackslash}X} Level & Locking & Purpose \\ \hline Per-thread pool & Data ownership & High-speed allocation \\
memorder/memorder.tex +4 -4
@@ -2315,7 +2315,7 @@ exists (1:r2=0 /\ x1=2) \begin{figure}[htbp] \centering -\resizebox{\columnwidth}{!}{\includegraphics{memorder/fr}} +\resizebox{\twocolumnwidth}{!}{\includegraphics{memorder/fr}} \caption{Load-to-Store is Counter-Temporal} \label{fig:memorder:Load-to-Store is Counter-Temporal} \end{figure}
@@ -2439,7 +2439,7 @@ Listing~\ref{lst:memorder:W+WRC Litmus Test With More Barriers} \begin{figure}[tbp] \centering -\resizebox{\columnwidth}{!}{\includegraphics{memorder/co}} +\resizebox{\twocolumnwidth}{!}{\includegraphics{memorder/co}} \caption{Store-to-Store is Counter-Temporal} \label{fig:memorder:Store-to-Store is Counter-Temporal} \end{figure}
@@ -2458,7 +2458,7 @@ But sometimes time is on our side, as shown in the next section. \begin{figure}[tbp] \centering -\resizebox{\columnwidth}{!}{\includegraphics{memorder/rf}} +\resizebox{\twocolumnwidth}{!}{\includegraphics{memorder/rf}} \caption{Store-to-Load is Temporal} \label{fig:memorder:Store-to-Load is Temporal} \end{figure}
@@ -4111,7 +4111,7 @@ in Alpha's heyday. \begin{figure}[tbp] \centering -\resizebox{\columnwidth}{!}{\includegraphics{memorder/Alpha}} +\resizebox{\twocolumnwidth}{!}{\includegraphics{memorder/Alpha}} \caption{Why \tco{smp_read_barrier_depends()} is Required} \label{fig:memorder:Why smp-read-barrier-depends() is Required} \end{figure}
perfbook.tex +4 -0
@@ -119,6 +119,7 @@ \captionsetup{hangindent=20pt} \captionsetup[listing]{hangindent=20pt} + \begin{document} %%HTMLSKIP
@@ -193,15 +194,18 @@ \renewcommand\dbltopfraction{.75} \renewcommand\dblfloatpagefraction{.5} +\newlength{\twocolumnwidth} \IfTwoColumn{ \setlength{\textheight}{8.25in} \setlength{\textwidth}{6.5in} \setlength{\columnsep}{0.25in} +\setlength{\twocolumnwidth}{\columnwidth} \renewcommand\floatpagefraction{.75} }{ \setlength{\textheight}{8.25in} \setlength{\textwidth}{4.75in} \setlength{\columnsep}{0in} +\setlength{\twocolumnwidth}{3.125in} \addtolength{\oddsidemargin}{0.3in} \addtolength{\evensidemargin}{-0.3in} }
Signature · 1 line
2.7.4
PATCH 3/5 Use \O{} macro for 'order-of'
In reply to Akira YokosawaFrom e63ddb2e13bb0467de8ad00a767c35a5c75e6cc6 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 20:40:59 +0900
Subject: [PATCH 3/5] Use \O{} macro for 'order-of'
This macro was defined in commit b4ad25eae241 ("future/QC: Use upright glyph for math constant and descriptive suffix"). Use the same macro in other cases for consistency.
--- advsync/rt.tex | 8 ++++---- count/count.tex | 4 ++-- datastruct/datastruct.tex | 2 +- 3 files changed, 7 insertions(+), 7 deletions(-)
advsync/rt.tex +4 -4
@@ -843,7 +843,7 @@ timed delays (as in \co{sleep(1)}, which are rarely cancelled), and timeouts for the \co{poll()} system call (which are often cancelled before they have a chance to fire). A good data structure for such timers would therefore be a priority queue -whose addition and deletion primitives were fast and $O(1)$ in the number +whose addition and deletion primitives were fast and $\O{1}$ in the number of timers posted. The classic data structure for this purpose is the \emph{calendar queue},
@@ -897,7 +897,7 @@ which, taken together, is much smaller than the 256-element array that would be required for a single array. This approach works extremely well for throughput-based systems. -Each timer operation is $O(1)$ with small constant, and each timer +Each timer operation is $\O{1}$ with small constant, and each timer element is touched at most $m+1$ times, where $m$ is the number of levels.
@@ -949,7 +949,7 @@ degradations of latency in real-time systems. Of course, real-time systems could simply choose a different data structure, for example, some form of heap or tree, giving up -$O(1)$ bounds on insertion and deletion operations to gain $O(\log n)$ +$\O{1}$ bounds on insertion and deletion operations to gain $\O{\log n}$ limits on data-structure-maintenance operations. This can be a good choice for special-purpose RTOSes, but is inefficient for general-purpose systems such as Linux, which routinely support
@@ -964,7 +964,7 @@ is good and sufficient. Another key observation is that error-handling timeouts are normally cancelled very early, often before they can be cascaded. A final observation is that systems commonly have many more error-handling -timeouts than they do timer events, so that an $O(\log n)$ +timeouts than they do timer events, so that an $\O{\log n}$ data structure should provide acceptable performance for timer events. In short, the Linux kernel's -rt patchset uses timer wheels for
count/count.tex +2 -2
@@ -414,13 +414,13 @@ avoids the delays inherent in such circulation. The hardware could also apply an order to the requests, thus returning to each CPU the return value corresponding to its particular atomic increment. - This results in instruction latency that varies as $O(\log N)$, + This results in instruction latency that varies as $\O{\log N}$, where $N$ is the number of CPUs, as shown in Figure~\ref{fig:count:Data Flow For Global Combining-Tree Atomic Increment}. And CPUs with this sort of hardware optimization are starting to appear as of 2011. - This is a great improvement over the $O(N)$ performance + This is a great improvement over the $\O{N}$ performance of current hardware shown in Figure~\ref{fig:count:Data Flow For Global Atomic Increment}, and it is possible that hardware latencies might decrease
datastruct/datastruct.tex +1 -1
@@ -1800,7 +1800,7 @@ a resize operation. It turns out that it is possible to reduce the per-element memory overhead from a pair of pointers to a single pointer, while still retaining -$O(1)$ deletions. +$\O{1}$ deletions. This is accomplished by augmenting split-order list~\cite{OriShalev2006SplitOrderListHash} with RCU
Signature · 1 line
2.7.4
PATCH 4/5 Update tables using booktabs and alternate-row coloring scheme
In reply to Akira YokosawaFrom d60ffad87aa1fdbd34e224437e4275c672cb3be1 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 22:59:35 +0900
Subject: [PATCH 4/5] Update tables using booktabs and alternate-row coloring scheme
Note: Some of complex or large tables have not touched yet.
--- SMPdesign/SMPdesign.tex | 10 +++-- appendix/questions/after.tex | 25 +++++++++---- appendix/styleguide/styleguide.tex | 14 ++++--- count/count.tex | 50 +++++++++++++++---------- cpu/overheads.tex | 76 +++++++++++++++++--------------------- defer/rcuapi.tex | 16 ++++---- defer/rcufundamental.tex | 16 ++++---- defer/rcuusage.tex | 10 +++-- defer/whichtochoose.tex | 27 +++++--------- formal/spinhint.tex | 68 +++++++++++++++++----------------- future/QC.tex | 75 +++++++++++++++++++------------------ perfbook.tex | 1 + together/refcnt.tex | 25 +++++++------ 13 files changed, 215 insertions(+), 198 deletions(-)
SMPdesign/SMPdesign.tex +6 -4
@@ -1346,17 +1346,19 @@ as shown in Table~\ref{fig:app:questions:Schematic of Real-World Parallel Allocator}. \begin{table}[tbp] -\footnotesize +\rowcolors{1}{}{lightgray} +\small \centering \renewcommand*{\arraystretch}{1.25} -\setlength\tabcolsep{4pt} -\begin{tabularx}{\twocolumnwidth}{l|l|>{\raggedright\arraybackslash}X} +\begin{tabularx}{\twocolumnwidth}{ll>{\raggedright\arraybackslash}X} +\toprule Level & Locking & Purpose \\ -\hline +\midrule Per-thread pool & Data ownership & High-speed allocation \\ Global block pool & Data locking & Distributing blocks among threads \\ Coalescing & Data locking & Combining blocks into pages \\ System memory & Code locking & Memory from/to system \\ +\bottomrule \end{tabularx} \caption{Schematic of Real-World Parallel Allocator} \label{fig:app:questions:Schematic of Real-World Parallel Allocator}
appendix/questions/after.tex +17 -8
@@ -138,11 +138,15 @@ columns labelled ``a'', ``b'', and ``c'' show the amount that these variables increased since the prior snapshot collected by the consumer. \begin{table}[htbp] +\rowcolors{1}{}{lightgray} +\renewcommand*{\arraystretch}{1.2} +\sisetup{group-digits=false} \centering \scriptsize -\begin{tabular}{rcrrrr} -seq & time (seconds) & delta~ & a & b & c \\ -\hline +\begin{tabular}{rS[table-format=7.6]rS[table-format=3.0]S[table-format=3.0]S[table-format=3.0]} +\toprule +seq & \multicolumn{1}{c}{time (seconds)} & delta~ & a & b & c \\ +\midrule 17563: & 1152396.251585 & ($-16.928$) & 27 & 27 & 27 \\ 18004: & 1152396.252581 & ($-12.875$) & 24 & 24 & 24 \\ 18163: & 1152396.252955 & ($-19.073$) & 18 & 18 & 18 \\
@@ -150,6 +154,7 @@ seq & time (seconds) & delta~ & a & b & c \\ 19863: & 1152396.256960 & ($-6.914$) & 18 & 18 & 18 \\ 21644: & 1152396.260959 & ($-5.960$) & 18 & 18 & 18 \\ 23408: & 1152396.264957 & ($-20.027$) & 15 & 15 & 15 \\ +\bottomrule \end{tabular} \caption{``After'' Program Sample Output} \label{tab:app:questions:After Program Sample Output}
@@ -219,13 +224,17 @@ there are only cases with more than 1,000 counts difference between consecutive reads by the consumer. \begin{table}[htbp] +\renewcommand*{\arraystretch}{1.2} +\sisetup{group-digits=false} \centering \scriptsize -\begin{tabular}{rcrrrr} -seq & time (seconds) & delta~ & a & b & c \\ -\hline -58597: & 1156521.556296 & (3.815) & 1485 & 1485 & 1485 \\ -403927: & 1156523.446636 & (2.146) & 2583 & 2583 & 2583 \\ +\begin{tabular}{rS[table-format=7.6]rS[table-format=4.0]S[table-format=4.0]S[table-format=4.0]} +\toprule +seq & \multicolumn{1}{c}{time (seconds)} & delta~ & a & b & c \\ +\midrule +58597: & 1156521.556296 & ($3.815$) & 1485 & 1485 & 1485 \\ +403927: & 1156523.446636 & ($2.146$) & 2583 & 2583 & 2583 \\ +\bottomrule \end{tabular} \caption{Locked ``After'' Program Sample Output} \label{fig:app:questions:Locked After Program Sample Output}
appendix/styleguide/styleguide.tex +9 -5
@@ -268,14 +268,18 @@ Table~\ref{tab:app:styleguide:Digit-Grouping Style}. \begin{tabular}{lrrr}\toprule Style & \multicolumn{3}{c}{Outputs of \co{\\num\{\}}} \\ \midrule - NIST/SI (English) & \num{\NumDigitGrpA} & \num{\NumDigitGrpB} & \num{\NumDigitGrp} \\ - SI (French) & \num[locale=FR]{\NumDigitGrpA} & - \num[locale=FR]{\NumDigitGrpB} & \num[locale=FR]{\NumDigitGrp} \\ + NIST/SI (English) & \num[group-separator={\,},group-digits=integer]{\NumDigitGrpA} & + \num[group-separator={\,},group-digits=integer]{\NumDigitGrpB} & + \num[group-separator={\,},group-digits=integer]{\NumDigitGrp} \\ + SI (French) & \num[locale=FR,group-separator={\,}]{\NumDigitGrpA} & + \num[locale=FR,group-separator={\,}]{\NumDigitGrpB} & + \num[locale=FR,group-separator={\,}]{\NumDigitGrp} \\ English & \num[group-separator={,},group-digits=integer]{\NumDigitGrpA} & \num[group-separator={,},group-digits=integer]{\NumDigitGrpB} & \num[group-separator={,},group-digits=integer]{\NumDigitGrp} \\ - French & \num[locale=FR]{\NumDigitGrpA} & - \num[locale=FR]{\NumDigitGrpB} & \num[locale=FR]{\NumDigitGrp} \\ + French & \num[locale=FR,group-separator={\,}]{\NumDigitGrpA} & + \num[locale=FR,group-separator={\,}]{\NumDigitGrpB} & + \num[locale=FR,group-separator={\,}]{\NumDigitGrp} \\ Other Europe & \num[group-separator={.},output-decimal-marker={,},group-digits=integer]{\NumDigitGrpA} & \num[group-separator={.},output-decimal-marker={,},group-digits=integer]{\NumDigitGrpB} & \num[group-separator={.},output-decimal-marker={,},group-digits=integer]{\NumDigitGrp} \\
count/count.tex +30 -20
74 lines not on this page · raw message
cpu/overheads.tex +34 -42
104 lines not on this page · raw message
defer/rcuapi.tex +9 -7
@@ -460,20 +460,21 @@ the memory-ordering models of each of the 20+ CPU families that Linux supports~\cite{Spraul01}. \begin{table*}[tb] +\renewcommand*{\arraystretch}{1.15} \footnotesize \centering -\begin{tabular}{l|l|l|p{1.2in}} +\begin{tabular}{lllp{1.2in}} +\toprule Category & Primitives & Availability & Overhead \\ -\hline -\hline +\midrule List traversal & \tco{list_for_each_entry_rcu()} & 2.5.59 & Simple instructions (memory barrier on Alpha) \\ -\hline +\midrule List update & \tco{list_add_rcu()} & 2.5.44 &
@@ -494,7 +495,7 @@ List update & \tco{list_splice_init_rcu()} & 2.6.21 & Grace-period latency \\ -\hline +\midrule Hlist traversal & \tco{hlist_for_each_entry_rcu()} & 2.6.8 &
@@ -519,16 +520,17 @@ Hlist traversal & \tco{hlist_replace_rcu()} & 2.6.15 & Memory barrier \\ -\hline +\midrule Pointer traversal & \tco{rcu_dereference()} & 2.6.9 & Simple instructions (memory barrier on Alpha) \\ -\hline +\midrule Pointer update & \tco{rcu_assign_pointer()} & 2.6.10 & Memory barrier \\ +\bottomrule \end{tabular} \caption{RCU Publish-Subscribe and Version Maintenance APIs} \label{tab:defer:RCU Publish-Subscribe and Version Maintenance APIs}
defer/rcufundamental.tex +9 -7
@@ -380,30 +380,32 @@ circular list: \vspace{5pt} \begin{table*}[tb] +\renewcommand*{\arraystretch}{1.2} \centering -\scriptsize -\begin{tabular}{l||l|l|l} +\footnotesize +\begin{tabular}{llll} +\toprule Category & Publish & Retract & Subscribe \\ -\hline -\hline +\midrule Pointers & \tco{rcu_assign_pointer()} & \tco{rcu_assign_pointer(..., NULL)} & \tco{rcu_dereference()} \\ -\hline +\midrule Lists & \parbox[c][0.37in][c]{1.3in}{ \co{list_add_rcu()} \\ \co{list_add_tail_rcu()} \\ \co{list_replace_rcu()} } & \tco{list_del_rcu()} & \tco{list_for_each_entry_rcu()} \\ -\hline +\midrule Hlists & \parbox[c][0.5in][c]{1.3in}{ \co{hlist_add_after_rcu()} \\ \co{hlist_add_before_rcu()} \\ \co{hlist_add_head_rcu()} \\ \co{hlist_replace_rcu()} } & \tco{hlist_del_rcu()} - & \tco{hlist_for_each_entry_rcu()} + & \tco{hlist_for_each_entry_rcu()} \\ +\bottomrule \end{tabular} \caption{RCU Publish and Subscribe Primitives} \label{tab:defer:RCU Publish and Subscribe Primitives}
defer/rcuusage.tex +6 -4
@@ -5,12 +5,13 @@ \OriginallyPublished{Section}{sec:defer:RCU Usage}{RCU Usage}{Linux Weekly News}{PaulEMcKenney2008WhatIsRCUUsage} \begin{table}[tb] +\renewcommand*{\arraystretch}{1.2} \centering -\scriptsize -\begin{tabular}{l|l} +\small +\begin{tabular}{ll} +\toprule Mechanism RCU Replaces & Section \\ -\hline -\hline +\midrule Reader-writer locking & Section~\ref{sec:defer:RCU is a Reader-Writer Lock Replacement} \\ Restricted reference-counting mechanism &
@@ -25,6 +26,7 @@ Type-Safe Memory & Section~\ref{sec:defer:RCU is a Way of Providing Type-Safe Memory} \\ Wait for things to finish & Section~\ref{sec:defer:RCU is a Way of Waiting for Things to Finish} \\ +\bottomrule \end{tabular} \caption{RCU Usage} \label{tab:defer:RCU Usage}
defer/whichtochoose.tex +10 -17
@@ -5,88 +5,81 @@ \label{sec:defer:Which to Choose?} \begin{table*} +\rowcolors{1}{}{lightgray} +\renewcommand*{\arraystretch}{1.25} \footnotesize \centering\OneColumnHSpace{-.3in} -\begin{tabularx}{5.3in}{>{\raggedright\arraybackslash}p{1.1in}|| - >{\raggedright\arraybackslash}p{1.2in}| - >{\raggedright\arraybackslash}X| - >{\raggedright\arraybackslash}X| +\begin{tabularx}{5.3in}{>{\raggedright\arraybackslash}p{1.1in} + >{\raggedright\arraybackslash}p{1.2in} + >{\raggedright\arraybackslash}X + >{\raggedright\arraybackslash}X >{\raggedright\arraybackslash}p{.9in}} - + \toprule + Property & Reference Counting & Hazard Pointers & Sequence Locks & RCU \\ - \hline % RC HP SL RCU \\ - \hline + \midrule Existence Guarantees & Complex & Yes & No & Yes \\ - \hline Updates and Readers Progress Concurrently & Yes & Yes & No & Yes \\ - \hline Contention Among Readers & High & None & None & None \\ - \hline Reader Per\-/Critical\-/Section Overhead & N/A & N/A & Two \tco{smp_mb()} & Ranges from none to two \tco{smp_mb()} \\ - \hline Reader Per-Object Traversal Overhead & Read-modify-write atomic operations, memory\-/barrier instructions, and cache misses & \tco{smp_mb()} & None, but unsafe & None (volatile accesses) \\ - \hline Reader Forward Progress Guarantee & Lock free & Lock free & Blocking & Bounded wait free \\ - \hline Reader Reference Acquisition & Can fail (conditional) & Can fail (conditional) & Unsafe & Cannot fail (unconditional) \\ - \hline Memory Footprint & Bounded & Bounded & Bounded & Unbounded \\ - \hline Reclamation Forward Progress & Lock free & Lock free & N/A & Blocking \\ - \hline Automatic Reclamation & Yes & No & N/A & No \\ - \hline Lines of Code & 94 & 79 & 79 & 73 \\ + \bottomrule \end{tabularx} \caption{Which Deferred Technique to Choose?} \label{tab:defer:Which Deferred Technique to Choose?}
formal/spinhint.tex +33 -35
86 lines not on this page · raw message
future/QC.tex +37 -38
128 lines not on this page · raw message
perfbook.tex +1 -0
@@ -56,6 +56,7 @@ \usepackage[xspace]{ellipsis} \usepackage{braket} % for \ket{} macro in QC section \usepackage{siunitx} % for \num{} macro +\sisetup{group-minimum-digits=4,group-separator={,},group-digits=integer} % custom packages
together/refcnt.tex +14 -11
@@ -65,21 +65,24 @@ locking, and RCU. } \QuickQuizEnd \begin{table}[tb] -\footnotesize +\renewcommand*{\arraystretch}{1.25} +\rowcolors{3}{}{lightgray} +\small \centering -\begin{tabular}{l||c|c|c} +\begin{tabular}{lccc} + \toprule & \multicolumn{3}{c}{Release Synchronization} \\ - \cline{2-4} - Acquisition & & Reference & \\ - Synchronization & Locking & Counting & RCU \\ - \hline - \hline + \cmidrule(l){2-4} + \parbox[c]{.8in}{Acquisition\\Synchronization} + & Locking + & \parbox[c]{.5in}{Reference\\Counting} + & RCU \\ + \cmidrule{1-1} \cmidrule(l){2-4} Locking & $-$ & CAM & CA \\ - \hline - Reference & A & AM & A \\ - Counting & & & \\ - \hline + \parbox[c][6ex]{.8in}{Reference\\Counting} + & A & AM & A \\ RCU & CA & MCA & CA \\ + \bottomrule \end{tabular} \caption{Reference Counting and Synchronization Mechanisms} \label{tab:together:Reference Counting and Synchronization Mechanisms}
Signature · 1 line
2.7.4
PATCH 5/5 datastruct: Convert 'NUMA Topology of System Under Test' to figure
In reply to Akira YokosawaFrom d224db4bfed5d4ce0639062a920bafc6f9442e16 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:31:29 +0900
Subject: [PATCH 5/5] datastruct: Convert 'NUMA Topology of System Under Test' to figure
This can be regarded as a figure drawn using the "tabular" environment. By using dashed rules of "arydshln" package, it looks more like a figure.
--- datastruct/datastruct.tex | 21 +++++++++++++++------ 1 file changed, 15 insertions(+), 6 deletions(-)
datastruct/datastruct.tex +15 -6
@@ -458,7 +458,7 @@ Clearly something else is going on. The problem is that this is a multi-socket system, with CPUs~0-7 and~32-39 mapped to the first socket as shown in -Table~\ref{tab:datastruct:NUMA Topology of System Under Test}. +Figure~\ref{fig:datastruct:NUMA Topology of System Under Test}. Test runs confined to the first eight CPUs therefore perform quite well, but tests that involve socket~0's CPUs~0-7 as well as socket~1's CPU~8 incur the overhead of passing data across
@@ -504,27 +504,36 @@ the caches, which in turn promotes locality of reference. The next section therefore examines optimizations that can be carried out in read-mostly cases where updates are rare, but could happen at any time. -\begin{table} +\setlength\dashlinedash{1pt} +\setlength\dashlinegap{2pt} + +\begin{figure} +\renewcommand*{\arraystretch}{1.2} \footnotesize \centering -\begin{tabular}{r|r|r|r|r|r|r|r|r} - Socket & \multicolumn{8}{|c}{Core} \\ +\begin{tabular}{r|r:r:r:r:r:r:r:r|} + Socket & \multicolumn{8}{c|}{Core} \\ \hline 0 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ + \cdashline{2-9} & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 \\ \hline 1 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ + \cdashline{2-9} & 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 \\ \hline 2 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ + \cdashline{2-9} & 48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 \\ \hline 3 & 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\ + \cdashline{2-9} & 56 & 47 & 58 & 59 & 60 & 61 & 62 & 63 \\ + \hline \end{tabular} \caption{NUMA Topology of System Under Test} -\label{tab:datastruct:NUMA Topology of System Under Test} -\end{table} +\label{fig:datastruct:NUMA Topology of System Under Test} +\end{figure} \section{Read-Mostly Data Structures} \label{sec:datastruct:Read-Mostly Data Structures}
Signature · 1 line
2.7.4
Paul E. McKenney
AppliedQuoted 22 lines · Akira Yokosawa
Quoted 1 line
From
d224db4bfed5d4ce0639062a920bafc6f9442e16Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:55:49 +0900
Subject: [PATCH 0/5] Update table layoutHi Paul,
My first idea was to add a make target for "table captions at the top". But I changed my mind and promoted the layout as default. Instead, I added a target "perfbook-tcb.pdf" (tcb: Table Caption Bottom), which keeps the caption at the bottom.
Patch #1 does the change in perfbook.tex and
Makefile.Patches #2 and #3 are minor fixes I noticed while updating tables.
Patch #4 updates most tables to use the new table layout experimented in Style Guide for a while. It contains changes to use "S" column specifier provided by the "siunitx" package.
Patch #5 converts a table into a figure drawn by tabular.
Quoted 7 lines
There remains several tables not yet touched. They are complex and large ones. They need extra work to use the new scheme.
NOTE: Table 13.1 does not contain legends and does not use subscripts as shown in Table D.5 at the moment. In the text, it looks OK to me.
Thoughts?
At a first scan, this all looks good. There are a few remaining tables in the old format, including a couple that we discussed earlier as being quite complex. Which should be fine, for the time being, at least. But what are your thoughts on the remaining old-style tables?
Queued and pushed, thank you!
Thanx, Paul
Quoted 31 lines
Thanks, Akira
--
Akira Yokosawa (5):
Move caption of table to top
Define \twocolumnwidth for 1c layout
Use \O{} macro for 'order-of'
Update tables using booktabs and alternate-row coloring scheme
datastruct: Convert 'NUMA Topology of System Under Test' to figureMakefile | 6 ++- SMPdesign/SMPdesign.tex | 10 +++-- advsync/rt.tex | 8 ++-- appendix/questions/after.tex | 25 +++++++++---- appendix/styleguide/styleguide.tex | 20 ++++++---- count/count.tex | 54 ++++++++++++++++----------- cpu/overheads.tex | 76 +++++++++++++++++--------------------- datastruct/datastruct.tex | 23 ++++++++---- defer/rcuapi.tex | 16 ++++---- defer/rcufundamental.tex | 16 ++++---- defer/rcuusage.tex | 10 +++-- defer/whichtochoose.tex | 27 +++++--------- formal/spinhint.tex | 68 +++++++++++++++++----------------- future/QC.tex | 75 +++++++++++++++++++------------------ memorder/memorder.tex | 8 ++-- perfbook.tex | 17 +++++++++ together/refcnt.tex | 25 +++++++------ 17 files changed, 266 insertions(+), 218 deletions(-)Signature · 1 line
2.7.4
Quoted 29 lines · Paul E. McKenney
Quoted 28 lines · Akira Yokosawa
Quoted 1 line
From
d224db4bfed5d4ce0639062a920bafc6f9442e16Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:55:49 +0900
Subject: [PATCH 0/5] Update table layoutHi Paul,
My first idea was to add a make target for "table captions at the top". But I changed my mind and promoted the layout as default. Instead, I added a target "perfbook-tcb.pdf" (tcb: Table Caption Bottom), which keeps the caption at the bottom.
Patch #1 does the change in perfbook.tex and
Makefile.Patches #2 and #3 are minor fixes I noticed while updating tables.
Patch #4 updates most tables to use the new table layout experimented in Style Guide for a while. It contains changes to use "S" column specifier provided by the "siunitx" package.
Patch #5 converts a table into a figure drawn by tabular.
There remains several tables not yet touched. They are complex and large ones. They need extra work to use the new scheme.
NOTE: Table 13.1 does not contain legends and does not use subscripts as shown in Table D.5 at the moment. In the text, it looks OK to me.
Quoted 7 lines
Quoted 1 line
Thoughts?
At a first scan, this all looks good. There are a few remaining tables in the old format, including a couple that we discussed earlier as being quite complex. Which should be fine, for the time being, at least. But what are your thoughts on the remaining old-style tables?
Tables 17.1 and 17.2 are hard ones. Alternate-row coloring scheme can not be applied for them. We need to figure out how to improve them. I'm fine with them to be left for the moment.
Table 7.1 does not fit to the format because of the "Null (Not Held)" column. As all the cells of the column are all blank, vertical rules actually helps in this table. If you put some character/symbol to indicate compatibility, it can be converted to the new format. If you have a good candidate, please let me know.
I'm sending patches to update Tables 9.3 and C.1, and a patch to convert Tables C.2, C.3, and C.4 into Listings.
If there is any table I'm missing, feel free to tell me.
Thanks, Akira
Quoted 37 lines
Queued and pushed, thank you!
Thanx, Paul
Quoted 31 lines
Thanks, Akira
--
Akira Yokosawa (5):
Move caption of table to top
Define \twocolumnwidth for 1c layout
Use \O{} macro for 'order-of'
Update tables using booktabs and alternate-row coloring scheme
datastruct: Convert 'NUMA Topology of System Under Test' to figureMakefile | 6 ++- SMPdesign/SMPdesign.tex | 10 +++-- advsync/rt.tex | 8 ++-- appendix/questions/after.tex | 25 +++++++++---- appendix/styleguide/styleguide.tex | 20 ++++++---- count/count.tex | 54 ++++++++++++++++----------- cpu/overheads.tex | 76 +++++++++++++++++--------------------- datastruct/datastruct.tex | 23 ++++++++---- defer/rcuapi.tex | 16 ++++---- defer/rcufundamental.tex | 16 ++++---- defer/rcuusage.tex | 10 +++-- defer/whichtochoose.tex | 27 +++++--------- formal/spinhint.tex | 68 +++++++++++++++++----------------- future/QC.tex | 75 +++++++++++++++++++------------------ memorder/memorder.tex | 8 ++-- perfbook.tex | 17 +++++++++ together/refcnt.tex | 25 +++++++------ 17 files changed, 266 insertions(+), 218 deletions(-)Signature · 1 line
2.7.4
Quoted 32 lines · Akira Yokosawa
Quoted 31 lines · Paul E. McKenney
Quoted 29 lines · Akira Yokosawa
Quoted 1 line
From
d224db4bfed5d4ce0639062a920bafc6f9442e16Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:55:49 +0900
Subject: [PATCH 0/5] Update table layoutHi Paul,
My first idea was to add a make target for "table captions at the top". But I changed my mind and promoted the layout as default. Instead, I added a target "perfbook-tcb.pdf" (tcb: Table Caption Bottom), which keeps the caption at the bottom.
Patch #1 does the change in perfbook.tex and
Makefile.Patches #2 and #3 are minor fixes I noticed while updating tables.
Patch #4 updates most tables to use the new table layout experimented in Style Guide for a while. It contains changes to use "S" column specifier provided by the "siunitx" package.
Patch #5 converts a table into a figure drawn by tabular.
There remains several tables not yet touched. They are complex and large ones. They need extra work to use the new scheme.
NOTE: Table 13.1 does not contain legends and does not use subscripts as shown in Table D.5 at the moment. In the text, it looks OK to me.
Thoughts?
Quoted 8 lines
Quoted 4 lines
At a first scan, this all looks good. There are a few remaining tables in the old format, including a couple that we discussed earlier as being quite complex. Which should be fine, for the time being, at least. But what are your thoughts on the remaining old-style tables?
Tables 17.1 and 17.2 are hard ones. Alternate-row coloring scheme can not be applied for them. We need to figure out how to improve them. I'm fine with them to be left for the moment.
Works for me as well!
Quoted 5 lines
Table 7.1 does not fit to the format because of the "Null (Not Held)" column. As all the cells of the column are all blank, vertical rules actually helps in this table. If you put some character/symbol to indicate compatibility, it can be converted to the new format. If you have a good candidate, please let me know.
Hmmm... Is there a very light grey variant of the square that appears at the end of each quick quiz? "\rule{7pt}{7pt}}", if I am not getting too confused. Ah, there is. Please see the crude experimental patch below. (As in if you do choose to do something like this, please make a more sensible/maintainable version.)
Quoted 4 lines
I'm sending patches to update Tables 9.3 and C.1, and a patch to convert Tables C.2, C.3, and C.4 into Listings.
If there is any table I'm missing, feel free to tell me.
I will try them out, thank you!
Thanx, Paul
------------------------------------------------------------------------
locking/locking.tex +9 -7
@@ -1311,6 +1311,8 @@ or even milliseconds. \subsection{Beyond Reader-Writer Locks} \label{sec:locking:Beyond Reader-Writer Locks} +\newcommand{\x}{\textcolor{gray!20}{\rule{7pt}{7pt}}} + \begin{table} \small \centering
@@ -1336,19 +1338,19 @@ or even milliseconds. \end{picture} \\ \hline -% NL CR CW PR PW EX +% NL CR CW PR PW EX \hline - Null (Not Held) & ~ & ~ & ~ & ~ & ~ & ~ \\ + Null (Not Held) & \x & \x & \x & \x & \x & \x \\ \hline - Concurrent Read & ~ & ~ & ~ & ~ & ~ & X \\ + Concurrent Read & \x & \x & \x & \x & \x & X \\ \hline - Concurrent Write & ~ & ~ & ~ & X & X & X \\ + Concurrent Write & \x & \x & \x & X & X & X \\ \hline - Protected Read & ~ & ~ & X & ~ & X & X \\ + Protected Read & \x & \x & X & \x & X & X \\ \hline - Protected Write & ~ & ~ & X & X & X & X \\ + Protected Write & \x & \x & X & X & X & X \\ \hline - Exclusive & ~ & X & X & X & X & X \\ + Exclusive & \x & X & X & X & X & X \\ \end{tabular} \caption{VAX/VMS Distributed Lock Manager Policy} \label{tab:locking:VAX/VMS Distributed Lock Manager Policy}
Quoted 50 lines · Paul E. McKenney
Quoted 32 lines · Akira Yokosawa
Quoted 31 lines · Paul E. McKenney
Quoted 29 lines · Akira Yokosawa
Quoted 1 line
From
d224db4bfed5d4ce0639062a920bafc6f9442e16Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:55:49 +0900
Subject: [PATCH 0/5] Update table layoutHi Paul,
My first idea was to add a make target for "table captions at the top". But I changed my mind and promoted the layout as default. Instead, I added a target "perfbook-tcb.pdf" (tcb: Table Caption Bottom), which keeps the caption at the bottom.
Patch #1 does the change in perfbook.tex and
Makefile.Patches #2 and #3 are minor fixes I noticed while updating tables.
Patch #4 updates most tables to use the new table layout experimented in Style Guide for a while. It contains changes to use "S" column specifier provided by the "siunitx" package.
Patch #5 converts a table into a figure drawn by tabular.
There remains several tables not yet touched. They are complex and large ones. They need extra work to use the new scheme.
NOTE: Table 13.1 does not contain legends and does not use subscripts as shown in Table D.5 at the moment. In the text, it looks OK to me.
Thoughts?
Quoted 8 lines
Quoted 4 lines
At a first scan, this all looks good. There are a few remaining tables in the old format, including a couple that we discussed earlier as being quite complex. Which should be fine, for the time being, at least. But what are your thoughts on the remaining old-style tables?
Tables 17.1 and 17.2 are hard ones. Alternate-row coloring scheme can not be applied for them. We need to figure out how to improve them. I'm fine with them to be left for the moment.
Works for me as well!
Quoted 5 lines
Table 7.1 does not fit to the format because of the "Null (Not Held)" column. As all the cells of the column are all blank, vertical rules actually helps in this table. If you put some character/symbol to indicate compatibility, it can be converted to the new format. If you have a good candidate, please let me know.
Quoted 5 lines
Hmmm... Is there a very light grey variant of the square that appears at the end of each quick quiz? "\rule{7pt}{7pt}}", if I am not getting too confused. Ah, there is. Please see the crude experimental patch below. (As in if you do choose to do something like this, please make a more sensible/maintainable version.)
So, I've just submitted a patch to do the format conversion. I'm not sure "\x" is the right name to use, but one character is convenient in this table. In this case, coloring alternate rows is not necessary.
The following patch is to keep position of table captions consistent.
Ah, there is another reminder for you.
You need to mention the moved "advsync/rt" section in the outline of advsync chapter, don't you? Honestly speaking, it is not obvious at first glance how it relates to weaker synchronization.
A good introduction should help readers.
Thanks, Akira
Quoted 53 lines
Quoted 5 lines
I'm sending patches to update Tables 9.3 and C.1, and a patch to convert Tables C.2, C.3, and C.4 into Listings.
If there is any table I'm missing, feel free to tell me.
I will try them out, thank you!
Thanx, Paul
------------------------------------------------------------------------locking/locking.tex +9
-7@@ -1311,6 +1311,8 @@ or even milliseconds. \subsection{Beyond Reader-Writer Locks} \label{sec:locking:Beyond Reader-Writer Locks} +\newcommand{\x}{\textcolor{gray!20}{\rule{7pt}{7pt}}} + \begin{table} \small \centering@@ -1336,19 +1338,19 @@ or even milliseconds. \end{picture} \\ \hline -% NL CR CW PR PW EX +% NL CR CW PR PW EX \hline - Null (Not Held) & ~ & ~ & ~ & ~ & ~ & ~ \\ + Null (Not Held) & \x & \x & \x & \x & \x & \x \\ \hline - Concurrent Read & ~ & ~ & ~ & ~ & ~ & X \\ + Concurrent Read & \x & \x & \x & \x & \x & X \\ \hline - Concurrent Write & ~ & ~ & ~ & X & X & X \\ + Concurrent Write & \x & \x & \x & X & X & X \\ \hline - Protected Read & ~ & ~ & X & ~ & X & X \\ + Protected Read & \x & \x & X & \x & X & X \\ \hline - Protected Write & ~ & ~ & X & X & X & X \\ + Protected Write & \x & \x & X & X & X & X \\ \hline - Exclusive & ~ & X & X & X & X & X \\ + Exclusive & \x & X & X & X & X & X \\ \end{tabular} \caption{VAX/VMS Distributed Lock Manager Policy} \label{tab:locking:VAX/VMS Distributed Lock Manager Policy}
Quoted 57 lines · Akira Yokosawa
Quoted 50 lines · Paul E. McKenney
Quoted 32 lines · Akira Yokosawa
Quoted 31 lines · Paul E. McKenney
Quoted 29 lines · Akira Yokosawa
Quoted 1 line
From
d224db4bfed5d4ce0639062a920bafc6f9442e16Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Sun, 22 Oct 2017 23:55:49 +0900
Subject: [PATCH 0/5] Update table layoutHi Paul,
My first idea was to add a make target for "table captions at the top". But I changed my mind and promoted the layout as default. Instead, I added a target "perfbook-tcb.pdf" (tcb: Table Caption Bottom), which keeps the caption at the bottom.
Patch #1 does the change in perfbook.tex and
Makefile.Patches #2 and #3 are minor fixes I noticed while updating tables.
Patch #4 updates most tables to use the new table layout experimented in Style Guide for a while. It contains changes to use "S" column specifier provided by the "siunitx" package.
Patch #5 converts a table into a figure drawn by tabular.
There remains several tables not yet touched. They are complex and large ones. They need extra work to use the new scheme.
NOTE: Table 13.1 does not contain legends and does not use subscripts as shown in Table D.5 at the moment. In the text, it looks OK to me.
Thoughts?
Quoted 8 lines
Quoted 4 lines
At a first scan, this all looks good. There are a few remaining tables in the old format, including a couple that we discussed earlier as being quite complex. Which should be fine, for the time being, at least. But what are your thoughts on the remaining old-style tables?
Tables 17.1 and 17.2 are hard ones. Alternate-row coloring scheme can not be applied for them. We need to figure out how to improve them. I'm fine with them to be left for the moment.
Works for me as well!
Quoted 5 lines
Table 7.1 does not fit to the format because of the "Null (Not Held)" column. As all the cells of the column are all blank, vertical rules actually helps in this table. If you put some character/symbol to indicate compatibility, it can be converted to the new format. If you have a good candidate, please let me know.
Quoted 5 lines
Hmmm... Is there a very light grey variant of the square that appears at the end of each quick quiz? "\rule{7pt}{7pt}}", if I am not getting too confused. Ah, there is. Please see the crude experimental patch below. (As in if you do choose to do something like this, please make a more sensible/maintainable version.)
Quoted 3 lines
So, I've just submitted a patch to do the format conversion. I'm not sure "\x" is the right name to use, but one character is convenient in this table. In this case, coloring alternate rows is not necessary.
Fair point! I must confess that I had hoped that you would come up with a more clever way to do this, but is it possible to somehow undefine \x immediately after use? Just to give better diagnostics for inadvertent reuse...
Quoted 1 line
The following patch is to keep position of table captions consistent.
I am taking that one. I am on a plane right now, so it might be some time before they show up outside of my laptop.
Quoted 4 lines
Ah, there is another reminder for you.
You need to mention the moved "advsync/rt" section in the outline of advsync chapter, don't you? Honestly speaking, it is not obvious at first glance how it relates to weaker synchronization.
I was thinking that there is more than one way to "advance" synchronization, but agreed, I do need to make this clear.
Quoted 1 line
A good introduction should help readers.
I took a shot at this and pushed it out. Thoughts?
Thanx, Paul
PATCH 1/3 whymb: Update table layout
In reply to Paul E. McKenneyFrom 0bec999ee614a8c92d42876957b1072329b62829 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 23 Oct 2017 23:13:26 +0900
Subject: [PATCH 1/3] whymb: Update table layout
--- appendix/whymb/whymemorybarriers.tex | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-)
appendix/whymb/whymemorybarriers.tex +8 -12
@@ -565,29 +565,25 @@ Finally, CPU~1 reads the cache line at address~8, which uses a \begin{table*} \small \centering -\begin{tabular}{r|c|l||c|c|c|c||c|c} - & & & \multicolumn{4}{c||}{CPU Cache} & \multicolumn{2}{c}{Memory} \\ - \cline{4-7} +\renewcommand*{\arraystretch}{1.2} +\rowcolors{6}{}{lightgray} +\begin{tabular}{rclcccccc} + \toprule + & & & \multicolumn{4}{c}{CPU Cache} & \multicolumn{2}{c}{Memory} \\ + \cmidrule(lr){4-7} \cmidrule(l){8-9} Sequence \# & CPU \# & Operation & 0 & 1 & 2 & 3 & 0 & 8 \\ - \hline + \cmidrule(r){1-3} \cmidrule(lr){4-7} \cmidrule(l){8-9} % Seq CPU Operation ------------- CPU ------------- - Memory - % 0 1 2 3 0 8 - \hline 0 & & Initial State & $-$/I & $-$/I & $-$/I & $-$/I & V & V \\ - \hline 1 & 0 & Load & 0/S & $-$/I & $-$/I & $-$/I & V & V \\ - \hline 2 & 3 & Load & 0/S & $-$/I & $-$/I & 0/S & V & V \\ - \hline 3 & 0 & Invalidation & 8/S & $-$/I & $-$/I & 0/S & V & V \\ - \hline 4 & 2 & RMW & 8/S & $-$/I & 0/E & $-$/I & V & V \\ - \hline 5 & 2 & Store & 8/S & $-$/I & 0/M & $-$/I & I & V \\ - \hline 6 & 1 & Atomic Inc & 8/S & 0/M & $-$/I & $-$/I & I & V \\ - \hline 7 & 1 & Writeback & 8/S & 8/S & $-$/I & $-$/I & V & V \\ + \bottomrule \end{tabular} \caption{Cache Coherence Example} \label{tab:app:whymb:Cache Coherence Example}
Signature · 1 line
2.7.4
PATCH 2/3 defer/rcuapi: Update table layout
From 953186f749ee9052636fc52b04c2830a35c4de75 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 23 Oct 2017 23:15:10 +0900
Subject: [PATCH 2/3] defer/rcuapi: Update table layout
--- defer/rcuapi.tex | 29 ++++++++++------------------- 1 file changed, 10 insertions(+), 19 deletions(-)
defer/rcuapi.tex +10 -19
@@ -17,112 +17,103 @@ presents concluding remarks. \label{sec:defer:RCU has a Family of Wait-to-Finish APIs} \begin{sidewaystable*}[htbp] +\rowcolors{1}{}{lightgray} +\renewcommand*{\arraystretch}{1.3} \centering \footnotesize -\begin{tabularx}{7.9in}{>{\raggedright\arraybackslash}p{1.08in}| - >{\raggedright\arraybackslash}X| - >{\raggedright\arraybackslash}X| - >{\raggedright\arraybackslash}X| - >{\raggedright\arraybackslash}X| +\begin{tabularx}{7.9in}{>{\raggedright\arraybackslash}p{1.08in} + >{\raggedright\arraybackslash}X + >{\raggedright\arraybackslash}X + >{\raggedright\arraybackslash}X + >{\raggedright\arraybackslash}X >{\raggedright\arraybackslash}p{1.22in}} +\toprule Attribute & RCU Classic & RCU BH & RCU Sched & Realtime RCU & SRCU \\ -\hline -\hline +\midrule Purpose & Original & Prevent DDoS attacks & Wait for preempt-disable regions, hardirqs, \& NMIs & Realtime response & Sleeping readers \\ -\hline Availability & 2.5.43 & 2.6.9 & 2.6.12 & 2.6.26 & 2.6.19 \\ -\hline Read-side primitives & \tco{rcu_read_lock()}~! \tco{rcu_read_unlock()}~! & \tco{rcu_read_lock_bh()} \tco{rcu_read_unlock_bh()} & \tco{preempt_disable()} \tco{preempt_enable()} (and friends) & \tco{rcu_read_lock()} \tco{rcu_read_unlock()} & \tco{srcu_read_lock()} \tco{srcu_read_unlock()} \\ -\hline { Update-side primitives (synchronous) } & { \tco{synchronize_rcu()} \tco{synchronize_net()} } & \tco{synchronize_rcu_bh()} & \tco{synchronize_sched()} & { \tco{synchronize_rcu()} \tco{synchronize_net()} } & \tco{synchronize_srcu()} \\ -\hline { Update-side primitives (asynchronous/callback) } & \tco{call_rcu()} ! & \tco{call_rcu_bh()} & \tco{call_rcu_sched()} & \tco{call_rcu()} & \tco{call_srcu()} \\ -\hline { Update-side primitives (wait for callbacks) } & \tco{rcu_barrier()} & \tco{rcu_barrier_bh()} & \tco{rcu_barrier_sched()} & \tco{rcu_barrier()} & N/A \\ -\hline Type-safe memory & \tco{SLAB_DESTROY_BY_RCU} & & & \tco{SLAB_DESTROY_BY_RCU} & \\ -\hline Read side constraints & No blocking & No bottom-half (BH) enabling & No blocking & Only preemption and lock acquisition & No \tco{synchronize_srcu()} with same \tco{srcu_struct} \\ -\hline Read side overhead & Preempt disable/enable (free on non-\tco{PREEMPT}) & BH disable/enable & Preempt disable/enable (free on non-\tco{PREEMPT}) & Simple instructions, \IRQ\ disable/enable & Simple instructions, preempt disable/enable, memory barriers \\ -\hline Asynchronous update-side overhead & sub-microsecond & sub-microsecond & sub-microsecond & sub-microsecond & N/A \\ -\hline Grace-period latency & 10s of milliseconds & 10s of milliseconds & 10s of milliseconds & 10s of milliseconds & 10s of milliseconds \\ -\hline Non-\tco{PREEMPT_RT} implementation & RCU Classic & RCU BH & RCU Classic & Preemptible RCU & SRCU \\ -\hline \tco{PREEMPT_RT} implementation & Preemptible RCU & Realtime RCU & Forced Schedule on all CPUs & Realtime RCU & SRCU \\ +\bottomrule \end{tabularx} \caption{RCU Wait-to-Finish APIs} \label{tab:defer:RCU Wait-to-Finish APIs}
Signature · 1 line
2.7.4
PATCH 3/3 Convert table of code fragments to 'listing'
In reply to Akira YokosawaFrom 8f4cb48165bcd63d8fcbff966f7d3794a5c5863a Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 23 Oct 2017 23:33:11 +0900
Subject: [PATCH 3/3] Convert table of code fragments to 'listing'
Also reduce font size to scriptsize.
NOTE: In these cases, the "ruled" style is not appropriate. "plaintop" style is a better choice.
--- appendix/whymb/whymemorybarriers.tex | 38 +++++++++++++++++++++--------------- 1 file changed, 22 insertions(+), 16 deletions(-)
appendix/whymb/whymemorybarriers.tex +22 -16
@@ -1345,12 +1345,15 @@ as we will see.\footnote{ \subsection{Example 1} \label{sec:app:whymb:Example 1} -Table~\ref{tab:app:whymb:Memory Barrier Example 1} +Listing~\ref{lst:app:whymb:Memory Barrier Example 1} shows three code fragments, executed concurrently by CPUs~0, 1, and 2. Each of ``a'', ``b'', and ``c'' are initially zero. -\begin{table*} -\small +\floatstyle{plaintop} +\restylefloat{listing} + +\begin{listing} +\scriptsize \centering{\tt \begin{tabular}{l|l|l} \multicolumn{1}{c|}{\nf{CPU~0}} &
@@ -1366,8 +1369,8 @@ Each of ``a'', ``b'', and ``c'' are initially zero. & & assert(z == 0 || x == 1); \\ \end{tabular}} \caption{Memory Barrier Example 1} -\label{tab:app:whymb:Memory Barrier Example 1} -\end{table*} +\label{lst:app:whymb:Memory Barrier Example 1} +\end{listing} Suppose CPU~0 recently experienced many cache misses, so that its message queue is full, but that CPU~1 has been running exclusively within
@@ -1405,12 +1408,12 @@ the assertion. \subsection{Example 2} \label{sec:app:whymb:Example 2} -Table~\ref{tab:app:whymb:Memory Barrier Example 2} +Listing~\ref{lst:app:whymb:Memory Barrier Example 2} shows three code fragments, executed concurrently by CPUs~0, 1, and 2. Both ``a'' and ``b'' are initially zero. -\begin{table*} -\small +\begin{listing} +\scriptsize \centering{\tt \begin{tabular}{l|l|l} \multicolumn{1}{c|}{\nf{CPU~0}} &
@@ -1425,8 +1428,8 @@ Both ``a'' and ``b'' are initially zero. & & assert(y == 0 || x == 1); \\ \end{tabular}} \caption{Memory Barrier Example 2} -\label{tab:app:whymb:Memory Barrier Example 2} -\end{table*} +\label{lst:app:whymb:Memory Barrier Example 2} +\end{listing} Again, suppose CPU~0 recently experienced many cache misses, so that its message queue is full, but that CPU~1 has been running exclusively within
@@ -1447,11 +1450,11 @@ mainstream computer systems. \subsection{Example 3} \label{sec:app:whymb:Example 3} -Table~\ref{tab:app:whymb:Memory Barrier Example 3} +Listing~\ref{lst:app:whymb:Memory Barrier Example 3} shows three code fragments, executed concurrently by CPUs~0, 1, and 2. All variables are initially zero. -\begin{table*} +\begin{listing*} \scriptsize \centering{\tt \begin{tabular}{r|l|l|l}
@@ -1471,8 +1474,11 @@ All variables are initially zero. 9 & e = 1; & & assert(e == 0 || a == 1); \\ \end{tabular}} \caption{Memory Barrier Example 3} -\label{tab:app:whymb:Memory Barrier Example 3} -\end{table*} +\label{lst:app:whymb:Memory Barrier Example 3} +\end{listing*} + +\floatstyle{ruled} +\restylefloat{listing} Note that neither CPU~1 nor CPU~2 can proceed to line~5 until they see CPU~0's assignment to ``b'' on line~3.
@@ -1487,7 +1493,7 @@ Therefore, CPU~2's assertion on line~9 is guaranteed \emph{not} to fire. \QuickQuiz{} Suppose that lines~3-5 for CPUs~1 and 2 in - Table~\ref{tab:app:whymb:Memory Barrier Example 3} + Listing~\ref{lst:app:whymb:Memory Barrier Example 3} are in an interrupt handler, and that the CPU~2's line~9 runs at process level. In other words, the code in all three columns of the table
@@ -1524,7 +1530,7 @@ assert(r1 == 0 || a == 1); \QuickQuiz{} If CPU~2 executed an \co{assert(e==0||c==1)} in the example in - Table~\ref{tab:app:whymb:Memory Barrier Example 3}, + Listing~\ref{lst:app:whymb:Memory Barrier Example 3}, would this assert ever trigger? \QuickQuizAnswer{ The result depends on whether the CPU supports ``transitivity''.
Signature · 1 line
2.7.4
Re: [PATCH 1/3] whymb: Update table layout
In reply to Akira YokosawaQuoted 6 lines · Akira Yokosawa
Quoted 1 line
From
0bec999ee614a8c92d42876957b1072329b62829Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 23 Oct 2017 23:13:26 +0900
Subject: [PATCH 1/3] whymb: Update table layoutSigned-off-by Akira Yokosawa <[email protected]>
All three look good, queued and pushed, thank you!
Thanx, Paul
Quoted 50 lines
--- appendix/whymb/whymemorybarriers.tex | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-)appendix/whymb/whymemorybarriers.tex +8
-12@@ -565,29 +565,25 @@ Finally, CPU~1 reads the cache line at address~8, which uses a \begin{table*} \small \centering -\begin{tabular}{r|c|l||c|c|c|c||c|c} - & & & \multicolumn{4}{c||}{CPU Cache} & \multicolumn{2}{c}{Memory} \\ - \cline{4-7} +\renewcommand*{\arraystretch}{1.2} +\rowcolors{6}{}{lightgray} +\begin{tabular}{rclcccccc} + \toprule + & & & \multicolumn{4}{c}{CPU Cache} & \multicolumn{2}{c}{Memory} \\ + \cmidrule(lr){4-7} \cmidrule(l){8-9} Sequence \# & CPU \# & Operation & 0 & 1 & 2 & 3 & 0 & 8 \\ - \hline + \cmidrule(r){1-3} \cmidrule(lr){4-7} \cmidrule(l){8-9} % Seq CPU Operation ------------- CPU ------------- - Memory - % 0 1 2 3 0 8 - \hline 0 & & Initial State & $-$/I & $-$/I & $-$/I & $-$/I & V & V \\ - \hline 1 & 0 & Load & 0/S & $-$/I & $-$/I & $-$/I & V & V \\ - \hline 2 & 3 & Load & 0/S & $-$/I & $-$/I & 0/S & V & V \\ - \hline 3 & 0 & Invalidation & 8/S & $-$/I & $-$/I & 0/S & V & V \\ - \hline 4 & 2 & RMW & 8/S & $-$/I & 0/E & $-$/I & V & V \\ - \hline 5 & 2 & Store & 8/S & $-$/I & 0/M & $-$/I & I & V \\ - \hline 6 & 1 & Atomic Inc & 8/S & 0/M & $-$/I & $-$/I & I & V \\ - \hline 7 & 1 & Writeback & 8/S & 8/S & $-$/I & $-$/I & V & V \\ + \bottomrule \end{tabular} \caption{Cache Coherence Example} \label{tab:app:whymb:Cache Coherence Example}Signature · 1 line
2.7.4