Recent love for redo?
231 views
Skip to first unread message
Nathaniel Filardo
Sep 2, 2018, 7:51:38 PM9/2/18
to redo
Salutations, list.
I recently found an excuse to build up a project around redo and I'm finding it quite delightful. Are others still using it?
In case anyone's interested, I've experimentally started a C implementation, https://github.com/nwf/redo/tree/c, which
right now knows how to do `redo-stamp` and little else. I also found the "dodir" discussions interesting, and so have a
very inefficient implementation, complete with shadow hierarchy, for prototyping up at
Cheers!
--nwf;
Jeff Stearns
Sep 2, 2018, 8:20:46 PM9/2/18
to Nathaniel Filardo, redo
Nathaniel -
I use redo on occasion. It’s an appealing concept, but the documentation falls short. It’s rather like trying to learn Danish by reading a dictionary. You might teach yourself the words, but you’ll have a tough time if you move to Copenhagen and try to do get things done.
FYI, there is already at least one C implementation. There are also implementations in bash, Python, and other languages. I didn’t find any two that are completely compatible with each other. And none are documented well enough to answer the questions that’ll come up when you try to use them for large projects.
Oh, and all have bugs. I tried three or four different implementations, and each had bugs. The problems were severe enough to prevent them from being used by folks who weren’t willing to do troubleshooting and debugging. Thus it feels wrong to use redo on something that would be used by anybody but me.
I use redo on occasion. It’s an appealing concept, but the documentation falls short. It’s rather like trying to learn Danish by reading a dictionary. You might teach yourself the words, but you’ll have a tough time if you move to Copenhagen and try to do get things done.
FYI, there is already at least one C implementation. There are also implementations in bash, Python, and other languages. I didn’t find any two that are completely compatible with each other. And none are documented well enough to answer the questions that’ll come up when you try to use them for large projects.
Oh, and all have bugs. I tried three or four different implementations, and each had bugs. The problems were severe enough to prevent them from being used by folks who weren’t willing to do troubleshooting and debugging. Thus it feels wrong to use redo on something that would be used by anybody but me.
Nathaniel Filardo
Sep 2, 2018, 8:28:04 PM9/2/18
to redo
On Mon, Sep 3, 2018 at 1:20 AM Jeff Stearns <jeff.s...@gmail.com> wrote:
FYI, there is already at least one C implementation. There are also implementations in bash, Python, and other languages. I didn’t find any two that are completely compatible with each other. And none are documented well enough to answer the questions that’ll come up when you try to use them for large projects.
Is there a list of these implementations? I only know of https://github.com/apenwarr/redo and its recently maintained fork https://github.com/bocchino/redo .
Oh, and all have bugs. I tried three or four different implementations, and each had bugs. The problems were severe enough to prevent them from being used by folks who weren’t willing to do troubleshooting and debugging. Thus it feels wrong to use redo on something that would be used by anybody but me.
It's young software, so that's perhaps to be expected. Could you expand a little bit about the bugs you've encountered? I'd like to grow the test suite and experienced bugs are useful things.
Cheers,
--nwf;
Jeff Stearns
Sep 2, 2018, 9:35:14 PM9/2/18
to Nathaniel Filardo, redo
I did my redo research several years ago, and discarded my list of candidates after I chose the one that worked best for me. I made my list based on web searches and message boards.
The most common bug I encountered was differences between implementations. Given the same source tree and redo files, two different implementations would behave differently. I’d have to tweak the redo files one way to make one implementation work, and tweak them differently for the other. No amount of reading the documentation would clarify which implementation was correct.
After a few days of writing tests, I had the distinct impression that my tests were venturing into uncharted territory. It seemed that I was already beyond the limits of how much any author had tested their code. That makes me distinctly uneasy.
One redo implementation has a bug that’s sometimes triggered when a build fails or is interrupted. Subsequent redo invocations will act as if there’s no need to do anything. In order to get redo working properly again, I must delete all of the state information from a sqlite database. This bug is especially troublesome because it causes silent errors with no indication of failure. This is a showstopper for production use.
Another redo implementation stores its state information in the filesystem; I recall that it would also sometimes get confused. I needed to delete all those files on a few occasions in order to make it work properly.
Problems like this might not be objectionable to folks working on small personal projects, but I can’t imagine recommending on any of these implementations for serious production use.
I’ve been using make to build software since 1980 or so. I sure don’t love the syntax, but I gotta admit that it never had bugs like this. (And I was once in a meeting where Stuart Feldman apologized for choosing the tab character as a separator, so I’m over that, too.)
Avery Pennarun
Sep 11, 2018, 7:54:12 AM9/11/18
to jeff.s...@gmail.com, nwfi...@gmail.com, redo
On Sun, Sep 2, 2018 at 9:35 PM Jeff Stearns <jeff.s...@gmail.com> wrote:
> The most common bug I encountered was differences between implementations.
> Given the same source tree and redo files, two different implementations would
> behave differently. I’d have to tweak the redo files one way to make one
> implementation work, and tweak them differently for the other. No amount of
> reading the documentation would clarify which implementation was correct.
Yeah, this suggests that all implementations would benefit from some
> The most common bug I encountered was differences between implementations.
> Given the same source tree and redo files, two different implementations would
> behave differently. I’d have to tweak the redo files one way to make one
> implementation work, and tweak them differently for the other. No amount of
> reading the documentation would clarify which implementation was correct.
kind of well-maintained cross-implementation test suite. And any
incompatibilities not covered, of course, should be added to the
suite.
> After a few days of writing tests, I had the distinct impression that my tests were venturing
> into uncharted territory. It seemed that I was already beyond the limits of how much any
> author had tested their code. That makes me distinctly uneasy.
apenwarr/redo a few years ago, and it worked pretty reliably. Of
course, there are not that many users and the fact that it worked for
me is not much of an indicator that it would work for anyone else.
> One redo implementation has a bug that’s sometimes triggered when a build
> fails or is interrupted. Subsequent redo invocations will act as if there’s no
> need to do anything. In order to get redo working properly again, I must
> delete all of the state information from a sqlite database. This bug is especially
> troublesome because it causes silent errors with no indication of failure. This is
> a showstopper for production use.
easy to construct an automated test to catch (at least if it happens
somewhat consistently).
> Another redo implementation stores its state information in the filesystem; I recall
> that it would also sometimes get confused. I needed to delete all those files on
> a few occasions in order to make it work properly.
somewhere :) And yeah, one of the fundamentally annoying things about
a stateful build system is that if it messes up its state, then you
have a problem. redo's data model is fundamentally pretty clean (for
example, it should be safe to delete state for just one target
directory and have something sensible happen) but that depends on the
implementation not being crazy. And it shouldn't be corrupting its
state in the first place.
> I’ve been using make to build software since 1980 or so. I sure don’t love the syntax,
> but I gotta admit that it never had bugs like this. (And I was once in a meeting where
> Stuart Feldman apologized for choosing the tab character as a separator, so I’m over that, too.)
(including some that did stateful things). And of course, make's
weird global/recursive behaviour leads to bugs in Makefiles that have
to maintain their own state. But at least then, as the owner of the
Makefile, you have the ability to fix it.
Despite a years-long absence, I've been thinking about getting back
into redo lately. I feel like most of the problems people have are
simply problems with a) immature/undocumented implementations, and b)
not enough users so that problems go unreported, and c) even reported
problems don't get fixed because of a lack of maintainers.
Redo reminds me a bit of something someone told me back in the '90s
about Linux CD player programs: all of them suck, because it's too
easy to write a new one, so everyone writes a new one instead of
fixing the ones that are there. The core concepts of redo are so
simple that it's easy and educational to make a new toy version (like
I did!) but it won't ever be appropriate for production unless we
actually get serious about it.
Have fun,
Avery
Nils Dagsson Moskopp
Oct 1, 2018, 2:09:06 PM10/1/18
to Nathaniel Filardo, redo
Nathaniel Filardo <nwfi...@gmail.com> writes:
> On Mon, Sep 3, 2018 at 1:20 AM Jeff Stearns <jeff.s...@gmail.com> wrote:
>
>> FYI, there is already at least one C implementation. There are also
>> implementations in bash, Python, and other languages. I didn’t find any
>> two that are completely compatible with each other. And none are
>> documented well enough to answer the questions that’ll come up when you try
>> to use them for large projects.
>>
>
> Is there a list of these implementations? I only know of
> https://github.com/apenwarr/redo and its recently maintained fork
> https://github.com/bocchino/redo .
<http://news.dieweltistgarnichtso.net/bin/redo-sh.html#implementation-comparison>
> On Mon, Sep 3, 2018 at 1:20 AM Jeff Stearns <jeff.s...@gmail.com> wrote:
>
>> FYI, there is already at least one C implementation. There are also
>> implementations in bash, Python, and other languages. I didn’t find any
>> two that are completely compatible with each other. And none are
>> documented well enough to answer the questions that’ll come up when you try
>> to use them for large projects.
>>
>
> Is there a list of these implementations? I only know of
> https://github.com/apenwarr/redo and its recently maintained fork
> https://github.com/bocchino/redo .
>> Oh, and all have bugs. I tried three or four different implementations,
>> and each had bugs. The problems were severe enough to prevent them from
>> being used by folks who weren’t willing to do troubleshooting and
>> debugging. Thus it feels wrong to use redo on something that would be used
>> by anybody but me.
>>
>
> It's young software, so that's perhaps to be expected. Could you expand a
> little bit about the bugs you've encountered? I'd like to grow the test
> suite and experienced bugs are useful things.
git clone http://daten.dieweltistgarnichtso.net/src/redo-testcases.git
> Cheers,
> --nwf;
>
> --
> You received this message because you are subscribed to the Google Groups "redo" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to redo-list+...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
--
Nils Dagsson Moskopp // erlehmann
<http://dieweltistgarnichtso.net>
Nils Dagsson Moskopp
Oct 1, 2018, 3:18:32 PM10/1/18
to Jeff Stearns, Nathaniel Filardo, redo
Jeff Stearns <jeff.s...@gmail.com> writes:
> I did my redo research several years ago, and discarded my list of
> candidates after I chose the one that worked best for me. I made my
> list based on web searches and message boards.
What do you think of my table of redo implementations with differences?
> I did my redo research several years ago, and discarded my list of
> candidates after I chose the one that worked best for me. I made my
> list based on web searches and message boards.
<http://news.dieweltistgarnichtso.net/bin/redo-sh.html#implementation-comparison>
> The most common bug I encountered was differences between
> implementations. Given the same source tree and redo files, two
> different implementations would behave differently. I’d have to tweak
> the redo files one way to make one implementation work, and tweak them
> differently for the other. No amount of reading the documentation
> would clarify which implementation was correct.
hard problems come up, unless someone is using them themselves. I wrote
my own implementation after finding that most redo implementations were
toys, i.e. neither used in the real world nor usable in the real world.
A common theme seems that documentation does not match the actual code.
Take the parameter $2, in apenwarr redo, which, should be “the basename
of the target, minus the extension, if any”. From “man 1 basename” I do
know that constructing a basename strips leading directory components …
<https://github.com/apenwarr/redo#user-content-what-are-the-three-parameters-1-2-3-to-a-do-file>
I actually have a test in my suite for that, one that I wrote just now;
it demonstrates that this documentation of Apenwarr redo does not match
the behaviour whenever a dofile in some parent directory is being used.
With my redo:
; redo
redo all
redo directory/target
PASS: ${2} = target
redo directory/target.xyz
PASS: ${2} = target
With Apenwarr redo:
; PATH=/home/erlehmann/share/src/redo-python/:$PATH redo
redo all
redo directory/target
PASS: ${2} = target
redo directory/target.xyz
FAIL: ${2} = directory/target != target
I personally have come to the conclusion that it is an error to allow
dofiles in parent directories, as it makes implementations needlessly
complex and does not allow one to find out which dofile would be used
before building a project just by looking at files in one directory …
I also suspect that the ensuing non-existence dependencies are rarely
handled correctly by redo-implementations.
However, having code not matching the documentation is not very nice!
> After a few days of writing tests, I had the distinct impression that
> my tests were venturing into uncharted territory. It seemed that I
> was already beyond the limits of how much any author had tested their
> code. That makes me distinctly uneasy.
> One redo implementation has a bug that’s sometimes triggered when a
> build fails or is interrupted. Subsequent redo invocations will act
> as if there’s no need to do anything. In order to get redo working
> properly again, I must delete all of the state information from a
> sqlite database. This bug is especially troublesome because it causes
> silent errors with no indication of failure. This is a showstopper
> for production use.
would you be willing to share which implementation does these things?
> Another redo implementation stores its state information in the
> filesystem; I recall that it would also sometimes get confused. I
> needed to delete all those files on a few occasions in order to make
> it work properly.
wonder how storing data in a filesystem could be problematic. Can you
elaborate on the filesystem bit? If this is my implementation, please
send me an email with your findings.
> Problems like this might not be objectionable to folks working on
> small personal projects, but I can’t imagine recommending on any of
> these implementations for serious production use.
work for has code that uses both Apenwarr do and my redo as I include
Apenwarr do as a fallback in each repository where I have used redo …
> I’ve been using make to build software since 1980 or so. I sure don’t
> love the syntax, but I gotta admit that it never had bugs like this.
> (And I was once in a meeting where Stuart Feldman apologized for
> choosing the tab character as a separator, so I’m over that, too.)
dependency and you will most likely never notice it. To quote myself:
> Especially when using C or C++, often target files depend on
> nonexistent files as well, meaning that a target file should be
> rebuilt when a previosly nonexistent file is created: If the
> preprocessor includes /usr/include/stdio.h because it could not find
> /usr/local/include/stdio.h, the creation of the latter file should
> trigger a rebuild.
<http://news.dieweltistgarnichtso.net/posts/redo-gcc-automatic-dependencies.html>
The takeaway is that make has an error mode of not rebuilding silently,
outputting binaries that do not necessarily correspond with the source.
If you rebuild everything from scratch, you will not have that problem,
but why are you using make then?
>> On Mon, Sep 3, 2018 at 1:20 AM Jeff Stearns <jeff.s...@gmail.com <mailto:jeff.s...@gmail.com>> wrote:
>> FYI, there is already at least one C implementation. There are also
>> implementations in bash, Python, and other languages. I didn’t find
>> any two that are completely compatible with each other. And none are
>> documented well enough to answer the questions that’ll come up when
>> you try to use them for large projects.
>>
>> Is there a list of these implementations? I only know of
>> https://github.com/apenwarr/redo <https://github.com/apenwarr/redo>
>> FYI, there is already at least one C implementation. There are also
>> implementations in bash, Python, and other languages. I didn’t find
>> any two that are completely compatible with each other. And none are
>> documented well enough to answer the questions that’ll come up when
>> you try to use them for large projects.
>>
>> Is there a list of these implementations? I only know of
>> and its recently maintained fork https://github.com/bocchino/redo
>> <https://github.com/bocchino/redo> .
>>
>> Oh, and all have bugs. I tried three or four different
>> implementations, and each had bugs. The problems were severe enough
>> to prevent them from being used by folks who weren’t willing to do
>> troubleshooting and debugging. Thus it feels wrong to use redo on
>> something that would be used by anybody but me.
>>
>> It's young software, so that's perhaps to be expected. Could you
>> expand a little bit about the bugs you've encountered? I'd like to
>> grow the test suite and experienced bugs are useful things.
>>
>> Cheers,
>> --nwf;
>
>> <https://github.com/bocchino/redo> .
>>
>> Oh, and all have bugs. I tried three or four different
>> implementations, and each had bugs. The problems were severe enough
>> to prevent them from being used by folks who weren’t willing to do
>> troubleshooting and debugging. Thus it feels wrong to use redo on
>> something that would be used by anybody but me.
>>
>> It's young software, so that's perhaps to be expected. Could you
>> expand a little bit about the bugs you've encountered? I'd like to
>> grow the test suite and experienced bugs are useful things.
>>
>> Cheers,
>> --nwf;
>
Nils Dagsson Moskopp
Oct 1, 2018, 4:18:32 PM10/1/18
to Avery Pennarun, jeff.s...@gmail.com, nwfi...@gmail.com, redo
Avery Pennarun <apen...@gmail.com> writes:
> On Sun, Sep 2, 2018 at 9:35 PM Jeff Stearns <jeff.s...@gmail.com> wrote:
>> The most common bug I encountered was differences between
>> implementations. Given the same source tree and redo files, two
>> different implementations would behave differently. I’d have to
>> tweak the redo files one way to make one implementation work, and
>> tweak them differently for the other. No amount of reading the
>> documentation would clarify which implementation was correct.
>
> Yeah, this suggests that all implementations would benefit from some
> kind of well-maintained cross-implementation test suite. And any
> incompatibilities not covered, of course, should be added to the
> suite.
What do you think of my test suite? You can clone it with this command:
> On Sun, Sep 2, 2018 at 9:35 PM Jeff Stearns <jeff.s...@gmail.com> wrote:
>> The most common bug I encountered was differences between
>> implementations. Given the same source tree and redo files, two
>> different implementations would behave differently. I’d have to
>> tweak the redo files one way to make one implementation work, and
>> tweak them differently for the other. No amount of reading the
>> documentation would clarify which implementation was correct.
>
> Yeah, this suggests that all implementations would benefit from some
> kind of well-maintained cross-implementation test suite. And any
> incompatibilities not covered, of course, should be added to the
> suite.
git clone http://daten.dieweltistgarnichtso.net/src/redo-testcases.git/
>> After a few days of writing tests, I had the distinct impression that
>> my tests were venturing into uncharted territory. It seemed that I
>> was already beyond the limits of how much any author had tested their
>> code. That makes me distinctly uneasy.
>
> Not sure. I built some quite complex (non open source) stuff with
> apenwarr/redo a few years ago, and it worked pretty reliably. Of
> course, there are not that many users and the fact that it worked for
> me is not much of an indicator that it would work for anyone else.
in Bourne Shell. The problems I personally had with Apenwarr redo were:
• Documentation does not match implementation, i.e. $2 is not basename;
see my previous email from today / use my testsuite to see the issue.
• It claims that dofiles can not be generated during the build process,
which to me meant that redo dependency calculation is probably broken
in subtle ways. Since it passes my test for generating dofiles during
the build, I wonder if this is still true … What is the problem here?
• It has Python as a dependency. This was unacceptable, since not every
machine I had was able to run Python. GNU coreutils or busybox do run
on all of my devices. I used redo on my old Nokia N900 Smartphone, as
my web site is generated with redo – it enabled me to render locally.
• It has sqlite as a dependency. I suspect the assertion filesystems do
not deliver the required performance was never properly researched. I
found during my performance optimizations that fstat is not a problem
while excessively forking processes is, e.g. creating many subshells.
• Apenwarr redo does not rebuild files that were modified. This means I
could not rely on it to produce a known state, unless I read output …
• If I understand it correctly, Apenwarr redo is based on timestamps. I
do not think this is correct. If Apenwarr redo would rebuild modified
targets (like my redo implementation does, it simply finds the target
is not up to date), one could just truncate a target to rebuild that.
• The documentation uses the idea of dofiles without outputs to justify
the timestamp decision. I think it is a bad idea to encourage dofiles
that do not build targets. A dofile that produces an empty target and
does not depend on anything is confusing by itself. I have seen weird
complaints from people who do not understand that targets are files –
someone complained that build scripts consisting only of side effects
were only run once by my redo implementation if they dependet on it …
• Generating multiple targets would be easy if a build process supports
targets that are changed outside the observed build process: Generate
tar files – then depend on those plus the result of their exctration.
• IIRC, Apenwarr do had a problem with filenames containing non-ASCII …
I patched it (it was trivial), but I have not yet released the patch.
• My own redo implementation contains redo-dot(1) and some other tools.
That being said, your redo implementation is not bad. It clearly served
as an introduction to the concept of DJB redo and it worked okay before
I wrote my own redo implementation to overcome the shortcomings listed.
>> One redo implementation has a bug that’s sometimes triggered when a
>> build fails or is interrupted. Subsequent redo invocations will act
>> as if there’s no need to do anything. In order to get redo working
>> properly again, I must delete all of the state information from a
>> sqlite database. This bug is especially troublesome because it
>> causes silent errors with no indication of failure. This is a
>> showstopper for production use.
>
> That would be a showstopper all right, although it should be quite
> easy to construct an automated test to catch (at least if it happens
> somewhat consistently).
>> Another redo implementation stores its state information in the
>> filesystem; I recall that it would also sometimes get confused. I
>> needed to delete all those files on a few occasions in order to make
>> it work properly.
>
> I think they all store their state information "in the filesystem"
> somewhere :) And yeah, one of the fundamentally annoying things about
> a stateful build system is that if it messes up its state, then you
> have a problem. redo's data model is fundamentally pretty clean (for
> example, it should be safe to delete state for just one target
> directory and have something sensible happen) but that depends on the
> implementation not being crazy. And it shouldn't be corrupting its
> state in the first place.
>> I’ve been using make to build software since 1980 or so. I sure
>> don’t love the syntax, but I gotta admit that it never had bugs like
>> this. (And I was once in a meeting where Stuart Feldman apologized
>> for choosing the tab character as a separator, so I’m over that,
>> too.)
>
> Hah! I've used plenty of make implementations with bugs like that
> (including some that did stateful things). And of course, make's
> weird global/recursive behaviour leads to bugs in Makefiles that have
> to maintain their own state. But at least then, as the owner of the
> Makefile, you have the ability to fix it.
>
> Despite a years-long absence, I've been thinking about getting back
> into redo lately. I feel like most of the problems people have are
> simply problems with a) immature/undocumented implementations, and b)
> not enough users so that problems go unreported, and c) even reported
> problems don't get fixed because of a lack of maintainers.
>
> Redo reminds me a bit of something someone told me back in the '90s
> about Linux CD player programs: all of them suck, because it's too
> easy to write a new one, so everyone writes a new one instead of
> fixing the ones that are there. The core concepts of redo are so
> simple that it's easy and educational to make a new toy version (like
> I did!) but it won't ever be appropriate for production unless we
> actually get serious about it.
handling, redo-ifcreate … or they decide the parameters $1 / $2 / $3 do
have a different meaning in their implementation or are obsolete or so.
I have used my own redo implementation for several years – I would like
to chat with people who have redo-based workflows that are serious: Not
work … yet things that are not done to show off, but to build software.
The game “Liberation Circuit” by Linley Henzell can be build with redo,
for example. I have tested both Apenwarr do and my redo implementation;
I do however doubt that it can be built with JdeBP's redo … as it seems
to follow differing ideas about the meaning of parameters $1 / $2 / $3.
<https://github.com/linleyh/liberation-circuit>
> Have fun,
>
> Avery
Avery Pennarun
Oct 1, 2018, 7:17:24 PM10/1/18
to Nils Dagsson Moskopp, Jeff Stearns, Nathaniel Filardo, redo
On Mon, Oct 1, 2018 at 4:18 PM, Nils Dagsson Moskopp
<ni...@dieweltistgarnichtso.net> wrote:
> Avery Pennarun <apen...@gmail.com> writes:
>> On Sun, Sep 2, 2018 at 9:35 PM Jeff Stearns <jeff.s...@gmail.com> wrote:
>>> The most common bug I encountered was differences between
>>> implementations. Given the same source tree and redo files, two
>>> different implementations would behave differently. I’d have to
>>> tweak the redo files one way to make one implementation work, and
>>> tweak them differently for the other. No amount of reading the
>>> documentation would clarify which implementation was correct.
>>
>> Yeah, this suggests that all implementations would benefit from some
>> kind of well-maintained cross-implementation test suite. And any
>> incompatibilities not covered, of course, should be added to the
>> suite.
>
> What do you think of my test suite? You can clone it with this command:
> git clone http://daten.dieweltistgarnichtso.net/src/redo-testcases.git/
I haven't tried it yet, but thanks for working on it. I'll look when
<ni...@dieweltistgarnichtso.net> wrote:
> Avery Pennarun <apen...@gmail.com> writes:
>> On Sun, Sep 2, 2018 at 9:35 PM Jeff Stearns <jeff.s...@gmail.com> wrote:
>>> The most common bug I encountered was differences between
>>> implementations. Given the same source tree and redo files, two
>>> different implementations would behave differently. I’d have to
>>> tweak the redo files one way to make one implementation work, and
>>> tweak them differently for the other. No amount of reading the
>>> documentation would clarify which implementation was correct.
>>
>> Yeah, this suggests that all implementations would benefit from some
>> kind of well-maintained cross-implementation test suite. And any
>> incompatibilities not covered, of course, should be added to the
>> suite.
>
> What do you think of my test suite? You can clone it with this command:
> git clone http://daten.dieweltistgarnichtso.net/src/redo-testcases.git/
I have some time.
>>> After a few days of writing tests, I had the distinct impression that
>>> my tests were venturing into uncharted territory. It seemed that I
>>> was already beyond the limits of how much any author had tested their
>>> code. That makes me distinctly uneasy.
>>
>> Not sure. I built some quite complex (non open source) stuff with
>> apenwarr/redo a few years ago, and it worked pretty reliably. Of
>> course, there are not that many users and the fact that it worked for
>> me is not much of an indicator that it would work for anyone else.
>
> Apenwarr redo worked for me, but I chose to write my own implementation
> in Bourne Shell. The problems I personally had with Apenwarr redo were:
>
> • Documentation does not match implementation, i.e. $2 is not basename;
> see my previous email from today / use my testsuite to see the issue.
definition and a new --old-args option to give back the old behaviour
in the short term. Some of the docs may not have been updated.
> • It claims that dofiles can not be generated during the build process,
> which to me meant that redo dependency calculation is probably broken
> in subtle ways. Since it passes my test for generating dofiles during
> the build, I wonder if this is still true … What is the problem here?
limitation of the docs.
> • It has Python as a dependency. This was unacceptable, since not every
> machine I had was able to run Python. GNU coreutils or busybox do run
> on all of my devices. I used redo on my old Nokia N900 Smartphone, as
> my web site is generated with redo – it enabled me to render locally.
*actually* expect to build software on almost certainly can run
python, so it's not quite an emergency. The right language to rewrite
it in is probably C, but then we have the problem of needing to
compile redo before we can use it, so it's less appropriate for just
bundling along with a package that builds using redo. (That last idea
might sound crazy, but it's how autoconf got popular. You don't
bundle autoconf per se, but you do bundle its giant output files so
that people can build your program without installing autoconf first.)
> • It has sqlite as a dependency. I suspect the assertion filesystems do
> not deliver the required performance was never properly researched. I
> found during my performance optimizations that fstat is not a problem
> while excessively forking processes is, e.g. creating many subshells.
situation is complicated. In the 'simple' branch of
github.com/apenwarr/redo, I have an incomplete-but-mostly-working
example of code that stores state in the filesystem rather than an
sqlite database. It works, but it's not really better. Performance
isn't the problem; rather the extra clutter of files it produces.
sqlite is 1000% overkill for the very small and simple state data that
redo keeps around. However, virtually every platform in existence
already has sqlite, so arguably it's the right choice anyway. redo
state (as alluded to earlier in the thread) is very susceptible to
problems like locking and interrupted transactions, which sqlite
solved cross-platform, years ago.
> • Apenwarr redo does not rebuild files that were modified. This means I
> could not rely on it to produce a known state, unless I read output …
you clobber files they spent hours working on. Furthermore, if you
want to edit a file temporarily (for example, autoconf generates a
config.h and I want to test out building with changes to that file),
you would like those changes to *not* be overwritten.
This works okay with make, because it considers a file which mtime >=
dependency mtimes to be "done." That rule is fragile in many other
ways and creates big, hard-to-debug problems for make in some
situations though. So redo instead says a target is done when its
mtime == the mtime it had when we generated it. We could choose to
always regenerate it if the mtime changes, which would give the
behaviour you seem to want. But why did the mtime change outside
redo? Presumably someone did that on purpose. IMHO it is very rude
to overwrite the file in that case.
> • If I understand it correctly, Apenwarr redo is based on timestamps. I
> do not think this is correct. If Apenwarr redo would rebuild modified
> targets (like my redo implementation does, it simply finds the target
> is not up to date), one could just truncate a target to rebuild that.
(and also st_dev and st_ino) to track whether a target is still "the
same" as it was last time redo built it. You can further tweak its
behaviour with redo-always (so it will rebuild regardless of
timestamp) and redo-stamp (so it won't rebuild under some conditions,
eg. if the timestamp has changed but the file content has not).
(Incidentally, because of redo-stamp, I disagree with the part of your
comparison chart that says apenwarr/redo doesn't support "file content
hash check." redo doesn't do the check itself - that's expensive and
not always what you want - but you can use redo-stamp to make
dependencies based on hash checks if that's what you need.)
I don't know what person truncates a target to get it to rebuild.
That certainly wouldn't work with 'make' either. In redo, you can
delete the file, and it will rebuild. You probably should ask
yourself why you need to force redo to redo a target though: what's
wrong with your declared dependencies?
Related to that, in the doc above your comparison chart, you note that
your implementation does not record a dependency on a target which did
not produce an output file. That's super dangerous. What if you
later update that target which previously produced no output? The
downstream target will not know it needs to rebuild, which is a major
error.
> • The documentation uses the idea of dofiles without outputs to justify
> the timestamp decision. I think it is a bad idea to encourage dofiles
> that do not build targets. A dofile that produces an empty target and
> does not depend on anything is confusing by itself. I have seen weird
> complaints from people who do not understand that targets are files –
> someone complained that build scripts consisting only of side effects
> were only run once by my redo implementation if they dependet on it …
of targets that produce no output files. I just really like rules
like 'redo all' and 'redo clean' to work without cluttering things.
Arguably it's the wrong tradeoff.
> • Generating multiple targets would be easy if a build process supports
> targets that are changed outside the observed build process: Generate
> tar files – then depend on those plus the result of their exctration.
to support multiple targets. I don't think any of them are "easy."
> • IIRC, Apenwarr do had a problem with filenames containing non-ASCII …
> I patched it (it was trivial), but I have not yet released the patch.
usually call minimal/do) here. I'm guessing the former since sh
doesn't have problems with non-ASCII characters generally. Worth
fixing in the python version; you're right that I likely never tested
it.
> • My own redo implementation contains redo-dot(1) and some other tools.
> That being said, your redo implementation is not bad. It clearly served
> as an introduction to the concept of DJB redo and it worked okay before
> I wrote my own redo implementation to overcome the shortcomings listed.
version just because the original has a few shortcomings :) But since
my version was essentially unmaintained, you had little choice I
guess.
It does sound like your version has many shortcomings that would be
much worse for me. For example, the suggestion in your docs to just
do "redo-ifchange x & redo-ifchange y; wait" to implement parallelism
is unfortunately way too naive. If I try to compile 1000 source files
that way, I will end up with 1000 copies of the compiler running at
once, and my computer probably crashes. apenwarr/redo goes through a
lot of effort to implement safe parallelism in a way that
interoperates well with GNU make's parallelism (so you can hand off
smoothly between make and redo in very large projects that include
other projects).
Another scary part of your doc is the indication that things like
redo-always can cause the same target to be rebuilt multiple times, if
different parts of the dependency graph depend on it. That's not
correct behaviour. apenwarr/redo goes through extra effort to do the
right thing here.
It's true that apenwarr/redo can't handle a few of the odder cases you
mention (eg. a .do script that waits on inotify and then launches
redo-ifchange based on what changes). I'm not sure those are super
important though; in fact, I might prefer to have just a normal script
or daemon, which can run 'redo all' or something whenever inotify
gives it a notification. It's a bit odd for the daemon itself be a
.do script. (Of course, to allow for maximum functionality of the
daemon, you'd want to be able to re-entrantly call redo on different
sub-parts of the tree depending what changed, and you might want to do
that in parallel, while a previous part is running even though they
might depend on shared sub-parts of the dependency graph. Because
apenwarr/redo's state database is so carefully implemented, this kind
of re-entrancy *does* work, and correctly manages to build each target
only once per relevant change.)
> I agree. Additionally, some implementors leave out features like stdout
> handling, redo-ifcreate … or they decide the parameters $1 / $2 / $3 do
> have a different meaning in their implementation or are obsolete or so.
convenient) and the $1/$2/$3 parameters are pretty user unfriendly,
I'll grant that. redo-ifcreate seems kind of important, though maybe
its lack can be worked around in some inelegant way.
> I have used my own redo implementation for several years – I would like
> to chat with people who have redo-based workflows that are serious: Not
> work … yet things that are not done to show off, but to build software.
in building large systems with whole-project dependencies (eg.
embedded systems that slurp in whole libraries, most of which are
built using make). apenwarr/redo's ability to seamlessly go back and
forth between make and redo - where a .do can call make and a Makefile
can call redo - and still get the parallelism right - has been
extremely valuable to me. Recursive make has huge problems with this
sort of thing, non-recursive make is epically ugly with such huge
projects, and most new age build systems expect you to convert all the
sub-project dependencies instead of just calling make, which is not an
option. Or else they only work with one language in the first place,
which is kind of insultingly ridiculous.
I find redo's advantages show most clearly in that kind of
"parallelizable dependency glue" situation.
Have fun,
Avery
Avery Pennarun
Oct 24, 2018, 10:58:37 PM10/24/18
to redo
Someone wrote:
> actually, see
> https://groups.google.com/forum/#!msg/redo-list/iBkdbc4duoM/s92qF5gIBwAJ
Thanks for the link! I was very busy and not keeping up with
discussions over the last few years, and only recently climbed out of
my hole :)
That discussion was interesting, but ultimately unconstructive I
guess, because the main participants ended up talking past each other.
If I can paraphrase the two sides of the argument, they would be:
A) If I say redo-ifchange x, and the dependencies of x have changed
since x was built, then you should bloody well rebuild x
and
B) If you recheck the dependency tree of x every time someone says
redo-ifchange x during a build, you're going to do a ton of redundant
work. Also, if a target needs to be build more than once during a
session, we have some kind of dependency loop and that sounds like bad
news for consistency.
I think the reason it was so hard for one of these points of view to
win is that... they're both right!
I'm starting to come around to Nils' point of view that there are
realistic cases where you might want to rebuild the same target during
a session. Outside of unit tests for redo itself (which arguably are
okay to hack around to make work), the easy example is the one Nils
gives above, where a .do script uses inotify or whatever to launch
redo-ifchange on targets when it notices that various source files
have changed. Now, the workaround for that one is easy (why is that
toplevel a .do script in the first place?) but one can imagine more
complicated situations that might make sense. Another example he
mentioned is an /sbin/init system written in redo, which I have to
admit is a *very* interesting concept for me that I had never thought
of before. So maybe we need to support the idea of rebuilding things
more than once during a session.
On the other hand, I myself came from point of view B, and that's how
apenwarr/redo is written. My redo has the concept of a "run": the
toplevel redo in a hierarchy picks a run id, then sets REDO_RUNID to
that number, and all child redo processes inherit that runid. Using
the runid, it can perform an optimization (and yes, I use the work
optimization advisedly here :)) where it doesn't need to stat any
dependencies more than once in a single run... as long as we assume
that we won't need to build the same target more than once during a
run.
There are some cases that slip through because there is no need to
optimize them:
1) If you call redo instead of redo-ifchange, we assume you really
really mean it. The 'redo' command is unnecessary if it checks
dependencies (that's what redo-ifchange is for), so we don't. We
build or rebuild the target every time.
2) If you build a target using redo, it updates the state database
anyhow. When it does this, it's quite easy to simultaneously record
that targets depending on it are now outdated, so those could be worth
rebuilding if you redo-ifchange them again later, even inside the same
runid.
I think #1 is good behaviour, but upon further reflection, #2 seems to
be inconsistent. 'targets' can dirty other targets more than once
during a run, but 'sources' (files that aren't produced by redo) can
only dirty a target once. That's kinda weird. If we want to do the
optimization for only stat'ing sources once (which I think is
extremely valuable in large projects), we should maybe be consistent
by also not marking targets dirty when their dependency targets
change.
Incidentally, the runid thing was designed pretty carefully to try to
give sensible results, if you're going with goal B above.
apenwarr/redo is designed to be re-entrant, which means you can start
*separate* redo process hierarchies that know nothing about each
other, all running on the same state database with the same sources
and targets. It's very careful about locking to make this possible.
(AFAIK all the other redo implementations don't do locking at all and
don't even attempt this feature.) Each separate redo process tree
will choose its own runid, so it'll notice whether a particular
dependency has been checked by *its* runid or not. <waves hands
around> the result is that we might accidentally build a target too
many times, if both runs are trying to build similar targets, but we
won't forget to build it or accidentally forget a dirty dependency.
If the goal is, "look like we build every requested target that was
dirty, at least once during every given run" then we achieve that by
careful use of the runid.
So okay, now I need to bring up an issue that was danced around in the
thread, but never stated explicitly. What does anyone even *expect*
to happen if source files change *during* a run? Clearly opinions
differ on this. I think all of the opinions stated in the 2016 thread
are not quite right. Here's what I think should happen:
i) If target X is depended upon by targets A...E which are all being
built in a single run, then all of targets A....E should see the same
value of X, to produce a consistent build.
ii) If target X depends on source Y, and source Y changes during the
build of X, then we should stamp X with the *original* stat data for
Y, not the stat data for Y after the build of X is complete. That
makes it clear that on the next run, X is already dirty. However, in
order to achieve (i), we should consider X to still be clean for
*this* run (because we don't want to have to re-stat Y all the time.)
iii) And yet, we want to allow for situations where we *do* want to
build X more than once. If we allow this, the result is that targets
A...E might be inconsistent with each other. I don't think such
inconsistency should be the default. Right now, apenwarr/redo's unit
tests have a 'flush-cache' command that basically drops the stat cache
once, causing a one-time re-stat of all sources, and thus allows this
sort of inconsistency in a semi-controlled way. I propose a new
command, redo-inconsistent, which lets you do this in a more
controlled and standardized way: specify a list of targets or sources,
and we flush the cache for the current run for *only* the given files
and their dependencies, forcing a one-time re-stat. I personally
think that any script needing this inconsistent build behaviour will
know very well that it needs it, and this command would make the
author state it explicitly, which is good for readability and
cacheability.
IMHO, the *need* for this kind of consistency is a bit of a special
case; for someone using 'make', we'd just say "well maybe don't change
source files in the middle of a build then." So arguably Nils's
implementation, which just rebuilds things every time any source
changes (basically, lacking a stat cache) is already correct. For his
implementation, then, redo-inconsistent could just be a no-op. To
make his .do scripts compatible with stat-caching implementations, he
would just need to call redo-inconsistent from a few places.
What do you think?
Have fun,
Avery
[P.S. Another point that came up in that thread was that apenwarr/redo
is really slow and sh implementations are much faster, and also that
sqlite3 is super slow compared to the filesystem. I'm a little
confused by this, perhaps mostly the benchmarking methodology. When I
wrote redo in 2010, redo-ifchange runtime was already much less than
the compile time of a typical c++ file. In the intervening years, c++
compilers have managed to get *even slower* while redo has (of course
since I stopped working on it) stayed about the same. And even so,
about 0% of redo-ifchange runtime is spent manipulating sqlite. I
wonder if y'all have some kind of different distro, or different
settings, or different hardware, or something than me which causes are
results to be so stunningly different. I mean, I'm not against a C
redo, but redo-ifchange starts in ~0.02s for me, which is not exactly
a nightmare even if it's ~20x as slow as starting a C program.]
> Avery Pennarun wrote:
> > Another scary part of your doc is the indication that things like
> > redo-always can cause the same target to be rebuilt multiple times, if
> > different parts of the dependency graph depend on it. That's not
> > correct behaviour. apenwarr/redo goes through extra effort to do the
> > right thing here.
> >
> > It's true that apenwarr/redo can't handle a few of the odder cases you
> > mention (eg. a .do script that waits on inotify and then launches
> > redo-ifchange based on what changes). I'm not sure those are super
> > important though; in fact, I might prefer to have just a normal script
> > or daemon, which can run 'redo all' or something whenever inotify
> > gives it a notification. It's a bit odd for the daemon itself be a
> > .do script. (Of course, to allow for maximum functionality of the
> > daemon, you'd want to be able to re-entrantly call redo on different
> > sub-parts of the tree depending what changed, and you might want to do
> > that in parallel, while a previous part is running even though they
> > might depend on shared sub-parts of the dependency graph. Because
> > apenwarr/redo's state database is so carefully implemented, this kind
> > of re-entrancy *does* work, and correctly manages to build each target
> > only once per relevant change.)
>
> We had a discussion about this topic some time ago on this mailing list
> > Another scary part of your doc is the indication that things like
> > redo-always can cause the same target to be rebuilt multiple times, if
> > different parts of the dependency graph depend on it. That's not
> > correct behaviour. apenwarr/redo goes through extra effort to do the
> > right thing here.
> >
> > It's true that apenwarr/redo can't handle a few of the odder cases you
> > mention (eg. a .do script that waits on inotify and then launches
> > redo-ifchange based on what changes). I'm not sure those are super
> > important though; in fact, I might prefer to have just a normal script
> > or daemon, which can run 'redo all' or something whenever inotify
> > gives it a notification. It's a bit odd for the daemon itself be a
> > .do script. (Of course, to allow for maximum functionality of the
> > daemon, you'd want to be able to re-entrantly call redo on different
> > sub-parts of the tree depending what changed, and you might want to do
> > that in parallel, while a previous part is running even though they
> > might depend on shared sub-parts of the dependency graph. Because
> > apenwarr/redo's state database is so carefully implemented, this kind
> > of re-entrancy *does* work, and correctly manages to build each target
> > only once per relevant change.)
>
> actually, see
> https://groups.google.com/forum/#!msg/redo-list/iBkdbc4duoM/s92qF5gIBwAJ
Thanks for the link! I was very busy and not keeping up with
discussions over the last few years, and only recently climbed out of
my hole :)
That discussion was interesting, but ultimately unconstructive I
guess, because the main participants ended up talking past each other.
If I can paraphrase the two sides of the argument, they would be:
A) If I say redo-ifchange x, and the dependencies of x have changed
since x was built, then you should bloody well rebuild x
and
B) If you recheck the dependency tree of x every time someone says
redo-ifchange x during a build, you're going to do a ton of redundant
work. Also, if a target needs to be build more than once during a
session, we have some kind of dependency loop and that sounds like bad
news for consistency.
I think the reason it was so hard for one of these points of view to
win is that... they're both right!
I'm starting to come around to Nils' point of view that there are
realistic cases where you might want to rebuild the same target during
a session. Outside of unit tests for redo itself (which arguably are
okay to hack around to make work), the easy example is the one Nils
gives above, where a .do script uses inotify or whatever to launch
redo-ifchange on targets when it notices that various source files
have changed. Now, the workaround for that one is easy (why is that
toplevel a .do script in the first place?) but one can imagine more
complicated situations that might make sense. Another example he
mentioned is an /sbin/init system written in redo, which I have to
admit is a *very* interesting concept for me that I had never thought
of before. So maybe we need to support the idea of rebuilding things
more than once during a session.
On the other hand, I myself came from point of view B, and that's how
apenwarr/redo is written. My redo has the concept of a "run": the
toplevel redo in a hierarchy picks a run id, then sets REDO_RUNID to
that number, and all child redo processes inherit that runid. Using
the runid, it can perform an optimization (and yes, I use the work
optimization advisedly here :)) where it doesn't need to stat any
dependencies more than once in a single run... as long as we assume
that we won't need to build the same target more than once during a
run.
There are some cases that slip through because there is no need to
optimize them:
1) If you call redo instead of redo-ifchange, we assume you really
really mean it. The 'redo' command is unnecessary if it checks
dependencies (that's what redo-ifchange is for), so we don't. We
build or rebuild the target every time.
2) If you build a target using redo, it updates the state database
anyhow. When it does this, it's quite easy to simultaneously record
that targets depending on it are now outdated, so those could be worth
rebuilding if you redo-ifchange them again later, even inside the same
runid.
I think #1 is good behaviour, but upon further reflection, #2 seems to
be inconsistent. 'targets' can dirty other targets more than once
during a run, but 'sources' (files that aren't produced by redo) can
only dirty a target once. That's kinda weird. If we want to do the
optimization for only stat'ing sources once (which I think is
extremely valuable in large projects), we should maybe be consistent
by also not marking targets dirty when their dependency targets
change.
Incidentally, the runid thing was designed pretty carefully to try to
give sensible results, if you're going with goal B above.
apenwarr/redo is designed to be re-entrant, which means you can start
*separate* redo process hierarchies that know nothing about each
other, all running on the same state database with the same sources
and targets. It's very careful about locking to make this possible.
(AFAIK all the other redo implementations don't do locking at all and
don't even attempt this feature.) Each separate redo process tree
will choose its own runid, so it'll notice whether a particular
dependency has been checked by *its* runid or not. <waves hands
around> the result is that we might accidentally build a target too
many times, if both runs are trying to build similar targets, but we
won't forget to build it or accidentally forget a dirty dependency.
If the goal is, "look like we build every requested target that was
dirty, at least once during every given run" then we achieve that by
careful use of the runid.
So okay, now I need to bring up an issue that was danced around in the
thread, but never stated explicitly. What does anyone even *expect*
to happen if source files change *during* a run? Clearly opinions
differ on this. I think all of the opinions stated in the 2016 thread
are not quite right. Here's what I think should happen:
i) If target X is depended upon by targets A...E which are all being
built in a single run, then all of targets A....E should see the same
value of X, to produce a consistent build.
ii) If target X depends on source Y, and source Y changes during the
build of X, then we should stamp X with the *original* stat data for
Y, not the stat data for Y after the build of X is complete. That
makes it clear that on the next run, X is already dirty. However, in
order to achieve (i), we should consider X to still be clean for
*this* run (because we don't want to have to re-stat Y all the time.)
iii) And yet, we want to allow for situations where we *do* want to
build X more than once. If we allow this, the result is that targets
A...E might be inconsistent with each other. I don't think such
inconsistency should be the default. Right now, apenwarr/redo's unit
tests have a 'flush-cache' command that basically drops the stat cache
once, causing a one-time re-stat of all sources, and thus allows this
sort of inconsistency in a semi-controlled way. I propose a new
command, redo-inconsistent, which lets you do this in a more
controlled and standardized way: specify a list of targets or sources,
and we flush the cache for the current run for *only* the given files
and their dependencies, forcing a one-time re-stat. I personally
think that any script needing this inconsistent build behaviour will
know very well that it needs it, and this command would make the
author state it explicitly, which is good for readability and
cacheability.
IMHO, the *need* for this kind of consistency is a bit of a special
case; for someone using 'make', we'd just say "well maybe don't change
source files in the middle of a build then." So arguably Nils's
implementation, which just rebuilds things every time any source
changes (basically, lacking a stat cache) is already correct. For his
implementation, then, redo-inconsistent could just be a no-op. To
make his .do scripts compatible with stat-caching implementations, he
would just need to call redo-inconsistent from a few places.
What do you think?
Have fun,
Avery
[P.S. Another point that came up in that thread was that apenwarr/redo
is really slow and sh implementations are much faster, and also that
sqlite3 is super slow compared to the filesystem. I'm a little
confused by this, perhaps mostly the benchmarking methodology. When I
wrote redo in 2010, redo-ifchange runtime was already much less than
the compile time of a typical c++ file. In the intervening years, c++
compilers have managed to get *even slower* while redo has (of course
since I stopped working on it) stayed about the same. And even so,
about 0% of redo-ifchange runtime is spent manipulating sqlite. I
wonder if y'all have some kind of different distro, or different
settings, or different hardware, or something than me which causes are
results to be so stunningly different. I mean, I'm not against a C
redo, but redo-ifchange starts in ~0.02s for me, which is not exactly
a nightmare even if it's ~20x as slow as starting a C program.]
Nils Dagsson Moskopp
Oct 25, 2018, 10:36:06 AM10/25/18
to Avery Pennarun, redo
<http://news.dieweltistgarnichtso.net/bin/redo-sh.html#why-built-twice>
Quoting myself here, just so we're all on the same page regarding this:
> Why can a target be built twice during a run?
>
> Some build processes require several builds of the same target. Naïve
> implementors of build systems disregard this possibility and do not
> check the validity of a target again if it was built during a run.
>
> • A target that has a dofile that invokes redo-always will be rebuilt
> several more times, if several targets invoke redo-ifchange for it.
>
> • A dofile can use a loop involving inotifywait to wait for changes to
> dependencies and immediately rebuild targets if a dependency changes.
>
> • TeX documents can contain internal references. Page and equation
> numbers are written to an external file needed for a second build.
>
> • TemplateHaskell with profiling needs an executable compiled twice.
>
> • The technique detailed in David A. Wheeler's Fully Countering
> Trusting Trust through Diverse Double-Compiling requires two builds
> of a target.
Greetings,
Nils Dagsson Moskopp
Oct 25, 2018, 2:31:17 PM10/25/18
to Avery Pennarun, redo
Avery Pennarun <apen...@gmail.com> writes:
> B) If you recheck the dependency tree of x every time someone says
> redo-ifchange x during a build, you're going to do a ton of redundant
> work.
> […]
> B) If you recheck the dependency tree of x every time someone says
> redo-ifchange x during a build, you're going to do a ton of redundant
> work.
> If we want to do the optimization for only stat'ing sources once
> (which I think is extremely valuable in large projects)
> ii) If target X depends on source Y, and source Y changes during the
> build of X, then we should stamp X with the *original* stat data for
> Y, not the stat data for Y after the build of X is complete. That
> makes it clear that on the next run, X is already dirty. However, in
> order to achieve (i), we should consider X to still be clean for
> *this* run (because we don't want to have to re-stat Y all the time.)
> What do you think?
I know not a single project in which the tiny overhead of stat(2)-ing
lots of files is worse than potentially stale builds. Please show and
tell when the overhead becomes too much, preferably with a real-world
project.
By the way, making “redo-ifchange” not rebuild targets in some special
cases is a surprise to users. Such surprises are evidence of security,
safety, and usability issues. If I wanted a build system that randomly
does not rebuild stuff when it would be appropriate to do it … I would
use make(1).
Greetings,
Avery Pennarun
Oct 25, 2018, 8:11:38 PM10/25/18
to Nils Dagsson Moskopp, redo
On Thu, Oct 25, 2018 at 10:36 AM Nils Dagsson Moskopp
<ni...@dieweltistgarnichtso.net> wrote:
> I have some examples of targets needing to be built several times here:
> <http://news.dieweltistgarnichtso.net/bin/redo-sh.html#why-built-twice>
>
> Quoting myself here, just so we're all on the same page regarding this:
>
> > Why can a target be built twice during a run?
> >
> > Some build processes require several builds of the same target. Naïve
> > implementors of build systems disregard this possibility and do not
> > check the validity of a target again if it was built during a run.
While true, some non-naive implementors also do this. I thought it
<ni...@dieweltistgarnichtso.net> wrote:
> I have some examples of targets needing to be built several times here:
> <http://news.dieweltistgarnichtso.net/bin/redo-sh.html#why-built-twice>
>
> Quoting myself here, just so we're all on the same page regarding this:
>
> > Why can a target be built twice during a run?
> >
> > Some build processes require several builds of the same target. Naïve
> > implementors of build systems disregard this possibility and do not
> > check the validity of a target again if it was built during a run.
through very carefully when designing apenwarr/redo, which I hope I
can convince you of.
> > • A target that has a dofile that invokes redo-always will be rebuilt
> > several more times, if several targets invoke redo-ifchange for it.
other self-consistent models.
Rebuilding the same target multiple times in a run is explicitly not
desirable in various important situations. In my previous mail in
this thread, I pointed out that if I ask redo to build X, Y, and Z
that all depend on A, B, and C, then it is quite reasonable to expect
redo to construct them all based on the *same* version of A, B, and C.
There's also the cost: redo-always targets (and their downstream
targets) may be very expensive to run. Or perhaps just a little
expensive, times 10,000 targets that depend on them. A typical use of
redo-always is to create a list of files (find -type f, etc). I
typically then have several downstream targets that grep that list and
redo-stamp on the result. There is really no reason to reproduce the
initial list for each of those downstream targets. If I wanted to
redo that target every single time, I wouldn't need redo at all; I
could just call a shell script or command.
A more confusing case arises when you do parallel builds (which I
think your version doesn't support, unless you count "redo-ifchange
&", which can't scale to large projects). If A depends on X, Y, and
Z, and those three depend on M, and M is redo-always, and I run "redo
-j3 A", then it will launch the .do scripts for X, Y, and Z. Each of
those scripts will run redo-ifchange M, but only one (say X) will
obtain the lock. When it releases the lock, M will have been built.
Should Y and Z then consecutively obtain the lock on M, rebuilding it
each time, or should they use the same value of M as X did? Keep in
mind that at the time X, Y, and Z were launched, the state of the
universe leading to M was exactly the same; it is, in some sense,
lying to give them three different versions of M. Moreover, if M was
locked when you tried to build it, it is theoretically safe to assume
that M is up-to-date (or unbuildable due to errors) when it becomes
unlocked. That's the point of the lock.
> > • A dofile can use a loop involving inotifywait to wait for changes to
> > dependencies and immediately rebuild targets if a dependency changes.
other cases inefficient.
> > • TeX documents can contain internal references. Page and equation
> > numbers are written to an external file needed for a second build.
> >
> > • TemplateHaskell with profiling needs an executable compiled twice.
> >
> > • The technique detailed in David A. Wheeler's Fully Countering
> > Trusting Trust through Diverse Double-Compiling requires two builds
> > of a target.
more times in a row, but I think you are mapping that to redo's model
in a weird way. When I say 'redo X', I expect X to be *done*. You're
saying that it might not be done the first time, and I should redo it
again. You're also saying that it's easy to tell when I should do
this: it or its dependencies will be out-of-date according to redo
semantics. Okay, but why was your X.do script leaving X out of date
when it was done? That's very weird.
It seems to me that in all three cases, what you want is one of:
a) a single X.do script that actually does the job twice. (latex &&
latex, or whatever). Note that this script could also decide that
only one run is necessary; eg. maybe you don't need to re-run tex if
the text layout hasn't changed (I don't know, that's just an example).
b) two completely separate targets with different output files /
directories. Most people double-building compilers, for example, seem
to do it that way. This makes sense because if you find a bug in
compiler #1 by building compiler #2, you can fix it without deleting
all your #2 .o files so you can build #1 from scratch over again.
...
In the big picture, I'm proposing redo-inconsistent (or some similar
idea) because sometimes you want to do what apenwarr/redo does (only
building a dependency once per run) and sometimes you want to do what
your system does (build a dependency whenever it's out of date and
someone asks for it). redo-inconsistent means redo chooses the fast,
consistent option first, and allows you to do the slower, second
option in cases where it's desired.
Have fun,
Avery
Avery Pennarun
Oct 25, 2018, 8:21:07 PM10/25/18
to Nils Dagsson Moskopp, redo
On Thu, Oct 25, 2018 at 2:31 PM Nils Dagsson Moskopp
<ni...@dieweltistgarnichtso.net> wrote:
> I know not a single project in which the tiny overhead of stat(2)-ing
> lots of files is worse than potentially stale builds. Please show and
> tell when the overhead becomes too much, preferably with a real-world
> project.
It all depends on the size and shape of your project. Fundamentally,
<ni...@dieweltistgarnichtso.net> wrote:
> I know not a single project in which the tiny overhead of stat(2)-ing
> lots of files is worse than potentially stale builds. Please show and
> tell when the overhead becomes too much, preferably with a real-world
> project.
checking dependencies *is* the slow part of an incremental build; it's
why recursive make is so slow.
As a trivial example, check out 10 or 100 copies of the Linux kernel
and put them all in the same git repository, and then run 'git
status'. It will take at least a couple of seconds, even if
everything is already in cache. And git has the fastest file status
checking code I've ever seen anywhere (other than push-based like
inotify of course). IMHO, two seconds is way too long to wait on
every incremental build. And there are plenty of organizations with
source trees even larger than 100x a Linux kernel (scarily enough).
This is amplified by orders of magnitude when your dependencies are
on, say, NFS or a fuse filesystem.
And of course, my code is not as fast as git, so all the problems are
automatically much worse. A single Linux kernel's worth of source
files is enough to make my redo-ifchange take a couple of seconds. If
you have to fork stat(1) for every source file, I assume it's even
worse in a pure-sh version of redo.
> By the way, making “redo-ifchange” not rebuild targets in some special
> cases is a surprise to users. Such surprises are evidence of security,
> safety, and usability issues. If I wanted a build system that randomly
> does not rebuild stuff when it would be appropriate to do it … I would
> use make(1).
behaviour is very surprising, if that's what a user has been led to
expect. Admittedly, the (my) redo documentation isn't super clear on
this, because I assumed it was obvious. Since you interpreted it
differently, clearly I was wrong in that assumption.
A human, handed a list of tasks, will not necessarily go back to you
after each task to see if you have a new one. Similarly, my version
of redo takes a list of high-level tasks from you, plans them all out
(checks all the dependencies at once), and executes once. As I
mentioned in my other email, this is a self-consistent view of the
world that I think is pretty easy to explain, and as a bonus allows
for lots of neat optimizations. Your view is also self-consistent,
but does not allow for neat optimizations. And I don't think yours is
actually any easier to explain.
Have fun,
Avery
Tharre
Oct 25, 2018, 11:54:37 PM10/25/18
to Avery Pennarun, redo
On 10/24, Avery Pennarun wrote:
mailing list ;-)
> On the other hand, I myself came from point of view B, and that's how
> apenwarr/redo is written. My redo has the concept of a "run": the
> toplevel redo in a hierarchy picks a run id, then sets REDO_RUNID to
> that number, and all child redo processes inherit that runid. Using
> the runid, it can perform an optimization (and yes, I use the work
> optimization advisedly here :)) where it doesn't need to stat any
> dependencies more than once in a single run... as long as we assume
> that we won't need to build the same target more than once during a
> run.
That's pretty much also how I implemented it, too.
> apenwarr/redo is designed to be re-entrant, which means you can start
> *separate* redo process hierarchies that know nothing about each
> other, all running on the same state database with the same sources
> and targets. It's very careful about locking to make this possible.
> (AFAIK all the other redo implementations don't do locking at all and
> don't even attempt this feature.) Each separate redo process tree
> will choose its own runid, so it'll notice whether a particular
> dependency has been checked by *its* runid or not. [...]
I've tried to implement something very similar, except with atomic
appends. Alas it has never actually tested in this way and is thus
probably broken.
> So okay, now I need to bring up an issue that was danced around in the
> thread, but never stated explicitly. What does anyone even *expect*
> to happen if source files change *during* a run? Clearly opinions
> differ on this. I think all of the opinions stated in the 2016 thread
> are not quite right. Here's what I think should happen:
>
> i) If target X is depended upon by targets A...E which are all being
> built in a single run, then all of targets A....E should see the same
> value of X, to produce a consistent build.
Agreed.
> ii) If target X depends on source Y, and source Y changes during the
> build of X, then we should stamp X with the *original* stat data for
> Y, not the stat data for Y after the build of X is complete. That
> makes it clear that on the next run, X is already dirty. However, in
> order to achieve (i), we should consider X to still be clean for
> *this* run (because we don't want to have to re-stat Y all the time.)
Agreed. And note that the alternative is really terrible, if you have
i.e. libraries that get built before your actual program. You don't want
to descend down into their dependency graphs every time you
redo-ifchange their .so file.
> iii) And yet, we want to allow for situations where we *do* want to
> build X more than once. If we allow this, the result is that targets
> A...E might be inconsistent with each other. I don't think such
> inconsistency should be the default. Right now, apenwarr/redo's unit
> tests have a 'flush-cache' command that basically drops the stat cache
> once, causing a one-time re-stat of all sources, and thus allows this
> sort of inconsistency in a semi-controlled way. I propose a new
> command, redo-inconsistent, which lets you do this in a more
> controlled and standardized way: specify a list of targets or sources,
> and we flush the cache for the current run for *only* the given files
> and their dependencies, forcing a one-time re-stat. [...]
I like the idea. Though the name, redo-inconsistent seems confusing,
maybe redo-recheck would be better? Names are hard.
> I personally think that any script needing this inconsistent build
> behaviour will know very well that it needs it, and this command would
> make the author state it explicitly, which is good for readability and
> cacheability.
Yes, and most importantly it should make it obvious to someone not
familiar with a specific set of .do files what is happening.
> [P.S. Another point that came up in that thread was that apenwarr/redo
> is really slow and sh implementations are much faster, and also that
> sqlite3 is super slow compared to the filesystem. I'm a little
> confused by this, perhaps mostly the benchmarking methodology. When I
> wrote redo in 2010, redo-ifchange runtime was already much less than
> the compile time of a typical c++ file. In the intervening years, c++
> compilers have managed to get *even slower* while redo has (of course
> since I stopped working on it) stayed about the same. And even so,
> about 0% of redo-ifchange runtime is spent manipulating sqlite. I
> wonder if y'all have some kind of different distro, or different
> settings, or different hardware, or something than me which causes are
> results to be so stunningly different. I mean, I'm not against a C
> redo, but redo-ifchange starts in ~0.02s for me, which is not exactly
> a nightmare even if it's ~20x as slow as starting a C program.]
I'm 99% sure the slowness we talked about back then is just caused by
python's terrible startup time. Arguably that isn't that important
anyway if the majority of your build time is spent actually compiling
stuff, but as we've seen people use redo for crazy stuff ;-)
Regards,
Tharre
--
PGP fingerprint: 42CE 7698 D6A0 6129 AA16 EF5C 5431 BDE2 C8F0 B2F4
> Someone wrote:
> > We had a discussion about this topic some time ago on this mailing list
> > actually, see
> > https://groups.google.com/forum/#!msg/redo-list/iBkdbc4duoM/s92qF5gIBwAJ
>
> Thanks for the link! I was very busy and not keeping up with
> discussions over the last few years, and only recently climbed out of
> my hole :)
Heh, that somebody was me, and that mail was meant to go to the hole
> > We had a discussion about this topic some time ago on this mailing list
> > actually, see
> > https://groups.google.com/forum/#!msg/redo-list/iBkdbc4duoM/s92qF5gIBwAJ
>
> Thanks for the link! I was very busy and not keeping up with
> discussions over the last few years, and only recently climbed out of
> my hole :)
mailing list ;-)
> On the other hand, I myself came from point of view B, and that's how
> apenwarr/redo is written. My redo has the concept of a "run": the
> toplevel redo in a hierarchy picks a run id, then sets REDO_RUNID to
> that number, and all child redo processes inherit that runid. Using
> the runid, it can perform an optimization (and yes, I use the work
> optimization advisedly here :)) where it doesn't need to stat any
> dependencies more than once in a single run... as long as we assume
> that we won't need to build the same target more than once during a
> run.
> apenwarr/redo is designed to be re-entrant, which means you can start
> *separate* redo process hierarchies that know nothing about each
> other, all running on the same state database with the same sources
> and targets. It's very careful about locking to make this possible.
> (AFAIK all the other redo implementations don't do locking at all and
> don't even attempt this feature.) Each separate redo process tree
> will choose its own runid, so it'll notice whether a particular
I've tried to implement something very similar, except with atomic
appends. Alas it has never actually tested in this way and is thus
probably broken.
> So okay, now I need to bring up an issue that was danced around in the
> thread, but never stated explicitly. What does anyone even *expect*
> to happen if source files change *during* a run? Clearly opinions
> differ on this. I think all of the opinions stated in the 2016 thread
> are not quite right. Here's what I think should happen:
>
> i) If target X is depended upon by targets A...E which are all being
> built in a single run, then all of targets A....E should see the same
> value of X, to produce a consistent build.
> ii) If target X depends on source Y, and source Y changes during the
> build of X, then we should stamp X with the *original* stat data for
> Y, not the stat data for Y after the build of X is complete. That
> makes it clear that on the next run, X is already dirty. However, in
> order to achieve (i), we should consider X to still be clean for
> *this* run (because we don't want to have to re-stat Y all the time.)
i.e. libraries that get built before your actual program. You don't want
to descend down into their dependency graphs every time you
redo-ifchange their .so file.
> iii) And yet, we want to allow for situations where we *do* want to
> build X more than once. If we allow this, the result is that targets
> A...E might be inconsistent with each other. I don't think such
> inconsistency should be the default. Right now, apenwarr/redo's unit
> tests have a 'flush-cache' command that basically drops the stat cache
> once, causing a one-time re-stat of all sources, and thus allows this
> sort of inconsistency in a semi-controlled way. I propose a new
> command, redo-inconsistent, which lets you do this in a more
> controlled and standardized way: specify a list of targets or sources,
> and we flush the cache for the current run for *only* the given files
I like the idea. Though the name, redo-inconsistent seems confusing,
maybe redo-recheck would be better? Names are hard.
> I personally think that any script needing this inconsistent build
> behaviour will know very well that it needs it, and this command would
> make the author state it explicitly, which is good for readability and
> cacheability.
familiar with a specific set of .do files what is happening.
> [P.S. Another point that came up in that thread was that apenwarr/redo
> is really slow and sh implementations are much faster, and also that
> sqlite3 is super slow compared to the filesystem. I'm a little
> confused by this, perhaps mostly the benchmarking methodology. When I
> wrote redo in 2010, redo-ifchange runtime was already much less than
> the compile time of a typical c++ file. In the intervening years, c++
> compilers have managed to get *even slower* while redo has (of course
> since I stopped working on it) stayed about the same. And even so,
> about 0% of redo-ifchange runtime is spent manipulating sqlite. I
> wonder if y'all have some kind of different distro, or different
> settings, or different hardware, or something than me which causes are
> results to be so stunningly different. I mean, I'm not against a C
> redo, but redo-ifchange starts in ~0.02s for me, which is not exactly
> a nightmare even if it's ~20x as slow as starting a C program.]
python's terrible startup time. Arguably that isn't that important
anyway if the majority of your build time is spent actually compiling
stuff, but as we've seen people use redo for crazy stuff ;-)
Regards,
Tharre
--
PGP fingerprint: 42CE 7698 D6A0 6129 AA16 EF5C 5431 BDE2 C8F0 B2F4
Avery Pennarun
Oct 26, 2018, 12:42:08 AM10/26/18
to tha...@gmail.com, redo
On Thu, Oct 25, 2018 at 11:54 PM Tharre <tha...@gmail.com> wrote:
> I've tried to implement something very similar, except with atomic
> appends. Alas it has never actually tested in this way and is thus
> probably broken.
Yeah, mine is only lightly tested. We probably need some good
> I've tried to implement something very similar, except with atomic
> appends. Alas it has never actually tested in this way and is thus
> probably broken.
automated tests added for this (which is a little tricky since the
automated tests run inside a redo instance, of course...)
> I like the idea. Though the name, redo-inconsistent seems confusing,
> maybe redo-recheck would be better? Names are hard.
thousands of dependencies at once) but for me, python startup time is
still fairly quick: on the order of 0.02s, vs a C program with
~0.001s. Are you seeing something different?
One thing I learned about a few years ago is that some python installs
get slower and slower if there are extra "packages" installed, because
they all add to the python search path and introduce a bit of extra
initialization cost. A hacky workaround is to start python with
"#!/usr/bin/python -S" instead of "#!/usr/bin/env python" to see if
that changes the timing. The -S parameter tells it not to run any
startup scripts, which include the gunk added by easy_install.
I nevertheless agree that a C version of redo-ifchange is likely to
run 10-20x faster than python, which is desirable if only for bragging
purposes.
Have fun,
Avery
Tharre
Oct 27, 2018, 12:53:51 PM10/27/18
to Avery Pennarun, redo
On 10/26, Avery Pennarun wrote:
> That makes sense, and matches my own experience (except when checking
> thousands of dependencies at once) but for me, python startup time is
> still fairly quick: on the order of 0.02s, vs a C program with
> ~0.001s. Are you seeing something different?
No, that seems to be roughly what I'm seeing as well. Although it's
> That makes sense, and matches my own experience (except when checking
> thousands of dependencies at once) but for me, python startup time is
> still fairly quick: on the order of 0.02s, vs a C program with
> ~0.001s. Are you seeing something different?
somewhat worse if you do it many many times over.
Of course, proper benchmarks for this sort of stuff would be nice.
Nils Dagsson Moskopp
Oct 27, 2018, 6:59:41 PM10/27/18
to Avery Pennarun, redo
Avery Pennarun <apen...@gmail.com> writes:
> On Thu, Oct 25, 2018 at 2:31 PM Nils Dagsson Moskopp
> <ni...@dieweltistgarnichtso.net> wrote:
>>
>> […]
> On Thu, Oct 25, 2018 at 2:31 PM Nils Dagsson Moskopp
> <ni...@dieweltistgarnichtso.net> wrote:
>>
>>
>> By the way, making “redo-ifchange” not rebuild targets in some special
>> cases is a surprise to users. Such surprises are evidence of security,
>> safety, and usability issues. If I wanted a build system that randomly
>> does not rebuild stuff when it would be appropriate to do it … I would
>> use make(1).
>
> I know what you mean, but I don't think the "build at most once"
> behaviour is very surprising, if that's what a user has been led to
> expect. Admittedly, the (my) redo documentation isn't super clear on
> this, because I assumed it was obvious. Since you interpreted it
> differently, clearly I was wrong in that assumption.
Your documentation contains this description of redo-ifchange behaviour:
>> By the way, making “redo-ifchange” not rebuild targets in some special
>> cases is a surprise to users. Such surprises are evidence of security,
>> safety, and usability issues. If I wanted a build system that randomly
>> does not rebuild stuff when it would be appropriate to do it … I would
>> use make(1).
>
> I know what you mean, but I don't think the "build at most once"
> behaviour is very surprising, if that's what a user has been led to
> expect. Admittedly, the (my) redo documentation isn't super clear on
> this, because I assumed it was obvious. Since you interpreted it
> differently, clearly I was wrong in that assumption.
> The redo-ifchange command means, "build each of my arguments. If any
> of them or their dependencies ever change, then I need to run the
> current script over again."
Source: <https://github.com/apenwarr/redo>
I just implemented that behaviour the simplest way it could possibly
work. To make it obvious that something is built only once, the text
should have been something along the lines of:
> The redo-ifchange command means, “build each of my arguments, except
> for those that were already built in the recent past. If any of them
> or their dependencies ever change, then I need to run the current
> script over again, unless it was already run in the recent past or
> redo can not figure out why an argument or its dependency changed.”
As you can probably guess from that “in the recent past”, I have no idea
how to even describe the behaviour of not rebuilding out-of-date targets
that your redo implementation exhibits in layman's terms. I do know this
phenomenon, of not documenting stuff, which is why I always let ordinary
people outside of a project review the documentation for it. My own redo
man pages were a mess in the first version, before my friends read them.
> A human, handed a list of tasks, will not necessarily go back to you
> after each task to see if you have a new one.
will probably check those before each task. The redo idea is about such
prerequisites for tasks, i.e. “if this resource is not in such-and-such
state, do this task to rectify the situation”. And the major reason why
one would use redo is that other systems do this in a way that does not
capture everything. Make, for example, can not ever handle nonexistence
dependencies – no system that needs the full dependency tree before the
build can.
> Similarly, my version of redo takes a list of high-level tasks from
> you, plans them all out (checks all the dependencies at once), and
> executes once. As I mentioned in my other email, this is a
> self-consistent view of the world that I think is pretty easy to
> explain, and as a bonus allows for lots of neat optimizations.
redo-always and/or dependencies on resources that could change during a
run without user intervention (the output of “curl http://example.org”,
for example) is guaranteed to be subtly wrong using this redo approach.
The *big* problem is that “redo-ifchange” is no longer atomic – what you
attempted to make atomic is the whole build. Yet for that to make sense,
you could only replace files at the very end of it and freeze everything
that could be dependency-checked at the very beginning (making the cache
the reality, in a way). If you are not root / have a networked computer,
this is impossible.
A dofile involving loops and an iterative process is not even possible:
The result would even differ depending on such loop being in the dofile
or in a shell script which invokes redo, because the latter does ensure
that dependencies are checked.
I can not show them to you, since I wrote them in a work context, but I
did write dofiles that generated API documentation for a HTTP Backend …
and this documentation included examples that were the calls to the API
that I was documenting and the responses. This meant that each of those
targets depended on the service being in a running state. Now, having a
target that starts a service and outputs the state of it is technically
racy, but it was very useful, since other processes on the same machine
also involved starting (or killing) the service. Your solution would be
one that would start the service once even if redo-always was involved,
if I am not mistaken – but it would pretend that one service started is
online forever, even if it was not in reality, as it would not rebuild.
> Your view is also self-consistent, but does not allow for neat
> optimizations. And I don't think yours is actually any easier to
> explain.
can not take some shortcuts. It also explains why my own parallelization
attempts went nowhere, as I tried to solve a different (harder) problem.
The result is that with my approach, users could achieve everything that
is possible with your approach. On the other hand, your approach has the
same set of issues that make(1) has: It is possible that targets are not
being rebuilt, even though they probably should.
I want to again ask you for real-world projects you have been using redo
in. As I have written before, I wrote my redo implementation because the
build process I had should neither have stale builds, nor do superfluous
rebuilds. As I understand it, your implementation basically codifies the
opinion that superfluous rebuilds are worse than stale builds – while my
implementation basically codifies the opinion that a build system should
do the most it can to make sure that nothing in a build is out of date …
so ”Better fast than correct!” or vice versa. Would you agree with that?
Another suggestion: Your approach works if all sources are idempotent –
which could be approximately true for files, but mostly wrong for other
things. My approach does not care about that property.
Just to make it clear: I would have nothing against any stat cache if a
caching implementation was just faster than non-caching implementations
are. I think “Make it correct, then make it fast.” is a good approach …
One more thing: Since “do” does always rebuild and has no stat cache, it
is basically correct from my point of view. It does remove targets (that
surely is a problem) – but it will never erroneously not build a target.
Avery Pennarun
Oct 28, 2018, 12:40:38 AM10/28/18
to Nils Dagsson Moskopp, redo
On Sat, Oct 27, 2018 at 6:59 PM Nils Dagsson Moskopp
<ni...@dieweltistgarnichtso.net> wrote:
indicate that redo-ifchange does two separate things:
1) It requests redo to build the targets if needed
2) It explains to redo that when checking the *current* target in the
future, that it depends on the given targets.
If X depends on A, then ever after building X, if A has changed since
last time we checked, yes, we have to build X again. What my
documentation doesn't say is that we *will* run the current script
again *right now*. No information is lost. You're creating weird
dependency loops and expecting something useful to happen; there is no
unambiguous way to resolve a dependency loop in such a way that we can
expect the loop to ever terminate. redo isn't prolog; nobody expects
it to just run forever until the chain finally breaks.
> I just implemented that behaviour the simplest way it could possibly
> work. To make it obvious that something is built only once, the text
> should have been something along the lines of:
>
> > The redo-ifchange command means, “build each of my arguments, except
> > for those that were already built in the recent past. If any of them
> > or their dependencies ever change, then I need to run the current
> > script over again, unless it was already run in the recent past or
> > redo can not figure out why an argument or its dependency changed.”
Your text above makes it sound like redo will re-run the "current
script" again in the current run, without even being asked. That's
not even what redo-ifchange means, ever.
> As you can probably guess from that “in the recent past”, I have no idea
> how to even describe the behaviour of not rebuilding out-of-date targets
> that your redo implementation exhibits in layman's terms. I do know this
> phenomenon, of not documenting stuff, which is why I always let ordinary
> people outside of a project review the documentation for it. My own redo
> man pages were a mess in the first version, before my friends read them.
I'm not making a claim that my documentation is perfect or wouldn't be
greatly improved by having more proofreaders. Sure.
However, by your own admission, your original docs were a mess until
your friends read them. This may mean that your mental model is a
mess. Maybe you should ask your friends if "redo-ifchange only builds
a given target at most once per run" is confusing or not?
> > A human, handed a list of tasks, will not necessarily go back to you
> > after each task to see if you have a new one.
>
> A strange point; but a human, given a list of *prerequisites* for tasks
> will probably check those before each task. The redo idea is about such
> prerequisites for tasks, i.e. “if this resource is not in such-and-such
> state, do this task to rectify the situation”. And the major reason why
> one would use redo is that other systems do this in a way that does not
> capture everything. Make, for example, can not ever handle nonexistence
> dependencies – no system that needs the full dependency tree before the
> build can.
There are many ways a human might execute a task list. One obvious
way is this: imagine my job is to take out all the garbage from each
floor of a building, once per day. I go to each floor, and take out
the garbage. After I'm done, I don't revisit each floor to see if
more garbage has appeared. If someone asks me at the end of the day
whether I took out "all" the garbage, I can say with 100% certainty,
yes I did! If they ask me to go take out all the garbage again, I can
do that. I don't think this way of doing things is confusing for most
humans. Moreover, when I ask redo to do something, that's exactly
what I want it to do. Don't be fancy, just do the things I tell you.
Once. If I want you to do it more than once, I'll say so.
> > Similarly, my version of redo takes a list of high-level tasks from
> > you, plans them all out (checks all the dependencies at once), and
> > executes once. As I mentioned in my other email, this is a
> > self-consistent view of the world that I think is pretty easy to
> > explain, and as a bonus allows for lots of neat optimizations.
>
> I seriously doubt the consistency of this approach – anything involving
> redo-always and/or dependencies on resources that could change during a
> run without user intervention (the output of “curl http://example.org”,
> for example) is guaranteed to be subtly wrong using this redo approach.
My point about "consistency" is that everything built in a given run
is built using a *single* result of, say, your "curl
http://example.org". If you have multiple .o files depending on that
input, say, then they will all be working from the same thing.
As a silly example, imagine I have a date.do that does just this:
date >$3
redo-always
redo-stamp <$3
Then I do various transformations on the date. For example,
version.h.do turns it into a version number for my nightly build, and
nightly.do produces a tarball that uses the date in a version number.
Both of those targets depend on date. If date is not identical for
*both*, and say the compile is slow or started at 11:59pm, then I
could end up with a release where version.h says yesterday but the
tarball filename is today. Oops!
If you really want to re-run curl every time its output is used, then
just run it directly. redo doesn't add anything. Despite its name,
most of the purpose of redo is to *not* redo things when not
necessary. Otherwise you'd just use a shell script.
> The *big* problem is that “redo-ifchange” is no longer atomic – what you
> attempted to make atomic is the whole build. Yet for that to make sense,
> you could only replace files at the very end of it and freeze everything
> that could be dependency-checked at the very beginning (making the cache
> the reality, in a way). If you are not root / have a networked computer,
> this is impossible.
If your external dependencies change atomically, then actually you
could construct a set of redo scripts that retrieves the atomic set of
values from the server once per run. Then downstream .do files could
pull parts of the retrieved files to generate individual targets.
That would give you an atomically correct build.
I think that would work with my implementation, but not yours, because
yours has no way to stop redo-always targets from running repeatedly
and breaking atomicity.
My proposal in an earlier email was to add a command like redo-recheck
(originally redo-inconsistent) to optionally make my version able to
act like yours, while explicitly declaring that you don't want this
atomicity.
> A dofile involving loops and an iterative process is not even possible:
> The result would even differ depending on such loop being in the dofile
> or in a shell script which invokes redo, because the latter does ensure
> that dependencies are checked.
I'm not sure what you mean here. I use dofiles with loops all the
time. But I don't "redo-ifchange" the same thing repeatedly across
loop iterations, that's true. I feel like at most you just want to
call 'redo' there instead of 'redo-ifchange'. 'redo' doesn't check
dependencies nor add dependencies.
> I can not show them to you, since I wrote them in a work context, but I
> did write dofiles that generated API documentation for a HTTP Backend …
> and this documentation included examples that were the calls to the API
> that I was documenting and the responses. This meant that each of those
> targets depended on the service being in a running state. Now, having a
> target that starts a service and outputs the state of it is technically
> racy, but it was very useful, since other processes on the same machine
> also involved starting (or killing) the service. Your solution would be
> one that would start the service once even if redo-always was involved,
> if I am not mistaken – but it would pretend that one service started is
> online forever, even if it was not in reality, as it would not rebuild.
This example is awful; you have an admittedly racy service that you
and others are starting and stopping at random times, presumably all
on the same port, hoping that you're the one who wins, and praying
that the output you get from your hopefully-still-running version is
what you wanted so that you can use it to complete the current build.
Whoa! Nothing redo can do will make your plan a good plan.
One thing you could try would be to start a copy of the service on a
randomized port number so that other people don't conflict with yours.
Then you could, yes, start it only one time instead of multiple times.
As a bonus, your build would go faster because you don't have to
constantly start/stop your service only to try to shrink the race
condition window.
> > Your view is also self-consistent, but does not allow for neat
> > optimizations. And I don't think yours is actually any easier to
> > explain.
>
> As I see it, the single downside of my approach is that the implementors
> can not take some shortcuts. It also explains why my own parallelization
> attempts went nowhere, as I tried to solve a different (harder) problem.
>
> The result is that with my approach, users could achieve everything that
> is possible with your approach. On the other hand, your approach has the
> same set of issues that make(1) has: It is possible that targets are not
> being rebuilt, even though they probably should.
Your model of build systems apparently doesn't include "run fast" as a
thing that can be achieved, because your model cannot ever achieve
that if it isn't allowed to ever cache dependency checks. This was
also one of my annoyances with the "Build systems a la carte" paper,
which was theoretically interesting but practically missed a lot of
important stuff.
In any case, my version of redo supports parallelism and very large
projects, and none of the others do. This is because I thought
through this stuff in advance. Parallelism is massively important to
all my use cases.
I also proposed a redo-recheck command that seems to enable the few
rare cases that you bring up that my system currently rejects.
> I want to again ask you for real-world projects you have been using redo
> in.
You can play with my wvbuild and wvstreams projects (on github) if you
like. wvbuild's toplevel redo scripts compile big projects like
openssl (itself using make) and then uses them as dependencies for the
wvstreams project (which is no entirely redo-ized). Beware that
currently wvstreams relies on my original redo-whichdo syntax,
although I think you've convinced me to switch to your proposed
whichdo syntax.
A much uglier project is buildroot, which I've been working to
partially switch over to redo, with great success so far. Startup
time is much shorter than with (non-recursive) make, and yet
dependency handling is clearer with redo, so there can be more
parallelism, thus also reducing build times. buildroot extracts many
full-sized open source packages and wants to know what to rebuild when
you change one of the source files in any of them, so the dependency
tree is quite a nightmare. apenwarr/redo is still annoyingly slow
when I add all the dependencies I want, and that's with all my
optimizations currently in place, so it's a great place to look for
further improvements. I haven't released my buildroot patches yet
because they're too messy, however.
> As I have written before, I wrote my redo implementation because the
> build process I had should neither have stale builds, nor do superfluous
> rebuilds. As I understand it, your implementation basically codifies the
> opinion that superfluous rebuilds are worse than stale builds – while my
> implementation basically codifies the opinion that a build system should
> do the most it can to make sure that nothing in a build is out of date …
> so ”Better fast than correct!” or vice versa. Would you agree with that?
No, that's not how I would phrase it. Both your version and my
version are correct, for different definitions of correct. My version
expects dependencies to be in the shape of a DAG and that any
dependency will not change during a run unless redo is what changed
it. Even so, if you violate these expectations (change a dependency
during a run, from outside redo) it will react in a predictable way:
it will consider the right targets to be out of date even after redo
returns. This is not incorrect, it's a well-defined model that
doesn't match yours.
> Another suggestion: Your approach works if all sources are idempotent –
> which could be approximately true for files, but mostly wrong for other
> things. My approach does not care about that property.
I assume you mean 'targets are idempotent' here, not sources. Yes, I
suppose that's an implicit assumption I've been using. It's true that
if you have a random.do that reads a bunch of bytes from /dev/urandom,
you might be in for some unexpected results.
> One more thing: Since “do” does always rebuild and has no stat cache, it
> is basically correct from my point of view. It does remove targets (that
> surely is a problem) – but it will never erroneously not build a target.
That was the intention, that it be the simplest possible thing that's
basically correct, albeit inefficient. However, even minimal/do will
only build a redo-always target once per run. Since it doesn't
remember dependencies at all, this was the only way to implement
redo-ifchange without building every dependency again every time any
target depended on it.
Have fun,
Avery
<ni...@dieweltistgarnichtso.net> wrote:
> Avery Pennarun <apen...@gmail.com> writes:
> > I know what you mean, but I don't think the "build at most once"
> > behaviour is very surprising, if that's what a user has been led to
> > expect. Admittedly, the (my) redo documentation isn't super clear on
> > this, because I assumed it was obvious. Since you interpreted it
> > differently, clearly I was wrong in that assumption.
>
> Your documentation contains this description of redo-ifchange behaviour:
>
> > The redo-ifchange command means, "build each of my arguments. If any
> > of them or their dependencies ever change, then I need to run the
> > current script over again."
>
> Source: <https://github.com/apenwarr/redo>
I can see how that phrase is confusing, but it is intending to
> > I know what you mean, but I don't think the "build at most once"
> > behaviour is very surprising, if that's what a user has been led to
> > expect. Admittedly, the (my) redo documentation isn't super clear on
> > this, because I assumed it was obvious. Since you interpreted it
> > differently, clearly I was wrong in that assumption.
>
> Your documentation contains this description of redo-ifchange behaviour:
>
> > The redo-ifchange command means, "build each of my arguments. If any
> > of them or their dependencies ever change, then I need to run the
> > current script over again."
>
> Source: <https://github.com/apenwarr/redo>
indicate that redo-ifchange does two separate things:
1) It requests redo to build the targets if needed
2) It explains to redo that when checking the *current* target in the
future, that it depends on the given targets.
If X depends on A, then ever after building X, if A has changed since
last time we checked, yes, we have to build X again. What my
documentation doesn't say is that we *will* run the current script
again *right now*. No information is lost. You're creating weird
dependency loops and expecting something useful to happen; there is no
unambiguous way to resolve a dependency loop in such a way that we can
expect the loop to ever terminate. redo isn't prolog; nobody expects
it to just run forever until the chain finally breaks.
> I just implemented that behaviour the simplest way it could possibly
> work. To make it obvious that something is built only once, the text
> should have been something along the lines of:
>
> > The redo-ifchange command means, “build each of my arguments, except
> > for those that were already built in the recent past. If any of them
> > or their dependencies ever change, then I need to run the current
> > script over again, unless it was already run in the recent past or
> > redo can not figure out why an argument or its dependency changed.”
script" again in the current run, without even being asked. That's
not even what redo-ifchange means, ever.
> As you can probably guess from that “in the recent past”, I have no idea
> how to even describe the behaviour of not rebuilding out-of-date targets
> that your redo implementation exhibits in layman's terms. I do know this
> phenomenon, of not documenting stuff, which is why I always let ordinary
> people outside of a project review the documentation for it. My own redo
> man pages were a mess in the first version, before my friends read them.
greatly improved by having more proofreaders. Sure.
However, by your own admission, your original docs were a mess until
your friends read them. This may mean that your mental model is a
mess. Maybe you should ask your friends if "redo-ifchange only builds
a given target at most once per run" is confusing or not?
> > A human, handed a list of tasks, will not necessarily go back to you
> > after each task to see if you have a new one.
>
> A strange point; but a human, given a list of *prerequisites* for tasks
> will probably check those before each task. The redo idea is about such
> prerequisites for tasks, i.e. “if this resource is not in such-and-such
> state, do this task to rectify the situation”. And the major reason why
> one would use redo is that other systems do this in a way that does not
> capture everything. Make, for example, can not ever handle nonexistence
> dependencies – no system that needs the full dependency tree before the
> build can.
way is this: imagine my job is to take out all the garbage from each
floor of a building, once per day. I go to each floor, and take out
the garbage. After I'm done, I don't revisit each floor to see if
more garbage has appeared. If someone asks me at the end of the day
whether I took out "all" the garbage, I can say with 100% certainty,
yes I did! If they ask me to go take out all the garbage again, I can
do that. I don't think this way of doing things is confusing for most
humans. Moreover, when I ask redo to do something, that's exactly
what I want it to do. Don't be fancy, just do the things I tell you.
Once. If I want you to do it more than once, I'll say so.
> > Similarly, my version of redo takes a list of high-level tasks from
> > you, plans them all out (checks all the dependencies at once), and
> > executes once. As I mentioned in my other email, this is a
> > self-consistent view of the world that I think is pretty easy to
> > explain, and as a bonus allows for lots of neat optimizations.
>
> I seriously doubt the consistency of this approach – anything involving
> redo-always and/or dependencies on resources that could change during a
> run without user intervention (the output of “curl http://example.org”,
> for example) is guaranteed to be subtly wrong using this redo approach.
is built using a *single* result of, say, your "curl
http://example.org". If you have multiple .o files depending on that
input, say, then they will all be working from the same thing.
As a silly example, imagine I have a date.do that does just this:
date >$3
redo-always
redo-stamp <$3
Then I do various transformations on the date. For example,
version.h.do turns it into a version number for my nightly build, and
nightly.do produces a tarball that uses the date in a version number.
Both of those targets depend on date. If date is not identical for
*both*, and say the compile is slow or started at 11:59pm, then I
could end up with a release where version.h says yesterday but the
tarball filename is today. Oops!
If you really want to re-run curl every time its output is used, then
just run it directly. redo doesn't add anything. Despite its name,
most of the purpose of redo is to *not* redo things when not
necessary. Otherwise you'd just use a shell script.
> The *big* problem is that “redo-ifchange” is no longer atomic – what you
> attempted to make atomic is the whole build. Yet for that to make sense,
> you could only replace files at the very end of it and freeze everything
> that could be dependency-checked at the very beginning (making the cache
> the reality, in a way). If you are not root / have a networked computer,
> this is impossible.
could construct a set of redo scripts that retrieves the atomic set of
values from the server once per run. Then downstream .do files could
pull parts of the retrieved files to generate individual targets.
That would give you an atomically correct build.
I think that would work with my implementation, but not yours, because
yours has no way to stop redo-always targets from running repeatedly
and breaking atomicity.
My proposal in an earlier email was to add a command like redo-recheck
(originally redo-inconsistent) to optionally make my version able to
act like yours, while explicitly declaring that you don't want this
atomicity.
> A dofile involving loops and an iterative process is not even possible:
> The result would even differ depending on such loop being in the dofile
> or in a shell script which invokes redo, because the latter does ensure
> that dependencies are checked.
time. But I don't "redo-ifchange" the same thing repeatedly across
loop iterations, that's true. I feel like at most you just want to
call 'redo' there instead of 'redo-ifchange'. 'redo' doesn't check
dependencies nor add dependencies.
> I can not show them to you, since I wrote them in a work context, but I
> did write dofiles that generated API documentation for a HTTP Backend …
> and this documentation included examples that were the calls to the API
> that I was documenting and the responses. This meant that each of those
> targets depended on the service being in a running state. Now, having a
> target that starts a service and outputs the state of it is technically
> racy, but it was very useful, since other processes on the same machine
> also involved starting (or killing) the service. Your solution would be
> one that would start the service once even if redo-always was involved,
> if I am not mistaken – but it would pretend that one service started is
> online forever, even if it was not in reality, as it would not rebuild.
and others are starting and stopping at random times, presumably all
on the same port, hoping that you're the one who wins, and praying
that the output you get from your hopefully-still-running version is
what you wanted so that you can use it to complete the current build.
Whoa! Nothing redo can do will make your plan a good plan.
One thing you could try would be to start a copy of the service on a
randomized port number so that other people don't conflict with yours.
Then you could, yes, start it only one time instead of multiple times.
As a bonus, your build would go faster because you don't have to
constantly start/stop your service only to try to shrink the race
condition window.
> > Your view is also self-consistent, but does not allow for neat
> > optimizations. And I don't think yours is actually any easier to
> > explain.
>
> As I see it, the single downside of my approach is that the implementors
> can not take some shortcuts. It also explains why my own parallelization
> attempts went nowhere, as I tried to solve a different (harder) problem.
>
> The result is that with my approach, users could achieve everything that
> is possible with your approach. On the other hand, your approach has the
> same set of issues that make(1) has: It is possible that targets are not
> being rebuilt, even though they probably should.
thing that can be achieved, because your model cannot ever achieve
that if it isn't allowed to ever cache dependency checks. This was
also one of my annoyances with the "Build systems a la carte" paper,
which was theoretically interesting but practically missed a lot of
important stuff.
In any case, my version of redo supports parallelism and very large
projects, and none of the others do. This is because I thought
through this stuff in advance. Parallelism is massively important to
all my use cases.
I also proposed a redo-recheck command that seems to enable the few
rare cases that you bring up that my system currently rejects.
> I want to again ask you for real-world projects you have been using redo
> in.
like. wvbuild's toplevel redo scripts compile big projects like
openssl (itself using make) and then uses them as dependencies for the
wvstreams project (which is no entirely redo-ized). Beware that
currently wvstreams relies on my original redo-whichdo syntax,
although I think you've convinced me to switch to your proposed
whichdo syntax.
A much uglier project is buildroot, which I've been working to
partially switch over to redo, with great success so far. Startup
time is much shorter than with (non-recursive) make, and yet
dependency handling is clearer with redo, so there can be more
parallelism, thus also reducing build times. buildroot extracts many
full-sized open source packages and wants to know what to rebuild when
you change one of the source files in any of them, so the dependency
tree is quite a nightmare. apenwarr/redo is still annoyingly slow
when I add all the dependencies I want, and that's with all my
optimizations currently in place, so it's a great place to look for
further improvements. I haven't released my buildroot patches yet
because they're too messy, however.
> As I have written before, I wrote my redo implementation because the
> build process I had should neither have stale builds, nor do superfluous
> rebuilds. As I understand it, your implementation basically codifies the
> opinion that superfluous rebuilds are worse than stale builds – while my
> implementation basically codifies the opinion that a build system should
> do the most it can to make sure that nothing in a build is out of date …
> so ”Better fast than correct!” or vice versa. Would you agree with that?
version are correct, for different definitions of correct. My version
expects dependencies to be in the shape of a DAG and that any
dependency will not change during a run unless redo is what changed
it. Even so, if you violate these expectations (change a dependency
during a run, from outside redo) it will react in a predictable way:
it will consider the right targets to be out of date even after redo
returns. This is not incorrect, it's a well-defined model that
doesn't match yours.
> Another suggestion: Your approach works if all sources are idempotent –
> which could be approximately true for files, but mostly wrong for other
> things. My approach does not care about that property.
suppose that's an implicit assumption I've been using. It's true that
if you have a random.do that reads a bunch of bytes from /dev/urandom,
you might be in for some unexpected results.
> One more thing: Since “do” does always rebuild and has no stat cache, it
> is basically correct from my point of view. It does remove targets (that
> surely is a problem) – but it will never erroneously not build a target.
basically correct, albeit inefficient. However, even minimal/do will
only build a redo-always target once per run. Since it doesn't
remember dependencies at all, this was the only way to implement
redo-ifchange without building every dependency again every time any
target depended on it.
Have fun,
Avery
Nils Dagsson Moskopp
Oct 28, 2018, 5:58:51 PM10/28/18
to Avery Pennarun, tha...@gmail.com, redo
Avery Pennarun <apen...@gmail.com> writes:
> On Thu, Oct 25, 2018 at 11:54 PM Tharre <tha...@gmail.com> wrote:
>> I've tried to implement something very similar, except with atomic
>> appends. Alas it has never actually tested in this way and is thus
>> probably broken.
>
> Yeah, mine is only lightly tested. We probably need some good
> automated tests added for this (which is a little tricky since the
> automated tests run inside a redo instance, of course...)
>
>> I like the idea. Though the name, redo-inconsistent seems confusing,
>> maybe redo-recheck would be better? Names are hard.
>
> Yeah, that sounds like a better name.
I do not get it. How would redo-inconsistent or redo-recheck be used?
> On Thu, Oct 25, 2018 at 11:54 PM Tharre <tha...@gmail.com> wrote:
>> I've tried to implement something very similar, except with atomic
>> appends. Alas it has never actually tested in this way and is thus
>> probably broken.
>
> Yeah, mine is only lightly tested. We probably need some good
> automated tests added for this (which is a little tricky since the
> automated tests run inside a redo instance, of course...)
>
>> I like the idea. Though the name, redo-inconsistent seems confusing,
>> maybe redo-recheck would be better? Names are hard.
>
> Yeah, that sounds like a better name.
And are you two sure that your cache can not be improved? By the way,
is it possible to exit(1), as soon as a case comes up where the cache
would be inconsistent with the “real world”, or at least provide some
kind of warning? Or would checking for that case destroy all of those
speedups you want to preserve by using the cache? I think you can get
the consistent world view you want that way, without confusing users.
-S”, the “big-tree” test case (from my test suite) builds in 60 seconds,
while it takes 80 seconds with “#!/usr/bin/env python”. The Bourne shell
redo implementation I wrote takes around 30 seconds with Dash as /bin/sh
and 21 seconds with BusyBox as /bin/sh.
All tests were run with “time -v redo” twice with a fresh directory that
contained three dofiles, all.do, default.branch.do, and default.leaf.do.
; cat all.do
#!/bin/sh
for i in $(seq 10); do
redo-ifchange $i.branch
done
; cat default.branch.do
#!/bin/sh
for i in $(seq 100); do
redo-ifchange $2$i.leaf
done
date +%s
; cat default.leaf.do
#!/bin/sh
date +%s
I used the second run of “time -v redo” to estimate dependency checking
performance. I found that the Python implementation returned in under a
second if nothing would be rebuilt, my Bourne shell implementations did
return in a range from under 3 to under 5 seconds. The slowness can not
be attributed to the number of stat(2) calls, however, which in both of
those cases take less than 0.01 percent of the runtime; the reason most
likely is the number of subprocesses involved – redo implementations in
Bourne shell can spend 20 percent of runtime in wait4(2) – and the read
builtin's glacial pace.
Note that this is not representative of real-world programs … I suggest
to use the game “Liberation Circuit”, which can be built with redo (and
in fact, the Make and CMake builds have various issues) for benchmarks,
as I think it has a typical “diamond” C / C++ project dependency graph.
<https://github.com/linleyh/liberation-circuit>
> I nevertheless agree that a C version of redo-ifchange is likely to
> run 10-20x faster than python, which is desirable if only for bragging
> purposes.
dependency. I guess you could try, but I have yet to see a redo project
where the parts of redo you could redo (ha!) in C were the bottlenecks.
Greetings,
Nils Dagsson Moskopp
Oct 28, 2018, 6:39:00 PM10/28/18
to Tharre, Avery Pennarun, redo
Tharre <tha...@gmail.com> writes:
> On 10/26, Avery Pennarun wrote:
>> That makes sense, and matches my own experience (except when checking
>> thousands of dependencies at once) but for me, python startup time is
>> still fairly quick: on the order of 0.02s, vs a C program with
>> ~0.001s. Are you seeing something different?
>
> No, that seems to be roughly what I'm seeing as well. Although it's
> somewhat worse if you do it many many times over.
>
> Of course, proper benchmarks for this sort of stuff would be nice.
Would a proper benchmark involve the use of “time -v” or “strace -cf”?
> On 10/26, Avery Pennarun wrote:
>> That makes sense, and matches my own experience (except when checking
>> thousands of dependencies at once) but for me, python startup time is
>> still fairly quick: on the order of 0.02s, vs a C program with
>> ~0.001s. Are you seeing something different?
>
> No, that seems to be roughly what I'm seeing as well. Although it's
> somewhat worse if you do it many many times over.
>
> Of course, proper benchmarks for this sort of stuff would be nice.
Greetings,
Avery Pennarun
Oct 28, 2018, 7:43:25 PM10/28/18
to Nils Dagsson Moskopp, tha...@gmail.com, redo
On Sun, Oct 28, 2018 at 5:58 PM Nils Dagsson Moskopp
<ni...@dieweltistgarnichtso.net> wrote:
> Avery Pennarun <apen...@gmail.com> writes:
> > On Thu, Oct 25, 2018 at 11:54 PM Tharre <tha...@gmail.com> wrote:
> >> I've tried to implement something very similar, except with atomic
> >> appends. Alas it has never actually tested in this way and is thus
> >> probably broken.
> >
> > Yeah, mine is only lightly tested. We probably need some good
> > automated tests added for this (which is a little tricky since the
> > automated tests run inside a redo instance, of course...)
> >
> >> I like the idea. Though the name, redo-inconsistent seems confusing,
> >> maybe redo-recheck would be better? Names are hard.
> >
> > Yeah, that sounds like a better name.
>
> I do not get it. How would redo-inconsistent or redo-recheck be used?
> And are you two sure that your cache can not be improved? By the way,
> is it possible to exit(1), as soon as a case comes up where the cache
> would be inconsistent with the “real world”, or at least provide some
> kind of warning? Or would checking for that case destroy all of those
> speedups you want to preserve by using the cache? I think you can get
> the consistent world view you want that way, without confusing users.
The idea is that you can't detect that you *do* need to recheck
<ni...@dieweltistgarnichtso.net> wrote:
> Avery Pennarun <apen...@gmail.com> writes:
> > On Thu, Oct 25, 2018 at 11:54 PM Tharre <tha...@gmail.com> wrote:
> >> I've tried to implement something very similar, except with atomic
> >> appends. Alas it has never actually tested in this way and is thus
> >> probably broken.
> >
> > Yeah, mine is only lightly tested. We probably need some good
> > automated tests added for this (which is a little tricky since the
> > automated tests run inside a redo instance, of course...)
> >
> >> I like the idea. Though the name, redo-inconsistent seems confusing,
> >> maybe redo-recheck would be better? Names are hard.
> >
> > Yeah, that sounds like a better name.
>
> I do not get it. How would redo-inconsistent or redo-recheck be used?
> And are you two sure that your cache can not be improved? By the way,
> is it possible to exit(1), as soon as a case comes up where the cache
> would be inconsistent with the “real world”, or at least provide some
> kind of warning? Or would checking for that case destroy all of those
> speedups you want to preserve by using the cache? I think you can get
> the consistent world view you want that way, without confusing users.
dependencies that might have changed during a run; the only way to
detect that is to do the check, so optimization would be impossible.
However, if you assume you *don't* need to recheck, and allow the .do
file to tell you otherwise, then you can have it both ways. My
original idea was to call it redo-inconsistent because it breaks the
atomicity/inconsistency guarantees discussed above: if you have a
target that is redo-always, we will normally make sure all targets you
build during a run get the same value of that target; if you run
redo-inconsistent on that target, it disables that guarantee and you
might get a new one. As a bonus, if you're going to break such a
guarantee, it's nice to have a notice right in the .do file that this
is what you expect.
(I understand that you would argue the other way: you're expecting a
"will rebuild if sources have changed, even in the interim" guarantee.
But I don't know how to provide that guarantee by default without
throwing away useful optimizations.)
It might be useful in general to provide a warning if a *target*
changes more than once during a build, which could happen trivially if
you eg. 'redo X' more than once during a run. I'm not sure that
warning is super useful, though I'm willing to be convinced. The more
useful warning, that a source file has changed during the course of a
run, would be nice, but can't be detected without extra stat() calls.
> > One thing I learned about a few years ago is that some python installs
> > get slower and slower if there are extra "packages" installed, because
> > they all add to the python search path and introduce a bit of extra
> > initialization cost. A hacky workaround is to start python with
> > "#!/usr/bin/python -S" instead of "#!/usr/bin/env python" to see if
> > that changes the timing. The -S parameter tells it not to run any
> > startup scripts, which include the gunk added by easy_install.
>
> On my machine, this improves build times indeed. With “#!/usr/bin/python
> -S”, the “big-tree” test case (from my test suite) builds in 60 seconds,
> while it takes 80 seconds with “#!/usr/bin/env python”.
argument, so you can't have both /usr/bin/env and -S at the same time,
forcing me to opt for the former. There are potential workarounds,
such as having a redo-python installed that just runs python with -S,
and then using "#!/usr/bin/env redo-python", but that's kinda hacky.
> The Bourne shell
> redo implementation I wrote takes around 30 seconds with Dash as /bin/sh
> and 21 seconds with BusyBox as /bin/sh.
time it takes python to screw around with its modules directory.
> All tests were run with “time -v redo” twice with a fresh directory that
> contained three dofiles, all.do, default.branch.do, and default.leaf.do.
>
> ; cat all.do
> #!/bin/sh
> for i in $(seq 10); do
> redo-ifchange $i.branch
> done
>
> ; cat default.branch.do
> #!/bin/sh
> for i in $(seq 100); do
> redo-ifchange $2$i.leaf
> done
> date +%s
>
> ; cat default.leaf.do
> #!/bin/sh
> date +%s
targets depending on other targets, not on sources. It should mainly
test the time it takes to start redo-ifchange and the time it takes to
check dependencies. It also doesn't seem to share any dependencies
between branches (ie. a single leaf only appears once in the DAG).
This means you get no benefit from apenwarr/redo's stat cache, and
it's a bit unrealistic (almost all build processes share at least some
dependencies).
Note also that you're running redo-ifchange in a loop here, which is
bad for parallelism. If you instead did something like:
for i in $(seq 100); do
done | xargs redo-ifchange
(/bin/rc has special syntax for exactly this kind of thing, sigh.)
You would probably find apenwarr/redo goes extremely fast. If you
then ran apenwarr/redo with -j10, it would probably easily beat any
other redo implementation for speed of first build.
> I used the second run of “time -v redo” to estimate dependency checking
> performance. I found that the Python implementation returned in under a
> second if nothing would be rebuilt, my Bourne shell implementations did
> return in a range from under 3 to under 5 seconds. The slowness can not
> be attributed to the number of stat(2) calls, however, which in both of
> those cases take less than 0.01 percent of the runtime; the reason most
> likely is the number of subprocesses involved – redo implementations in
> Bourne shell can spend 20 percent of runtime in wait4(2) – and the read
> builtin's glacial pace.
total dependencies.
As an experiment, you could try replacing your call to 'stat' with
something like 'echo ...' (a fake output of stat). This would
eliminate all the fork/exec overhead of executing the subprogram. My
guess is you would then be much faster than apenwarr/redo at
dependency checking.
FWIW, in that benchmark, doing just the dependency check,
apenwarr/redo almost certainly will be spending most of its time in
sqlite, which is a potentially good argument for doing something more
custom. But it's worth verifying that theory before I charge ahead :)
> Note that this is not representative of real-world programs … I suggest
> to use the game “Liberation Circuit”, which can be built with redo (and
> in fact, the Make and CMake builds have various issues) for benchmarks,
> as I think it has a typical “diamond” C / C++ project dependency graph.
> > I nevertheless agree that a C version of redo-ifchange is likely to
> > run 10-20x faster than python, which is desirable if only for bragging
> > purposes.
>
> This not only is premature optimization, but makes a C compiler a build
> dependency. I guess you could try, but I have yet to see a redo project
> where the parts of redo you could redo (ha!) in C were the bottlenecks.
in compiled programs (for whatever reason), and to reduce
dependencies. A pure-C, no-sqlite redo would be suitable for
bootstrapping an OS, for example, while a python/sqlite based one is
less appropriate. An sh version is also good here.
> Would a proper benchmark involve the use of “time -v” or “strace -cf”?
time taken, for obvious reasons. If we want to compare
implementations, the overall time measurement is what wins the
argument.
When I want to actually start optimizing, I need to figure out what
causes it to be so slow, which means other techniques are needed. I
rarely use strace for this purpose because most of the time I'm not
bounded by syscalls; once I get the rest of the slowness out of my
implementation, it's almost certain that stat(2) calls will be the
bottleneck for large builds. But I don't think we're there yet.
That said, the bottlenecks in apenwarr/redo are mostly *surrounding*
stat calls. That is, we call stat(2) and then do a bunch of crap,
including updating an sqlite database. So when I try to optimize by
"doing less stat() calls" I am actually eliminating many iterations of
that expensive code, not just stat(2) itself. The same is true of
your sh implementation, I'm sure, including the fork-exec overhead
parts of calling stat(1), maintaining dependency data structures, etc.
Have fun,
Avery
Prakhar Goel
Oct 28, 2018, 8:35:43 PM10/28/18
to Avery Pennarun, Nils Dagsson Moskopp, Tharre, redo...@googlegroups.com
On Sun, Oct 28, 2018 at 7:43 PM Avery Pennarun <apen...@gmail.com> wrote:
>
> The idea is that you can't detect that you *do* need to recheck
> dependencies that might have changed during a run; the only way to
> detect that is to do the check, so optimization would be impossible.
Nah. You don't even lose that (consistent deps) because you never had
>
> The idea is that you can't detect that you *do* need to recheck
> dependencies that might have changed during a run; the only way to
> detect that is to do the check, so optimization would be impossible.
it in the first place. If files are changing _during_ a run then there
is no even theoretically correct way of getting repeatable outputs and
especially not with trying some hackery with making redo-ifchange redo
a pile of work. What we really want is some way of ensuring that redo
always sees a static state of the world. Then we can have it give us
build outputs consistent with that state of the world and if the user
wants to update for a new state of the world, he can run redo again
with the new static state of the world. Given that FSs aren't even
transactional, this is an unachievable goal. The only hope here is to
make the user responsible for ensuring that the state that their build
depends on is static enough. In this case, assuming deps do not need
to be re-checked is perfectly reasonable.
The one other case that Nils has brought up many times is when a part
of the build modifies a file on the fly (that other parts of the build
depend on). This means that the specific order of build commands
matters. do scripts can no longer be black boxes. It no longer
suffices to do any sort of incremental building because the system
can't be sure what "up-to-date" even means. It is sheer insanity.
Summary: redo-recheck is a non-solution to a problem that shouldn't
exist in the first place. A build where dependencies can change while
the build is in progress implies either that the build setup is broken
or that the user has failed to hide the dynamism of the outside world
well enough in which case trying to maintain a little bit of
consistency (by not re-running on redo-ifchange) can only help.
Keeping up with new changes _dynamically_ without any user calls is
not within redo's purview (as currently designed). It is something
that needs to be handled by a separate component (even if it is just a
shell scripts that calls redo in a loop).
Avery, if you do want to add a new command, add in redo-watch that
execs a program whenever some dependencies do change and exists
outside the usual redo run-time. Inotify can be used to watch most
deps and redo-always deps can be handled by specifying a checking
frequency.
-- PG
Avery Pennarun
Oct 28, 2018, 10:02:37 PM10/28/18
to Prakhar Goel, Nils Dagsson Moskopp, tha...@gmail.com, redo
On Sun, Oct 28, 2018 at 8:35 PM Prakhar Goel <newt...@gmail.com> wrote:
> On Sun, Oct 28, 2018 at 7:43 PM Avery Pennarun <apen...@gmail.com> wrote:
> > The idea is that you can't detect that you *do* need to recheck
> > dependencies that might have changed during a run; the only way to
> > detect that is to do the check, so optimization would be impossible.
>
> Nah. You don't even lose that (consistent deps) because you never had
> it in the first place. If files are changing _during_ a run then there
> is no even theoretically correct way of getting repeatable outputs and
> especially not with trying some hackery with making redo-ifchange redo
> a pile of work. What we really want is some way of ensuring that redo
> always sees a static state of the world. Then we can have it give us
> build outputs consistent with that state of the world and if the user
> wants to update for a new state of the world, he can run redo again
> with the new static state of the world. Given that FSs aren't even
> transactional, this is an unachievable goal.
Well, you actually could do it with something like btrfs snapshots,
> On Sun, Oct 28, 2018 at 7:43 PM Avery Pennarun <apen...@gmail.com> wrote:
> > The idea is that you can't detect that you *do* need to recheck
> > dependencies that might have changed during a run; the only way to
> > detect that is to do the check, so optimization would be impossible.
>
> Nah. You don't even lose that (consistent deps) because you never had
> it in the first place. If files are changing _during_ a run then there
> is no even theoretically correct way of getting repeatable outputs and
> especially not with trying some hackery with making redo-ifchange redo
> a pile of work. What we really want is some way of ensuring that redo
> always sees a static state of the world. Then we can have it give us
> build outputs consistent with that state of the world and if the user
> wants to update for a new state of the world, he can run redo again
> with the new static state of the world. Given that FSs aren't even
> transactional, this is an unachievable goal.
but it's true, I was glossing over that point. Nevertheless, running
redo-always targets more than once per build *creates* this situation,
even if the user is *not* changing stuff from outside redo.
> The only hope here is to
> make the user responsible for ensuring that the state that their build
> depends on is static enough. In this case, assuming deps do not need
> to be re-checked is perfectly reasonable.
anything is *now* out of date, and decide what to do about it.
redo-ood does this.
> Summary: redo-recheck is a non-solution to a problem that shouldn't
> exist in the first place. A build where dependencies can change while
> the build is in progress implies either that the build setup is broken
> or that the user has failed to hide the dynamism of the outside world
> well enough in which case trying to maintain a little bit of
> consistency (by not re-running on redo-ifchange) can only help.
> Keeping up with new changes _dynamically_ without any user calls is
> not within redo's purview (as currently designed). It is something
> that needs to be handled by a separate component (even if it is just a
> shell scripts that calls redo in a loop).
long-running .do file that happens to run 'redo X' for various various
values of X, at various times, and may redo X more than once. When
the 'redo X' subprocess does redo-ifchange, then in some cases, we
*do* want to re-check all the dependencies of X. The obvious case is
a file watcher, but there are other cases I can imagine, like an
autobuilder. I'm not sure why those would be .do scripts instead of
normal sh scripts, but I have a feeling that sooner or later the
situation of a long-running .do script will arise.
A very specific problem case is in apenwarr/redo's current unit tests,
which already contain numerous calls to ../flush-cache, a custom hacky
shell script that zaps the redo state cache, so that redo-ifchange
will actually recheck things after we make a change. Arguably, redo's
unit tests could run from a shell script instead of a .do script, and
then you'd run ./test.sh instead of 'redo test', but that's not what
people expect. It would be nice to replace flush-cache with something
official, especially because we'd like those tests to be able to run
on any version of redo. Right now they depend on an internal detail
of my implementation.
> Avery, if you do want to add a new command, add in redo-watch that
> execs a program whenever some dependencies do change and exists
> outside the usual redo run-time. Inotify can be used to watch most
> deps and redo-always deps can be handled by specifying a checking
> frequency.
belongs in redo itself. It seems like this is pretty easy to write
using a small shell script and the existing redo API, for example:
while sleep 1; do redo-ood | xargs redo-ifchange; done
...and then replace "sleep" with your favourite magic incantation for
your OS-specific file watching tool.
It seems to me that we should try to keep the redo API down to the
bare minimum needed to provide all the "necessary" semantics.
Clearing the cache seems to be necessary in a few cases, and in redo
implementations without a cache, is easy to implement as just
/bin/true. A file watcher seems like can exist outside the system
without any special knowledge.
(Even redo-ood might be overkill. If you're monitoring source file
changes, you probably know which targets you want to follow anyway.
You could just run 'redo-ifchange all' or something.)
Have fun,
Avery
Avery Pennarun
Oct 29, 2018, 2:04:14 AM10/29/18
to Nils Dagsson Moskopp, redo
On Mon, Oct 1, 2018 at 2:09 PM Nils Dagsson Moskopp
<ni...@dieweltistgarnichtso.net> wrote:
> I have a test suite you can clone with Git with the following command:
> git clone http://daten.dieweltistgarnichtso.net/src/redo-testcases.git
I finally had a chance to look at your test suite tonight. It seems
<ni...@dieweltistgarnichtso.net> wrote:
> I have a test suite you can clone with Git with the following command:
> git clone http://daten.dieweltistgarnichtso.net/src/redo-testcases.git
like a good set of tests, especially since it exposes several API
incompatibilities between apenwarr/redo and your redo-sh package.
Here are the notes I took while running it:
- #!/bin/sh in a .do script forces the use of /bin/sh, which on some
systems is a not-very-posixy shell. apenwarr/redo goes out of its way
to pick a "good" default shell, so it's nice to leave this out. Also,
when no #! line is specified, apenwarr/redo can pass -x and -v options
to the shell automatically, which is really handy for debugging.
- The root-level all.do does "(cd $dir && redo)", presuming that this
will be equivalent to 'redo all'. However, apenwarr/redo intentionally
does not add the implicit "all" when run as a subprocess of a toplevel
redo. That's so things like "echo $deps | xargs redo" won't go crazy
if there are no deps. That makes the test suite not run; to fix it,
just change it to 'redo all' in all.do.
- Also in the toplevel all.do, it seems like it should be fine to
simply "redo $dir/all" rather than make a subshell and cd by hand.
- The tests print FAIL but still exit 0, so even if tests fail, 'redo
all' returns true. This seems non-optimal.
- In the "basename" test, it seems to be testing that "redo
directory/target.xyz" will cd to "directory" and then redo target.xyz.
This is different from apenwarr/redo, which always does a cd to the
.do file directory, not the directory of the target. That's
intentional: if a given .do file provides, say, relative paths for -I
and -L options to a C compiler, this makes it so the relative paths
can be the same regardless of how deep your source files are in the
directory hierarchy.
- In the dofile-in-python test, the run() calls need close_fds=False,
or they interfere with file descriptors needed by parallel make /
parallel redo. (Luckily my redo implementation prints a fairly
helpful warning about this.)
- The "parallel" test always fails if you aren't doing a parallel
build (which I guess is the point). However, if you run it a second
time, it passes, having already generated its dependencies.
- The "always" test fails as expected, for the reasons we've been
discussing in other threads.
- The "stamp" test seems just wrong: c.do doesn't redo-always, so
there's no reason two subsequent calls to "redo-ifchange c" should
return different values.
- There are no .gitignore files, which clutters the 'git status' output.
I've pushed fixes for most (not all) of these to the branch
'redo-testcases' branch of my redo repo:
https://github.com/apenwarr/redo (branch 'redo-testcases')
Thanks for working on this! If we can get both our redo
implementations to pass this test suite, it'll be a pretty good sign
that they're aligned.
I'd also like to make it so your implementation can pass my
apenwarr/redo tests. We're probably not very far from that, except
that my flush-cache script makes assumptions about the .redo database
that aren't applicable in other redo implementations.
Have fun,
Avery
Reply all
Reply to author
Forward
0 new messages