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 :| -- Libvir-list mailing list Libvir-list@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/libvir-list