Re: [Qemu-block] [Qemu-devel] [PATCH 2/3] block: Emit modules in bdrv_iterate_format()

[Eric Blake]

On 11/02/2016 06:15 AM, Kevin Wolf wrote:
> Am 02.11.2016 um 11:52 hat Hao QingFeng geschrieben:
>> Sorry for a bit late response. The function looks fine but just some
>> doubt on g_renew in this piece of code(and the legacy), does
>> g_renew(realloc) has much performance impact if it's call many times
>> since alloc and memory copy are both also run many times?  So how
>> about increase the memory for more instead of 1 each time?
>>
>> formats = g_renew(const char *, formats, count + 10);
>>
>> A new counter also needs to be introduced to record the space size.

You are correct that the naive code has O(n^2) complexity, but so does
your replacement.  The only way to get to O(n) amortized complexity is
to change count by a geometric scale (the simplest is doubling each time
you have to realloc, but even something like increasing by 50% any time
an increase is needed would also work).  So if it is ever worth tracking
allocation size to reduce reallocation costs, it is worth doing it right
by using geometric rather than linear growth.

> 
> This code is not on a hot path, so keeping the code simple and easy to
> maintain is preferrable to complicating it just so --help can save a few
> CPU cycles.

But Kevin makes a good point - for small values of n, the difference
between running a complex O(n) algorithm or a simpler naive O(n^2)
algorithm can actually be faster for the naive algorithm; complexity
alone is not necessarily a good measure of performance until you have
large enough n that it becomes the dominating factor.  And this
certainly counts as code that is not executed frequently, nor where we
expect to have so many distinct formats that n will ever grow large
enough that the O(n^2) nature of the algorithm is noticeable to the
humans reading the help output.

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

signature.asc
Description: OpenPGP digital signature