Fixes to recent updates in count
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
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
@@ -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
PATCH 2/3 count: Add dashed line indicating ideal time of (non-atomic) increment
In reply to Akira YokosawaFrom 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
@@ -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
CodeSamples/count/plots.sh +1 -1
@@ -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
PATCH 3/3 count: Update CPU type/system
In reply to Akira YokosawaFrom 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
@@ -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
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/systemCodeSamples/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
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
@@ -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
Re: [RFC PATCH] count: Merge tables of statistical and limited counter performance
Quoted 18 lines · Akira Yokosawa
Quoted 1 line
From
0e0d8d79f0416bcbe284d8d191bd76a74f352f14Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Sun, 27 Oct 2019 22:07:59 +0900
Subject: [RFC PATCH] count: Merge tables of statistical and limited counter performanceTo 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.Signed-off-by Akira Yokosawa <[email protected]>---
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@@ -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 ofSignature · 1 line
2.17.1
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
@@ -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
Re: [PATCH] count: Reduce width of performance table
Quoted 17 lines · Akira Yokosawa
Quoted 1 line
From
a4f6e08b2ef23b39eed420e0f1595affbb624c5fMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 28 Oct 2019 22:29:17 +0900
Subject: [PATCH] count: Reduce width of performance tableReperesent 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{}.
Suggested-by Paul E. McKenney <[email protected]>Signed-off-by Akira Yokosawa <[email protected]>---
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@@ -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