Skip to contentSkip to conversation

Fixes to recent updates in count

PATCH In review Akira Yokosawa 2 participants 9 messages Oct 26, 2019 – Oct 28, 2019

lore
Share & tools
lore
#0 lore raw

cover Fixes to recent updates in count

Hi Paul,

So you had (or still have?) a chance to run the parallel count algorithms on the large x86 (224-core with HT) system. Interesting data.

This patch set is to adjust a few contexts with existing contents.

Patch #1 adjusts horizontal spacing of tables getting wider than 1c column width.
Patch #2 adds a dashed line mentioned in Quick Quiz 5.8. Patch #3 substitutes "x86" for "POWER6".

If you have conflicting local updates, I'd be happy to rebase.

Also, you might want to add a Quick Quiz on the slope changes in Figure 5.1 at number of CPUs 2 and 28. I think you know what I mean.

Thanks, Akira
--
Akira Yokosawa (3):
count: Tweak horizontal spacing of wide tables in 1c layout
count: Add dashed line indicating ideal time of (non-atomic) increment
count: Update CPU type/system

 CodeSamples/count/atomic_hps.eps | 111 ++++++++++++++++++++++++++++++-
 CodeSamples/count/atomic_hps.png | Bin 3113 -> 3120 bytes
 CodeSamples/count/plots.sh       |   2 +-
 count/count.tex                  |  12 ++--
 4 files changed, 117 insertions(+), 8 deletions(-)
Signature · 1 line
2.17.1
#1 lore raw

PATCH 1/3 count: Tweak horizontal spacing of wide tables in 1c layout

From 0a2fa3b2687fc4ca1d79856fa30825f3cbea76f4 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sat, 26 Oct 2019 00:07:26 +0900
Subject: [PATCH 1/3] count: Tweak horizontal spacing of wide tables in 1c layout

These tables got wider than the width of 1c layout by recent update using the results obtained on a larger system.

Also adjust "table-format" specifiers to the digit counts in the table (now grown to 6 digits).

---
 count/count.tex | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)
count/count.tex +6 -4
index 9735a89c..4b01bc75 100644
@@ -2817,8 +2817,9 @@ will expand on these lessons.
 \rowcolors{4}{}{lightgray}
 \renewcommand*{\arraystretch}{1.1}
 \small
-\centering
-\begin{tabular}{lrS[table-format = 2.1]S[table-format = 3.0]S[table-format = 5.0]S[table-format = 5.0]S[table-format = 5.0]}
+\centering\OneColumnHSpace{-.25in}
+\begin{tabular}{lrS[table-format=1.1]S[table-format=3.0]S[table-format=4.0]
+		  S[table-format=6.0]S[table-format=6.0]}
 	\toprule
 	& & & \multicolumn{4}{c}{Reads (ns)} \\
 	\cmidrule{4-7}
@@ -2904,8 +2905,9 @@ courtesy of eventual consistency.
 \rowcolors{4}{}{lightgray}
 \renewcommand*{\arraystretch}{1.1}
 \small
-\centering
-\begin{tabular}{lrcS[table-format = 2.1]S[table-format = 3.0]S[table-format = 5.0]S[table-format = 5.0]S[table-format = 5.0]}
+\centering\OneColumnHSpace{-.4in}
+\begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
+		   S[table-format=6.0]S[table-format=6.0]}
 	\toprule
 	& & & & \multicolumn{4}{c}{Reads (ns)} \\
 	\cmidrule{5-8}
Signature · 1 line
2.17.1
#2 lore raw

PATCH 2/3 count: Add dashed line indicating ideal time of (non-atomic) increment

In reply to Akira Yokosawa

From 5329aeeca8bcdc96241f902748ea4c8d52099031 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 27 Oct 2019 08:48:49 +0900
Subject: [PATCH 2/3] count: Add dashed line indicating ideal time of (non-atomic) increment

This line is mentioned in Quick Quiz 5.8
The value 1.46041 is taken from count_nonatomic:u.hps.2019.10.23a.dat.

---
 CodeSamples/count/atomic_hps.eps | 111 ++++++++++++++++++++++++++++++-
 CodeSamples/count/atomic_hps.png | Bin 3113 -> 3120 bytes
 CodeSamples/count/plots.sh       |   2 +-
 3 files changed, 110 insertions(+), 3 deletions(-)
CodeSamples/count/atomic_hps.eps +109 -2
index 05dedb24..df873ec0 100644
@@ -1,7 +1,7 @@
 %!PS-Adobe-2.0
 %%Title: Is Parallel Programming Hard, And, If So, What Can You Do About It?
 %%Creator: gnuplot 5.2 patchlevel 2
-%%CreationDate: Thu Oct 24 06:55:35 2019
+%%CreationDate: Sat Oct 26 08:12:20 2019
 %%DocumentFonts: (atend)
 %%BoundingBox: 50 95 302 355
 %%Orientation: Portrait
@@ -1872,7 +1872,7 @@ SDict begin [
   /Creator (gnuplot 5.2 patchlevel 2)
 %  /Producer (gnuplot)
 %  /Keywords ()
-  /CreationDate (Thu Oct 24 06:55:35 2019)
+  /CreationDate (Sat Oct 26 08:12:20 2019)
   /DOCINFO pdfmark
 end
 } ifelse
@@ -2546,6 +2546,113 @@ LCb setrgbcolor
 50 24 V
 25 8 V
 % End plot #2
