Re: [Qemu-devel] [PATCH v1 01/10] qdict: implement a qdict_crumple method for un-flattening a dict

[Daniel P. Berrange]

On Sat, Mar 05, 2016 at 04:15:59PM +0100, Max Reitz wrote:
> On 03.03.2016 12:01, Daniel P. Berrange wrote:
> > On Wed, Mar 02, 2016 at 05:13:59PM +0100, Max Reitz wrote:
> >> On 19.02.2016 17:47, Daniel P. Berrange wrote:
> >>> The qdict_flatten() method will take a dict whose elements are
> >>> further nested dicts/lists and flatten them by concatenating
> >>> keys.
> >>>
> >>> The qdict_crumple() method aims todo the reverse, taking a flat
> >>> qdict, and turning it into a set of nested dicts/lists. It will
> >>> apply nesting based on the key name, with a '.' indicating a
> >>> new level in the hierarchy. If the keys in the nested structure
> >>> are all numeric, it will create a list, otherwise it will create
> >>> a dict.
> >>>
> >>> If the keys are a mixture of numeric and non-numeric, or the
> >>> numeric keys are not in strictly ascending order, an error will
> >>> be reported.
> 
> [...]
> 
> >>> +            if (!child) {
> >>> +                goto error;
> >>> +            }
> >>> +
> >>> +            qdict_put_obj(tmp2, entry->key, child);
> >>> +        } else {
> >>> +            qobject_incref(entry->value);
> >>> +            qdict_put_obj(tmp2, entry->key, entry->value);
> >>> +        }
> >>> +
> >>> +        entry = next;
> >>> +    }
> >>> +    QDECREF(tmp1);
> >>> +
> >>> +    /* Step 3: detect if we need to turn our dict into list */
> >>
> >> You could use qdict_array_entries(tmp2, "") > 0 for this.
> >>
> >> If you do want to make { "0": 42, "2": 23 } and { "0": 42, "x": 23 }
> >> errors (my qdict_unflatten() just kept those QDicts), then you'd have to
> >> check on qdict_array_entries() error whether the QDict contained an
> >> integer key, but that would still be simpler than the following loop and
> >> the check in step 4.
> > 
> > If I use qdict_array_entries() then it does 2 O(N) iterations
> > of the input qdict, and to check the errors, I'll have todo
> > yet another iteration.  My inlined code here does everything
> > in a single O(N) iteration instead of 3. I think that's
> > compelling enough to reason to not use that function.
> 
> O(3N) = O(N) :-)
> 
> Making qdict_array_entries() O(N) (pretending that O(N) and O(2N) were
> different things) for this case is trivial: Just omit the second loop if
> "" has been passed as the subqdict.
> 
> So then you'd end up with "O(2N)", if you do the error checking.
> 
> So you are right, there is a reason not to use qdict_array_entries(),
> but I'd personally still use it. I only have very limited knowledge of
> the whole qemu code base, but it doesn't appear to me as if QDict
> functions are ever used in a hot path or as if QDicts ever contain a
> large number of elements (with large being more than, say, 1000),
> especially not the kind of QDicts you'd want to crumple.
> 
> Because of that, I chose to use these existing functions, even while
> knowing that they are probably not optimal for this case.
> 
> You did propose removing qdict_array_entries() and qdict_array_split()
> in favor of just using this function in their stead (see my reply
> below), so if we do so, reusing them would obviously not be ideal any
> more. In that case, I'd still put this into its own static function if
> possible.
> 
> tl;dr: I don't think runtime complexity is an issue here, but if we are
> going to drop qdict_array_entries() and qdict_array_split() anyway, then
> using them is a bad idea, obviously. It would then still be nice to put
> this into an own function.

So looking at the current usage of qdict_flatten,  qdict_extract_subqdict,
qdict_array_split and qdict_array_entries, it is basically only the block
layer.

The root cause of this usage all stems from that fact that historically
the block layer was driven off QemuOpts CLI args which are a flat data
structure. Over time we've tried to bolt on recursive data structure
support, but the main APIs are still accepting QDicts whose contents are
flat. Increasingly I see the internal code is based on QAPI which is an
inherantly nested data structure, as a result the block layer is getting
more & more places where it has to process the flat data structure to
extract nested bits (qdict_extract_subqdict, qdict_array_entries and
qdict_array_split). Conversely when fed data coming from QMP it has to
flatten the data structure with qdict_flatten.

With this new qdict_crumple() method (or equivalently you qdict_unflatten)
it strikes me we can significantly simplify the block layer to always use
a nested QDict internally. All that would be required is to call the
qdict_crumple() method in the places which have the flat QemuOpts derived
QDict. At that point we would potentially be able to delete all of
qdict_flatten, qdict_extract_subqdict, qdict_array_split and
qdict_array_entries

Of course I'm not suggesting we do that for 2.6, but it actually doesn't
look like it would be that hard todo this conversion.

> > The only user of qdict_array_entries() and qdict_array_split()
> > is the block quorum driver. From a brief look at that code
> > I think it could probably be changed to just call this new
> > qdict_crumple() method, and those 2 inefficient functions
> > could be deleted, so we don't have duplication of code.
> 
> I'm not sure. First, you do not want to crumple recursively there, so
> you'd have to re-flatten all the QList elements after you have crumpled
> them. Could be solved by adding a "bool recurse" parameter to this function.
> 
> Second, yes, qdict_array_entries() is used by quorum. However, it does
> (no longer) use qdict_array_split(); the users of that are
> util/qemu-config.c and blockdev.c. Replacing those with a non-recursing
> call to qdict_crumple() should be trivial, but quorum is going to be a
> bit more difficult. You could make it just call qdict_crumple(), get the
> size of the resulting list and then discard it, but that seems a bit
> over the top.
> 
> All in all, I think you're right in that this function can replace the
> (potentially) worse qdict_array_split() function (if the caller can stop
> it from recursing), but I don't know whether we can get rid of
> qdict_array_entries() so easily.

Yeah, that would require the big block layer conversion to always use a
nested QDict and never use a flat QDict.

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|