summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/l3experimental/l3benchmark.dtx
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/l3experimental/l3benchmark.dtx
Initial commit
Diffstat (limited to 'macros/latex/contrib/l3experimental/l3benchmark.dtx')
-rw-r--r--macros/latex/contrib/l3experimental/l3benchmark.dtx584
1 files changed, 584 insertions, 0 deletions
diff --git a/macros/latex/contrib/l3experimental/l3benchmark.dtx b/macros/latex/contrib/l3experimental/l3benchmark.dtx
new file mode 100644
index 0000000000..c7b172488a
--- /dev/null
+++ b/macros/latex/contrib/l3experimental/l3benchmark.dtx
@@ -0,0 +1,584 @@
+% \iffalse meta-comment
+%
+%% File: l3benchmark.dtx
+%
+% Copyright (C) 2011,2012,2014-2019 The LaTeX3 Project
+%
+% It may be distributed and/or modified under the conditions of the
+% LaTeX Project Public License (LPPL), either version 1.3c of this
+% license or (at your option) any later version. The latest version
+% of this license is in the file
+%
+% http://www.latex-project.org/lppl.txt
+%
+% This file is part of the "l3experimental bundle" (The Work in LPPL)
+% and all files in that bundle must be distributed together.
+%
+% -----------------------------------------------------------------------
+%
+% The development version of the bundle can be found at
+%
+% https://github.com/latex3/latex3
+%
+% for those people who are interested.
+%
+%<*driver|package>
+\RequirePackage{expl3}
+%</driver|package>
+%<*driver>
+\documentclass[full]{l3doc}
+\begin{document}
+ \DocInput{\jobname.dtx}
+\end{document}
+%</driver>
+% \fi
+%
+% \title{^^A
+% The \pkg{l3benchmark} package\\ Experimental benchmarking^^A
+% }
+%
+% \author{^^A
+% The \LaTeX3 Project\thanks
+% {^^A
+% E-mail:
+% \href{mailto:latex-team@latex-project.org}
+% {latex-team@latex-project.org}^^A
+% }^^A
+% }
+%
+% \date{Released 2019-08-25}
+%
+% \maketitle
+%
+% \begin{documentation}
+%
+% \section{Additions to \pkg{l3sys}: elapsed time}
+%
+% \begin{function}{\sys_gzero_timer:}
+% \begin{syntax}
+% \cs{sys_gzero_timer:}
+% \end{syntax}
+% Resets the timer to zero.
+% \end{function}
+%
+% \begin{function}[EXP]{\sys_timer:}
+% \begin{syntax}
+% \cs{sys_timer:}
+% \end{syntax}
+% Expands to the current value of the engine's timer clock, a
+% non-negative integer. In engines without clock support this expands
+% to $0$ after an error. In \LuaTeX{} only the CPU time is measured,
+% while in other engines real time is measured (including time waiting
+% for user input).
+% \end{function}
+%
+% \section{Benchmark}
+%
+% \begin{variable}{\g_benchmark_duration_target_fp}
+% This variable (default value: $1$) controls roughly for how long
+% \cs{benchmark:n} will repeat code to more accurately benchmark it.
+% The actual duration of one call to \cs{benchmark:n} typically lasts
+% between half and twice \cs{g_benchmark_duration_target_fp} seconds,
+% unless of course running the code only once already lasts longer
+% than this.
+% \end{variable}
+%
+% \begin{function}{\benchmark_once:n}
+% \begin{syntax}
+% \cs{benchmark_once:n} \Arg{code}
+% \end{syntax}
+% Prints to the terminal the time taken by \TeX{} to run the
+% \meta{code}, and an estimated number of elementary operations. The
+% \meta{code} is run only once so the time may be quite inaccurate for
+% fast code.
+% \end{function}
+%
+% \begin{function}{\benchmark:n}
+% \begin{syntax}
+% \cs{benchmark:n} \Arg{code}
+% \end{syntax}
+% Prints to the terminal the time taken by \TeX{} to run the
+% \meta{code}, and an estimated number of elementary operations. The
+% \meta{code} may be run many times and not within a group, thus code
+% with side-effects may cause problems.
+% \end{function}
+%
+% \begin{function}{\benchmark_tic:, \benchmark_toc:}
+% \begin{syntax}
+% \cs{benchmark_tic:} \meta{slow code} \cs{benchmark_toc:}
+% \end{syntax}
+% When it is not possible to run \cs{benchmark:n} (e.g., the code is
+% part of the execution of a package which cannot be looped) the
+% tic/toc commands can be used instead to time between two points in
+% the code. When executed, \cs{benchmark_tic:} will print a line to the
+% terminal, and \cs{benchmark_toc:} will print a matching line with a
+% time to indicate the duration between them in seconds.
+% These commands can be nested.
+% \end{function}
+%
+% \end{documentation}
+%
+% \begin{implementation}
+%
+% \section{\pkg{l3benchmark} implementation}
+%
+% Our working unit is the scaled second, namely $2^{-16}$ seconds.
+%
+% \begin{macrocode}
+%<*initex|package>
+% \end{macrocode}
+%
+% \begin{macrocode}
+%<*package>
+\ProvidesExplPackage{l3benchmark}{2019-08-25}{}
+ {L3 Experimental benchmarking}
+%</package>
+% \end{macrocode}
+%
+% \subsection{Additions to \pkg{l3sys}: elapsed time}
+%
+% \begin{macrocode}
+%<@@=sys>
+% \end{macrocode}
+%
+% \begin{macro}[EXP]{\sys_timer:}
+% \begin{macro}[EXP,pTF]{\sys_if_timer_exist:}
+% In \LuaTeX{}, use emulation (see \pkg{l3luatex}),
+% otherwise try to locate the primitive. The
+% elapsed time will be available if this succeeds.
+% \begin{macrocode}
+\sys_if_engine_luatex:TF
+ {
+ \cs_new:Npn \sys_timer:
+ { \lua_now:n { l3kernel.elapsedtime() } }
+ }
+ {
+ \cs_if_exist:NT \tex_elapsedtime:D
+ {
+ \cs_new:Npn \sys_timer:
+ { \int_value:w \tex_elapsedtime:D }
+ }
+ }
+\@@_const:nn { sys_if_timer_exist }
+ { \cs_if_exist_p:N \sys_timer: }
+% \end{macrocode}
+% \end{macro}
+% \end{macro}
+%
+% \begin{macro}{\sys_gzero_timer:, \@@_timer_fp:}
+% \begin{variable}{\g_@@_timer_base_fp}
+% Three case, and in each case we define \cs{sys_gzero_timer:}.
+% \begin{macrocode}
+\cs_if_exist:NTF \sys_timer:
+ {
+ \sys_if_engine_luatex:TF
+ {
+ \cs_new_protected:Npn \sys_gzero_timer:
+ { \lua_now:n { l3kernel.resettimer() } }
+ }
+ { \cs_new_protected:Npn \sys_gzero_timer: { \tex_resettimer:D } }
+ }
+% \end{macrocode}
+% If the elapsed time cannot be accessed then we define user
+% commands to produce errors.
+% \begin{macrocode}
+ {
+ \__kernel_msg_new:nnnn { kernel } { no-elapsed-time }
+ { No~clock~detected~for~#1. }
+ { The~current~engine~provides~no~way~to~access~the~system~time. }
+ \cs_new_protected:Npn \sys_gzero_timer:
+ {
+ \__kernel_msg_error:nnn { kernel } { no-elapsed-time }
+ { \sys_gzero_timer: }
+ }
+ \cs_new:Npn \sys_timer:
+ {
+ \int_value:w
+ \__kernel_msg_expandable_error:nnn { kernel } { no-elapsed-time }
+ { \sys_timer: }
+ \c_zero_int
+ }
+ }
+% \end{macrocode}
+% \end{variable}
+% \end{macro}
+%
+% \subsection{Benchmarking code}
+%
+% \begin{macrocode}
+%<@@=benchmark>
+% \end{macrocode}
+%
+% \begin{variable}{\g_benchmark_duration_target_fp}
+% The benchmark is constrained to take roughly (from half to twice)
+% \cs{g_benchmark_duration_target_fp} seconds, unless one iteration of
+% the code takes longer.
+% \begin{macrocode}
+\fp_new:N \g_benchmark_duration_target_fp
+\fp_gset:Nn \g_benchmark_duration_target_fp { 1 }
+% \end{macrocode}
+% \end{variable}
+%
+% Having access to the system time is essential.
+% \begin{macrocode}
+\sys_if_timer_exist:F
+ {
+ \fp_gset:Nn \g_benchmark_duration_target_fp { nan }
+ \cs_new_protected:Npn \benchmark_once:n #1
+ { \msg_error:nn { benchmark } { no-time } }
+ \cs_new_eq:NN \benchmark:n \benchmark_once:n
+ \cs_new_protected:Npn \benchmark_tic:
+ { \msg_error:nn { benchmark } { no-time } }
+ \cs_new_eq:NN \benchmark_toc: \benchmark_tic:
+ \msg_new:nnnn { benchmark } { no-time }
+ { The~l3benchmark~package~failed~to~access~a~clock. }
+ { The~current~engine~provides~no~way~to~access~the~system~time. }
+ \msg_critical:nn { benchmark } { no-time }
+ }
+% \end{macrocode}
+%
+% \subsubsection{Raw measurement}
+%
+% \begin{variable}{\g_@@_nesting_int}
+% \begin{macro}{\@@_raw:nN, \@@_raw_aux:N, \@@_raw_end:N}
+% Store in the given integer variable the time it took to perform a given
+% piece of code, in scaled seconds. We call \cs{sys_timer:} as
+% close before and after the code as possible. We store the
+% intermediate result in a new integer when \cs{@@_raw:nN} is
+% nested.
+% \begin{macrocode}
+\int_new:N \g_@@_nesting_int
+\cs_new_protected:Npn \@@_raw:nN #1
+ {
+ \int_gincr:N \g_@@_nesting_int
+ \exp_args:Nc \@@_raw_aux:N
+ { g_@@_ \int_use:N \g_@@_nesting_int _int }
+ \@@_raw_aux:
+ #1
+ \@@_raw_end:N
+ }
+\cs_new_protected:Npn \@@_raw_aux:N #1
+ {
+ \int_gzero_new:N #1
+ \cs_gset_protected:Npn \@@_raw_aux: { \int_gset:Nn #1 { \sys_timer: } }
+ }
+\cs_new_protected:Npn \@@_raw_end:N #1
+ {
+ \int_gset:Nn #1
+ {
+ \sys_timer: -
+ \int_use:c { g_@@_ \int_use:N \g_@@_nesting_int _int }
+ }
+ \int_gdecr:N \g_@@_nesting_int
+ }
+% \end{macrocode}
+% \end{macro}
+% \end{variable}
+%
+% \begin{macro}{\@@_raw_replicate:nnN, \@@_tmp:w}
+% Here, we wish to measure the time it takes for the piece of code
+% |#2| to be run |#1| times, and store the result in the
+% integer~|#3|.
+%
+% If the number of copies required is large, defining \cs{@@_tmp:w}
+% would exhaust \TeX{}'s main memory. In that case, we replicate
+% $|#1|/5000$ times the given code before passing it to the main call
+% to \cs{@@_tmp:w}. Of course the division rounds to an integer, so
+% that step introduces a relative error of order at most
+% $5000/500000$, less than many other sources of variability.
+%
+% We subtract the time for another call to \cs{@@_tmp:w}, with the
+% same arguments (to capture the time it takes to read the argument)
+% but empty expansion.
+% \begin{macrocode}
+\cs_new_eq:NN \@@_tmp:w ?
+\cs_new_protected:Npn \@@_raw_replicate:nnN #1
+ {
+ \int_compare:nNnTF {#1} > { 500000 }
+ { \@@_raw_replicate_large:nnN {#1} }
+ { \@@_raw_replicate_small:nnN {#1} }
+ }
+\cs_new_protected:Npn \@@_raw_replicate_large:nnN #1#2
+ {
+ \cs_set:Npx \@@_tmp:w ##1 { \prg_replicate:nn { 5000 } {##1} }
+ \exp_args:Nno \@@_raw_replicate:nnN { #1 / 5000 }
+ { \@@_tmp:w {#2} }
+ }
+\cs_new_protected:Npn \@@_raw_replicate_small:nnN #1#2
+ {
+ \cs_set:Npx \@@_tmp:w ##1##2 { \prg_replicate:nn {#1} {##1} }
+ \@@_raw:nN { \@@_tmp:w {#2} { } } \g_@@_time_int
+ \exp_args:No \@@_raw_replicate_aux:nnN
+ { \int_use:N \g_@@_time_int } {#2}
+ }
+\cs_new_protected:Npn \@@_raw_replicate_aux:nnN #1#2#3
+ {
+ \@@_raw:nN { \@@_tmp:w { } {#2} } \g_@@_time_int
+ \int_gset:Nn #3 { #1 - \g_@@_time_int }
+ \cs_set_eq:NN \@@_tmp:w \prg_do_nothing:
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \subsubsection{Main benchmarking}
+%
+% \begin{variable}{\g_@@_time_fp, \g_@@_ops_fp}
+% Functions such as \cs{benchmark:n} store the measured time in
+% \cs{g_@@_time_fp} (in seconds) and the estimated number of
+% operations in \cs{g_@@_ops_fp}.
+% \begin{macrocode}
+\fp_new:N \g_@@_time_fp
+\fp_new:N \g_@@_ops_fp
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{variable}{\g_@@_duration_int}
+% A conversion of \cs{g_benchmark_duration_target_fp} seconds into scaled seconds.
+% \begin{macrocode}
+\int_new:N \g_@@_duration_int
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{variable}{\g_@@_time_int, \g_@@_time_a_int, \g_@@_time_b_int, \g_@@_time_c_int, \g_@@_time_d_int}
+% These variables hold the time for running a piece of code, as an
+% integer in scaled seconds.
+% \begin{macrocode}
+\int_new:N \g_@@_time_int
+\int_new:N \g_@@_time_a_int
+\int_new:N \g_@@_time_b_int
+\int_new:N \g_@@_time_c_int
+\int_new:N \g_@@_time_d_int
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{variable}{\g_@@_repeat_int}
+% Holds the number of times that the piece of code was
+% repeated when timing.
+% \begin{macrocode}
+\int_new:N \g_@@_repeat_int
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{variable}{\g_@@_code_tl}
+% Holds the piece of code to repeat.
+% \begin{macrocode}
+\tl_new:N \g_@@_code_tl
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{macro}{\benchmark_once:n}
+% Convert the raw time from scaled seconds to seconds, and convert to
+% a number of operations. It is important to measure the elementary
+% operation before running the user code because both measurements use
+% the same temporary variables.
+% \begin{macrocode}
+\cs_new_protected:Npn \benchmark_once:n #1
+ {
+ \@@_measure_op:
+ \@@_raw:nN {#1} \g_@@_time_int
+ \fp_gset:Nn \g_@@_time_fp { \g_@@_time_int / 65536 }
+ \@@_display:
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\benchmark:n}
+% After setting up some variables the work is done by \cs{@@_aux:}.
+% \begin{macrocode}
+\cs_new_protected:Npn \benchmark:n #1
+ {
+ \@@_measure_op:
+ \tl_gset:Nn \g_@@_code_tl {#1}
+ \@@_aux:
+ \@@_display:
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\@@_aux:}
+% The main timing function. First time the user code once. If that
+% took more than half the allotted time (\cs{g_@@_duration_int}) we're
+% done. If that took much less, repeatedly quadruple the number of
+% copies until it takes a reasonable amount of time. Once we reach a
+% reasonable time (or we risk an overflow), compute a number of times
+% that can fit in one quarter of the allotted time and measure that
+% four times. To save time we reuse the result of the first pass if
+% \cs{g_@@_repeat_int} is one. Once we have four results, find the
+% smallest, divided by $65536$ and by the number of repetitions, and
+% display that.
+% \begin{macrocode}
+\cs_new_protected:Npn \@@_aux:
+ {
+ \int_gset:Nn \g_@@_repeat_int { 1 }
+ \@@_raw:nN { \g_@@_code_tl } \g_@@_time_int
+ \int_compare:nNnF \g_@@_time_int < { \g_@@_duration_int / 2 }
+ { \prg_break: }
+ \bool_until_do:nn
+ {
+ \int_compare_p:nNn \g_@@_time_int > { \g_@@_duration_int / 32 }
+ || \int_compare_p:nNn \g_@@_repeat_int > { \c_max_int / 4 }
+ }
+ {
+ \int_gset:Nn \g_@@_repeat_int { 4 * \g_@@_repeat_int }
+ \@@_run:N \g_@@_time_int
+ }
+ \int_gset:Nn \g_@@_repeat_int
+ {
+ \fp_to_int:n
+ {
+ max ( 1 , min ( \c_max_int ,
+ \g_@@_duration_int * \g_@@_repeat_int /
+ \int_eval:n { 4 * \g_@@_time_int } ) )
+ }
+ }
+ \int_compare:nNnTF \g_@@_repeat_int = 1
+ { \int_gset_eq:NN \g_@@_time_a_int \g_@@_time_int }
+ { \@@_run:N \g_@@_time_a_int }
+ \@@_run:N \g_@@_time_b_int
+ \@@_run:N \g_@@_time_c_int
+ \@@_run:N \g_@@_time_d_int
+ \int_gset:Nn \g_@@_time_int
+ {
+ \int_min:nn
+ { \int_min:nn \g_@@_time_a_int \g_@@_time_b_int }
+ { \int_min:nn \g_@@_time_c_int \g_@@_time_d_int }
+ }
+ \prg_break_point:
+ \int_compare:nNnT \g_@@_time_int < 3 { \int_gzero:N \g_@@_time_int }
+ \fp_gset:Nn \g_@@_time_fp
+ { \g_@@_time_int / \g_@@_repeat_int / 65536 }
+ }
+\cs_new_protected:Npn \@@_run:N
+ { \exp_args:NNo \@@_raw_replicate:nnN \g_@@_repeat_int { \g_@@_code_tl } }
+% \end{macrocode}
+% \end{macro}
+%
+% \subsubsection{Display}
+%
+% \begin{variable}{\g_@@_one_op_fp}
+% Time for one operation.
+% \begin{macrocode}
+\fp_new:N \g_@@_one_op_fp
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{macro}{\@@_measure_op:}
+% Measure one arbitrary single operation (which we put in \cs{g_@@_code_tl}).
+% This uses a common auxiliary \cs{@@_aux:} with the main benchmark function.
+% \begin{macrocode}
+\cs_new_protected:Npn \@@_measure_op:
+ {
+ \int_gset:Nn \g_@@_duration_int
+ { \fp_to_int:n { 65536 * \g_benchmark_duration_target_fp } / 4 }
+ \tl_gset:Nn \g_@@_code_tl
+ { \int_gadd:Nn \g_@@_duration_int { 0 } }
+ \@@_aux:
+ \fp_gset:Nn \g_@@_one_op_fp { max(\g_@@_time_fp, 1e-16) }
+ \int_gset:Nn \g_@@_duration_int
+ { \fp_to_int:n { 65536 * \g_benchmark_duration_target_fp } }
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\@@_fp_to_tl:N, \@@_fp_to_tl_aux:nN}
+% Similar to \cs{fp_to_tl:N} but rounds to $3$ significant digits and
+% uses scientific notation starting from |1e3|.
+% \begin{macrocode}
+\cs_new:Npn \@@_fp_to_tl:N #1
+ {
+ \fp_compare:nTF { abs(#1) < 1000 }
+ { \fp_to_tl:n { round(#1, 2 - logb(#1)) } }
+ {
+ \exp_args:Nf \@@_fp_to_tl_aux:nN
+ { \fp_to_int:n { logb(#1) } } #1
+ }
+ }
+\cs_new:Npn \@@_fp_to_tl_aux:nN #1#2
+ { \fp_to_tl:n { round(#2 * 1e-#1, 2) } e#1 }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\@@_display:}
+% Function to display the time that was measured and the estimated
+% number of operations.
+% \begin{macrocode}
+\cs_new_protected:Npn \@@_display:
+ {
+ \fp_gset:Nn \g_@@_ops_fp { \g_@@_time_fp / \g_@@_one_op_fp }
+ \iow_term:x
+ {
+ \@@_fp_to_tl:N \g_@@_time_fp \c_space_tl seconds \c_space_tl
+ ( \@@_fp_to_tl:N \g_@@_ops_fp \c_space_tl ops)
+ }
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \subsection{Benchmark tic toc}
+%
+% \begin{variable}{\g_@@_tictoc_int, \g_@@_tictoc_seq, \l_@@_tictoc_pop_tl}
+% \begin{macrocode}
+\int_new:N \g_@@_tictoc_int
+\seq_new:N \g_@@_tictoc_seq
+\tl_new:N \l_@@_tictoc_pop_tl
+% \end{macrocode}
+% \end{variable}
+%
+% \begin{macro}[EXP]{\@@_tictoc_prefix:}
+% We include the package name in analogy with continuation lines of
+% error/warning messages.
+% \begin{macrocode}
+\cs_new:Npn \@@_tictoc_prefix:
+ {
+ (l3benchmark) \c_space_tl
+ + \prg_replicate:nn { \g_@@_tictoc_int } { -+ } \c_space_tl
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\benchmark_tic:}
+% \begin{macrocode}
+\cs_new_protected:Npn \benchmark_tic:
+ {
+ \iow_term:x { \@@_tictoc_prefix: TIC }
+ \exp_args:NNf \seq_gput_right:Nn \g_@@_tictoc_seq { \sys_timer: }
+ \int_gincr:N \g_@@_tictoc_int
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macro}{\benchmark_toc:, \@@_toc:}
+% \begin{macrocode}
+\cs_new:Npn \benchmark_toc:
+ {
+ \seq_gpop_right:NNTF \g_@@_tictoc_seq \l_@@_tictoc_pop_tl
+ { \@@_toc: }
+ { \msg_error:nn { benchmark } { toc-first } }
+ }
+\cs_new_protected:Npn \@@_toc:
+ {
+ \int_gdecr:N \g_@@_tictoc_int
+ \fp_gset:Nn \g_@@_time_fp
+ { ( \sys_timer: - \l_@@_tictoc_pop_tl ) / 65536 }
+ \iow_term:x
+ {
+ \@@_tictoc_prefix:
+ TOC: \c_space_tl
+ \@@_fp_to_tl:N \g_@@_time_fp \c_space_tl s
+ }
+ }
+\msg_new:nnn { benchmark } { toc-first }
+ {
+ \token_to_str:N \benchmark_toc: \c_space_tl without~
+ \token_to_str:N \benchmark_tic: \c_space_tl !
+ }
+% \end{macrocode}
+% \end{macro}
+%
+% \begin{macrocode}
+%</initex|package>
+% \end{macrocode}
+%
+% \end{implementation}
+%
+% \PrintIndex