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
_______________________________________________
Virt-test-devel mailing list
[email protected]
https://www.redhat.com/mailman/listinfo/virt-test-devel