+% Begin plot #3
+stroke
+LTb
+LT2
+LCb setrgbcolor
+/NimbusSanL-Regu findfont 100 scalefont setfont
+670 1265 M
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+17 0 V
+16 0 V
+17 0 V
+17 0 V
+17 0 V
+% End plot #3
 stroke
 2.000 UL
 LTb
CodeSamples/count/atomic_hps.png binary +0 -0
index 8f000fdf09313ff13e2ab1adc49b5d2b6bbfe623..b0f211726dba0190cd5425b8534cc10e2b915226 100644
GIT binary patch
CodeSamples/count/plots.sh +1 -1
index cf0f7374..a76ab07b 100644
@@ -96,7 +96,7 @@ set logscale xy
 #set yrange [1:10000]
 #set yrange [100:10000]
 set nokey
-plot "data/count_atomic:u.hps.2019.10.23a.dat" w e, "data/count_atomic:u.hps.2019.10.23a.dat" w l
+plot "data/count_atomic:u.hps.2019.10.23a.dat" w e, "data/count_atomic:u.hps.2019.10.23a.dat" w l, 1.46041
 set term png medium
 set output "atomic_hps.png"
 replot
Signature · 1 line
2.17.1
#3 lore raw

PATCH 3/3 count: Update CPU type/system

In reply to Akira Yokosawa

From 79832886d01cd0e9e5d491132528dba83440a548 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 27 Oct 2019 09:03:44 +0900
Subject: [PATCH 3/3] count: Update CPU type/system

We are now talking about results obrained on an x86 system.

---
 count/count.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
count/count.tex +1 -1
index 4b01bc75..6430abd5 100644
@@ -2934,7 +2934,7 @@ courtesy of eventual consistency.
 Table~\ref{tab:count:Limit Counter Performance on x86}
 shows the performance of the parallel limit-counting algorithms.
 Exact enforcement of the limits incurs a substantial performance
-penalty, although on this 4.7\,GHz \Power{6} system that penalty can be reduced
+penalty, although on this x86 system that penalty can be reduced
 by substituting signals for atomic operations.
 All of these implementations suffer from read-side lock contention
 in the face of concurrent readers.
Signature · 1 line
2.17.1
#4 lore raw
In reply to Akira Yokosawa
Quoted 4 lines · Akira Yokosawa

Hi Paul,

So you had (or still have?) a chance to run the parallel count algorithms on the large x86 (224-core with HT) system. Interesting data.

Yes, but access is still a bit patchy. I probably should have waited, but I was too pleased to have large-scale data. What can I say? ;-)

Quoted 4 lines

This patch set is to adjust a few contexts with existing contents.

Patch #1 adjusts horizontal spacing of tables getting wider than 1c column width.

Good point -- I should have checked, thank you for catching this! Would it make sense to rotate the "Exact?" heading 90 degrees and to put the "(ns)" underneath the "Updates"? Those two changes might make Figure 5.2 fit horizontally.

Quoted 2 lines

Patch #2 adds a dashed line mentioned in Quick Quiz 5.8. Patch #3 substitutes "x86" for "POWER6".

Good catches, all three queued and pushed, thank you!

Quoted 1 line

If you have conflicting local updates, I'd be happy to rebase.

No problem, as my updates didn't conflict. Sometimes we get lucky. ;-)

Quoted 2 lines

Also, you might want to add a Quick Quiz on the slope changes in Figure 5.1 at number of CPUs 2 and 28. I think you know what I mean.

You are right, that would be good. I believe that at least some of the change in slope is due to hyperthreading, but I do not believe that this is the only effect. But I need to get the system into better shape before I will be able to track this down, which might be a few weeks.

If I forget, please feel free to remind me again, though!

Thanx, Paul

Quoted 16 lines

Thanks, Akira
--
Akira Yokosawa (3):
count: Tweak horizontal spacing of wide tables in 1c layout
count: Add dashed line indicating ideal time of (non-atomic) increment
count: Update CPU type/system

 CodeSamples/count/atomic_hps.eps | 111 ++++++++++++++++++++++++++++++-
 CodeSamples/count/atomic_hps.png | Bin 3113 -> 3120 bytes
 CodeSamples/count/plots.sh       |   2 +-
 count/count.tex                  |  12 ++--
 4 files changed, 117 insertions(+), 8 deletions(-)
Signature · 1 line
2.17.1
#5 lore raw

RFC PATCH 1/1 count: Merge tables of statistical and limited counter performance

From 0e0d8d79f0416bcbe284d8d191bd76a74f352f14 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 27 Oct 2019 22:07:59 +0900
Subject: [RFC PATCH] count: Merge tables of statistical and limited counter performance

To help comparison of performance of various counter algorithms, merge the tables and align data of both statistical and limited counters.
Also update the wording of references to the merged table.

---
Hi Paul,

Quoted 3 lines

Would it make sense to rotate the "Exact?" heading 90 degrees and to put the "(ns)" underneath the "Updates"? Those two changes might make Figure 5.2 fit horizontally.

Another idea is to merge those 2 tables and align performance results vertically, which this RFC patch attempts to do.

As the "Exact?" column is irrelevant to statistical counters, I made those cells look blank.

How does this look to you?

Thanks, Akira

Signature · 2 lines
 count/count.tex | 96 +++++++++++++++++++------------------------------
 1 file changed, 37 insertions(+), 59 deletions(-)
