formal/spinhint: Update code snippet
cover formal/spinhint: Update code snippet
Hi Paul,
Here is another round of code snippet update, with modernization of outputs of Spin and tables of state search results.
Patch #1 updates fcvextract.pl so that .spin files are handled as the same as C source files.
Patch #2 applies the new scheme to code snippets. It also contains minor changes for better typesetting.
Patch #3 replaces captures of Spin outputs with those obtained from Spin version 6.4.8. This commit adds outputs as .lst files under CodeSamples/formal/promela/. They are added to the dependency in the top level Makefile.
Patch #4 updates tables of Spin result. For qrcu.spin, I used the compiler flag -DCOLLAPSE to complete the state search for updaters=3 readers=2 on a machine with 16GB memory. As far as I understand correctly, this compiler flag does not affect the completeness of state search. So I added some explanation in the text to mention the flag and the argument -mN of ./pan to increase the limit of search depth.
Patch #5 tweaks footnote on a cell in a table.
Patch #6 is a nitpick patch to consistently use \co{}.
I'm wondering if Patch #4 is OK from your perspective. Any feedback is welcome!
Thanks, Akira
--
Akira Yokosawa (6):
fcvextract.pl: Treat '.spin' files as C sources formal/spinhint: Employ new scheme for code snippet formal/spinhint: Update output lists of spin formal/spinhint: Update tables of memory usage of Spin formal/spinhint: Put footnote on header in table formal/spinhint: Use \co{...} rather than {\tt ...}
CodeSamples/formal/promela/atomicincrement.spin | 2 + .../formal/promela/atomicincrement.spin.lst | 28 + CodeSamples/formal/promela/increment.spin | 46 +- CodeSamples/formal/promela/increment.spin.lst | 28 + .../formal/promela/increment.spin.trail.lst | 42 + CodeSamples/formal/promela/lock.h | 16 +- CodeSamples/formal/promela/lock.spin | 46 +- CodeSamples/formal/promela/lock.spin.lst | 29 + CodeSamples/formal/promela/qrcu.spin | 95 ++- Makefile | 4 +- formal/spinhint.tex | 874 ++++++--------------- perfbook.tex | 1 + utilities/fcvextract.pl | 8 +- 13 files changed, 502 insertions(+), 717 deletions(-) create mode 100644 CodeSamples/formal/promela/atomicincrement.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.trail.lst create mode 100644 CodeSamples/formal/promela/lock.spin.lst
Signature · 1 line
2.7.4
PATCH 1/6 fcvextract.pl: Treat '.spin' files as C sources
From b33a50ba42fee982662ca34001c2495d1787b4fd Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Thu, 31 Jan 2019 00:07:53 +0900
Subject: [PATCH 1/6] fcvextract.pl: Treat '.spin' files as C sources
"spin" command accepts preprocessor directives and comments of C style. Merge the setup of regular expressions for ".spin" files with that for C sources.
--- utilities/fcvextract.pl | 8 ++------ 1 file changed, 2 insertions(+), 6 deletions(-)
utilities/fcvextract.pl +2 -6
@@ -105,7 +105,7 @@ # NOTE: "#ifdef FCV_SNIPPET" is not recognized. # "#else" can be omitted. # -# Copyright (C) Akira Yokosawa, 2018 +# Copyright (C) Akira Yokosawa, 2018, 2019 # # Authors: Akira Yokosawa <[email protected]>
@@ -142,14 +142,10 @@ $extract_labelbase = $ARGV[1]; $begin_re = qr/\\begin\{snippet\}.*labelbase=[^,\]]*$extract_labelbase[,\]]/ ; $end_re = qr/\\end\{snippet\}/; -if ($src_file =~ /.*\.[ch]$/ ) { +if ($src_file =~ /.*\.[ch]$/ || $src_file =~ /.*\.spin$/) { $lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!; $lnlbl_re2 = qr!(.*?)(s*/\*\s*)\\lnlbl\{(.*)}\s*\*/(.*)$!; $c_src = 1; -} elsif ($src_file =~ /.*\.c$/ ) { - $lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!; -} elsif ($src_file =~ /.*\.spin$/ ) { - $lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!; } elsif ($src_file =~ /.*\.sh$/ ) { $lnlbl_re = qr!(.*?)(\s*#\s*)\\lnlbl\{(.*)}\s*$!; } elsif ($src_file =~ /.\.ltms$/ ) {
Signature · 1 line
2.7.4
PATCH 2/6 formal/spinhint: Employ new scheme for code snippet
In reply to Akira YokosawaFrom 7c319159fddc42f02836e23581a73facd5d54b47 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Thu, 31 Jan 2019 00:08:30 +0900
Subject: [PATCH 2/6] formal/spinhint: Employ new scheme for code snippet
Other than simple transformations, this commit includes the following changes:
o Move "listing" environment to outside of "enumerate" environment. This is to avoid slight behavior change of "VerbatimL" environment inside "enumerate".
("VerbatimN" looks OK inside "enumerate".)
o Embed the unoptimized definition of sum_unordered into CodeSamples/formal/promela/qrcu.spin using the "#ifndef FCV_SNIPPET" construct, rather than putting it in spinhint.tex. Luckily, we don't reference the optimized definition as a code snippet. (Related to Quick Quiz 12.3)
o Substitute white spaces for tab characters in snippets which appear in the middle of a line.
o Enclose "do-od" and "if-fi" in \co{} macros.
--- CodeSamples/formal/promela/atomicincrement.spin | 2 + CodeSamples/formal/promela/increment.spin | 46 +- CodeSamples/formal/promela/lock.h | 16 +- CodeSamples/formal/promela/lock.spin | 46 +- CodeSamples/formal/promela/qrcu.spin | 95 ++-- formal/spinhint.tex | 681 +++++++----------------- 6 files changed, 318 insertions(+), 568 deletions(-)
CodeSamples/formal/promela/atomicincrement.spin +2 -0
@@ -3,6 +3,7 @@ byte counter = 0; byte progress[NUMPROCS]; +//\begin{snippet}[labelbase=ln:formal:promela:atomicincrement:incrementer,commandchars=\\\@\$] proctype incrementer(byte me) { int temp;
@@ -13,6 +14,7 @@ proctype incrementer(byte me) } progress[me] = 1; } +//\end{snippet} init { int i = 0;
CodeSamples/formal/promela/increment.spin +24 -22
64 lines not on this page · raw message
CodeSamples/formal/promela/lock.h +9 -7
@@ -1,14 +1,16 @@ +//\begin{snippet}[labelbase=ln:formal:promela:lock:whole,commandchars=\!\[\]] #define spin_lock(mutex) \ - do \ - :: 1 -> atomic { \ + do /* \lnlbl{dood:b} */\ + :: 1 -> atomic { /* \lnlbl{one} */\ if \ - :: mutex == 0 -> \ - mutex = 1; \ - break \ - :: else -> skip \ + :: mutex == 0 -> /* \lnlbl{notheld} */\ + mutex =1 ;/* \lnlbl{acq} */ \ + break /* \lnlbl{break} */\ + :: else -> skip /* \lnlbl{held} */\ fi \ } \ - od +od /* \lnlbl{dood:e} */ #define spin_unlock(mutex) \ mutex =0 +//\end{snippet}
CodeSamples/formal/promela/lock.spin +24 -22
67 lines not on this page · raw message
CodeSamples/formal/promela/qrcu.spin +61 -34
176 lines not on this page · raw message
formal/spinhint.tex +198 -483
944 lines not on this page · raw message
Signature · 1 line
2.7.4
PATCH 3/6 formal/spinhint: Update output lists of spin
In reply to Akira YokosawaFrom 986b559571721ae7c57a8d05c7b2da5b03c1ce21 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Thu, 31 Jan 2019 00:11:11 +0900
Subject: [PATCH 3/6] formal/spinhint: Update output lists of spin
Update the captures of output of Spin with those of Spin Version 6.4.8. *.spin.lst and *.spin.trail.lst files are placed under CodeSamples/formal/promela/.
.spin.lst files are manually folded for 2c layout.
Also add dependency to those .lst files in the top-level Makefile.
--- .../formal/promela/atomicincrement.spin.lst | 28 +++++ CodeSamples/formal/promela/increment.spin.lst | 28 +++++ .../formal/promela/increment.spin.trail.lst | 42 +++++++ CodeSamples/formal/promela/lock.spin.lst | 29 +++++ Makefile | 4 +- formal/spinhint.tex | 127 ++------------------- 6 files changed, 140 insertions(+), 118 deletions(-) create mode 100644 CodeSamples/formal/promela/atomicincrement.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.trail.lst create mode 100644 CodeSamples/formal/promela/lock.spin.lst
CodeSamples/formal/promela/atomicincrement.spin.lst new file +28 -0
@@ -0,0 +1,28 @@ +(Spin Version 6.4.8 -- 2 March 2018) + + Partial Order Reduction + +Full statespace search for: + never claim - (none specified) + assertion violations + + cycle checks - (disabled by -DSAFETY) + invalid end states + + +State-vector 48 byte, depth reached 22, errors: 0 + 52 states, stored + 21 states, matched + 73 transitions (= stored+matched) + 68 atomic steps +hash conflicts: 0 (resolved) + +Stats on memory usage (in Megabytes): + 0.004 equivalent memory usage for states + (stored*(State-vector + overhead)) + 0.290 actual memory usage for states + 128.000 memory used for hash table (-w24) + 0.534 memory used for DFS stack (-m10000) + 128.730 total actual memory usage + +unreached in proctype incrementer + (0 of 5 states) +unreached in init + (0 of 24 states)
CodeSamples/formal/promela/increment.spin.lst new file +28 -0
@@ -0,0 +1,28 @@ +pan:1: assertion violated + ((sum<2)||(counter==2)) (at depth 22) +pan: wrote increment.spin.trail + +(Spin Version 6.4.8 -- 2 March 2018) +Warning: Search not completed + + Partial Order Reduction + +Full statespace search for: + never claim - (none specified) + assertion violations + + cycle checks - (disabled by -DSAFETY) + invalid end states + + +State-vector 48 byte, depth reached 24, errors: 1 + 45 states, stored + 13 states, matched + 58 transitions (= stored+matched) + 53 atomic steps +hash conflicts: 0 (resolved) + +Stats on memory usage (in Megabytes): + 0.003 equivalent memory usage for states + (stored*(State-vector + overhead)) + 0.290 actual memory usage for states + 128.000 memory used for hash table (-w24) + 0.534 memory used for DFS stack (-m10000) + 128.730 total actual memory usage
CodeSamples/formal/promela/increment.spin.trail.lst new file +42 -0
42 lines not on this page · raw message
CodeSamples/formal/promela/lock.spin.lst new file +29 -0
@@ -0,0 +1,29 @@ +(Spin Version 6.4.8 -- 2 March 2018) + + Partial Order Reduction + +Full statespace search for: + never claim - (none specified) + assertion violations + + cycle checks - (disabled by -DSAFETY) + invalid end states + + +State-vector 52 byte, depth reached 360, errors: 0 + 576 states, stored + 929 states, matched + 1505 transitions (= stored+matched) + 368 atomic steps +hash conflicts: 0 (resolved) + +Stats on memory usage (in Megabytes): + 0.044 equivalent memory usage for states + (stored*(State-vector + overhead)) + 0.288 actual memory usage for states + 128.000 memory used for hash table (-w24) + 0.534 memory used for DFS stack (-m10000) + 128.730 total actual memory usage + +unreached in proctype locker + lock.spin:19, state 20, "-end-" + (1 of 20 states) +unreached in init + (0 of 22 states)
Makefile +3 -1
@@ -11,6 +11,8 @@ LATEXSOURCES = \ */*.tex \ */*/*.tex +LST_SOURCES := $(wildcard CodeSamples/formal/promela/*.lst) + LATEXGENERATED = autodate.tex qqz.tex contrib.tex origpub.tex ABBREVTARGETS := tcb 1c hb msns mss mstx msr msn msnt 1csf
@@ -123,7 +125,7 @@ $(PDFTARGETS): %.pdf: %.tex %.bbl $(PDFTARGETS:.pdf=.bbl): %.bbl: %.aux $(BIBSOURCES) bibtex $(basename $@) -$(PDFTARGETS:.pdf=.aux): $(LATEXGENERATED) $(LATEXSOURCES) +$(PDFTARGETS:.pdf=.aux): $(LATEXGENERATED) $(LATEXSOURCES) $(LST_SOURCES) sh utilities/runfirstlatex.sh $(basename $@) autodate.tex: perfbook.tex $(LATEXSOURCES) $(BIBSOURCES) $(SVGSOURCES) $(FIGSOURCES) $(DOTSOURCES) $(EPSORIGIN) $(SOURCES_OF_SNIPPET) utilities/fcvextract.pl
formal/spinhint.tex +10 -117
153 lines not on this page · raw message
Signature · 1 line
2.7.4
PATCH 4/6 formal/spinhint: Update tables of memory usage of Spin
In reply to Akira YokosawaFrom 72b1807d846432592d01c8642cebfa6a655802ed Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Thu, 31 Jan 2019 00:13:21 +0900
Subject: [PATCH 4/6] formal/spinhint: Update tables of memory usage of Spin
Update tables of memory usage of increment.spin and qrcu.spin.
As for qrcu.spin, to complete search of 3 updaters and 2 readers on a machine with 16GB memory, the "-DCOLLAPSE" flag is necessary to avoid memory exhaustion. This doesn't affect the completeness of state search. Add explantion of the flag and update the table of qrcu.spin with the usage obtained with the flag enabled.
There seems to have been incomplete searches due to insufficient search depth. Update "# state" figures from the complete results obtained with deeper search limits.
Depth reached:
updaters readers depth
1 1 95
1 2 218
1 3 385
2 1 859
2 2 2352
2 3 12857
3 1 53809
3 2 328014
--- formal/spinhint.tex | 64 ++++++++++++++++++++++++++++++++--------------------- 1 file changed, 39 insertions(+), 25 deletions(-)
formal/spinhint.tex +39 -25
@@ -198,22 +198,22 @@ Listing~\ref{lst:analysis:Atomic Increment spin Output}. \begin{table} \rowcolors{1}{}{lightgray} -\renewcommand*{\arraystretch}{1.2} \small +\renewcommand*{\arraystretch}{1.2} \centering \begin{tabular}{S[table-format = 1.0]S[table-format = 7.0]S[table-format = 3.1]} \toprule \multicolumn{1}{l}{\# incrementers} & \multicolumn{1}{r}{\# states} & - \multicolumn{1}{r}{megabytes} \\ + \multicolumn{1}{r}{total memory usage (MB)} \\ \midrule - 1 & 11 & 2.6 \\ - 2 & 52 & 2.6 \\ - 3 & 372 & 2.6 \\ - 4 & 3 496 & 2.7 \\ - 5 & 40 221 & 5.0 \\ - 6 & 545 720 & 40.5 \\ - 7 & 8 521 450 & 652.7 \\ + 1 & 11 & 128.7 \\ + 2 & 52 & 128.7 \\ + 3 & 372 & 128.7 \\ + 4 & 3 496 & 128.9 \\ + 5 & 40 221 & 131.7 \\ + 6 & 545 720 & 174.0 \\ + 7 & 8 521 446 & 881.9 \\ \bottomrule \end{tabular} \caption{Memory Usage of Increment Model}
@@ -226,7 +226,7 @@ as a function of number of incrementers modeled (by redefining {\tt NUMPROCS}): Running unnecessarily large models is thus subtly discouraged, although -652\,MB is well within the limits of modern desktop and laptop machines. +882\,MB is well within the limits of modern desktop and laptop machines. With this example under our belt, let's take a closer look at the commands used to analyze Promela models and then look at more
@@ -240,7 +240,7 @@ Given a source file \path{qrcu.spin}, one can use the following commands: \begin{description}[style=nextline] \item [\tco{spin -a qrcu.spin}] Create a file \path{pan.c} that fully searches the state machine. -\item [\tco{cc -DSAFETY -o pan pan.c}] +\item [\tco{cc -DSAFETY [-DCOLLAPSE] -o pan pan.c}] Compile the generated state-machine search. The \co{-DSAFETY} generates optimizations that are appropriate if you have only assertions (and perhaps \co{never} statements). If you have
@@ -253,12 +253,20 @@ Given a source file \path{qrcu.spin}, one can use the following commands: An example situation where you cannot use \co{-DSAFETY} is when checking for livelocks (AKA ``non-progress cycles'') via \co{-DNP}. -\item [\tco{./pan}] + + The optional \co{-DCOLLAPSE} generates code for a state vector + compression mode. +\item [\tco{./pan [-mN]}] This actually searches the state space. The number of states can reach into the tens of millions with very small state machines, so you will need a machine with large memory. - For example, \path{qrcu.spin} with 3 readers and 2 updaters required - 2.7\,GB of memory. + For example, \path{qrcu.spin} with 3~updaters and 2~readers required + 10.5\,GB of memory even with the \co{-DCOLLAPSE} flag. + + If you see a message from \co{pan} saying: + ``error: max search depth too small'', you need to increase + the maximum depth by a \co{-mN} flag for a complete search. + The default is \co{-m10000}. If you aren't sure whether your machine has enough memory, run \co{top} in one window and \co{./pan} in another. Keep the
@@ -269,6 +277,10 @@ Given a source file \path{qrcu.spin}, one can use the following commands: windowing system to grab enough memory to do anything for you. + Another option to avoid memory exhaustion is the + \co{-DMEMLIM=N} compiler flag. \co{-DMEMLIM=2000} + would set the maximum of 2\,GB. + Don't forget to capture the output, especially if you are working on a remote machine.
@@ -826,8 +838,8 @@ Then use the following commands to build and run the QRCU model: \begin{VerbatimU} spin -a qrcu.spin -cc -DSAFETY -o pan pan.c -./pan +cc -DSAFETY [-DCOLLAPSE] -o pan pan.c +./pan [-mN] \end{VerbatimU} \begin{table}
@@ -843,14 +855,14 @@ cc -DSAFETY -o pan pan.c \multicolumn{1}{r}{\# states} & \multicolumn{1}{r}{MB} \\ \midrule - 1 & 1 & 376 & 2.6 \\ - 1 & 2 & 6 177 & 2.9 \\ - 1 & 3 & 82 127 & 7.5 \\ - 2 & 1 & 29 399 & 4.5 \\ - 2 & 2 & 1 071 180 & 75.4 \\ - 2 & 3 & 33 866 700 & 2 715.2 \\ - 3 & 1 & 258 605 & 22.3 \\ - 3 & 2 & 169 533 000 & 14 979.9 \\ + 1 & 1 & 376 & 128.7 \\ + 1 & 2 & 6 177 & 128.9 \\ + 1 & 3 & 99 728 & 132.6 \\ + 2 & 1 & 29 399 & 129.8 \\ + 2 & 2 & 1 071 181 & 169.6 \\ + 2 & 3 & 33 866 736 & 1 540.8 \\ + 3 & 1 & 2 749 453 & 236.6 \\ + 3 & 2 & 186 202 860 & 10 483.7 \\ \bottomrule \end{tabular} \caption{Memory Usage of QRCU Model}
@@ -859,7 +871,9 @@ cc -DSAFETY -o pan pan.c The resulting output shows that this model passes all of the cases shown in -Table~\ref{tab:advsync:Memory Usage of QRCU Model}. +Table~\ref{tab:advsync:Memory Usage of QRCU Model}.\footnote{ + Figures in the table are obtained with the \co{-DCOLLAPSE} + compiler flag specified.} Now, it would be nice to run the case with three readers and three updaters, however, simple extrapolation indicates that this will require on the order of a terabyte of memory best case.
Signature · 1 line
2.7.4
PATCH 5/6 formal/spinhint: Put footnote on header in table
In reply to Akira YokosawaFrom 5db712d3f30c38dc5e2dbc6bf0ad68dd0b24870b Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Thu, 31 Jan 2019 00:14:56 +0900
Subject: [PATCH 5/6] formal/spinhint: Put footnote on header in table
The "savenotes" environment provided by the "footnote" package allows us to put a footnote in a table whose text is placed at the bottom of the page.
Also wordsmith the footnote's text.
--- formal/spinhint.tex | 10 ++++++---- perfbook.tex | 1 + 2 files changed, 7 insertions(+), 4 deletions(-)
formal/spinhint.tex +6 -4
@@ -842,6 +842,7 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c ./pan [-mN] \end{VerbatimU} +\begin{savenotes} \begin{table} \rowcolors{1}{}{lightgray} \renewcommand*{\arraystretch}{1.2}
@@ -853,7 +854,9 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c \multicolumn{1}{r}{updaters} & \multicolumn{1}{r}{readers} & \multicolumn{1}{r}{\# states} & - \multicolumn{1}{r}{MB} \\ + \multicolumn{1}{r}{MB\footnote{ + Obtained with the compiler flag \co{-DCOLLAPSE} + specified.}} \\ \midrule 1 & 1 & 376 & 128.7 \\ 1 & 2 & 6 177 & 128.9 \\
@@ -868,12 +871,11 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c \caption{Memory Usage of QRCU Model} \label{tab:advsync:Memory Usage of QRCU Model} \end{table} +\end{savenotes} The resulting output shows that this model passes all of the cases shown in -Table~\ref{tab:advsync:Memory Usage of QRCU Model}.\footnote{ - Figures in the table are obtained with the \co{-DCOLLAPSE} - compiler flag specified.} +Table~\ref{tab:advsync:Memory Usage of QRCU Model}. Now, it would be nice to run the case with three readers and three updaters, however, simple extrapolation indicates that this will require on the order of a terabyte of memory best case.
perfbook.tex +1 -0
@@ -52,6 +52,7 @@ \usepackage[bottom]{footmisc} % place footnotes under floating figures/tables \usepackage{tabularx} \usepackage[hyphens]{url} +\usepackage{footnote} \usepackage[bookmarks=true,bookmarksnumbered=true,pdfborder={0 0 0}]{hyperref} \usepackage{footnotebackref} % to enable cross-ref of footnote \usepackage[all]{hypcap} % for going to the top of figure and table
Signature · 1 line
2.7.4
PATCH 6/6 formal/spinhint: Use \co{...} rather than {\tt ...}
In reply to Akira YokosawaFrom 211a647f0530d7c7fbdab93ae5e76e71e04295f6 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sat, 2 Feb 2019 20:00:36 +0900
Subject: [PATCH 6/6] formal/spinhint: Use \co{...} rather than {\tt ...}
--- formal/spinhint.tex | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-)
formal/spinhint.tex +7 -7
@@ -99,9 +99,9 @@ we lose no verification coverage by making them atomic. The \co{do-od} construct on lines~\lnref{dood1:b}-\lnref{dood1:e} implements a Promela loop, -which can be thought of as a C {\tt for (;;)} loop containing a +which can be thought of as a C \co{for (;;)} loop containing a \co{switch} statement that allows expressions in case labels. -The condition blocks (prefixed by {\tt ::}) +The condition blocks (prefixed by \co{::}) are scanned non-deterministically, though in this case only one of the conditions can possibly hold at a given time.
@@ -190,7 +190,7 @@ It is easy to fix this example by placing the body of the incrementer processes in an atomic blocks as shown in Listing~\ref{lst:analysis:Promela Code for Atomic Increment}. One could also have simply replaced the pair of statements with -{\tt counter = counter + 1}, because Promela statements are +\co{counter = counter + 1}, because Promela statements are atomic. Either way, running this modified model gives us an error-free traversal of the state space, as shown in
@@ -223,7 +223,7 @@ Listing~\ref{lst:analysis:Atomic Increment spin Output}. Table~\ref{tab:advsync:Memory Usage of Increment Model} shows the number of states and memory consumed as a function of number of incrementers modeled -(by redefining {\tt NUMPROCS}): +(by redefining \co{NUMPROCS}): Running unnecessarily large models is thus subtly discouraged, although 882\,MB is well within the limits of modern desktop and laptop machines.
@@ -571,15 +571,15 @@ As expected, this run has no assertion failures (``errors: 0''). \QuickQuizAnswer{ There are several: \begin{enumerate} - \item The declaration of {\tt sum} should be moved to within + \item The declaration of \co{sum} should be moved to within the init block, since it is not used anywhere else. \item The assertion code should be moved outside of the initialization loop. The initialization loop can then be placed in an atomic block, greatly reducing the state space (by how much?). \item The atomic block covering the assertion code should - be extended to include the initialization of {\tt sum} - and {\tt j}, and also to cover the assertion. + be extended to include the initialization of \co{sum} + and \co{j}, and also to cover the assertion. This also reduces the state space (again, by how much?). \end{enumerate}
Signature · 1 line
2.7.4
Quoted 24 lines · Akira Yokosawa
Hi Paul,
Here is another round of code snippet update, with modernization of outputs of Spin and tables of state search results.
Patch #1 updates fcvextract.pl so that .spin files are handled as the same as C source files.
Patch #2 applies the new scheme to code snippets. It also contains minor changes for better typesetting.
Patch #3 replaces captures of Spin outputs with those obtained from Spin version 6.4.8. This commit adds outputs as .lst files under CodeSamples/formal/promela/. They are added to the dependency in the top level
Makefile.Patch #4 updates tables of Spin result. For qrcu.spin, I used the compiler flag -DCOLLAPSE to complete the state search for updaters=3 readers=2 on a machine with 16GB memory. As far as I understand correctly, this compiler flag does not affect the completeness of state search. So I added some explanation in the text to mention the flag and the argument -mN of ./pan to increase the limit of search depth.
Quoted 6 lines
Patch #5 tweaks footnote on a cell in a table.
Patch #6 is a nitpick patch to consistently use \co{}.
I'm wondering if Patch #4 is OK from your perspective. Any feedback is welcome!
Very good, applied and pushed! I added a small patch on top of Patch #4 updating the extrapolation. It was about a terabyte, and is now about half that. I agree that -DCOLLAPSE is a pure optimization, so it should be OK. If we trust the documentation, anyway! ;-)
Thanx, Paul
Quoted 32 lines
Thanks, Akira
--
Akira Yokosawa (6):
fcvextract.pl: Treat '.spin' files as C sources formal/spinhint: Employ new scheme for code snippet formal/spinhint: Update output lists of spin formal/spinhint: Update tables of memory usage of Spin formal/spinhint: Put footnote on header in table formal/spinhint: Use \co{...} rather than {\tt ...}CodeSamples/formal/promela/atomicincrement.spin | 2 + .../formal/promela/atomicincrement.spin.lst | 28 + CodeSamples/formal/promela/increment.spin | 46 +- CodeSamples/formal/promela/increment.spin.lst | 28 + .../formal/promela/increment.spin.trail.lst | 42 + CodeSamples/formal/promela/lock.h | 16 +- CodeSamples/formal/promela/lock.spin | 46 +- CodeSamples/formal/promela/lock.spin.lst | 29 + CodeSamples/formal/promela/qrcu.spin | 95 ++- Makefile | 4 +- formal/spinhint.tex | 874 ++++++--------------- perfbook.tex | 1 + utilities/fcvextract.pl | 8 +- 13 files changed, 502 insertions(+), 717 deletions(-) create mode 100644 CodeSamples/formal/promela/atomicincrement.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.trail.lst create mode 100644 CodeSamples/formal/promela/lock.spin.lstSignature · 1 line
2.7.4
Quoted 27 lines · Paul E. McKenney
Quoted 26 lines · Akira Yokosawa
Hi Paul,
Here is another round of code snippet update, with modernization of outputs of Spin and tables of state search results.
Patch #1 updates fcvextract.pl so that .spin files are handled as the same as C source files.
Patch #2 applies the new scheme to code snippets. It also contains minor changes for better typesetting.
Patch #3 replaces captures of Spin outputs with those obtained from Spin version 6.4.8. This commit adds outputs as .lst files under CodeSamples/formal/promela/. They are added to the dependency in the top level
Makefile.Patch #4 updates tables of Spin result. For qrcu.spin, I used the compiler flag -DCOLLAPSE to complete the state search for updaters=3 readers=2 on a machine with 16GB memory. As far as I understand correctly, this compiler flag does not affect the completeness of state search. So I added some explanation in the text to mention the flag and the argument -mN of ./pan to increase the limit of search depth.
Patch #5 tweaks footnote on a cell in a table.
Quoted 8 lines
Quoted 4 lines
Patch #6 is a nitpick patch to consistently use \co{}.
I'm wondering if Patch #4 is OK from your perspective. Any feedback is welcome!
Very good, applied and pushed! I added a small patch on top of Patch #4 updating the extrapolation. It was about a terabyte, and is now about half that.
Half a terabyte is not prohibitively large these days, and Spin has another compaction option "-DMA=N" which aggressively reduces memory consumption in exchange of search speed.
It took three days to complete, with the total memory usage of 6.5GB. The output looks as follows:
--------
(Spin Version 6.4.6 -- 2 December 2016)
+ Partial Order Reduction
+ Graph Encoding (-DMA=96)
Full statespace search for:
never claim - (none specified)
assertion violations +
cycle checks - (disabled by -DSAFETY)
invalid end states +State-vector 96 byte, depth reached 2055621, errors: 0 MA stats: -DMA=84 is sufficient
Minimized Automaton: 56420520 nodes and 1.75128e+08 edges
9.6647071e+09 states, stored
9.7503813e+09 states, matched
1.9415088e+10 transitions (= stored+matched) 7.2047951e+09 atomic steps
Stats on memory usage (in Megabytes):
1142905.887 equivalent memory usage for states (stored*(State-vector + overhead))
5448.879 actual memory usage for states (compression: 0.48%)
1068.115 memory used for DFS stack (-m20000000)
1.619 memory lost to fragmentation
6515.375 total actual memory usageunreached in proctype qrcu_reader
(0 of 18 states)
unreached in proctype qrcu_updater
qrcu.spin:102, state 82, "-end-"
(1 of 82 states)
unreached in init
(0 of 23 states)pan: elapsed time 2.72e+05 seconds
pan: rate 35500.523 states/second
--------
I'm not sure if this result is worthy enough to be mentioned in the text.
Thoughts?
Thanks, Akira
Quoted 38 lines
I agree that -DCOLLAPSE is a pure optimization, so it should
be OK. If we trust the documentation, anyway! ;-)Thanx, Paul
Quoted 32 lines
Thanks, Akira
--
Akira Yokosawa (6):
fcvextract.pl: Treat '.spin' files as C sources formal/spinhint: Employ new scheme for code snippet formal/spinhint: Update output lists of spin formal/spinhint: Update tables of memory usage of Spin formal/spinhint: Put footnote on header in table formal/spinhint: Use \co{...} rather than {\tt ...}CodeSamples/formal/promela/atomicincrement.spin | 2 + .../formal/promela/atomicincrement.spin.lst | 28 + CodeSamples/formal/promela/increment.spin | 46 +- CodeSamples/formal/promela/increment.spin.lst | 28 + .../formal/promela/increment.spin.trail.lst | 42 + CodeSamples/formal/promela/lock.h | 16 +- CodeSamples/formal/promela/lock.spin | 46 +- CodeSamples/formal/promela/lock.spin.lst | 29 + CodeSamples/formal/promela/qrcu.spin | 95 ++- Makefile | 4 +- formal/spinhint.tex | 874 ++++++--------------- perfbook.tex | 1 + utilities/fcvextract.pl | 8 +- 13 files changed, 502 insertions(+), 717 deletions(-) create mode 100644 CodeSamples/formal/promela/atomicincrement.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.trail.lst create mode 100644 CodeSamples/formal/promela/lock.spin.lstSignature · 1 line
2.7.4
Quoted 79 lines · Akira Yokosawa
Quoted 27 lines · Paul E. McKenney
Quoted 26 lines · Akira Yokosawa
Hi Paul,
Here is another round of code snippet update, with modernization of outputs of Spin and tables of state search results.
Patch #1 updates fcvextract.pl so that .spin files are handled as the same as C source files.
Patch #2 applies the new scheme to code snippets. It also contains minor changes for better typesetting.
Patch #3 replaces captures of Spin outputs with those obtained from Spin version 6.4.8. This commit adds outputs as .lst files under CodeSamples/formal/promela/. They are added to the dependency in the top level
Makefile.Patch #4 updates tables of Spin result. For qrcu.spin, I used the compiler flag -DCOLLAPSE to complete the state search for updaters=3 readers=2 on a machine with 16GB memory. As far as I understand correctly, this compiler flag does not affect the completeness of state search. So I added some explanation in the text to mention the flag and the argument -mN of ./pan to increase the limit of search depth.
Patch #5 tweaks footnote on a cell in a table.
Quoted 8 lines
Quoted 4 lines
Patch #6 is a nitpick patch to consistently use \co{}.
I'm wondering if Patch #4 is OK from your perspective. Any feedback is welcome!
Very good, applied and pushed! I added a small patch on top of Patch #4 updating the extrapolation. It was about a terabyte, and is now about half that.
Half a terabyte is not prohibitively large these days, and Spin has another compaction option "-DMA=N" which aggressively reduces memory consumption in exchange of search speed.
It took three days to complete, with the total memory usage of 6.5GB. The output looks as follows:
--------
(Spin Version 6.4.6 -- 2 December 2016)
+ Partial Order Reduction
+ Graph Encoding (-DMA=96)Full statespace search for:
never claim - (none specified) assertion violations + cycle checks - (disabled by -DSAFETY) invalid end states +State-vector 96 byte, depth reached 2055621, errors: 0 MA stats: -DMA=84 is sufficient
Minimized Automaton: 56420520 nodes and 1.75128e+08 edges
9.6647071e+09 states, stored
9.7503813e+09 states, matched
1.9415088e+10 transitions (= stored+matched) 7.2047951e+09 atomic stepsStats on memory usage (in Megabytes):
1142905.887 equivalent memory usage for states (stored*(State-vector + overhead)) 5448.879 actual memory usage for states (compression: 0.48%) 1068.115 memory used for DFS stack (-m20000000) 1.619 memory lost to fragmentation 6515.375 total actual memory usageunreached in proctype
qrcu_reader(0 of 18 states) unreached in proctype qrcu_updater qrcu.spin:102, state 82, "-end-" (1 of 82 states) unreached in init (0 of 23 states)
Quoted 6 lines
pan: elapsed time 2.72e+05 seconds
pan: rate 35500.523 states/second
--------I'm not sure if this result is worthy enough to be mentioned in the text.
But of course!
As long as the entire table is generated with the same arguments and configuration, and those arguments and configuration are called out somewhere (perhaps in a script somewhere in CodeSamples), please do send me a patch!
Perhaps even better would be to call out those configurations and arguments earlier on in the section giving advice on how to use Promela and spin.
Thanx, Paul
Quoted 43 lines
Thoughts?
Thanks, Akira
Quoted 38 lines
I agree that -DCOLLAPSE is a pure optimization, so it should
be OK. If we trust the documentation, anyway! ;-)Thanx, Paul
Quoted 32 lines
Thanks, Akira
--
Akira Yokosawa (6):
fcvextract.pl: Treat '.spin' files as C sources formal/spinhint: Employ new scheme for code snippet formal/spinhint: Update output lists of spin formal/spinhint: Update tables of memory usage of Spin formal/spinhint: Put footnote on header in table formal/spinhint: Use \co{...} rather than {\tt ...}CodeSamples/formal/promela/atomicincrement.spin | 2 + .../formal/promela/atomicincrement.spin.lst | 28 + CodeSamples/formal/promela/increment.spin | 46 +- CodeSamples/formal/promela/increment.spin.lst | 28 + .../formal/promela/increment.spin.trail.lst | 42 + CodeSamples/formal/promela/lock.h | 16 +- CodeSamples/formal/promela/lock.spin | 46 +- CodeSamples/formal/promela/lock.spin.lst | 29 + CodeSamples/formal/promela/qrcu.spin | 95 ++- Makefile | 4 +- formal/spinhint.tex | 874 ++++++--------------- perfbook.tex | 1 + utilities/fcvextract.pl | 8 +- 13 files changed, 502 insertions(+), 717 deletions(-) create mode 100644 CodeSamples/formal/promela/atomicincrement.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.lst create mode 100644 CodeSamples/formal/promela/increment.spin.trail.lst create mode 100644 CodeSamples/formal/promela/lock.spin.lstSignature · 1 line
2.7.4
cover formal/spinhint: Add result and discussion of 3 readers 3 updaters QRCU Spin run
Hi Paul,
This patch set adds the result and discussion you suggested in this thread.
Instead of replacing the existing table of memory usage (with the flag "-DCOLLAPSE"), I added another table comparing the memory usage and runtime obtained with "-DCOLLAPSE" and "-DMA=N".
Patch #1 adds the result as a summary table and give some discussion of the usage of the compiler flag "-DMA=N". It also adds a quick quiz comparing the result of "-DCOLLAPSE" and "-DMA=N" with 2 readers and 3 updaters.
Patch #2 adds a column of search depth in the existing Table 12.2 of memory usage with "-DCOLLAPSE". This helps the extrapolation of necessary search depth for 3 readers and 3 updaters.
Patch #3 is a minor tweak of a footnote in Table 12.2.
It should be possible to reconstruct the story to reference only the added summary table, but I took another way to minimize the change of story. The point is that as long as you have sufficient memory, there is no need to use "-DMA=N". The search speed can be slower than that with the flag "-DCOLLAPSE" by nearly one order of magnitude.
Any feedback/update is more than welcome!
Thanks, Akira
--
Akira Yokosawa (3):
formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin run formal/spinhint: Add column of search depth in Table 12.2 formal/spinhint: Place footnote inside floating table
.../formal/promela/atomicincrement.spin.lst | 2 +- CodeSamples/formal/promela/increment.spin.lst | 2 +- CodeSamples/formal/promela/lock.spin.lst | 2 +- CodeSamples/formal/promela/qrcu.spin.33ma.lst | 37 +++++ .../formal/promela/qrcu.spin.col-ma.diff.lst | 48 ++++++ formal/spinhint.tex | 185 ++++++++++++++++++--- perfbook.tex | 2 +- 7 files changed, 254 insertions(+), 24 deletions(-) create mode 100644 CodeSamples/formal/promela/qrcu.spin.33ma.lst create mode 100644 CodeSamples/formal/promela/qrcu.spin.col-ma.diff.lst
Signature · 1 line
2.7.4
PATCH 1/3 formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin run
From fe701731c7296b90deae52747f5f3be556511289 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 10 Feb 2019 00:02:26 +0900
Subject: [PATCH 1/3] formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin run
By using the compiler flag "-DMA=N", run of qrcu.spin with 3 readers and 3 updaters can be completed with the memory usage of 6.5GHz.
This commit adds the result and the command used to run the verification. A Quick Quiz is added to present an indirect evidence of search completeness.
As the compiler flag "-DCOLLAPSE" generates much faster code, memory usage table with "-DCOLLAPSE" is kept. The complete table for the runs with the flag "-DMA=N" is added as another table.
--- .../formal/promela/atomicincrement.spin.lst | 2 +- CodeSamples/formal/promela/increment.spin.lst | 2 +- CodeSamples/formal/promela/lock.spin.lst | 2 +- CodeSamples/formal/promela/qrcu.spin.33ma.lst | 37 +++++ .../formal/promela/qrcu.spin.col-ma.diff.lst | 48 +++++++ formal/spinhint.tex | 150 ++++++++++++++++++++- 6 files changed, 234 insertions(+), 7 deletions(-) create mode 100644 CodeSamples/formal/promela/qrcu.spin.33ma.lst create mode 100644 CodeSamples/formal/promela/qrcu.spin.col-ma.diff.lst
CodeSamples/formal/promela/atomicincrement.spin.lst +1 -1
@@ -16,7 +16,7 @@ hash conflicts: 0 (resolved) Stats on memory usage (in Megabytes): 0.004 equivalent memory usage for states - (stored*(State-vector + overhead)) + (stored*(State-vector + overhead)) 0.290 actual memory usage for states 128.000 memory used for hash table (-w24) 0.534 memory used for DFS stack (-m10000)
CodeSamples/formal/promela/increment.spin.lst +1 -1
@@ -21,7 +21,7 @@ hash conflicts: 0 (resolved) Stats on memory usage (in Megabytes): 0.003 equivalent memory usage for states - (stored*(State-vector + overhead)) + (stored*(State-vector + overhead)) 0.290 actual memory usage for states 128.000 memory used for hash table (-w24) 0.534 memory used for DFS stack (-m10000)
CodeSamples/formal/promela/lock.spin.lst +1 -1
@@ -16,7 +16,7 @@ hash conflicts: 0 (resolved) Stats on memory usage (in Megabytes): 0.044 equivalent memory usage for states - (stored*(State-vector + overhead)) + (stored*(State-vector + overhead)) 0.288 actual memory usage for states 128.000 memory used for hash table (-w24) 0.534 memory used for DFS stack (-m10000)
CodeSamples/formal/promela/qrcu.spin.33ma.lst new file +37 -0
@@ -0,0 +1,37 @@ +(Spin Version 6.4.6 -- 2 December 2016) + + Partial Order Reduction + + Graph Encoding (-DMA=96) + +Full statespace search for: + never claim - (none specified) + assertion violations + + cycle checks - (disabled by -DSAFETY) + invalid end states + + +State-vector 96 byte, depth reached 2055621, errors: 0 +MA stats: -DMA=84 is sufficient +Minimized Automaton: 56420520 nodes and 1.75128e+08 edges +9.6647071e+09 states, stored +9.7503813e+09 states, matched +1.9415088e+10 transitions (= stored+matched) +7.2047951e+09 atomic steps + +Stats on memory usage (in Megabytes): +1142905.887 equivalent memory usage for states + (stored*(State-vector + overhead)) + 5448.879 actual memory usage for states + (compression: 0.48%) + 1068.115 memory used for DFS stack (-m20000000) + 1.619 memory lost to fragmentation + 6515.375 total actual memory usage + +unreached in proctype qrcu_reader + (0 of 18 states) +unreached in proctype qrcu_updater + qrcu.spin:102, state 82, "-end-" + (1 of 82 states) +unreached in init + (0 of 23 states) + +pan: elapsed time 2.72e+05 seconds +pan: rate 35500.523 states/second
CodeSamples/formal/promela/qrcu.spin.col-ma.diff.lst new file +48 -0
48 lines not on this page · raw message
formal/spinhint.tex +146 -4
177 lines not on this page · raw message
Signature · 1 line
2.7.4
Re: [PATCH 1/3] formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin run
Paul,
There was a typo in the commit log.
Quoted 7 lines · Akira Yokosawa
From
fe701731c7296b90deae52747f5f3be556511289Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 10 Feb 2019 00:02:26 +0900
Subject: [PATCH 1/3] formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin runBy using the compiler flag "-DMA=N", run of qrcu.spin with 3 readers and 3 updaters can be completed with the memory usage of 6.5GHz.
^^^^
6.5GB.Can you amend it for me?
Thanks, Akira
Quoted 22 lines
This commit adds the result and the command used to run the verification. A Quick Quiz is added to present an indirect evidence of search completeness.
As the compiler flag "-DCOLLAPSE" generates much faster code, memory usage table with "-DCOLLAPSE" is kept. The complete table for the runs with the flag "-DMA=N" is added as another table.
Signed-off-by Akira Yokosawa <[email protected]>--- .../formal/promela/atomicincrement.spin.lst | 2 +- CodeSamples/formal/promela/increment.spin.lst | 2 +- CodeSamples/formal/promela/lock.spin.lst | 2 +- CodeSamples/formal/promela/qrcu.spin.33ma.lst | 37 +++++ .../formal/promela/qrcu.spin.col-ma.diff.lst | 48 +++++++ formal/spinhint.tex | 150 ++++++++++++++++++++- 6 files changed, 234 insertions(+), 7 deletions(-) create mode 100644 CodeSamples/formal/promela/qrcu.spin.33ma.lst create mode 100644 CodeSamples/formal/promela/qrcu.spin.col-ma.diff.lst
[...]
Re: [PATCH 1/3] formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin run
Quoted 10 lines · Akira Yokosawa
Paul,
There was a typo in the commit log.
Quoted 5 lines · Akira Yokosawa
From
fe701731c7296b90deae52747f5f3be556511289Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 10 Feb 2019 00:02:26 +0900
Subject: [PATCH 1/3] formal/spinhint: Add result of 3 readers 3 updaters QRCU Spin run
Quoted 7 lines
Quoted 2 lines
By using the compiler flag "-DMA=N", run of qrcu.spin with 3 readers and 3 updaters can be completed with the memory usage of 6.5GHz.
^^^^ 6.5GB.Can you amend it for me?
Done! I queued and pushed all three, and also pushed out some minor wordsmithing. Please let me know if I messed anything up.
And nice approach showing the strengths and weaknesses of the two approaches, good stuff, thank you!
Thanx, Paul
Quoted 26 lines
Thanks, Akira
Quoted 22 lines
This commit adds the result and the command used to run the verification. A Quick Quiz is added to present an indirect evidence of search completeness.
As the compiler flag "-DCOLLAPSE" generates much faster code, memory usage table with "-DCOLLAPSE" is kept. The complete table for the runs with the flag "-DMA=N" is added as another table.
Signed-off-by Akira Yokosawa <[email protected]>--- .../formal/promela/atomicincrement.spin.lst | 2 +- CodeSamples/formal/promela/increment.spin.lst | 2 +- CodeSamples/formal/promela/lock.spin.lst | 2 +- CodeSamples/formal/promela/qrcu.spin.33ma.lst | 37 +++++ .../formal/promela/qrcu.spin.col-ma.diff.lst | 48 +++++++ formal/spinhint.tex | 150 ++++++++++++++++++++- 6 files changed, 234 insertions(+), 7 deletions(-) create mode 100644 CodeSamples/formal/promela/qrcu.spin.33ma.lst create mode 100644 CodeSamples/formal/promela/qrcu.spin.col-ma.diff.lst[...]
PATCH 2/3 formal/spinhint: Add column of search depth in Table 12.2
In reply to Akira YokosawaFrom 5c56bad538021adfb91fbb6b65ff0b5544f4e849 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 11 Feb 2019 08:44:25 +0900
Subject: [PATCH 2/3] formal/spinhint: Add column of search depth in Table 12.2
--- formal/spinhint.tex | 27 ++++++++++++++------------- 1 file changed, 14 insertions(+), 13 deletions(-)
formal/spinhint.tex +14 -13
@@ -856,26 +856,27 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c \begin{table} \rowcolors{1}{}{lightgray} \renewcommand*{\arraystretch}{1.2} -\small +\footnotesize \centering \begin{tabular}{S[table-format = 1.0]S[table-format = 1.0]S[table-format = 9.0] - S[table-format = 5.1]} + S[table-format = 6.0]S[table-format = 5.1]} \toprule \multicolumn{1}{r}{updaters} & \multicolumn{1}{r}{readers} & \multicolumn{1}{r}{\# states} & - \multicolumn{1}{r}{MB\footnote{ - Obtained with the compiler flag \co{-DCOLLAPSE} - specified.}} \\ + \multicolumn{1}{r}{depth} & + \multicolumn{1}{r}{memory (MB)\footnote{ + Obtained with the compiler flag \co{-DCOLLAPSE} + specified.}} \\ \midrule - 1 & 1 & 376 & 128.7 \\ - 1 & 2 & 6 177 & 128.9 \\ - 1 & 3 & 99 728 & 132.6 \\ - 2 & 1 & 29 399 & 129.8 \\ - 2 & 2 & 1 071 181 & 169.6 \\ - 2 & 3 & 33 866 736 & 1 540.8 \\ - 3 & 1 & 2 749 453 & 236.6 \\ - 3 & 2 & 186 202 860 & 10 483.7 \\ + 1 & 1 & 376 & 95 & 128.7 \\ + 1 & 2 & 6 177 & 218 & 128.9 \\ + 1 & 3 & 99 728 & 385 & 132.6 \\ + 2 & 1 & 29 399 & 859 & 129.8 \\ + 2 & 2 & 1 071 181 & 2 352 & 169.6 \\ + 2 & 3 & 33 866 736 & 12 857 & 1 540.8 \\ + 3 & 1 & 2 749 453 & 53 809 & 236.6 \\ + 3 & 2 & 186 202 860 & 328 014 & 10 483.7 \\ \bottomrule \end{tabular} \caption{Memory Usage of QRCU Model}
Signature · 1 line
2.7.4
PATCH 3/3 formal/spinhint: Place footnote inside floating table
In reply to Akira YokosawaFrom 05dd848e5c6610278ed6975bcb3cab256b9136d4 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 11 Feb 2019 10:43:57 +0900
Subject: [PATCH 3/3] formal/spinhint: Place footnote inside floating table
It turns out the "savenotes" environment tried in commit 5df9ce3b9449 ("formal/spinhint: Put footnote on header in table") is not robust enough. Depending on the layout, text of a footnote can appear at the bottom of a page ahead of (or behind) the page where the floating table itself is typeset.
Putting such footnotes inside a floating table by the help of the "threeparttable" package looks like an orthodox way recommended in the LaTeX community [1].
[1]: https://texfaq.org/FAQ-footintab
--- formal/spinhint.tex | 14 ++++++++------ perfbook.tex | 2 +- 2 files changed, 9 insertions(+), 7 deletions(-)
formal/spinhint.tex +8 -6
@@ -852,12 +852,12 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c ./pan [-mN] \end{VerbatimU} -\begin{savenotes} \begin{table} +\centering +\begin{threeparttable} \rowcolors{1}{}{lightgray} \renewcommand*{\arraystretch}{1.2} \footnotesize -\centering \begin{tabular}{S[table-format = 1.0]S[table-format = 1.0]S[table-format = 9.0] S[table-format = 6.0]S[table-format = 5.1]} \toprule
@@ -865,9 +865,7 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c \multicolumn{1}{r}{readers} & \multicolumn{1}{r}{\# states} & \multicolumn{1}{r}{depth} & - \multicolumn{1}{r}{memory (MB)\footnote{ - Obtained with the compiler flag \co{-DCOLLAPSE} - specified.}} \\ + \multicolumn{1}{r}{memory (MB)\tnote{a}} \\ \midrule 1 & 1 & 376 & 95 & 128.7 \\ 1 & 2 & 6 177 & 218 & 128.9 \\
@@ -879,10 +877,14 @@ cc -DSAFETY [-DCOLLAPSE] -o pan pan.c 3 & 2 & 186 202 860 & 328 014 & 10 483.7 \\ \bottomrule \end{tabular} +\begin{tablenotes} + \item [a] Obtained with the compiler flag \co{-DCOLLAPSE} + specified. +\end{tablenotes} +\end{threeparttable} \caption{Memory Usage of QRCU Model} \label{tab:advsync:Memory Usage of QRCU Model} \end{table} -\end{savenotes} The resulting output shows that this model passes all of the cases shown in
perfbook.tex +1 -1
@@ -52,7 +52,7 @@ \usepackage[bottom]{footmisc} % place footnotes under floating figures/tables \usepackage{tabularx} \usepackage[hyphens]{url} -\usepackage{footnote} +\usepackage{threeparttable} \usepackage[bookmarks=true,bookmarksnumbered=true,pdfborder={0 0 0}]{hyperref} \usepackage{footnotebackref} % to enable cross-ref of footnote \usepackage[all]{hypcap} % for going to the top of figure and table
Signature · 1 line
2.7.4