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
