Changing non-volatile access to volatile in counter examples
This series changes some of the counter examples to use volatile access, to avoid overly eager compilers/linkers to optimise out necessary reads/writes.
PATCH 1/4 Changing counttorture defaults.
From: "Palik, Imre" <[email protected]>
As the counter implementations are supposed to implement write-mostly parallelism, this patch changes the default behaviour of counttorture to reflect it.
--- CodeSamples/count/counttorture.h | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
CodeSamples/count/counttorture.h +6 -6
@@ -164,19 +164,19 @@ void perftestrun(int nthreads, int nreaders, int nupdaters)exit (EXIT_SUCCESS ); } -void perftest (int nreaders,int cpustride) +void perftest (int nwriters,int cpustride) {int i;long arg; -perftestinit (nreaders +1 ); -for (i =0 ; i < nreaders; i++) { +perftestinit (nwriters +1 ); +for (i =0 ; i < nwriters; i++) { arg = (long )(i * cpustride); -create_thread (count_read_perf_test, (void *)arg); +create_thread (count_update_perf_test, (void *)arg); } arg = (long )(i * cpustride); -create_thread (count_update_perf_test, (void *)arg); -perftestrun (i +1 , nreaders,1 ); +create_thread (count_read_perf_test, (void *)arg); +perftestrun (i +1 ,1 , nwriters); }void rperftest (int nreaders,int cpustride)
Signature · 1 line
2.7.4
PATCH 2/4 Making the counter implementations safer
In reply to Imre PalikFrom: "Palik, Imre" <[email protected]>
Relevant parts of some of the counter implementations were prone to be optimised out by an overly eager compiler/linker.
This patch makes the compiler's task easier, by declaring big parts of the implementation inline. Then proceeds to fix the issue.
Some barriers from the countertorture framework also got removed, as a proper multithreaded implementation should provide its own ordering guarantees.
--- CodeSamples/count/Makefile | 30 ++++++++++++++++-------------- CodeSamples/count/count_atomic.c | 6 +++--- CodeSamples/count/count_end.c | 9 +++++---- CodeSamples/count/count_end_rcu.c | 7 ++++--- CodeSamples/count/count_nonatomic.c | 8 ++++---- CodeSamples/count/count_stack.c | 9 +++++---- CodeSamples/count/count_stat.c | 6 +++--- CodeSamples/count/count_stat_atomic.c | 6 +++--- CodeSamples/count/count_stat_eventual.c | 2 +- CodeSamples/count/count_tstat.c | 3 ++- CodeSamples/count/counttorture.h | 2 -- 11 files changed, 46 insertions(+), 42 deletions(-)
CodeSamples/count/Makefile +16 -14
@@ -43,49 +43,51 @@ else all: $(PROGS) endif +CC?=cc + include $(top)/recipes.mk count_atomic: count_atomic.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_atomic count_atomic.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_atomic count_atomic.c -lpthread count_end: count_end.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_end count_end.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_end count_end.c -lpthread count_end_rcu: count_end_rcu.c ../api.h counttorture.h $(RCU_SRCS) - cc $(GCC_ARGS) $(CFLAGS) -o count_end_rcu count_end_rcu.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_end_rcu count_end_rcu.c -lpthread count_lim: count_lim.c ../api.h limtorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_lim count_lim.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_lim count_lim.c -lpthread count_lim_app: count_lim_app.c ../api.h limtorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_lim_app count_lim_app.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_lim_app count_lim_app.c -lpthread count_lim_atomic: count_lim_atomic.c ../api.h limtorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_lim_atomic count_lim_atomic.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_lim_atomic count_lim_atomic.c -lpthread count_lim_sig: count_lim_sig.c ../api.h limtorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_lim_sig count_lim_sig.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_lim_sig count_lim_sig.c -lpthread count_limd: count_limd.c ../api.h limtorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_limd count_limd.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_limd count_limd.c -lpthread count_nonatomic: count_nonatomic.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_nonatomic count_nonatomic.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_nonatomic count_nonatomic.c -lpthread count_stack: count_stack.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_stack count_stack.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_stack count_stack.c -lpthread count_stat: count_stat.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_stat count_stat.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_stat count_stat.c -lpthread count_stat_atomic: count_stat_atomic.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_stat_atomic count_stat_atomic.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_stat_atomic count_stat_atomic.c -lpthread count_stat_eventual: count_stat_eventual.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_stat_eventual count_stat_eventual.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_stat_eventual count_stat_eventual.c -lpthread count_tstat: count_tstat.c ../api.h counttorture.h - cc $(GCC_ARGS) $(CFLAGS) -o count_tstat count_tstat.c -lpthread + $(CC) $(GCC_ARGS) $(CFLAGS) -o count_tstat count_tstat.c -lpthread clean: rm -f $(PROGS)
CodeSamples/count/count_atomic.c +3 -3
@@ -27,16 +27,16 @@ void inc_count(void)atomic_inc (&counter); } -long read_count (void ) +__inline__long read_count (void ) {return atomic_read (&counter); } -void count_init (void ) +__inline__void count_init (void ) { } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_end.c +5 -4
@@ -26,9 +26,10 @@ unsigned long *counterp[NR_THREADS] = { NULL };unsigned long finalcount =0 ;DEFINE_SPINLOCK (final_mutex); -void inc_count (void ) +__inline__void inc_count (void ) { - counter++; +WRITE_ONCE (counter, +READ_ONCE (counter) +1 ); }unsigned long read_count (void )
@@ -45,7 +46,7 @@ unsigned long read_count(void)return sum; } -void count_init (void ) +__inline__void count_init (void ) { }
@@ -68,7 +69,7 @@ void count_unregister_thread(int nthreadsexpected)spin_unlock (&final_mutex); } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_end_rcu.c +4 -3
@@ -32,9 +32,10 @@ unsigned long __thread counter = 0;struct countarray *countarrayp =NULL ;DEFINE_SPINLOCK (final_mutex); -void inc_count (void ) +__inline__void inc_count (void ) { - counter++; +WRITE_ONCE (counter, +READ_ONCE (counter) +1 ); }unsigned long read_count (void )
@@ -94,7 +95,7 @@ void count_unregister_thread(int nthreadsexpected)free (capold); } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_nonatomic.c +4 -4
@@ -23,21 +23,21 @@unsigned long counter =0 ; -void inc_count (void ) +__inline__void inc_count (void ) { counter++; } -unsigned long read_count (void ) +__inline__unsigned long read_count (void ) {return counter; } -void count_init (void ) +__inline__void count_init (void ) { } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_stack.c +5 -4
@@ -26,9 +26,10 @@ unsigned long *counterp[NR_THREADS] = { NULL };unsigned long finalcount =0 ;DEFINE_SPINLOCK (final_mutex); -void inc_count (void ) +__inline__void inc_count (void ) { - (*counter)++; +WRITE_ONCE (*counter, +READ_ONCE (*counter) +1 ); }unsigned long read_count (void )
@@ -45,7 +46,7 @@ unsigned long read_count(void)return sum; } -void count_init (void ) +__inline__void count_init (void ) { }
@@ -69,7 +70,7 @@ void count_unregister_thread(int nthreadsexpected)spin_unlock (&final_mutex); } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_stat.c +3 -3
@@ -27,7 +27,7 @@ void inc_count(void)__get_thread_var (counter)++; } -unsigned long read_count (void ) +__inline__unsigned long read_count (void ) {int t;unsigned long sum =0 ;
@@ -37,11 +37,11 @@ unsigned long read_count(void)return sum; } -void count_init (void ) +__inline__void count_init (void ) { } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_stat_atomic.c +3 -3
@@ -27,7 +27,7 @@ void inc_count(void)atomic_inc (&__get_thread_var (counter)); } -unsigned long read_count (void ) +__inline__unsigned long read_count (void ) {int t;unsigned long sum =0 ;
@@ -37,11 +37,11 @@ unsigned long read_count(void)return sum; } -void count_init (void ) +__inline__void count_init (void ) { } -void count_cleanup (void ) +__inline__void count_cleanup (void ) { }
CodeSamples/count/count_stat_eventual.c +1 -1
@@ -31,7 +31,7 @@ void inc_count(void) READ_ONCE(__get_thread_var(counter)) + 1); } -unsigned long read_count (void ) +__inline__unsigned long read_count (void ) {return READ_ONCE (global_count); }
CodeSamples/count/count_tstat.c +2 -1
@@ -29,7 +29,8 @@ DEFINE_SPINLOCK(final_mutex);void inc_count (void ) { - counter++; +WRITE_ONCE (counter, +READ_ONCE (counter) +1 ); }unsigned long read_count (void )/* known failure with counttorture! */
CodeSamples/count/counttorture.h +0 -2
@@ -86,7 +86,6 @@ void *count_read_perf_test(void *arg)while (READ_ONCE (goflag) ==GOFLAG_RUN ) {for (i =COUNT_READ_RUN ; i >0 ; i--) { j +=read_count (); -barrier (); } n_reads_local +=COUNT_READ_RUN ; }
@@ -110,7 +109,6 @@ void *count_update_perf_test(void *arg)while (READ_ONCE (goflag) ==GOFLAG_RUN ) {for (i =COUNT_UPDATE_RUN ; i >0 ; i--) {inc_count (); -barrier (); } n_updates_local +=COUNT_UPDATE_RUN ; }
Signature · 1 line
2.7.4
PATCH 3/4 Updating count.tex with new counter code
In reply to Imre PalikFrom: "Palik, Imre" <[email protected]>
Now count.text reflects the changes made to the counter implementations, to restrict too eager compilers.
--- count/count.tex | 93 +++++++++++++++++++++++++++++---------------------------- 1 file changed, 47 insertions(+), 46 deletions(-)
count/count.tex +47 -46
@@ -1003,41 +1003,42 @@ comes at the cost of the additional thread running \co{eventual()}. 5 6 void inc_count(void) 7 { - 8 counter++; - 9 } - 10 - 11 long read_count(void) - 12 { - 13 int t; - 14 long sum; - 15 - 16 spin_lock(&final_mutex); - 17 sum = finalcount; - 18 for_each_thread(t) - 19 if (counterp[t] != NULL) - 20 sum += *counterp[t]; - 21 spin_unlock(&final_mutex); - 22 return sum; - 23 } - 24 - 25 void count_register_thread(void) - 26 { - 27 int idx = smp_thread_id(); - 28 - 29 spin_lock(&final_mutex); - 30 counterp[idx] = &counter; - 31 spin_unlock(&final_mutex); - 32 } - 33 - 34 void count_unregister_thread(int nthreadsexpected) - 35 { - 36 int idx = smp_thread_id(); - 37 - 38 spin_lock(&final_mutex); - 39 finalcount += counter; - 40 counterp[idx] = NULL; - 41 spin_unlock(&final_mutex); - 42 } + 8 WRITE_ONCE(counter, + 9 READ_ONCE(counter) + 1);counter++; + 10 } + 11 + 12 long read_count(void) + 13 { + 14 int t; + 15 long sum; + 16 + 17 spin_lock(&final_mutex); + 18 sum = finalcount; + 19 for_each_thread(t) + 20 if (counterp[t] != NULL) + 21 sum += *counterp[t]; + 22 spin_unlock(&final_mutex); + 23 return sum; + 24 } + 25 + 26 void count_register_thread(void) + 27 { + 28 int idx = smp_thread_id(); + 29 + 30 spin_lock(&final_mutex); + 31 counterp[idx] = &counter; + 32 spin_unlock(&final_mutex); + 33 } + 34 + 35 void count_unregister_thread(int nthreadsexpected) + 36 { + 37 int idx = smp_thread_id(); + 38 + 39 spin_lock(&final_mutex); + 40 finalcount += counter; + 41 counterp[idx] = NULL; + 42 spin_unlock(&final_mutex); + 43 } \end{verbbox} } \centering
@@ -1105,18 +1106,18 @@ value of the counter and exiting threads. } \QuickQuizEnd The \co{inc_count()} function used by updaters is quite simple, as can -be seen on lines~6-9. +be seen on lines~6-10. The \co{read_count()} function used by readers is a bit more complex. -Line~16 acquires a lock to exclude exiting threads, and line~21 releases +Line~17 acquires a lock to exclude exiting threads, and line~22 releases it. -Line~17 initializes the sum to the count accumulated by those threads that -have already exited, and lines~18-20 sum the counts being accumulated +Line~18 initializes the sum to the count accumulated by those threads that +have already exited, and lines~19-21 sum the counts being accumulated by threads currently running. -Finally, line~22 returns the sum. +Finally, line~23 returns the sum. \QuickQuiz{} - Doesn't the check for \co{NULL} on line~19 of + Doesn't the check for \co{NULL} on line~20 of Listing~\ref{lst:count:Per-Thread Statistical Counters} add extra branch mispredictions? Why not have a variable set permanently to zero, and point
@@ -1156,7 +1157,7 @@ Finally, line~22 returns the sum. \co{inc_count()} fastpath. } \QuickQuizEnd -Lines~25-32 show the \co{count_register_thread()} function, which +Lines~26-33 show the \co{count_register_thread()} function, which must be called by each thread before its first use of this counter. This function simply sets up this thread's element of the \co{counterp[]} array to point to its per-thread \co{counter} variable.
@@ -1177,14 +1178,14 @@ array to point to its per-thread \co{counter} variable. a hundred or so CPUs, there is no need to get fancy. } \QuickQuizEnd -Lines~34-42 show the \co{count_unregister_thread()} function, which +Lines~35-43 show the \co{count_unregister_thread()} function, which must be called prior to exit by each thread that previously called \co{count_register_thread()}. -Line~38 acquires the lock, and line~41 releases it, thus excluding any +Line~39 acquires the lock, and line~42 releases it, thus excluding any calls to \co{read_count()} as well as other calls to \co{count_unregister_thread()}. -Line~39 adds this thread's \co{counter} to the global \co{finalcount}, -and then line~40 \co{NULL}s out its \co{counterp[]} array entry. +Line~40 adds this thread's \co{counter} to the global \co{finalcount}, +and then line~41 \co{NULL}s out its \co{counterp[]} array entry. A subsequent call to \co{read_count()} will see the exiting thread's count in the global \co{finalcount}, and will skip the exiting thread when sequencing through the \co{counterp[]} array, thus obtaining
Signature · 1 line
2.7.4
PATCH 4/4 Regenerating the atomic counter graph on a more modern CPU
In reply to Imre PalikFrom: "Palik, Imre" <[email protected]>
Regenerating the graph on Kaby Lake, and updating the text.
--- CodeSamples/count/atomic.eps | 483 +++++++++++++---------- CodeSamples/count/atomic125.eps | 856 +++++++++++++++++----------------------- CodeSamples/count/atomic125.png | Bin 3337 -> 3189 bytes count/count.tex | 12 +- defer/rcuintro.tex | 2 +- locking/locking.tex | 2 +- 6 files changed, 658 insertions(+), 697 deletions(-)
CodeSamples/count/atomic.eps +280 -203
@@ -1,7 +1,7 @@ %!PS-Adobe-2.0 %%Title: Is Parallel Programming Hard, And, If So, What Can You Do About It? -%%Creator: gnuplot 4.4 patchlevel 0 -%%CreationDate: Wed Jan 5 07:20:50 2011 +%%Creator: gnuplot 5.0 patchlevel 3 +%%CreationDate: Mon Jul 16 22:02:17 2018 %%DocumentFonts: (atend) %%BoundingBox: 50 95 302 355 %%Orientation: Portrait
@@ -20,42 +20,29 @@ gnudict begin /Dashlength 1 def /Landscape false def /Level1 false def +/Level3 false def /Rounded false def /ClipToBoundingBox false def +/SuppressPDFMark false def /TransparentPatterns false def /gnulinewidth 5.000 def /userlinewidth gnulinewidth def /Gamma 1.0 def +/BackgroundColor {-1.000 -1.000 -1.000} def % /vshift -33 def /dl1 { - 10.0 Dashlength mul mul + 10.0 Dashlength userlinewidth gnulinewidth div mul mul mul Rounded { currentlinewidth 0.75 mul sub dup 0 le { pop 0.01 } if } if } def /dl2 { - 10.0 Dashlength mul mul + 10.0 Dashlength userlinewidth gnulinewidth div mul mul mul Rounded { currentlinewidth 0.75 mul add } if } def /hpt_ 31.5 def /vpt_ 31.5 def /hpt hpt_ def /vpt vpt_ def -Level1 {} { -/SDict 10 dict def -systemdict /pdfmark known not { - userdict /pdfmark systemdict /cleartomark get put -} if -SDict begin [ - /Title (Is Parallel Programming Hard, And, If So, What Can You Do About It?) - /Subject (gnuplot plot) - /Creator (gnuplot 4.4 patchlevel 0) - /Author (paulmck) -% /Producer (gnuplot) -% /Keywords () - /CreationDate (Wed Jan 5 07:20:50 2011) - /DOCINFO pdfmark -end -} ifelse /doclip { ClipToBoundingBox { newpath 50 50 moveto 302 50 lineto 302 410 lineto 50 410 lineto closepath
@@ -63,7 +50,7 @@ end } if } def % -% Gnuplot Prolog Version 4.4 (January 2010) +% Gnuplot Prolog Version 5.1 (Oct 2015) % %/SuppressPDFMark true def %
@@ -75,15 +62,16 @@ end /Z {closepath} bind def /C {setrgbcolor} bind def /f {rlineto fill} bind def +/g {setgray} bind def /Gshow {show} def % May be redefined later in the file to support UTF-8 /vpt2 vpt 2 mul def /hpt2 hpt 2 mul def /Lshow {currentpoint stroke M 0 vshift R - Blacktext {gsave 0 setgray show grestore} {show} ifelse} def + Blacktext {gsave 0 setgray textshow grestore} {textshow} ifelse} def /Rshow {currentpoint stroke M dup stringwidth pop neg vshift R - Blacktext {gsave 0 setgray show grestore} {show} ifelse} def + Blacktext {gsave 0 setgray textshow grestore} {textshow} ifelse} def /Cshow {currentpoint stroke M dup stringwidth pop -2 div vshift R - Blacktext {gsave 0 setgray show grestore} {show} ifelse} def + Blacktext {gsave 0 setgray textshow grestore} {textshow} ifelse} def /UP {dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def /hpt2 hpt 2 mul def /vpt2 vpt 2 mul def} def /DL {Color {setrgbcolor Solid {pop []} if 0 setdash}
@@ -96,7 +84,8 @@ end dup 1 lt {pop 1} if 10 mul /udl exch def} def /PL {stroke userlinewidth setlinewidth Rounded {1 setlinejoin 1 setlinecap} if} def -% Default Line colors +3.8 setmiterlimit +% Classic Line colors (version 5.0) /LCw {1 1 1} def /LCb {0 0 0} def /LCa {0 0 0} def
@@ -109,19 +98,21 @@ end /LC6 {0 0 0} def /LC7 {1 0.3 0} def /LC8 {0.5 0.5 0.5} def -% Default Line Types +% Default dash patterns (version 5.0) +/LTB {BL [] LCb DL} def /LTw {PL [] 1 setgray} def -/LTb {BL [] LCb DL} def +/LTb {PL [] LCb DL} def /LTa {AL [1 udl mul 2 udl mul] 0 setdash LCa setrgbcolor} def /LT0 {PL [] LC0 DL} def -/LT1 {PL [4 dl1 2 dl2] LC1 DL} def -/LT2 {PL [2 dl1 3 dl2] LC2 DL} def -/LT3 {PL [1 dl1 1.5 dl2] LC3 DL} def -/LT4 {PL [6 dl1 2 dl2 1 dl1 2 dl2] LC4 DL} def -/LT5 {PL [3 dl1 3 dl2 1 dl1 3 dl2] LC5 DL} def -/LT6 {PL [2 dl1 2 dl2 2 dl1 6 dl2] LC6 DL} def -/LT7 {PL [1 dl1 2 dl2 6 dl1 2 dl2 1 dl1 2 dl2] LC7 DL} def -/LT8 {PL [2 dl1 2 dl2 2 dl1 2 dl2 2 dl1 2 dl2 2 dl1 4 dl2] LC8 DL} def +/LT1 {PL [2 dl1 3 dl2] LC1 DL} def +/LT2 {PL [1 dl1 1.5 dl2] LC2 DL} def +/LT3 {PL [6 dl1 2 dl2 1 dl1 2 dl2] LC3 DL} def +/LT4 {PL [1 dl1 2 dl2 6 dl1 2 dl2 1 dl1 2 dl2] LC4 DL} def +/LT5 {PL [4 dl1 2 dl2] LC5 DL} def +/LT6 {PL [1.5 dl1 1.5 dl2 1.5 dl1 1.5 dl2 1.5 dl1 6 dl2] LC6 DL} def +/LT7 {PL [3 dl1 3 dl2 1 dl1 3 dl2] LC7 DL} def +/LT8 {PL [2 dl1 2 dl2 2 dl1 6 dl2] LC8 DL} def +/SL {[] 0 setdash} def /Pnt {stroke [] 0 setdash gsave 1 setlinecap M 0 0 V stroke grestore} def /Dia {stroke [] 0 setdash 2 copy vpt add M hpt neg vpt neg V hpt vpt neg V
@@ -328,7 +319,8 @@ end /PatternFill {gsave /PFa [ 9 2 roll ] def PFa 0 get PFa 2 get 2 div add PFa 1 get PFa 3 get 2 div add translate PFa 2 get -2 div PFa 3 get -2 div PFa 2 get PFa 3 get Rec - gsave 1 setgray fill grestore clip + TransparentPatterns {} {gsave 1 setgray fill grestore} ifelse + clip currentlinewidth 0.5 mul setlinewidth /PFs PFa 2 get dup mul PFa 3 get dup mul add sqrt def 0 0 M PFa 5 get rotate PFs -2 div dup translate
@@ -342,9 +334,14 @@ end % /languagelevel where {pop languagelevel} {1} ifelse - 2 lt - {/InterpretLevel1 true def} - {/InterpretLevel1 Level1 def} +dup 2 lt + {/InterpretLevel1 true def + /InterpretLevel3 false def} + {/InterpretLevel1 Level1 def + 2 gt + {/InterpretLevel3 Level3 def} + {/InterpretLevel3 false def} + ifelse } ifelse % % PostScript level 2 pattern fill definitions
@@ -433,16 +430,17 @@ Level1 {Level1PatternFill} {Level2PatternFill} ifelse /Symbol-Oblique /Symbol findfont [1 0 .167 1 0 0] makefont dup length dict begin {1 index /FID eq {pop pop} {def} ifelse} forall currentdict end definefont pop +% /MFshow { { dup 5 get 3 ge { 5 get 3 eq {gsave} {grestore} ifelse } {dup dup 0 get findfont exch 1 get scalefont setfont [ currentpoint ] exch dup 2 get 0 exch R dup 5 get 2 ne {dup dup 6 - get exch 4 get {Gshow} {stringwidth pop 0 R} ifelse }if dup 5 get 0 eq + get exch 4 get {textshow} {stringwidth pop 0 R} ifelse }if dup 5 get 0 eq {dup 3 get {2 get neg 0 exch R pop} {pop aload pop M} ifelse} {dup 5 get 1 eq {dup 2 get exch dup 3 get exch 6 get stringwidth pop -2 div dup 0 R} {dup 6 get stringwidth pop -2 div 0 R 6 get - show 2 index {aload pop M neg 3 -1 roll neg R pop pop} {pop pop pop + textshow 2 index {aload pop M neg 3 -1 roll neg R pop pop} {pop pop pop pop aload pop M} ifelse }ifelse }ifelse } ifelse } forall} def
@@ -1850,6 +1848,51 @@ ba6d2a8e73b10c6de72a8e8f3bfeab8344fe6622fadd5d01457e31e8facd74cb cleartomark {restore}if %%EndProcSet +Level1 SuppressPDFMark or +{} { +/SDict 10 dict def +systemdict /pdfmark known not { + userdict /pdfmark systemdict /cleartomark get put +} if +SDict begin [ + /Title (Is Parallel Programming Hard, And, If So, What Can You Do About It?) + /Subject (gnuplot plot) + /Creator (gnuplot 5.0 patchlevel 3) + /Author (imre) +% /Producer (gnuplot) +% /Keywords () + /CreationDate (Mon Jul 16 22:02:17 2018) + /DOCINFO pdfmark +end +} ifelse +% +% Support for boxed text - Ethan A Merritt May 2005 +% +/InitTextBox { userdict /TBy2 3 -1 roll put userdict /TBx2 3 -1 roll put + userdict /TBy1 3 -1 roll put userdict /TBx1 3 -1 roll put + /Boxing true def } def +/ExtendTextBox { Boxing + { gsave dup false charpath pathbbox + dup TBy2 gt {userdict /TBy2 3 -1 roll put} {pop} ifelse + dup TBx2 gt {userdict /TBx2 3 -1 roll put} {pop} ifelse + dup TBy1 lt {userdict /TBy1 3 -1 roll put} {pop} ifelse + dup TBx1 lt {userdict /TBx1 3 -1 roll put} {pop} ifelse + grestore } if } def +/PopTextBox { newpath TBx1 TBxmargin sub TBy1 TBymargin sub M + TBx1 TBxmargin sub TBy2 TBymargin add L + TBx2 TBxmargin add TBy2 TBymargin add L + TBx2 TBxmargin add TBy1 TBymargin sub L closepath } def +/DrawTextBox { PopTextBox stroke /Boxing false def} def +/FillTextBox { gsave PopTextBox 1 1 1 setrgbcolor fill grestore /Boxing false def} def +0 0 0 0 InitTextBox +/TBxmargin 20 def +/TBymargin 20 def +/Boxing false def +/textshow { ExtendTextBox Gshow } def +% +% redundant definitions for compatibility with prologue.ps older than 5.0.2 +/LTB {BL [] LCb DL} def +/LTb {PL [] LCb DL} def end %%EndProlog %%Page: 1 1
@@ -1861,402 +1904,436 @@ doclip 0 setgray newpath (NimbusSanL-Regu) findfont 100 scalefont setfont +BackgroundColor 0 lt 3 1 roll 0 lt exch 0 lt or or not {gsave BackgroundColor C clippath fill grestore} if 1.000 UL LTb -550 990 M +LCb setrgbcolor +490 975 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 990 M +430 975 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 0)] ] -33.3 MRshow 1.000 UL LTb -550 1192 M +LCb setrgbcolor +490 1181 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 1192 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 100)] +430 1181 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 20)] ] -33.3 MRshow 1.000 UL LTb -550 1394 M +LCb setrgbcolor +490 1386 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 1394 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 200)] +430 1386 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 40)] ] -33.3 MRshow 1.000 UL LTb -550 1597 M +LCb setrgbcolor +490 1592 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 1597 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 300)] +430 1592 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 60)] ] -33.3 MRshow 1.000 UL LTb -550 1799 M +LCb setrgbcolor +490 1797 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 1799 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 400)] +430 1797 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 80)] ] -33.3 MRshow 1.000 UL LTb -550 2001 M +LCb setrgbcolor +490 2003 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 2001 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 500)] +430 2003 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 100)] ] -33.3 MRshow 1.000 UL LTb -550 2203 M +LCb setrgbcolor +490 2208 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 2203 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 600)] +430 2208 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 120)] ] -33.3 MRshow 1.000 UL LTb -550 2406 M +LCb setrgbcolor +490 2414 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 2406 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 700)] +430 2414 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 140)] ] -33.3 MRshow 1.000 UL LTb -550 2608 M +LCb setrgbcolor +490 2619 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 2608 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 800)] +430 2619 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 160)] ] -33.3 MRshow 1.000 UL LTb -550 2810 M +LCb setrgbcolor +490 2825 M 63 0 V -1756 0 R +1786 0 R -63 0 V stroke -490 2810 M -[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 900)] +430 2825 M +[ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 180)] ] -33.3 MRshow 1.000 UL LTb -550 990 M +LCb setrgbcolor +490 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -550 890 M +490 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 1)] ] -33.3 MCshow 1.000 UL LTb -810 990 M +LCb setrgbcolor +754 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -810 890 M +754 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 2)] ] -33.3 MCshow 1.000 UL LTb -1070 990 M +LCb setrgbcolor +1018 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -1070 890 M +1018 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 3)] ] -33.3 MCshow 1.000 UL LTb -1330 990 M +LCb setrgbcolor +1282 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -1330 890 M +1282 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 4)] ] -33.3 MCshow 1.000 UL LTb -1589 990 M +LCb setrgbcolor +1547 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -1589 890 M +1547 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 5)] ] -33.3 MCshow 1.000 UL LTb -1849 990 M +LCb setrgbcolor +1811 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -1849 890 M +1811 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 6)] ] -33.3 MCshow 1.000 UL LTb -2109 990 M +LCb setrgbcolor +2075 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -2109 890 M +2075 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 7)] ] -33.3 MCshow 1.000 UL LTb -2369 990 M +LCb setrgbcolor +2339 975 M 0 63 V -0 1757 R +0 1787 R 0 -63 V stroke -2369 890 M +2339 875 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 ( 8)] ] -33.3 MCshow 1.000 UL LTb +LCb setrgbcolor 1.000 UL -LTb -550 2810 N -550 990 L -1819 0 V -0 1820 V --1819 0 V +LTB +LCb setrgbcolor +490 2825 N +490 975 L +1849 0 V +0 1850 V +-1849 0 V Z stroke +1.000 UP +1.000 UL +LTb LCb setrgbcolor -140 1900 M +LCb setrgbcolor +80 1900 M currentpoint gsave translate -270 rotate 0 0 moveto [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 (Time Per Increment \(nanoseconds\))] ] -33.3 MCshow grestore LTb LCb setrgbcolor -1459 740 M +1414 725 M [ [(NimbusSanL-Regu) 100.0 0.0 true true 0 (Number of CPUs \(Threads\))] ] -33.3 MCshow LTb -1.000 UP -1.000 UL -LTb % Begin plot #1 1.000 UP 1.000 UL -LT0 +LTb +LCb setrgbcolor /NimbusSanL-Regu findfont 100 scalefont setfont -550 1079 M -0 2 V --31 -2 R -62 0 V --62 2 R -62 0 V -229 118 R +/vshift -33 def +490 1019 M 0 10 V --31 -10 R -62 0 V --62 10 R +0 -10 R +31 0 V +-31 10 R +31 0 V +233 335 R +0 28 V +-31 -28 R 62 0 V -229 189 R -0 94 V --31 -94 R +-62 28 R 62 0 V --62 94 R +233 102 R +0 112 V +987 1494 M 62 0 V -229 205 R -0 97 V --31 -97 R +-62 112 R 62 0 V --62 97 R +233 3 R +0 199 V +-31 -199 R 62 0 V -228 64 R -0 80 V --31 -80 R +-62 199 R 62 0 V --62 80 R +234 69 R +0 133 V +-31 -133 R 62 0 V -229 96 R -0 281 V --31 -281 R +-62 133 R 62 0 V --62 281 R +233 -1 R +0 241 V +-31 -241 R 62 0 V -229 11 R -0 149 V --31 -149 R +-62 241 R 62 0 V --62 149 R +233 -56 R +0 238 V +-31 -238 R 62 0 V -229 27 R -0 144 V --31 -144 R +-62 238 R 62 0 V --62 144 R -62 0 V -550 1080 Pls -810 1204 Pls -1070 1454 Pls -1330 1739 Pls -1589 1904 Pls -1849 2163 Pls -2109 2398 Pls -2369 2588 Pls +233 63 R +0 200 V +-31 -200 R +31 0 V +-31 200 R +31 0 V +490 1023 Pls +754 1378 Pls +1018 1569 Pls +1282 1696 Pls +1547 1934 Pls +1811 2119 Pls +2075 2300 Pls +2339 2625 Pls % End plot #1 % Begin plot #2 1.000 UL +LTb LT1 +LCb setrgbcolor /NimbusSanL-Regu findfont 100 scalefont setfont -550 1080 M -260 124 V -260 250 V -260 285 V -259 165 V -260 259 V -260 235 V -260 190 V +490 1023 M +264 355 V +264 191 V +264 127 V +265 238 V +264 185 V +264 181 V +264 325 V % End plot #2 % Begin plot #3 stroke +LTb LT2 +LCb setrgbcolor /NimbusSanL-Regu findfont 100 scalefont setfont -550 1008 M -18 0 V +490 1066 M 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V -18 0 V 19 0 V 18 0 V 19 0 V -18 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V -18 0 V 19 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V -18 0 V 19 0 V 18 0 V 19 0 V -18 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V -18 0 V 19 0 V 18 0 V 19 0 V -18 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V 19 0 V 18 0 V -18 0 V 19 0 V -18 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V +19 0 V 18 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V +19 0 V 18 0 V 19 0 V +19 0 V 18 0 V +19 0 V % End plot #3 stroke +2.000 UL LTb -550 2810 N -550 990 L -1819 0 V -0 1820 V --1819 0 V +LCb setrgbcolor +1.000 UL +LTB +LCb setrgbcolor +490 2825 N +490 975 L +1849 0 V +0 1850 V +-1849 0 V Z stroke 1.000 UP 1.000 UL LTb +LCb setrgbcolor stroke grestore end
CodeSamples/count/atomic125.eps +370 -486
1,100 lines not on this page · raw message
CodeSamples/count/atomic125.png binary +0 -0
count/count.tex +6 -6
@@ -267,8 +267,8 @@ accuracies far greater than 50\,\% are almost always necessary. \begin{figure}[tb] \centering \resizebox{2.5in}{!}{\includegraphics{CodeSamples/count/atomic}} -\caption{Atomic Increment Scalability on Nehalem} -\label{fig:count:Atomic Increment Scalability on Nehalem} +\caption{Atomic Increment Scalability on Kaby Lake} +\label{fig:count:Atomic Increment Scalability on Kaby Lake} \end{figure} The straightforward way to count accurately is to use atomic operations,
@@ -296,7 +296,7 @@ This poor performance should not be a surprise, given the discussion in Chapter~\ref{chp:Hardware and its Habits}, nor should it be a surprise that the performance of atomic increment gets slower as the number of CPUs and threads increase, as shown in -Figure~\ref{fig:count:Atomic Increment Scalability on Nehalem}. +Figure~\ref{fig:count:Atomic Increment Scalability on Kaby Lake}. In this figure, the horizontal dashed line resting on the x~axis is the ideal performance that would be achieved by a perfectly scalable algorithm: with such an algorithm, a given
@@ -365,7 +365,7 @@ global variable, the cache line containing that variable must circulate among all the CPUs, as shown by the red arrows. Such circulation will take significant time, resulting in the poor performance seen in -Figure~\ref{fig:count:Atomic Increment Scalability on Nehalem}, +Figure~\ref{fig:count:Atomic Increment Scalability on Kaby Lake}, which might be thought of as shown in Figure~\ref{fig:count:Waiting to Count}.
@@ -3444,7 +3444,7 @@ courtesy of eventual consistency. ``Use the right tool for the job.'' As can be seen from - Figure~\ref{fig:count:Atomic Increment Scalability on Nehalem}, + Figure~\ref{fig:count:Atomic Increment Scalability on Kaby Lake}, single-variable atomic increment need not apply for any job involving heavy use of parallel updates. In contrast, the algorithms shown in
@@ -3730,7 +3730,7 @@ Summarizing the summary: \item Different levels of performance and scalability will affect algorithm and data-structure design, as do a large number of other factors. - Figure~\ref{fig:count:Atomic Increment Scalability on Nehalem} + Figure~\ref{fig:count:Atomic Increment Scalability on Kaby Lake} illustrates this point: Atomic increment might be completely acceptable for a two-CPU system, but be completely inadequate for an eight-CPU system.
defer/rcuintro.tex +1 -1
@@ -76,7 +76,7 @@ the figure. But how can we tell when the readers are finished? It is tempting to consider a reference-counting scheme, but -Figure~\ref{fig:count:Atomic Increment Scalability on Nehalem} +Figure~\ref{fig:count:Atomic Increment Scalability on Kaby Lake} in Chapter~\ref{chp:Counting} shows that this can also result in long delays, just as can
locking/locking.tex +1 -1
@@ -1578,7 +1578,7 @@ Either way, line~22 releases the root \co{rcu_node} structure's but only for relatively small numbers of CPUs. To see why it is problematic in systems with many hundreds of CPUs, look at - Figure~\ref{fig:count:Atomic Increment Scalability on Nehalem} + Figure~\ref{fig:count:Atomic Increment Scalability on Kaby Lake} and extrapolate the delay from eight to 1,000 CPUs. } \QuickQuizEnd
Signature · 1 line
2.7.4
Quoted 3 lines · Imre Palik
This series changes some of the counter examples to use volatile access, to avoid overly eager compilers/linkers to optimise out necessary reads/writes.
Applied and pushed, thank you!
And very nice to get that graph upgraded to the much more recent Kaby Lake! By the way, if you have one with more than eight hardware threads, I would not say "no" to an expanded graph. ;-)
Thanx, Paul