Re: [libvirt] [PATCH 2/5] Convert virDomainObjListPtr to use a hash of domain objects

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

 



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@xxxxxxxxxxxx  | Rpmfind RPM search engine http://rpmfind.net/
http://veillard.com/ | virtualization library  http://libvirt.org/

--
Libvir-list mailing list
Libvir-list@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/libvir-list

[Index of Archives]     [Virt Tools]     [Libvirt Users]     [Lib OS Info]     [Fedora Users]     [Fedora Desktop]     [Fedora SELinux]     [Big List of Linux Books]     [Yosemite News]     [KDE Users]     [Fedora Tools]