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

[Daniel P. Berrange]

On Wed, Oct 14, 2009 at 04:04:50PM +0200, Daniel Veillard wrote:
> 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 :-)

Yeah, I very much regret switching from the linked list to
an array. I don't know why I didn't go straight to a hash
table when I changed it last time :-(

> <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>

If that ever becomes a problem, which I very much doubt, then
we can easily enhance the hash table impl to automatically add
extra buckets once the number of elements passes some threshold
so you guarentee its always very close to O(1)

The important change here is really removal of the O(n) mutex
locks, whcih will always be O(1), because even if there are
many entries in each hash bucket you're still doing the lookup
based on the key, not the entry. So you'll only ever need to
lock the object you eventually find.

> 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 ?

I think it will probably be worth doing it for storage pools too.
And once we've done that we might as well do it for networks too
just to be consistent everywhere, but its not critical for now.

Daniel
-- 
|: Red Hat, Engineering, London   -o-   http://people.redhat.com/berrange/ :|
|: http://libvirt.org  -o-  http://virt-manager.org  -o-  http://ovirt.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: GnuPG: 7D3B9505  -o-  F3C9 553F A1DA 4AC2 5648 23C1 B3DF F742 7D3B 9505 :|