Skip to contentSkip to conversation

searching patch space (linear->bushy revisions)

DISCUSSION Tom Lord 1 participant 1 message Feb 1, 2002

lore
Share & tools
lore

Tom Lord

author
#0 lore raw

[Please CC me on replies]

Suppose two programmers each work on improving the performance of the scheduler. Each of them make a series of small, mostly independent changes, checking each set into a revision control system (`arch' in particular).

We then have two development paths:

	A1 -> A2 -> A3 -> A4 .... -> Am

	B1 -> B2 -> B3 -> B4 .... -> Bn

Now consider all non-empty subsets of the two development paths. These would include, for example:

	{A1, B3, A5, B6}

	{ B1 }

	....

There are (if I'm not doing my math too quickly):

		(2^(m + n) - 1)

subsets of patches.

For each subset of N patches, there are N! ways of ordering those patches. So, with no other information to narrow the choices, there are:

	       (m + n) * 1!
	    +  (2 choose (m + n)) * 2!
	    +  (3 choose (m + n)) * 3!
	    ...

ways in which we might pick a subset of the patches and apply them to a tree. If you remember your combinatorics, you can reduce that equation to:

"a very large number unless m and n are very small"

In the general case, some of those sequences of patches won't apply without conflicts. Some of them will result in the same final tree as others. Some final trees won't even compile. Of those that compile, some will have better performance than others.

Assuming all the patches meet other criteria, such as coding style, Linus' job is to find the optimal subset and sequence of patches according to some metric.

Linus has asked for a particular revision control feature that can help him search the space of patches: the ability to turn a linear sequence of patches into a bushy collection of patches by discovering which ones are orthogonal to the others.

If you use arch, discovering the bushiness of a linear sequence of patches can be done with a 5 line shell script: (use get' to build m' copies of the base revision, then use replay' to apply one of the Ax' patches to each tree, noting the exit status of replay to find out which patches apply cleanly).

You could extend such a shell script indefinitely: add additional criteria such as ``the final tree must be able to compile'', or recursively find all sequences of two or more patches, perhaps using an automated benchmark to prune or order the search.

`arch' is fun that way.

-t