count/count.tex +37 -59
index 6430abd5..cff56d72 100644
@@ -2817,33 +2817,43 @@ will expand on these lessons.
 \rowcolors{4}{}{lightgray}
 \renewcommand*{\arraystretch}{1.1}
 \small
-\centering\OneColumnHSpace{-.25in}
-\begin{tabular}{lrS[table-format=1.1]S[table-format=3.0]S[table-format=4.0]
+\centering\OneColumnHSpace{-.35in}
+\newcommand{\NA}{\cellcolor{white}}
+\begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
 		  S[table-format=6.0]S[table-format=6.0]}
 	\toprule
-	& & & \multicolumn{4}{c}{Reads (ns)} \\
-	\cmidrule{4-7}
-	Algorithm & Section & \multicolumn{1}{r}{Updates (ns)} &
+	& & & \multicolumn{1}{c}{Updates} & \multicolumn{4}{c}{Reads (ns)} \\
+	\cmidrule{5-8}
+	Algorithm & Section & Exact? & \multicolumn{1}{r}{(ns)} &
 				    \multicolumn{1}{r}{1 CPU} &
 					\multicolumn{1}{r}{8 CPUs} &
 					    \multicolumn{1}{r}{64 CPUs} &
 						\multicolumn{1}{r}{420 CPUs} \\
 		\midrule
-		\path{count_stat.c} & \ref{sec:count:Array-Based Implementation} &
+		\path{count_stat.c} & \ref{sec:count:Array-Based Implementation} & \NA &
 		 6.3 & 294 & 303   & 315     &    612 \\
-	\path{count_stat_eventual.c} & \ref{sec:count:Eventually Consistent Implementation} &
+	\path{count_stat_eventual.c} & \ref{sec:count:Eventually Consistent Implementation} & \NA &
 		 6.4 &   1 &   1   &   1     &      1 \\
-	\path{count_end.c} & \ref{sec:count:Per-Thread-Variable-Based Implementation} &
+	\path{count_end.c} & \ref{sec:count:Per-Thread-Variable-Based Implementation} & \NA &
 		 2.9 & 301 & 6 309 & 147 594 & 239 683 \\
-	\path{count_end_rcu.c} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} &
+	\path{count_end_rcu.c} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} & \NA &
 		 2.9 & 454 &   481 &     508 &   2 317 \\
+	\midrule
+	\path{count_lim.c} & \ref{sec:count:Simple Limit Counter Implementation} &
+		N &  3.2 & 435 & 6 678 & 156 175 & 239 422 \\
+	\path{count_lim_app.c} & \ref{sec:count:Approximate Limit Counter Implementation} &
+		N &  2.4 & 485 & 7 041 & 173 108 & 239 682 \\
+	\path{count_lim_atomic.c} & \ref{sec:count:Atomic Limit Counter Implementation} &
+		Y & 19.7 & 513 & 7 085 & 199 957 & 239 450 \\
+	\path{count_lim_sig.c} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
+		Y &  4.7 & 519 & 6 805 & 120 000 & 238 811 \\
 	\bottomrule
 \end{tabular}
-\caption{Statistical Counter Performance on x86}
-\label{tab:count:Statistical Counter Performance on x86}
+\caption{Statistical/Limit Counter Performance on x86}
+\label{tab:count:Statistical/Limit Counter Performance on x86}
 \end{table*}
 
-Table~\ref{tab:count:Statistical Counter Performance on x86}
+The top half of \cref{tab:count:Statistical/Limit Counter Performance on x86}
 shows the performance of the four parallel statistical counting
 algorithms.
 All four algorithms provide near-perfect linear scalability for updates.
@@ -2856,13 +2866,13 @@ This contention can be addressed using the deferred-processing
 techniques introduced in
 Chapter~\ref{chp:Deferred Processing},
 as shown on the \path{count_end_rcu.c} row of
-Table~\ref{tab:count:Statistical Counter Performance on x86}.
+\cref{tab:count:Statistical/Limit Counter Performance on x86}.
 Deferred processing also shines on the \path{count_stat_eventual.c} row,
 courtesy of eventual consistency.
 
 \QuickQuiz{}
 	On the \path{count_stat.c} row of
-	Table~\ref{tab:count:Statistical Counter Performance on x86},
+	\cref{tab:count:Statistical/Limit Counter Performance on x86},
 	we see that the read-side scales linearly with the number of
 	threads.
 	How is that possible given that the more threads there are,
@@ -2878,8 +2888,8 @@ courtesy of eventual consistency.
 } \QuickQuizEnd
 
 \QuickQuiz{}
-	Even on the last row of
-	Table~\ref{tab:count:Statistical Counter Performance on x86},
+	Even on the fourth row of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86},
 	the read-side performance of these statistical counter
 	implementations is pretty horrible.
 	So why bother with them?
@@ -2890,8 +2900,8 @@ courtesy of eventual consistency.
 	Figure~\ref{fig:count:Atomic Increment Scalability on x86},
 	single-variable atomic increment need not apply for any job
 	involving heavy use of parallel updates.
-	In contrast, the algorithms shown in
-	Table~\ref{tab:count:Statistical Counter Performance on x86}
+	In contrast, the algorithms shown in the top half of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}
 	do an excellent job of handling update-heavy situations.
 	Of course, if you have a read-mostly situation, you should
 	use something else, for example, an eventually consistent design
