Re: [Qemu-devel] [PATCH 4/4] json-streamer: Limit number of tokens in addition to total size

[Eric Blake]

On 10/29/2015 12:27 PM, Markus Armbruster wrote:
>> Sounds like we have some quadratic (or worse) scaling in the parser.
>> Worth fixing some day, but I also agree that we don't have to tackle it
>> in this series.
> 
> I believe it's linear with a criminally negligent constant (several KiB
> per token).  The first hog is actually fairly obvious: we use on QDict
> per token.

Wow.  I just read through the code, and you're right.  We are passing
around QDicts right and left (one per token, with 4 keys, which is
several mallocs per token), and then creating a QList of those tokens.

Prior to commit 65c0f1e9, when we were really incrementing the refcount
of each token on each level of nesting (as part of copying context, for
definite quadratic behavior), the refcounts let us ensure tokens would
be cleaned up at the end.  But I'm hard pressed to see the refcount of
tokens going above one in the current code, which means we aren't
gaining anything by using QDict for reference counting.  For that
matter, JSON is quite linear - the code talks about needing to backtrack
in different contexts, but JSON doesn't have ambiguities that need
backtracking to try multiple different rules.  It seems like the code is
overengineered because it is copied from another language where
backtracking to try several alternate parses actually makes sense.

I suspect that using a C struct per token, and a C array of those
structs, would go a long way towards alleviating memory abuse per token.

Are you tackling that, or would you like me to take a stab at it while
you work on flushing my pending qapi patches?

> 
>> I'm assuming you temporarily patched check-qjson to use larger constants
>> when you hit your ~100K token testing?  Because I am definitely seeing a
>> lot of execution time spent on large_dict when running tests/check-qjson
>> by hand, in relation to all the other tests of that file, but not
>> minutes worth.  Care to post the diff you played with?
> 
> I tested on a slow machine.

I guess it was all the malloc pressure on a low-memory system that would
make it so much slower than what I'm seeing, if you stuck with the
default gen_test_json(gstr, 10, 100).

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature