[ANN] Drake: Distributed Rake

[quixoticsycophant]

= DRAKE -- Distributed Rake

A branch of Rake supporting parallel task execution.

== Synopsis

Run up to three tasks in parallel:

% drake -j3

or equivalently,

% drake --threads 3

== Installation

% gem install drake

== Notes

=== Compatibility

Drake is 100% compatible with Rake. The code path for --threads=1 is
effectively identical to that of Rake's. Drake passes all of Rake's
unit tests, with any number of threads from 1 to 1000 (that's the most
I tested).

=== Dependencies

In a given Rakefile, it is possible (even likely) that the dependency
tree has not been properly defined. Consider

task :a => [:x, :y, :z]

With single-threaded Rake, _x_,_y_,_z_ will be invoked *in that order*
before _a_ is invoked. However with drake --threads=N (for N > 1),
one should not expect any particular order of execution. Since there
is no dependency specified between _x_,_y_,_z_ above, Drake is free to
run them in any order.

If you wish _x_,_y_,_z_ to be invoked sequentially, then write

task :a => seq[:x, :y, :z]

This is shorthand for

task :a => :z
task :z => :y
task :y => :x

Upon invoking _a_, the above rules say: "Can't do _a_ until _z_ is
complete; can't do _z_ until _y_ is complete; can't do _y_ until _x_
is complete; therefore do _x_." In this fashion the sequence
_x_,_y_,_z_ is enforced.

The problem of insufficient dependencies plagues Makefiles as well.
Package maintainers affectionately call it "not j-safe."

=== MultiTask

The use of +multitask+ is deprecated. Tasks which may properly be run
in parallel will be run in parallel; those which cannot, will not. It
is not the user's job to decide.

Drake's +multitask+ is an alias of +task+.

=== Task#invoke inside Task#invoke

Parallelizing code means surrendering control over the
micro-management of its execution. Manually invoking tasks inside
other tasks is rather contrary to this notion, throwing a monkey
wrench into the system. An exception will be raised when this is
attempted in non-single-threaded mode.

== Links

* Download: * http://rubyforge.org/frs/?group_id=6530
* Rubyforge home: http://rubyforge.org/projects/drake
* Repository: http://github.com/quix/rake

== Author

* James M. Lawrence <[email protected]>

 

[David Masover]

My first reaction was, "So hows is this different than Rake again? Rake has
multitask..."

=== MultiTask

The use of +multitask+ is deprecated. Tasks which may properly be run
in parallel will be run in parallel; those which cannot, will not. It
is not the user's job to decide.

Drake's +multitask+ is an alias of +task+.

Aha.

So what do you do with things which aren't thread-save? Or "j-safe"?

And how is this different than running Rake with 'task' set to an alias
of 'multitask'?

 

[quixoticsycophant]

So what do you do with things which aren't thread-save? Or "j-safe"?

The same thing you do with a Makefile that isn't j-safe: (1) write the
dependencies correctly, which makes it j-safe, or (2) don't run it
with -j.

And how is this different than running Rake with 'task' set to an alias
of 'multitask'?

If 'task' became 'multitask', Rake would run all your tasks at once --
all at the same time. That's probably not what you want

Thinking in terms of parallel execution has a little learning curve.
It's certainly a not a natural transition coming from single-threaded
thinking.

Incidentally there is a good litmus test for determining whether you
get the gist of parallelism: once it becomes obvious that 'multitask'
is a mistake, then you probably get it. The dependency graph tells us
what can be run in parallel and what can't. It's a math problem.
'multitask' stomps it all to pieces, having the power to declare 2 + 5
= 8 if it so chooses.

My advice for Rakefile writers is to incrementally move toward -j
correctness. Start with the bottom tasks first (those executed last)
and work your way up, testing each new task subtree.

Regards,
J

 

[quixoticsycophant]

I forgot to mention that there is a good reason for the gem-only
release. Despite outward appearances, Drake is internally the same as
Rake, down to using the same file names and top-level module named
'Rake'. This is to make a mainline merge easier, if Jim decides to do
so. (The fork stems from the latest Rake repository.)