@@ -2901,37 +2911,7 @@ courtesy of eventual consistency.
 	Section~\ref{sec:count:Eventually Consistent Implementation}.
 } \QuickQuizEnd
 
-\begin{table*}
-\rowcolors{4}{}{lightgray}
-\renewcommand*{\arraystretch}{1.1}
-\small
-\centering\OneColumnHSpace{-.4in}
-\begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
-		   S[table-format=6.0]S[table-format=6.0]}
-	\toprule
-	& & & & \multicolumn{4}{c}{Reads (ns)} \\
-	\cmidrule{5-8}
-	Algorithm & Section & Exact? & \multicolumn{1}{r}{Updates (ns)} &
-					\multicolumn{1}{r}{1 CPU} &
-					 \multicolumn{1}{r}{8 CPUs} &
-					  \multicolumn{1}{r}{64 CPUs} &
-					   \multicolumn{1}{r}{420 CPUs} \\
-	\midrule
-	\path{count_lim.c} & \ref{sec:count:Simple Limit Counter Implementation} &
-		N &  3.2 & 435 & 6 678 & 156 175 & 239 422 \\
-	\path{count_lim_app.c} & \ref{sec:count:Approximate Limit Counter Implementation} &
-		N &  2.4 & 485 & 7 041 & 173 108 & 239 682 \\
-	\path{count_lim_atomic.c} & \ref{sec:count:Atomic Limit Counter Implementation} &
-		Y & 19.7 & 513 & 7 085 & 199 957 & 239 450 \\
-	\path{count_lim_sig.c} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
-		Y &  4.7 & 519 & 6 805 & 120 000 & 238 811 \\
-	\bottomrule
-\end{tabular}
-\caption{Limit Counter Performance on x86}
-\label{tab:count:Limit Counter Performance on x86}
-\end{table*}
-
-Table~\ref{tab:count:Limit Counter Performance on x86}
+The bottom half of \cref{tab:count:Statistical/Limit Counter Performance on x86}
 shows the performance of the parallel limit-counting algorithms.
 Exact enforcement of the limits incurs a substantial performance
 penalty, although on this x86 system that penalty can be reduced
@@ -2940,8 +2920,8 @@ All of these implementations suffer from read-side lock contention
 in the face of concurrent readers.
 
 \QuickQuiz{}
-	Given the performance data shown in
-	Table~\ref{tab:count:Limit Counter Performance on x86},
+	Given the performance data shown in the bottom half of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86},
 	we should always prefer signals over atomic operations, right?
 \QuickQuizAnswer{
 	That depends on the workload.
@@ -2962,8 +2942,8 @@ in the face of concurrent readers.
 
 \QuickQuiz{}
 	Can advanced techniques be applied to address the lock
-	contention for readers seen in
-	Table~\ref{tab:count:Limit Counter Performance on x86}?
+	contention for readers seen in the bottom half of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}?
 \QuickQuizAnswer{
 	One approach is to give up some update-side performance, as is
 	done with scalable non-zero indicators
@@ -3126,8 +3106,7 @@ operations, so that a great many of these cheap operations are handled
 by a single synchronization operation.
 Batching optimizations of one sort or another are used by each of
 the counting algorithms listed in
-Tables~\ref{tab:count:Statistical Counter Performance on x86}
-and~\ref{tab:count:Limit Counter Performance on x86}.
+\cref{tab:count:Statistical/Limit Counter Performance on x86}.
 
 Finally, the eventually consistent statistical counter discussed in
 Section~\ref{sec:count:Eventually Consistent Implementation}
@@ -3158,20 +3137,19 @@ Summarizing the summary:
 	thereby decreasing synchronization overhead, in turn
 	improving performance and scalability.
 	All the algorithms shown in
-	Tables~\ref{tab:count:Statistical Counter Performance on x86}
-	and~\ref{tab:count:Limit Counter Performance on x86}
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}
 	make heavy use of batching.
 \item	Read-only code paths should remain read-only:  Spurious
 	synchronization writes to shared memory kill performance
 	and scalability, as seen in the \path{count_end.c} row of
-	Table~\ref{tab:count:Statistical Counter Performance on x86}.
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}.
 \item	Judicious use of delay promotes performance and scalability, as
 	seen in Section~\ref{sec:count:Eventually Consistent Implementation}.
 \item	Parallel performance and scalability is usually a balancing act:
 	Beyond a certain point, optimizing some code paths will degrade
 	others.
 	The \path{count_stat.c} and \path{count_end_rcu.c} rows of
-	Table~\ref{tab:count:Statistical Counter Performance on x86}
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}
 	illustrate this point.
 \item	Different levels of performance and scalability will affect
 	algorithm and data-structure design, as do a large number of
Signature · 1 line
2.17.1
#6 lore raw

Re: [RFC PATCH] count: Merge tables of statistical and limited counter performance

Quoted 18 lines · Akira Yokosawa
Quoted 1 line

From 0e0d8d79f0416bcbe284d8d191bd76a74f352f14 Mon Sep 17 00:00:00 2001

From: Akira Yokosawa <[email protected]>
Date: Sun, 27 Oct 2019 22:07:59 +0900
Subject: [RFC PATCH] count: Merge tables of statistical and limited counter performance

To help comparison of performance of various counter algorithms, merge the tables and align data of both statistical and limited counters.
Also update the wording of references to the merged table.

---
Hi Paul,

Quoted 3 lines

