Re: [libvirt] [PATCH 2/5] Convert virDomainObjListPtr to use a hash of domain objects
On Wed, Oct 14, 2009 at 11:48:51AM +0100, Daniel P. Berrange wrote:
The current virDomainObjListPtr object stores domain objects in
an array. This means that to find a particular objects requires
O(n) time, and more critically acquiring O(n) mutex locks.
The new impl replaces the array with a virHashTable, keyed off
UUID. Finding a object based on UUID is now O(1) time, and only
requires a single mutex lock. Finding by name/id is unchanged
in complexity.
In changing this, all code which iterates over the array had
to be updated to use a hash table iterator function callback.
Several of the functions which were identically duplicating
across all drivers were pulled into domain_conf.c
So we went from list to array, and now to hash table :-)
<nitpick>
I'm afraid the O(1) is an exageration since as the number grows
you would still need to lock each object on the clash list for
that hash. But for normal use we should end up in constant time,
but in theory I think it's still O(n) ...
</nitpick>
I expect that the gain will come from the fact all lookups intenally
are done though the UUID, the Name/ID being only convenience API.
I'm also wondering about the symetry for other kind of objects,
we probably don't need this for networks (less objects, less
operation and operation usually short), you really expect that
to be a single optimization and just for domains, right ?
Daniel
--
Daniel Veillard | libxml Gnome XML XSLT toolkit http://xmlsoft.org/
daniel(a)veillard.com | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library http://libvirt.org/