Re: [PATCH v2] Add '--shuffle' argument support
On Sat, Feb 19, 2022 at 09:57:13AM +0200, Eli Zaretskii wrote:
> > * Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
> > * builddos.bat: Add shuf.o into build script.
> This should also update build_w32.bat, which is used to build Make on
> MS-Windows. I think NEWS should also call out the new feature.
Sounds good! Added there and to makefile.com.
> > +Note that @code{make --shuffle clean all install} does reorder goals
> > +similar to how @code{make -j clean all install} runs all targets in
>
> These should use @kbd, not @code, since you are describing commands
> the user will type. I also recommend to wrap each one in @w{..}, so
> that these (long) command isn't broken between 2 lines.
Changed to @w{@kbd{..}}.
> > +@samp{--shuffle=} accepts an optional value:
>
> I think nowadays it's customary to use @option as markup for
> command-line options (unless Make wants to keep its manual compatible
> to very old versions of Texinfo -- this is up to Paul to decide).
I left it as is as I see on @option{} being used in make.texi.
Can do as a separate patch if others agree.
> > + /* TODO: could we make this shuffle more deterministic and less
> > + dependent on current filesystem state? */
> > + if (! file->was_shuffled)
> > +shuffle_file_deps_recursive (file);
>
> Should this TODO be resolved before installing the feature?
Sounds good. Added re-seeding for each implicit dependency to get
more deterministic shuffling.
> > + /* Handle shuffle mode argument. */
> > + if (shuffle_mode_arg)
> > + {
> > +if (streq (shuffle_mode_arg, "none"))
> > + sm = sm_none;
> > +else if (streq (shuffle_mode_arg, "identity"))
> > + sm = sm_identity;
> > +else if (streq (shuffle_mode_arg, "reverse"))
> > + sm = sm_reverse;
> > +else if (streq (shuffle_mode_arg, "random"))
> > + sm = sm_random;
> > +/* Assume explicit seed if starts from a digit. */
> > +else if (ISDIGIT (shuffle_mode_arg[0]))
> > + {
> > +sm = sm_random;
> > +shuffle_seed = atoi (shuffle_mode_arg);
> > + }
> > +else
> > + {
> > +O (error, NILF, _("error: unsupported --shuffle= option."));
> > +die (MAKE_FAILURE);
> > + }
> > +set_shuffle_mode (sm, shuffle_seed);
> > +
> > +/* Write fixed seed back to argument list to propagate fixed seed
> > + to child $(MAKE) runs. */
> > +free (shuffle_mode_arg);
> > +shuffle_mode_arg = xstrdup (shuffle_get_str_value ());
> > + }
>
> Should this be factored out and put on shuf.c?
Sounds goo.d Moved out to shuf.c. Only left small option rewrite bit in main.c.
> > + switch (mode)
> > +{
> > +case sm_random:
> > + if (seed == 0)
> > +seed = (int)time(NULL);
> > + srand (seed);
> > + shuffler = random_shuffle_array;
> > + sprintf(shuffle_str_value, "%d", seed);
>^^
> Stylistic comment: I believe our style is to leave one space between
> the function name and the opening parenthesis (here and elsewhere in
> the patch).
Good catch! Added whitespace everywhere in the new code.
> > +random_shuffle_array (void ** a, size_t len)
> > +{
> > + for (unsigned int i = 0; i < len; i++)
> ^^^
> This requires some minimal level of ANSI C support that I'm not sure
> Make already requires. Older compilers will error out here.
i think it does. Moved out to a separate declaration and switched to
size_t while at it to match function argument type.
> > + /* TODO: below is almost identical to goaldeps shuffle. The only
> > difference
> > + is a type change. Worth deduplicating? */
>
> Another TODO.
Deduplicated by coercing 'strct goaldep*' traversal into 'struct dep *'.
Similar to other dep.h primitives.
> > + /* Shuffle dependencies. */
> > + /* TODO: this is a naive recursion. Is it good enough? Or better
> > change it
> > + to queue based implementation? */
>
> And another one.
Dropped a TODO as it's no worse than naive recursion in update_file_1.
> > --- /dev/null
> > +++ b/tests/scripts/options/shuffle-reverse
>
> This test doesn't seem to test the random option. I understand why
> this is not easy, but shouldn't it still be tested, if only to make
> sure the option works, and also that different seeds produce different
> outcomes?
Added tests/scripts/misc/rand-shuf test to test for random order and
for unchanged order for a fixed seed.
Attaching v3-0001-Add-shuffle-argument-support.patch with all the above applied.
Thank you for thorough review, Eli!
--
Sergei
>From 42a1df1b2873a3e362936cef474273dca08d2c57 Mon Sep 17 00:00:00 2001
From: Sergei Trofimovich
Date: Fri, 4 Feb 2022 22:43:28 +
Subject: [PATCH v3] Add '--shuffle' argument support
The idea of the change is to introduce non-deterministic ordering
into goal and prerequisite traversal to imitate non-deterministic
ordering of 'make -j g1 g2 g3' mode.
The implementation is to introduce second
Re: [PATCH v2] Add '--shuffle' argument support
> From: Sergei Trofimovich
> Date: Fri, 18 Feb 2022 23:50:09 +
> Cc: Sergei Trofimovich
>
> * Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references.
> * builddos.bat: Add shuf.o into build script.
> * doc/make.1: Add '--shuffle' option description.
> * doc/make.texi: Add '--shuffle' option description.
> * src/dep.h (DEP): Add 'shuf' field to store shuffled order.
> * src/filedef.h (struct file): Add 'was_shuffled' bit flag to guard against
> circular dependencies.
> * src/implicit.c (pattern_search): Reshuffle dependencies for targets
> dynamically extended with dependencies from implicit rules.
> * src/job.c (child_error): Print shuffle parameter used for dependency
> shuffling.
> * src/main.c: Add '--shuffle' option handling.
> * src/remake.c (update_goal_chain): Change goal traversal order to shuffled.
> * src/shuf.c: New file with shuffle infrastructure.
> * src/shuf.h: New file with shuffle infrastructure declarations.
> * tests/scripts/options/shuffle-reverse: New file with basic tests.
This should also update build_w32.bat, which is used to build Make on
MS-Windows. I think NEWS should also call out the new feature.
> +Note that @code{make --shuffle clean all install} does reorder goals
> +similar to how @code{make -j clean all install} runs all targets in
These should use @kbd, not @code, since you are describing commands
the user will type. I also recommend to wrap each one in @w{..}, so
that these (long) command isn't broken between 2 lines.
> +@samp{--shuffle=} accepts an optional value:
I think nowadays it's customary to use @option as markup for
command-line options (unless Make wants to keep its manual compatible
to very old versions of Texinfo -- this is up to Paul to decide).
> + /* TODO: could we make this shuffle more deterministic and less
> + dependent on current filesystem state? */
> + if (! file->was_shuffled)
> +shuffle_file_deps_recursive (file);
Should this TODO be resolved before installing the feature?
> + /* Handle shuffle mode argument. */
> + if (shuffle_mode_arg)
> + {
> +if (streq (shuffle_mode_arg, "none"))
> + sm = sm_none;
> +else if (streq (shuffle_mode_arg, "identity"))
> + sm = sm_identity;
> +else if (streq (shuffle_mode_arg, "reverse"))
> + sm = sm_reverse;
> +else if (streq (shuffle_mode_arg, "random"))
> + sm = sm_random;
> +/* Assume explicit seed if starts from a digit. */
> +else if (ISDIGIT (shuffle_mode_arg[0]))
> + {
> +sm = sm_random;
> +shuffle_seed = atoi (shuffle_mode_arg);
> + }
> +else
> + {
> +O (error, NILF, _("error: unsupported --shuffle= option."));
> +die (MAKE_FAILURE);
> + }
> +set_shuffle_mode (sm, shuffle_seed);
> +
> +/* Write fixed seed back to argument list to propagate fixed seed
> + to child $(MAKE) runs. */
> +free (shuffle_mode_arg);
> +shuffle_mode_arg = xstrdup (shuffle_get_str_value ());
> + }
Should this be factored out and put on shuf.c?
> + switch (mode)
> +{
> +case sm_random:
> + if (seed == 0)
> +seed = (int)time(NULL);
> + srand (seed);
> + shuffler = random_shuffle_array;
> + sprintf(shuffle_str_value, "%d", seed);
^^
Stylistic comment: I believe our style is to leave one space between
the function name and the opening parenthesis (here and elsewhere in
the patch).
> +random_shuffle_array (void ** a, size_t len)
> +{
> + for (unsigned int i = 0; i < len; i++)
^^^
This requires some minimal level of ANSI C support that I'm not sure
Make already requires. Older compilers will error out here.
> + /* TODO: below is almost identical to goaldeps shuffle. The only
> difference
> + is a type change. Worth deduplicating? */
Another TODO.
> + /* Shuffle dependencies. */
> + /* TODO: this is a naive recursion. Is it good enough? Or better change
> it
> + to queue based implementation? */
And another one.
> --- /dev/null
> +++ b/tests/scripts/options/shuffle-reverse
This test doesn't seem to test the random option. I understand why
this is not easy, but shouldn't it still be tested, if only to make
sure the option works, and also that different seeds produce different
outcomes?
Thanks.
[PATCH v2] Add '--shuffle' argument support
From: Sergei Trofimovich The idea of the change is to introduce non-deterministic ordering into goal and prerequisite traversal to imitate non-deterministic ordering of 'make -j g1 g2 g3' mode. The implementation is to introduce second order into each dependency chain: 1. existing order is syntactic order reachable via 'dep->next' 2. new order is shuffled order stored as 'dep->shuf' in each 'dep' When goals or prerequisites are updated we use shuffled order when '--shuffle' is passed to make. When recipes are evaluated we use syntactic order of parameters. Sample execution looks like: $ while echo === && rm -f a b && make --shuffle; do sleep 1; done === touch a cp a b === cp a b cp: cannot stat 'a': No such file or directory make: *** [Makefile:5: b] Error 1 --shuffle=1644097687 Note: here first run succeeds while second run fails and exposes the bug in Makefile. --shuffle=1644097687 allows us to rerun the same build sequence again. * Makefile.am (make_SRCS): Add src/shuf.h and src/shuf.c file references. * builddos.bat: Add shuf.o into build script. * doc/make.1: Add '--shuffle' option description. * doc/make.texi: Add '--shuffle' option description. * src/dep.h (DEP): Add 'shuf' field to store shuffled order. * src/filedef.h (struct file): Add 'was_shuffled' bit flag to guard against circular dependencies. * src/implicit.c (pattern_search): Reshuffle dependencies for targets dynamically extended with dependencies from implicit rules. * src/job.c (child_error): Print shuffle parameter used for dependency shuffling. * src/main.c: Add '--shuffle' option handling. * src/remake.c (update_goal_chain): Change goal traversal order to shuffled. * src/shuf.c: New file with shuffle infrastructure. * src/shuf.h: New file with shuffle infrastructure declarations. * tests/scripts/options/shuffle-reverse: New file with basic tests. --- Makefile.am | 5 +- builddos.bat | 3 +- doc/make.1| 34 + doc/make.texi | 51 +++ src/dep.h | 1 + src/filedef.h | 2 + src/implicit.c| 9 ++ src/job.c | 19 ++- src/main.c| 45 ++ src/remake.c | 54 --- src/shuf.c| 202 ++ src/shuf.h| 34 + tests/scripts/options/shuffle-reverse | 112 ++ 13 files changed, 542 insertions(+), 29 deletions(-) create mode 100644 src/shuf.c create mode 100644 src/shuf.h create mode 100644 tests/scripts/options/shuffle-reverse diff --git a/Makefile.am b/Makefile.am index 9be60fec..3ad19e0c 100644 --- a/Makefile.am +++ b/Makefile.am @@ -35,8 +35,9 @@ make_SRCS = src/ar.c src/arscan.c src/commands.c src/commands.h \ src/hash.c src/hash.h src/implicit.c src/job.c src/job.h \ src/load.c src/loadapi.c src/main.c src/makeint.h src/misc.c \ src/os.h src/output.c src/output.h src/read.c src/remake.c \ - src/rule.c src/rule.h src/signame.c src/strcache.c \ - src/variable.c src/variable.h src/version.c src/vpath.c + src/rule.c src/rule.h src/shuf.h src/shuf.c src/signame.c \ + src/strcache.c src/variable.c src/variable.h src/version.c \ + src/vpath.c w32_SRCS = src/w32/pathstuff.c src/w32/w32os.c src/w32/compat/dirent.c \ src/w32/compat/posixfcn.c src/w32/include/dirent.h \ diff --git a/builddos.bat b/builddos.bat index 9cecabec..cfb224c2 100644 --- a/builddos.bat +++ b/builddos.bat @@ -68,12 +68,13 @@ gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/s gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/remote-stub.c -o remote-stub.o gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/getopt.c -o getopt.o gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/getopt1.c -o getopt1.o +gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/shuf.c -o shuf.o gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/lib/glob.c -o lib/glob.o gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/lib/fnmatch.c -o lib/fnmatch.o @echo off echo commands.o > respf.$$$ for %%f in (job output dir file misc main read remake rule implicit default variable) do echo %%f.o >> respf.$$$ -for %%f in (expand function vpath hash strcache version ar arscan signame remote-stub getopt getopt1) do echo %%f.o >> respf.$$$ +for %%f in (expand function vpath hash strcache version ar arscan signame remote-stub getopt getopt1 shuf) do echo %%f.o >> respf.$$$ for %%f in (lib\glob lib\fnmatch) do echo %%f.o