Would it make sense to rotate the "Exact?" heading 90 degrees and to put the "(ns)" underneath the "Updates"? Those two changes might make Figure 5.2 fit horizontally.

Quoted 7 lines

Another idea is to merge those 2 tables and align performance results vertically, which this RFC patch attempts to do.

As the "Exact?" column is irrelevant to statistical counters, I made those cells look blank.

How does this look to you?

Good improvement, queued and pushed, thank you!

I couldn't resist trying rotating the "Exact?" heading, though there has to be a better way to do this. Thoughts? (Feel free to provide an alternative, and I will be happy to replace my attempt with it.)

Another thing would be to make the "Algorithms" heading be something like "Algorithms: \co{count_*.c}", then trim the leading "count_" and trailing ".c" from each row's first column. Would that make sense?

Thanx, Paul

Quoted 202 lines

Thanks, Akira

Signature · 2 lines
 count/count.tex | 96 +++++++++++++++++++------------------------------
 1 file changed, 37 insertions(+), 59 deletions(-)
count/count.tex +37 -59
index 6430abd5..cff56d72 100644
@@ -2817,33 +2817,43 @@ will expand on these lessons.
 \rowcolors{4}{}{lightgray}
 \renewcommand*{\arraystretch}{1.1}
 \small
-\centering\OneColumnHSpace{-.25in}
-\begin{tabular}{lrS[table-format=1.1]S[table-format=3.0]S[table-format=4.0]
+\centering\OneColumnHSpace{-.35in}
+\newcommand{\NA}{\cellcolor{white}}
+\begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
 		  S[table-format=6.0]S[table-format=6.0]}
 	\toprule
-	& & & \multicolumn{4}{c}{Reads (ns)} \\
-	\cmidrule{4-7}
-	Algorithm & Section & \multicolumn{1}{r}{Updates (ns)} &
+	& & & \multicolumn{1}{c}{Updates} & \multicolumn{4}{c}{Reads (ns)} \\
+	\cmidrule{5-8}
+	Algorithm & Section & Exact? & \multicolumn{1}{r}{(ns)} &
 				    \multicolumn{1}{r}{1 CPU} &
 					\multicolumn{1}{r}{8 CPUs} &
 					    \multicolumn{1}{r}{64 CPUs} &
 						\multicolumn{1}{r}{420 CPUs} \\
 		\midrule
-		\path{count_stat.c} & \ref{sec:count:Array-Based Implementation} &
+		\path{count_stat.c} & \ref{sec:count:Array-Based Implementation} & \NA &
 		 6.3 & 294 & 303   & 315     &    612 \\
-	\path{count_stat_eventual.c} & \ref{sec:count:Eventually Consistent Implementation} &
+	\path{count_stat_eventual.c} & \ref{sec:count:Eventually Consistent Implementation} & \NA &
 		 6.4 &   1 &   1   &   1     &      1 \\
-	\path{count_end.c} & \ref{sec:count:Per-Thread-Variable-Based Implementation} &
+	\path{count_end.c} & \ref{sec:count:Per-Thread-Variable-Based Implementation} & \NA &
 		 2.9 & 301 & 6 309 & 147 594 & 239 683 \\
-	\path{count_end_rcu.c} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} &
+	\path{count_end_rcu.c} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} & \NA &
 		 2.9 & 454 &   481 &     508 &   2 317 \\
+	\midrule
+	\path{count_lim.c} & \ref{sec:count:Simple Limit Counter Implementation} &
+		N &  3.2 & 435 & 6 678 & 156 175 & 239 422 \\
+	\path{count_lim_app.c} & \ref{sec:count:Approximate Limit Counter Implementation} &
+		N &  2.4 & 485 & 7 041 & 173 108 & 239 682 \\
+	\path{count_lim_atomic.c} & \ref{sec:count:Atomic Limit Counter Implementation} &
+		Y & 19.7 & 513 & 7 085 & 199 957 & 239 450 \\
+	\path{count_lim_sig.c} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
+		Y &  4.7 & 519 & 6 805 & 120 000 & 238 811 \\
 	\bottomrule
 \end{tabular}
-\caption{Statistical Counter Performance on x86}
-\label{tab:count:Statistical Counter Performance on x86}
+\caption{Statistical/Limit Counter Performance on x86}
+\label{tab:count:Statistical/Limit Counter Performance on x86}
 \end{table*}
 
-Table~\ref{tab:count:Statistical Counter Performance on x86}
+The top half of \cref{tab:count:Statistical/Limit Counter Performance on x86}
 shows the performance of the four parallel statistical counting
 algorithms.
 All four algorithms provide near-perfect linear scalability for updates.
@@ -2856,13 +2866,13 @@ This contention can be addressed using the deferred-processing
 techniques introduced in
 Chapter~\ref{chp:Deferred Processing},
 as shown on the \path{count_end_rcu.c} row of
-Table~\ref{tab:count:Statistical Counter Performance on x86}.
+\cref{tab:count:Statistical/Limit Counter Performance on x86}.
 Deferred processing also shines on the \path{count_stat_eventual.c} row,
 courtesy of eventual consistency.
 
 \QuickQuiz{}
 	On the \path{count_stat.c} row of
-	Table~\ref{tab:count:Statistical Counter Performance on x86},
+	\cref{tab:count:Statistical/Limit Counter Performance on x86},
 	we see that the read-side scales linearly with the number of
 	threads.
 	How is that possible given that the more threads there are,