Since Rubygems installs each gem in separate directory, it it safe to
have Rake and Drake installed at the same time. However if you bypass
gems by executing drake's install.rb, your rake will be the parallized
one.

I also forgot to thank Jim, who transitioned to github in order to
help me do this.

Thanks--
J

 

[Jos Backus]

Does Drake properly clean up its children if it is aborted with SIGINT? ISTR
multitask in rake leaving orphans running.

 

[David Masover]

The same thing you do with a Makefile that isn't j-safe: (1) write the
dependencies correctly, which makes it j-safe, or (2) don't run it
with -j.

Still going to be a fair number of cases of (3), I imagine: use locks to
synchronize non-thread-safe libraries, for which there's still a benefit to
running those tasks in parallel.

If 'task' became 'multitask', Rake would run all your tasks at once --
all at the same time. That's probably not what you want

Actually, no, I assumed that 'multitask' only ran that specific task in
parallel.

Actually, I hadn't thought about it thoroughly enough to realize that this
wasn't what was happening:

The dependency graph tells us
what can be run in parallel and what can't.

I understand make -j, and I think I understand the difference with
multitask -- if I understand it:

multitask :foo ...
multitask :bar ...

In the above example, will everything really run concurrently? I'd assumed
that foo would run concurrently, and then bar would run concurrently.

In either case, I see what Drake is doing (real make -j behavior). Thanks for
explaining this -- it looks cool!


One more thing: I'm not sure what the best way to do this is, but I think it
would still be useful to have the task/multitask dichotomy, for legacy
programs. Multitasks would operate as properly parallized Drake tasks. Plain
old tasks would run in complete isolation, with the exception that if they
invoke a multitask, that multitask (and all its remaining dependencies) run
in j-parallized mode.

That would certainly break the purity of it, and it would be a bit more work,
but I think it could be made to work. The benefit is, you could translate an
existing project iteratively, without having to verify that the whole thing
is correct, first.

 

[Trans]

In a given Rakefile, it is possible (even likely) that the dependency
tree has not been properly defined. =A0Consider

=A0 =A0task :a =3D> [:x, :y, :z]

With single-threaded Rake, _x_,_y_,_z_ will be invoked *in that order*
before _a_ is invoked. =A0However with drake --threads=3DN (for N > 1),
one should not expect any particular order of execution. =A0Since there
is no dependency specified between _x_,_y_,_z_ above, Drake is free to
run them in any order.

If you wish _x_,_y_,_z_ to be invoked sequentially, then write

=A0 =A0task :a =3D> seq[:x, :y, :z]

This is shorthand for

=A0 =A0task :a =3D> :z
=A0 =A0task :z =3D> :y
=A0 =A0task :y =3D> :x

Upon invoking _a_, the above rules say: "Can't do _a_ until _z_ is
complete; can't do _z_ until _y_ is complete; can't do _y_ until _x_
is complete; therefore do _x_." =A0In this fashion the sequence
_x_,_y_,_z_ is enforced.

The problem of insufficient dependencies plagues Makefiles as well.
Package maintainers affectionately call it "not j-safe."

Hmmm.... this is not backward compatible. Things could go very badly
if I tried -j3 on my "badly" written Rakefiles.

May I make a suggestion? Have

task :a =3D> [:x, :y, :z]

translate into the task :a =3D> :z =3D> :y =3D> :x thing. And then

task :a =3D> [[:x, :y, :z]]

Run in parrallel.

That way all old script work fine, and as we get smart and make our
tasks j-safe we can add the extra "j-array".

And besides it sort of looks like parallel marks || x ||

Other than this one thing, I say very nice work.

T.

 

[Anton Ivanov]

== Installation

% gem install drake

% gem install drake
Successfully installed drake-0.8.1.11.0.1

% which drake
drake not found

 

[Anton Ivanov]

% gem install drake
Successfully installed drake-0.8.1.11.0.1

% which drake
drake not found

