Re: [libvirt] [PATCHv2 5/7] snapshot: virsh fallback for snapshot-list --descendants --from
On 10/09/2011 09:25 PM, Daniel Veillard wrote:
On Fri, Sep 30, 2011 at 05:09:27PM -0600, Eric Blake wrote:
> Given a list of snapshots and their parents, finding all descendants
> requires a hairy traversal. This code is O(n^3); it could maybe be
> made to scale O(n^2) with the use of a hash table, but that costs more
> memory. Hopefully there aren't too many people with a hierarchy
> so large as to approach REMOTE_DOMAIN_SNAPSHOT_LIST_NAMES_MAX (1024).
>
> + /* Make multiple passes over the list - first pass
NULLs
> + * out all roots except start, remaining passes NULL out
> + * any entry whose parent is not still in list. Also, we
> + * NULL out parent when name is known to be in list.
> + * Sorry, this is O(n^3) - hope your hierarchy isn't huge. */
ACK, to be removed in second patch set anyway :-)
Well, not so much removed from virsh, as never hit in the first place
once your server is new enough. But if you are still using an 0.9.6 (or
even 0.8.0) server, then yes, this is the best we can do without the
added complexity of mirroring a hash table and parent/child
relationships directly in virsh.
--
Eric Blake eblake(a)redhat.com +1-801-349-2682
Libvirt virtualization library http://libvirt.org