@@ -2878,8 +2888,8 @@ courtesy of eventual consistency.
 } \QuickQuizEnd
 
 \QuickQuiz{}
-	Even on the last row of
-	Table~\ref{tab:count:Statistical Counter Performance on x86},
+	Even on the fourth row of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86},
 	the read-side performance of these statistical counter
 	implementations is pretty horrible.
 	So why bother with them?
@@ -2890,8 +2900,8 @@ courtesy of eventual consistency.
 	Figure~\ref{fig:count:Atomic Increment Scalability on x86},
 	single-variable atomic increment need not apply for any job
 	involving heavy use of parallel updates.
-	In contrast, the algorithms shown in
-	Table~\ref{tab:count:Statistical Counter Performance on x86}
+	In contrast, the algorithms shown in the top half of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}
 	do an excellent job of handling update-heavy situations.
 	Of course, if you have a read-mostly situation, you should
 	use something else, for example, an eventually consistent design
@@ -2901,37 +2911,7 @@ courtesy of eventual consistency.
 	Section~\ref{sec:count:Eventually Consistent Implementation}.
 } \QuickQuizEnd
 
-\begin{table*}
-\rowcolors{4}{}{lightgray}
-\renewcommand*{\arraystretch}{1.1}
-\small
-\centering\OneColumnHSpace{-.4in}
-\begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
-		   S[table-format=6.0]S[table-format=6.0]}
-	\toprule
-	& & & & \multicolumn{4}{c}{Reads (ns)} \\
-	\cmidrule{5-8}
-	Algorithm & Section & Exact? & \multicolumn{1}{r}{Updates (ns)} &
-					\multicolumn{1}{r}{1 CPU} &
-					 \multicolumn{1}{r}{8 CPUs} &
-					  \multicolumn{1}{r}{64 CPUs} &
-					   \multicolumn{1}{r}{420 CPUs} \\
-	\midrule
-	\path{count_lim.c} & \ref{sec:count:Simple Limit Counter Implementation} &
-		N &  3.2 & 435 & 6 678 & 156 175 & 239 422 \\
-	\path{count_lim_app.c} & \ref{sec:count:Approximate Limit Counter Implementation} &
-		N &  2.4 & 485 & 7 041 & 173 108 & 239 682 \\
-	\path{count_lim_atomic.c} & \ref{sec:count:Atomic Limit Counter Implementation} &
-		Y & 19.7 & 513 & 7 085 & 199 957 & 239 450 \\
-	\path{count_lim_sig.c} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
-		Y &  4.7 & 519 & 6 805 & 120 000 & 238 811 \\
-	\bottomrule
-\end{tabular}
-\caption{Limit Counter Performance on x86}
-\label{tab:count:Limit Counter Performance on x86}
-\end{table*}
-
-Table~\ref{tab:count:Limit Counter Performance on x86}
+The bottom half of \cref{tab:count:Statistical/Limit Counter Performance on x86}
 shows the performance of the parallel limit-counting algorithms.
 Exact enforcement of the limits incurs a substantial performance
 penalty, although on this x86 system that penalty can be reduced
@@ -2940,8 +2920,8 @@ All of these implementations suffer from read-side lock contention
 in the face of concurrent readers.
 
 \QuickQuiz{}
-	Given the performance data shown in
-	Table~\ref{tab:count:Limit Counter Performance on x86},
+	Given the performance data shown in the bottom half of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86},
 	we should always prefer signals over atomic operations, right?
 \QuickQuizAnswer{
 	That depends on the workload.
@@ -2962,8 +2942,8 @@ in the face of concurrent readers.
 
 \QuickQuiz{}
 	Can advanced techniques be applied to address the lock
-	contention for readers seen in
-	Table~\ref{tab:count:Limit Counter Performance on x86}?
+	contention for readers seen in the bottom half of
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}?
 \QuickQuizAnswer{
 	One approach is to give up some update-side performance, as is
 	done with scalable non-zero indicators
@@ -3126,8 +3106,7 @@ operations, so that a great many of these cheap operations are handled
 by a single synchronization operation.
 Batching optimizations of one sort or another are used by each of
 the counting algorithms listed in
-Tables~\ref{tab:count:Statistical Counter Performance on x86}
-and~\ref{tab:count:Limit Counter Performance on x86}.
+\cref{tab:count:Statistical/Limit Counter Performance on x86}.
 
 Finally, the eventually consistent statistical counter discussed in
 Section~\ref{sec:count:Eventually Consistent Implementation}
@@ -3158,20 +3137,19 @@ Summarizing the summary:
 	thereby decreasing synchronization overhead, in turn
 	improving performance and scalability.
 	All the algorithms shown in
-	Tables~\ref{tab:count:Statistical Counter Performance on x86}
-	and~\ref{tab:count:Limit Counter Performance on x86}
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}
 	make heavy use of batching.
 \item	Read-only code paths should remain read-only:  Spurious
 	synchronization writes to shared memory kill performance
 	and scalability, as seen in the \path{count_end.c} row of
-	Table~\ref{tab:count:Statistical Counter Performance on x86}.
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}.
 \item	Judicious use of delay promotes performance and scalability, as
 	seen in Section~\ref{sec:count:Eventually Consistent Implementation}.
 \item	Parallel performance and scalability is usually a balancing act:
 	Beyond a certain point, optimizing some code paths will degrade
 	others.
 	The \path{count_stat.c} and \path{count_end_rcu.c} rows of
