Dne 28.11.2014 v 18:55 Paolo Bonzini napsal(a):
On 28/11/2014 18:40, Paolo Bonzini wrote:
On 28/11/2014 09:00, Lukáš Doktor wrote:
The benefit is, that on complex trees you'd not need to check all hooks,
only the ones which applies for given test. The cons against your idea
(if I understood it correctly) is, that your version would remove
non-suitable variants during multiplexation, my version would execute
the test up to the point where it gets to the params.get(trouble_maker)
call (where it would generate the TestNAError).
So correct me if I'm wrong, but my impression is that for bigger trees
with lots of irrelevant hooks your variant can be actually slower. For
small trees without variants, they should be probably the same speed and
for big trees with relevant hooks yours should be faster (and generates
smaller report as it'd skip irrelevant tests).
I think we should avoid hooks as much as possible. If done right, the
BDD processing should be ridiculously cheap, on the order of O(tree size).
As an example, the BDD for
~A | ~B &&
~A | ~C &&
~A | ~D &&
~B | ~C &&
~B | ~D &&
~C | ~D &&
A | B | C | D
(i.e. exactly one of A, B, C, D is 1) is as simple as
A
/ |
B B
/ |/ |
| C C
|/ | /|
| D D
|/ \ | \
False True False
(where left branch = variable is 1, right branch = variable is 0). This
means that a formula with n(n+1)/2-1 ORs and n(n-1)/2 ANDs is
represented by only 2n+1 nodes including the dummy True and False nodes.
All variants use different variables, so the total complexity of the
operations is roughly linear in the tree size.
Adding "A is the default" costs only two extra nodes:
expand?
/ |
A A
/ | / |
B B False
/ |/ |
| C C
|/ | /|
| D D
|/ \ | \
False True False
and you can do it in the library just by writing (if bdd1 is the
original bdd):
bdd1 = bdd1 & (expand | A)
Drawing BDDs for the formulas I have in my original message is a good
way to get familiar.
Paolo
Hi Paolo,
I tried but I'm still far away from understanding it. Right now I'm
finishing the yaml utils and multiple file support. Now I'm going to
implement the mux-choices and see how it behaves. Then I'll focus on the
default yaml sources (datadir, global, cmdline). When all this is done,
I'll take another look at your proposal an we'll see what I can do about it.
Additionally I'd like to create a tool to convert autotest config to
yaml (at least partial at first), which should help us identify
potential problems and additional requirements.
Thank you for all the ideas and advises,
Lukáš
_______________________________________________
Virt-test-devel mailing list
[email protected]
https://www.redhat.com/mailman/listinfo/virt-test-devel
