Re: [creduce-dev] Making creduce more parallel

[Nick Fitzgerald <fitzgen@gmail.com>]

Thanks for the reply, John!

> As I was saying, some randomness will need to be integrated into the
> passes to reduce the likelihood of conflicts.  The passes aren't
> really geared for that so that'll take a bit of thought.

Yep, the whole idea hinges on conflicts being rare enough (and
interestingness being preserved across merges enough) that attempting
merges ultimately pays off. Therefore, reducing conflicts is
important.

How are the passes / reducers structured right now? If we can generate
all of a pass's potential reductions up front, then they can be
inserted into the queue in a random order to reduce the likelihood of
conflicts. If the passes don't separate generating a potential
reduction from testing it, then we may need to refactor more.

> My intuition is that git/hg would eat a lot of performance but I
> could be wrong.  It would certainly be amusing if C-Reduce ended up
> being a small pile of git hooks :).

At least in my case, I suspect that git's cost would dominated by my
interestingness test. I agree that it is something we need to keep an
eye on and evaluate.

> The thing that I'm proudest of in the C-Reduce implementation is the
> modularity.  The core is just not that complicated, most of the good
> stuff lives in passes that can be thought of as purely functional.
> So the structure does lend itself to the kind of experimentation
> you're talking about.

I noticed (and appreciate) this!

> Anyhow take a look at Moritz's implementation too:

Will do.

> What IPC mechanism do you have in mind for the work queue?

I was imagining that the "orchestrator" process would spawn worker
threads that spawn-and-wait on interestingness processes and use
CSP-style channels to comminucate with the main thread that owns the
queue. This would leverage the modularity of passes that
generate potential reductions and of the interesting test.

Something like this diagram:
https://gist.githubusercontent.com/fitzgen/bf1acdc6dad217f2ed5accbabce9cf73/raw/981bff47be0f818e69041908eb63035fabb4e25a/orchestrator-diagram.txt

I was planning on prototyping in Rust, which has channels in its
standard library. Python's `queue.Queue` should also be able to handle
the job.

If you have other suggestions, I am all ears.