% sudo chmod +x /var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake
% /var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake -j2
/var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake: invalid option -- j
% /var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake --threads 2
/var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake: unrecognized option
`--threads'

 

[.]

Still going to be a fair number of cases of (3), I imagine: use
locks to synchronize non-thread-safe libraries, for which there's
still a benefit to running those tasks in parallel.

If by "non-thread-safe libraries" you mean a library whose Rakefile is
not j-safe, then you would just run it without -j. If it is a library
inside a larger project, you have at least two options:

(a) Run single-threaded rake in a subprocess for that library.

(b) Use the Rake module directly, as the unit tests do. The
no-invoke-inside-invoke rule applies per TaskManager, so you could
create a new TaskManager and do whatever you wish with it.

Keep in mind this is supposed to be stop-gap as you wait for the
author of the Rakefile in question to write the dependencies
correctly.

Actually, no, I assumed that 'multitask' only ran that specific task
in parallel.

Actually, I hadn't thought about it thoroughly enough to realize
that this wasn't what was happening:


I understand make -j, and I think I understand the difference with
multitask -- if I understand it:

multitask :foo ...
multitask :bar ...

In the above example, will everything really run concurrently? I'd
assumed that foo would run concurrently, and then bar would run
concurrently.

When I mentioned that multitask is an alias of task, you asked about
the converse: what if task is an alias of multitask? multitask
blindly executes all its prereqs at once, in parallel, one task per
thread. So if everything is a multitask, applying the rule
recursively, all tasks run at once.

Getting back to your question, your code

multitask :foo ...
multitask :bar ...

does not say "do foo, then do bar" (whether it's a task or a multitask
is not relevant). The code is only defining the dependency relations
and the tasks associated with each node, to be executed later. If foo
lists bar as a prereq, then bar will run before foo.

In either case, I see what Drake is doing (real make -j
behavior). Thanks for explaining this -- it looks cool!

One more thing: I'm not sure what the best way to do this is, but I
think it would still be useful to have the task/multitask dichotomy,
for legacy programs. Multitasks would operate as properly parallized
Drake tasks. Plain old tasks would run in complete isolation, with
the exception that if they invoke a multitask, that multitask (and
all its remaining dependencies) run in j-parallized mode.

I had anticipated the suggestion that 'multitask' enable parallelism.
It cannot solve the problem. See my other post on superstructures
around the graph concept.

As I mentioned, drake is 100% compatible with rake for -j1, the
default behavior. The only thing we lose is the speedup for a -j1
multitask, which is recovered (and then some) once the dependencies
are written correctly and -jN may be run.

I don't think it is too much to ask: in exchange for fixing your
dependency logic, your build times will divided by N (best case) for
an N-core machine. If you don't fix it, then expect a little slowdown
if you were using multitask for something nontrival. That situation
seems rare enough, and harmless enough, to not worry much about.

Also, do we really want to create elaborate special cases, introducing
bugs and complexity, just to save someone a few moments (perhaps
nothing) during a build? Especially considering this is being done in
order to allow the person to retain the logic errors in his code?

That would certainly break the purity of it, and it would be a bit
more work, but I think it could be made to work. The benefit is, you
could translate an existing project iteratively, without having to
verify that the whole thing is correct, first.

You can already translate it piecemeal, if that is what you meant by
iteratively. It simply requires testing the bottom-level tasks
individually and working your way up. When I explained this
previously, I mistakenly said bottom-level-last-executed. I meant the
opposite, of course -- bottom level (most-depended-upon) is executed
first.

 

[.]

There is a mathematical reality we cannot avoid, from which
special-case syntax and backwards-compatibility acrobatics cannot save
us. The problem is in our thinking. We didn't specify what depends
on what. We thought we did, but it turns out we were fooling
ourselves all along.

The dependency graph is at root a clear and simple concept. Defining
node relations is also clear and simple:

task :a => :b

Child nodes are on the left, pointing to parent nodes on the right.
Task a depends on task b. Clear. Simple. Now, are we certain that
we want to create a superstructure around this concept, and if so,
what exactly will it be?

Trans suggested that this

task :a => [:x, :y, :z]

should be translated into this

task :a => :z
task :z => :y
task :y => :x

while this

task :a => [[:x, :y, :z]]

is translated into this

task :a => :x
task :a => :y
task :a => :z

OK, but there are a million ways in which a programmer can
insufficiently define dependencies. This will not come close to
saving us. Let's take just one scenario from this example.

Nodes x,y,z are added *in that order* to the parent a (excuse me for
speaking in graph terms). We can still be accidentally depending on
that. The problem in our thinking is not solved.

Do we want

task :a => :x
task :a => :y
task :a => :z

to be equivalent to

task :a => :z
task :a => :x
task :a => :y

Yes or no? If a programmer wants them to mean different things, how
shall we accommodate him?

Again I am taken back to the cold, hard, mathematical reality of the
graph. We must think carefully about whether it actually represents
the necessary relations. Nothing can do this for us, not tricks of
grammar or syntax, which may even obscure the relations.

There is already a historical precedent with Makefiles. A new syntax
could have been added to Makefiles, but none was. The Makefiles had
bugs, but instead of timidly skirting around the problems while
praising the gods of backwards compatibility, people faced them
head-on, solving them one at at time. It is my hope that rubyists
will do the same.

While I endeavor to keep an open mind, I am not entirely convinced
that everyone clearly sees what the problem is (I am speaking of the
various conversations I've had about parallelism, not here
specifically). The problem is not obvious at all. It requires some
reflection. I understand the value of backwards compatibility, which
is why drake==rake for -j1. In this circumstance, however, it appears
to me that the answer is forced upon us by the sheer mathematics of
the situation.

 

[Martin DeMello]

Do we want

task :a => :x
task :a => :y
task :a => :z

to be equivalent to

task :a => :z
task :a => :x
task :a => :y

Yes or no? If a programmer wants them to mean different things, how
shall we accommodate him?

Yes! If you want it differently, you write in the ordering explicitly

task :a => :z
task :z => :y
task :y => :x

You have no reason to expect one operation to come before another if
there is not an explicit dependency chain between them

martin

 

[.]

Yes! If you want it differently, you write in the ordering explicitly

task :a => :z
task :z => :y
task :y => :x

You have no reason to expect one operation to come before another if
there is not an explicit dependency chain between them

martin

Yes, however my point was that if we agree this

task :a => :x
task :a => :y
task :a => :z

should be equivalent to this

task :a => :z
task :a => :x
task :a => :y

(and I should hope we all agree), then there is nothing which can save
us. We are forced to write our Rakefiles correctly. No backwards
compatibility mode is possible for threads>1.

JL

 

[Martin DeMello]

(and I should hope we all agree), then there is nothing which can save
us. We are forced to write our Rakefiles correctly. No backwards
compatibility mode is possible for threads>1.

A --file-order-implies-dependency flag might get us there in a lot of
cases, though of course there's no general solution. Of more value
would be a lint tool that helps convert a rakefile into parallelisable
form.

martin

 

[.]

Does Drake properly clean up its children if it is aborted with SIGINT? ISTR
multitask in rake leaving orphans running.

Can you construct a test case? The process table is clean after I hit
ctrl-c during drake -j100 on this

100.times { |i|
name = i.to_s.to_sym
task name do
fork {
loop { }
}
end
task :default => name
}

 

[Trans]

In a given Rakefile, it is possible (even likely) that the dependency
tree has not been properly defined. =A0Consider

=A0 =A0task :a =3D> [:x, :y, :z]

With single-threaded Rake, _x_,_y_,_z_ will be invoked *in that order*
before _a_ is invoked. =A0However with drake --threads=3DN (for N > 1),
one should not expect any particular order of execution. =A0Since there
is no dependency specified between _x_,_y_,_z_ above, Drake is free to
run them in any order.

If you wish _x_,_y_,_z_ to be invoked sequentially, then write

=A0 =A0task :a =3D> seq[:x, :y, :z]

This is shorthand for

=A0 =A0task :a =3D> :z
=A0 =A0task :z =3D> :y
=A0 =A0task :y =3D> :x

Upon invoking _a_, the above rules say: "Can't do _a_ until _z_ is
complete; can't do _z_ until _y_ is complete; can't do _y_ until _x_
is complete; therefore do _x_." =A0In this fashion the sequence
_x_,_y_,_z_ is enforced.

The problem of insufficient dependencies plagues Makefiles as well.
Package maintainers affectionately call it "not j-safe."

Hmmm.... this is not backward compatible. Things could go very badly
if I tried -j3 on my "badly" written Rakefiles.

May I make a suggestion? Have

=A0 =A0 task :a =3D> [:x, :y, :z]

translate into the task :a =3D> :z =3D> :y =3D> :x thing. And then

=A0 =A0 task :a =3D> [[:x, :y, :z]]

Run in parrallel.

That way all old script work fine, and as we get smart and make our
tasks j-safe we can add the extra "j-array".

I thought someone else might notice it and elaborate but there is
another potential benefit of this notation. Eg.

task :a =3D> [[:x, :y, :z], [:m, :n], :r]

Where :x, :y, :z can be run in parallel, as can :m and :n, but the
groups must run one before the other.

T.

 

[Jos Backus]

I'm misremembering. SIGINT seems to work okay, it's SIGTERM that leaves
orphaned children (with ppid 1) around with rake, presumably because it
doesn't catch that signal. Same with drake (0.8.1.11.0.1)

Can you construct a test case? The process table is clean after I hit
ctrl-c during drake -j100 on this

100.times { |i|
name = i.to_s.to_sym
task name do
fork {
loop { }
}
end
task :default => name
}

Thanks, I tried `drake &' folllowed by `kill $!' (using bash) and the forked
drake children revert from ppid $! to ppid 1. A `killall drake' is required to
clean up.

 

[.]

% sudo chmod +x /var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake
% /var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake -j2
/var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake: invalid option -- j
% /var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake --threads 2
/var/lib/gems/1.8/gems/drake-0.8.1.11.0.1/bin/drake: unrecognized option
`--threads'