-	Table~\ref{tab:count:Statistical Counter Performance on x86}
+	\cref{tab:count:Statistical/Limit Counter Performance on x86}
 	illustrate this point.
 \item	Different levels of performance and scalability will affect
 	algorithm and data-structure design, as do a large number of
Signature · 1 line
2.17.1
#7 lore raw

PATCH 1/1 count: Reduce width of performance table

From a4f6e08b2ef23b39eed420e0f1595affbb624c5f Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 28 Oct 2019 22:29:17 +0900
Subject: [PATCH] count: Reduce width of performance table

Reperesent algorithm names by unique part of their path names. To shrink vertical spaces in the heading, use "picture" environment and tweak placement manually.

By this change, the table now fits the 1c width and we can get rid of \OneColumnHSpace{}.

---

Quoted 3 lines · Paul E. McKenney

Another thing would be to make the "Algorithms" heading be something like "Algorithms: \co{count_*.c}", then trim the leading "count_" and trailing ".c" from each row's first column. Would that make sense?

This patch manages to do the tweak.
It might be over-engineering to do this level of tuning in the header. But at least it looks much better than what it would do without using \multirow{} and "picture" environment.

As you said, there might be alternative to do this at a higher level of LaTeX code. I'll see to it (with lower priority).

Thanks, Akira

Quoted 2 lines

Thanx, Paul

--

 count/count.tex | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)
count/count.tex +16 -12
index 1a8d7bf3..3820a551 100644
@@ -2817,36 +2817,40 @@ will expand on these lessons.
 \rowcolors{4}{}{lightgray}
 \renewcommand*{\arraystretch}{1.1}
 \small
-\centering\OneColumnHSpace{-.35in}
+\centering
 \newcommand{\NA}{\cellcolor{white}}
 \begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
 		  S[table-format=6.0]S[table-format=6.0]}
 	\toprule
-	& & \multirow{2}{*}{\begin{picture}(6,50)(0,-24)\rotatebox{90}{Exact?}\end{picture}} &
-		\multicolumn{1}{c}{Updates} & \multicolumn{4}{c}{Reads (ns)} \\
+	\multirow{2}{*}{\begin{picture}(60,15)(0,-3)\put(0,0){Algorithm}
+			\put(14,-10){(\path{count_*.c})}\end{picture}} &
+	    & \multirow{2}{*}{\begin{picture}(6,50)(0,-24)\rotatebox{90}{Exact?}\end{picture}} &
+		\multicolumn{1}{c}{\multirow{2}{*}{\begin{picture}(30,15)(0,-3)
+			\put(0,0){Updates}\put(15,-10){(ns)}\end{picture}}} &
+			\multicolumn{4}{c}{Reads (ns)} \\
 	\cmidrule{5-8}
-	Algorithm & Section & & \multicolumn{1}{c}{(ns)} &
+	    & Section & & &
 				   \multicolumn{1}{r}{1 CPU} &
 				      \multicolumn{1}{r}{8 CPUs} &
 					 \multicolumn{1}{r}{64 CPUs} &
 					    \multicolumn{1}{r}{420 CPUs} \\
 		\midrule
-		\path{count_stat.c} & \ref{sec:count:Array-Based Implementation} & \NA &
+		\path{stat} & \ref{sec:count:Array-Based Implementation} & \NA &
 		 6.3 & 294 & 303   & 315     &    612 \\
-	\path{count_stat_eventual.c} & \ref{sec:count:Eventually Consistent Implementation} & \NA &
+	\path{stat_eventual} & \ref{sec:count:Eventually Consistent Implementation} & \NA &
 		 6.4 &   1 &   1   &   1     &      1 \\
-	\path{count_end.c} & \ref{sec:count:Per-Thread-Variable-Based Implementation} & \NA &
+	\path{end} & \ref{sec:count:Per-Thread-Variable-Based Implementation} & \NA &
 		 2.9 & 301 & 6 309 & 147 594 & 239 683 \\
-	\path{count_end_rcu.c} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} & \NA &
+	\path{end_rcu} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} & \NA &
 		 2.9 & 454 &   481 &     508 &   2 317 \\
 	\midrule
-	\path{count_lim.c} & \ref{sec:count:Simple Limit Counter Implementation} &
+	\path{lim} & \ref{sec:count:Simple Limit Counter Implementation} &
 		N &  3.2 & 435 & 6 678 & 156 175 & 239 422 \\
-	\path{count_lim_app.c} & \ref{sec:count:Approximate Limit Counter Implementation} &
+	\path{lim_app} & \ref{sec:count:Approximate Limit Counter Implementation} &
 		N &  2.4 & 485 & 7 041 & 173 108 & 239 682 \\
-	\path{count_lim_atomic.c} & \ref{sec:count:Atomic Limit Counter Implementation} &
+	\path{lim_atomic} & \ref{sec:count:Atomic Limit Counter Implementation} &
 		Y & 19.7 & 513 & 7 085 & 199 957 & 239 450 \\
-	\path{count_lim_sig.c} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
+	\path{lim_sig} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
 		Y &  4.7 & 519 & 6 805 & 120 000 & 238 811 \\
 	\bottomrule
 \end{tabular}
Signature · 1 line
2.17.1
#8 lore raw

Re: [PATCH] count: Reduce width of performance table

Quoted 17 lines · Akira Yokosawa
Quoted 1 line

From a4f6e08b2ef23b39eed420e0f1595affbb624c5f Mon Sep 17 00:00:00 2001

