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

[Zhongyue Luo]

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.

[OpenStack Infra (hudson-openstack)]

Fix proposed to branch: master
Review: https://review.openstack.org/18568

[OpenStack Infra (hudson-openstack)]

Reviewed: https://review.openstack.org/18568
Committed: http://github.com/openstack/quantum/commit/e2b9b0df3838cbd7cefcb3a714e285510238769a
Submitter: Jenkins
Branch: master

commit e2b9b0df3838cbd7cefcb3a714e285510238769a
Author: Zhongyue Luo <email address hidden>
Date: Sat Dec 22 06:26:05 2012 +0800

    Fixes inefficiency in quantum.api.v2.base._filters

    Use iteritems() instead of getall() on request.GET

    Fixes bug #1092995

    Change-Id: Ic0b5e3d7c7b1ddd072d9fe918ea22a8e9aef9ee4