[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re: [libvirt] [PATCH 1/6] Optimize the elements the iterator visits.



On 01/09/2012 07:05 PM, Eric Blake wrote:
On 12/09/2011 08:07 AM, Stefan Berger wrote:
In this patch we introduce testing whether the iterator points to a
unique set of entries that have not been seen before at one of the previous
iterations. The point is to eliminate duplicates and with that unnecessary
filtering rules by preventing identical filtering rules from being
instantiated.
Example with two lists:

list1 = [1,2,1]
list2 = [1,3,1]
Is this something that happens frequently in practice due to user input
(that is, does the user really output list elements more than once), or
something that happens more because of combinatorial combinations as you
expand user inputs into something more precise?  I guess I'd like to
know why such repetitions are likely to occur, although I can agree with
doing less firewall rules if we can determine that the rules are duplicates.

Fair question. It's an optimization that I would admit is not absolutely necessary, but reduces the number of rules that are being generated in case duplicates would occur. Doing this calculation upfront rather than having duplicate rules evaluated on possibly thousands of packets seems worth the effort. The algorithm is rather short but maybe not as efficient as it should be.

  /*
+ * Test whether the iterator entry points to a distinguished set of entries
+ * that have not been seen before at one of the previous iterations.
+ *
+ * The point of this function is to eliminate duplicates.
+ * Example with two lists:
+ *
+ * list1 = [1,2,1]
+ * list2 = [1,3,1]
+ *
+ * The 1st iteration would take the 1st items of each list ->  1,1
+ * The 2nd iteration would take the 2nd items of each list ->  2,3
+ * The 3rd iteration would take the 3rd items of each list ->  1,1 but
+ * skip them since this pair has already been encountered in the 1st iteration
+ */
+static bool
+virNWFilterVarCombIterEntryAreUniqueEntries(virNWFilterVarCombIterEntryPtr cie,
+                                            virNWFilterHashTablePtr hash)
+{
+    unsigned int i, j;
+    virNWFilterVarValuePtr varValue, tmp;
+    const char *value;
+
+    varValue = virHashLookup(hash->hashTable, cie->varNames[0]);
+
+    value = virNWFilterVarValueGetNthValue(varValue, cie->curValue);
+
+    for (i = 0; i<  cie->curValue; i++) {
+        if (STREQ(value, virNWFilterVarValueGetNthValue(varValue, i))) {
+            bool isSame = true;
This function is called in a loop over the list, and itself does a loop
over the list, making it a quadratic check for duplicates.  Am I correct
that lists can provided by the user with arbitrary lengths?

Each variable can have an number of elements >= 1, for example A=[10,20,30,20].

+            for (j = 1; j<  cie->nVarNames; j++) {
Furthermore, we add another layer of looping (this time over the number
of parallel lists being combined), for an overall cubic algorithm.  Is
the number of parallel lists that can be provided by the user arbitrary?

The number of lists depends on the number of variables that are provided in one rule. So, $A, $B, and $C in one rule in different fields like this one below has 3 different lists (where the iterators ('@<n>') only change the behaviour for how the instantiated rules are generated):

<rule action='accept' direction='out'>
<tcp srcipaddr='$A[ 1]' srcportstart='$B[ 2]' dstportstart='$C[ 3]'
           dscp='4'/>
</rule>

That is, I'm wondering if we need to start worrying about reducing
complexity, and coming up with an algorithm that isn't quite so brute
force so as not to take quite so long on arbitrary-length inputs.

In case of no duplicates in $A, we have a complexity of O(n) [optimal case] for checking of a single rule (only 'vertical' checking, no 'horizontal' checking)

In case $A has duplicates the complexity then becomes O(n^2) in the worst case since we do horizonal checking accross $B and $C as well.

I think the elements in $A for example would have to be sorted for faster detection of duplicates. A = [10,20,30,20] -> A = [10,20,20,30]. Now if I step on A[2], I would see that A[2-1] = A[2] and wouldn't have to look at A[0] at all. So that would be O[1]. But sorting the elements may alter their meaning in terms of the sequential processing of the rules. Got to think about this...

On the other hand, until someone actually demonstrates slow input, I'm
okay with making assumptions that most users won't be merging large
amounts of long parallel lists, and that the overhead of reducing
algorithmic complexity may cost more overhead than all expected use
cases just being brute-forced.  So I'm okay checking this in as-is,
until (and unless) we have performance numbers proving that we need to
be smarter.

OK.
@@ -414,10 +460,15 @@ virNWFilterVarCombIterNext(virNWFilterVa
      unsigned int i;

      for (i = 0; i<  ci->nIter; i++) {
+next:
          ci->iter[i].curValue++;
-        if (ci->iter[i].curValue<= ci->iter[i].maxValue)
+        if (ci->iter[i].curValue<= ci->iter[i].maxValue) {
+            if (!virNWFilterVarCombIterEntryAreUniqueEntries(
+&ci->iter[i], ci->hashTable)) {
+                goto next;
Why do we need a backwards goto, when a 'continue' would get to the same
location?

Using the goto we don't increase 'i' but only do ci->iter[i].curValue++, which is what is needed.


+            }
              break;
-        else
+        } else
              ci->iter[i].curValue = 0;
      }
Coding style - the else needs {} since you added {} for the if.
Fixed.

I think this is okay, but wait until I review the rest of the series to
see how it was used in context.

I'll wait. Thanks.

   Stefan


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]