Support Parallel Builds

[MTecknology]

It'd be nice if ratt supported parallel builds... and even nicer if it also supported limiting number of processes available to sbuild. It seems like something with sync.WaitGroup would work well to support building up to X sbuilds.

I have a new server and an ambition to do efficient regression testing against a lot of packages and being able to efficiently abuse it would be helpful. :)

[stapelberg]

Agreed. Do you want to send a pull request? I don’t use ratt much currently, so it’d be better if you’d do it, I think :).

[MTecknology]

I'm not a good dev, don't really no golang all that well, and have a lot of time sensitive stuff going on for then next 3 months, but after that I can give it a go... maybe sooner if it seems less daunting? Is ratt checking subsequent reverse build deps? (build deps of build deps)

What seems exceptionally hard for me is that logic. If I have help with the logic to figure out when things can execute, I feel like I could build out the logic. Ideally, it'd just come in a dictionary of sets of batches that can run at the same time. Then it's just a matter of looping through each batch, making sure no more than X builds in each batch run at the same time, and popping bits off into goroutines to wait. That part seems like a day or two project that I could handle pretty easily.

[stapelberg]

Have a look at the code, it’s just 300 lines. https://github.com/Debian/ratt/blob/master/ratt.go#L261 is the place where we currently serially iterate through all identified reverse dependencies — the rdeps are known at that point, and won’t change. It should be simple to parallelize this.

[MTecknology]

If I were to just parallelize them at that point, then there would eventually be a race condition where one reverse build dep hasn't been built before another reverse build dep that depends on it has come up in the cycle. I couldn't follow the logic well enough to guess what would happen at that point.

This assumes we're recursively checking reverse build deps which... I don't see where that's happening. Please tell me it's happening... pretty please tell me I'm just that blind. :)

[stapelberg]

ratt (currently?) only builds direct reverse-dependencies (IIRC), not the transitive closure.

[MTecknology]

Is there any reason rebuild *ALL* the things shouldn't include traversing the tree? ;)

…

On Thu, 20 Apr 2017 01:56:57 -0700 Michael Stapelberg ***@***.***> wrote: ratt (currently?) only builds direct reverse-dependencies (IIRC), not the transitive closure.

-- Michael Lustfield

[stapelberg]

This wasn’t a conscious decision, rather the need never surfaced. At the point when ratt was written, the dependency trees for Go packages were quite flat. Extending ratt to work on the whole tree would be fine with me, but I can’t put in the engineering work right now.

[MTecknology]

"shouldn't" that was put there intentionally. I absolutely get why it didn't but I feel like it should. It is ALL, of course. :)

I'm okay building most of this but what I struggle with is the actual logic of building a dependency tree and building batches. Is there anyone you know of that could help with it? I don't even need help writing golang for it, I just need someone to help me with the logic behind coming up with build batches.

Honestly, if the race condition wasn't a concern and it was just a matter of max X builds at a time, I'd probably be able to finish it in an evening. Even knowing this doesn't support it, I just need help with the magical logic bits.

[stapelberg]

https://godoc.org/pault.ag/go/debian/control#OrderDSCForBuild might be useful: it does a topological sort using https://godoc.org/pault.ag/go/topsort to build packages in the correct order.

So, algorithmically speaking, I think you’d need to traverse the dependency graph in topological sort order. Does that help?

[MTecknology]

Yup, that's some shiny magic! It might take me a while to produce anything of value (anyone else up to the challenge is welcome!), but I think this seems pretty straight forward. -- Find all reverse build deps all the way up, the chain, find the magic order, start looping through and firing off up to X concurrent builds so long as the next build has no build depends on anything currently building. Then, adding an option to limit sbuild (is this something p/cowbuilder support) CPU's available would let you effectively tune builds to your personal stack. Is it really that simple or am I missing something?

[stapelberg]

Your description seems accurate to me.

[stapelberg]

FYI, I’m currently working on parallelizing ratt, not considering feeding build results into reverse-dependencies transitively for now.