From: Akira Yokosawa <[email protected]>
Date: Mon, 28 Oct 2019 22:29:17 +0900
Subject: [PATCH] count: Reduce width of performance table

Reperesent algorithm names by unique part of their path names. To shrink vertical spaces in the heading, use "picture" environment and tweak placement manually.

By this change, the table now fits the 1c width and we can get rid of \OneColumnHSpace{}.

---
On Sun, 27 Oct 2019 10:09:22 -0700, Paul E. McKenney wrote:

Quoted 8 lines
Quoted 3 lines

Another thing would be to make the "Algorithms" heading be something like "Algorithms: \co{count_*.c}", then trim the leading "count_" and trailing ".c" from each row's first column. Would that make sense?

This patch manages to do the tweak.
It might be over-engineering to do this level of tuning in the header. But at least it looks much better than what it would do without using \multirow{} and "picture" environment.

Completely agreed, so queued and pushed, thank you!

Quoted 2 lines

As you said, there might be alternative to do this at a higher level of LaTeX code. I'll see to it (with lower priority).

The strange thing is that \multirow seems to want \picture. But yes, as you say, lower priority.

Thanx, Paul

Quoted 69 lines

Thanks, Akira

Quoted 2 lines

Thanx, Paul

--

 count/count.tex | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)
count/count.tex +16 -12
index 1a8d7bf3..3820a551 100644
@@ -2817,36 +2817,40 @@ will expand on these lessons.
 \rowcolors{4}{}{lightgray}
 \renewcommand*{\arraystretch}{1.1}
 \small
-\centering\OneColumnHSpace{-.35in}
+\centering
 \newcommand{\NA}{\cellcolor{white}}
 \begin{tabular}{lrcS[table-format=2.1]S[table-format=3.0]S[table-format=4.0]
 		  S[table-format=6.0]S[table-format=6.0]}
 	\toprule
-	& & \multirow{2}{*}{\begin{picture}(6,50)(0,-24)\rotatebox{90}{Exact?}\end{picture}} &
-		\multicolumn{1}{c}{Updates} & \multicolumn{4}{c}{Reads (ns)} \\
+	\multirow{2}{*}{\begin{picture}(60,15)(0,-3)\put(0,0){Algorithm}
+			\put(14,-10){(\path{count_*.c})}\end{picture}} &
+	    & \multirow{2}{*}{\begin{picture}(6,50)(0,-24)\rotatebox{90}{Exact?}\end{picture}} &
+		\multicolumn{1}{c}{\multirow{2}{*}{\begin{picture}(30,15)(0,-3)
+			\put(0,0){Updates}\put(15,-10){(ns)}\end{picture}}} &
+			\multicolumn{4}{c}{Reads (ns)} \\
 	\cmidrule{5-8}
-	Algorithm & Section & & \multicolumn{1}{c}{(ns)} &
+	    & Section & & &
 				   \multicolumn{1}{r}{1 CPU} &
 				      \multicolumn{1}{r}{8 CPUs} &
 					 \multicolumn{1}{r}{64 CPUs} &
 					    \multicolumn{1}{r}{420 CPUs} \\
 		\midrule
-		\path{count_stat.c} & \ref{sec:count:Array-Based Implementation} & \NA &
+		\path{stat} & \ref{sec:count:Array-Based Implementation} & \NA &
 		 6.3 & 294 & 303   & 315     &    612 \\
-	\path{count_stat_eventual.c} & \ref{sec:count:Eventually Consistent Implementation} & \NA &
+	\path{stat_eventual} & \ref{sec:count:Eventually Consistent Implementation} & \NA &
 		 6.4 &   1 &   1   &   1     &      1 \\
-	\path{count_end.c} & \ref{sec:count:Per-Thread-Variable-Based Implementation} & \NA &
+	\path{end} & \ref{sec:count:Per-Thread-Variable-Based Implementation} & \NA &
 		 2.9 & 301 & 6 309 & 147 594 & 239 683 \\
-	\path{count_end_rcu.c} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} & \NA &
+	\path{end_rcu} & \ref{sec:together:RCU and Per-Thread-Variable-Based Statistical Counters} & \NA &
 		 2.9 & 454 &   481 &     508 &   2 317 \\
 	\midrule
-	\path{count_lim.c} & \ref{sec:count:Simple Limit Counter Implementation} &
+	\path{lim} & \ref{sec:count:Simple Limit Counter Implementation} &
 		N &  3.2 & 435 & 6 678 & 156 175 & 239 422 \\
-	\path{count_lim_app.c} & \ref{sec:count:Approximate Limit Counter Implementation} &
+	\path{lim_app} & \ref{sec:count:Approximate Limit Counter Implementation} &
 		N &  2.4 & 485 & 7 041 & 173 108 & 239 682 \\
-	\path{count_lim_atomic.c} & \ref{sec:count:Atomic Limit Counter Implementation} &
+	\path{lim_atomic} & \ref{sec:count:Atomic Limit Counter Implementation} &
 		Y & 19.7 & 513 & 7 085 & 199 957 & 239 450 \\
-	\path{count_lim_sig.c} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
+	\path{lim_sig} & \ref{sec:count:Signal-Theft Limit Counter Implementation} &
 		Y &  4.7 & 519 & 6 805 & 120 000 & 238 811 \\
 	\bottomrule
 \end{tabular}
Signature · 1 line
2.17.1