It must be pulling the old rake libs. In all my tests the gem has won
the $LOAD_PATH order. It is easy to check,

task :default do
puts $LOAD_PATH
end

% rake
/usr/local/stow/ruby-1.8.7-p72/lib/ruby/gems/1.8/gems/rake-0.8.1/bin
/usr/local/stow/ruby-1.8.7-p72/lib/ruby/gems/1.8/gems/rake-0.8.1/lib
[...]

% drake
/usr/local/stow/ruby-1.8.7-p72/lib/ruby/gems/1.8/gems/
drake-0.8.1.11.0.1/bin
/usr/local/stow/ruby-1.8.7-p72/lib/ruby/gems/1.8/gems/
drake-0.8.1.11.0.1/lib
[...]

What does yours say? Maybe your RUBYLIB environment var is pointing
at a lib directory containing the old rake.rb?

 

[.]

A --file-order-implies-dependency flag might get us there in a lot of
cases, though of course there's no general solution. Of more value
would be a lint tool that helps convert a rakefile into parallelisable
form.

martin

But I thought we just agreed those two forms should be the same? Now
you are proposing a flag which will make them different.

I think you're missing the larger point, which is that there are still
a million ways to make a mistake with the dependency graph. Your flag
will not come close to saving us.

A tool which analyzes our code and outputs what we meant to write
would be great. But until that glorious technology arrives, tools
will continue to operate on the principle of garbage-in, garbage-out.
As I've unsuccessfully explained in this thread, the problem lies in
our mistakes in thinking.

It seems to me the general solution is to not use -j until you've got
all your ducks in a row.

JL

 

[Martin DeMello]

But I thought we just agreed those two forms should be the same? Now
you are proposing a flag which will make them different.

They *should* be the same, but if we're discussing legacy rakefiles
where people have implicitly relied on their being different...

I agree that there's really no 'right' thing to do, though - either
you've specified your depgraph properly or you haven't.

martin