Re: Dependency-based running of collection scripts
Raphael Geissert <atomo64+debian@gmail.com> writes:
> Russ Allbery wrote:
>> So, the algorithm is as follows: Start by finding all collection
>> scripts with no dependencies and start them all in parallel. As
>> those collection scripts finish, remove them from the graph. If that
>> removes the last dependency of a node, start that collection script.
> + If that removes the last dependency of a *check* script, start it *after*
> starting the other collection scripts in parallel.
Yeah, we could start running a check before all the collection scripts
have finished. But that shouldn't require anything different about the
basic logic, just the ability to start running the odd check here and
there while the collection scripts finish.
>> Continue until we've started all collection scripts, then wait for
>> all remaining ones to finish.
> And the word "wait" is the one I'm trying to eliminate. Simply waiting
> instead of doing something in the meanwhile is a waste of time.
Sure, that makes sense. We ideally should only have to wait if we're at
the point where everything else we could do is blocked on a process that
hasn't finished.
>> * Co-dependencies. But I don't understand what this is for. I think
>> the above does everything we need to do without having that concept.
>> Am I missing something here that makes this worthwhile to have going
>> forward?
> The idea of prioritising collection scripts in favour of check scripts
> requires a way to indicate that.
Why do we need to do that?
Checks are done in the main Lintian process. Collection scripts are
done in the background. If we've unblocked a check, the main Lintian
process can just go do all unblocked checks right away. When it comes
back, it can see if any collection scripts have finished and therefore
any more checks are unblocked.
> If take a look at the modified reap_collect_jobs you will see that the
> goal is to return as soon as a collection script is done, so that both
> collection and check scripts can be processed as soon as possible.
The set thing that I proposed will do the same thing for you, I think.
> Since lightweight check scripts don't require much information, they
> are pretty fast and thus they are pretty good candidates for the "do
> something instead of waiting" concept.
Yup.
>> Certainly, we'd want to restructure the above code to be
>> object-oriented and add some of the accessor functions like known,
>> but I'm not sure why we'd want the selected/selectable code or
>> codependencies and I think the code would end up being a lot shorter.
> selected() is atm unused, it is a simple complement that I though it
> would be nice to have. selectable() is the way to ask "what should I
> process now that am not already processing?."
But that's exactly what the next_nodes function in my example gives you.
>> It would be nice if there were some non-destructive way to do the
>> traversal,
> It is destructive mainly because it avoids a lot of extra code that
> would otherwise be needed.
Yeah, agreed. It would be nice, but I didn't see a way to do it either.
>> but failing that, just doing something like:
>> sub deep_copy {
>> my $this = shift;
>> if (not ref $this) {
>> return $this;
>> } elsif (ref $this eq "ARRAY") {
>> return [ map deep_copy($_), @$this ];
>> } elsif (ref $this eq "HASH") {
>> return {map { $_ => deep_copy($this->{$_}) } keys %$this };
>> } else {
>> die "unsupported type ", ref $this;
>> }
>> }
> Which sounds pretty much what Data::Dumper internally does (not to
> mention that it uses C code and therefore works at the lower level,
> which is faster.)
Yeah, but without the weird eval and the $VAR1 thing and whatnot, and
hence rather easier to understand. I suppose we should benchmark and
see if we lose anything.
>> # start a bunch of children storing PIDs in %children
>> while (%children) {
>> my $child = wait;
> The problem I see here is that we are again 'wait'ing, which in other
> words means: blocking.
It will only block if no children are finished, which is the one case
where we *do* have to block because we can't do anything else.
In other words, the algorithm that I propose is this:
1. Kick off all dependency-free collect scripts (eventually, this will
start with unpack scripts).
2. wait for a collect script to finish. We have no checks we can do
without any results of at least an unpack script, so this doesn't
delay us any more than we have to be delayed. (If we ever did have
any, we could do them right away.)
3. See if the completed collect script frees us to run any more collect
scripts. If so, kick them all off.
4. See if the completed collect script unblocks any checks. If so, run
them all in the main lintian process.
5. Go to 2.
I think this is minimal -- you never wait when you could be doing
something. But you can't implement this with IPC::Run without calling
reap_nb on every outstanding object each time, which is less efficient
and (more importantly) harder to follow.
--
Russ Allbery (rra@debian.org) <http://www.eyrie.org/~eagle/>
Reply to: