yahoo-eng-team team mailing list archive

[Thierry Carrez <thierry.carrez+lp@xxxxxxxxx>]

** Changed in: quantum
       Status: Fix Committed => Fix Released

-- 
You received this bug notification because you are a member of Yahoo!
Engineering Team, which is subscribed to quantum.
https://bugs.launchpad.net/bugs/1092995

Title:
  Inefficient logic in _filters function of quantum.api.v2.base

Status in OpenStack Quantum (virtual network service):
  Fix Released

Bug description:
  The getall() of webobs MultiDict (which is request.GET) is implemented
  as:

  https://github.com/Pylons/webob/blob/master/webob/multidict.py

  def getall(self, key):
          """
          Return a list of all values matching the key (may be an empty list)
          """
          result = []
          for k, v in self._items:
              if key == k:
                  result.append(v)
          return result

  Therefore it iterates the entire key, val pair list to find all values for a key.
  So the original implementation is:
  O(keys) for "set(request.GET)" + O(unique(keys) * values) for "request.GET.getall()" for each unique key.
  Thus the complexity is O(unique(keys) * values)

  The complexity of my suggested method is O(values) for "request.GET.iteritems()" + O(unique(keys)) for "res.iteritems()"
  Since unique(keys) <= values, the new complexity will be O(values)

  This is only the comparison till preparing values of a key for
  conversion.

To manage notifications about this bug go to:
https://bugs.launchpad.net/quantum/+bug/1092995/+subscriptions