Re: [Qemu-devel] [PATCH 2/3] block: Emit modules in bdrv_iterate_format()
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
Re: [Qemu-devel] [PATCH 2/3] block: Emit modules in bdrv_iterate_format()
在 2016-11-02 19:15, Kevin Wolf 写道: 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. 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. Got it. thanks! Kevin -- QingFeng Hao(Robin)
Re: [Qemu-devel] [PATCH 2/3] block: Emit modules in bdrv_iterate_format()
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. 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. Kevin
Re: [Qemu-devel] [PATCH 2/3] block: Emit modules in bdrv_iterate_format()
在 2016-10-13 4:49, Max Reitz 写道:
Some block drivers may not be loaded yet, but qemu supports them
nonetheless. bdrv_iterate_format() should report them, too.
Signed-off-by: Max Reitz
---
block.c | 18 ++
1 file changed, 18 insertions(+)
diff --git a/block.c b/block.c
index e46e4b2..88a1ea5 100644
--- a/block.c
+++ b/block.c
@@ -2815,6 +2815,24 @@ void bdrv_iterate_format(void (*it)(void *opaque, const
char *name),
}
}
+for (i = 0; i < (int)ARRAY_SIZE(block_driver_modules); i++) {
+const char *format_name = block_driver_modules[i].format_name;
+
+if (format_name) {
+bool found = false;
+int j = count;
+
+while (formats && j && !found) {
+found = !strcmp(formats[--j], format_name);
+}
+
+if (!found) {
+formats = g_renew(const char *, formats, count + 1);
+formats[count++] = format_name;
+}
+}
+}
+
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.
Thanks
qsort(formats, count, sizeof(formats[0]), qsort_strcmp);
for (i = 0; i < count; i++) {
--
QingFeng Hao(Robin)
Re: [Qemu-devel] [PATCH 2/3] block: Emit modules in bdrv_iterate_format()
On 10/12/2016 03:49 PM, Max Reitz wrote: > Some block drivers may not be loaded yet, but qemu supports them > nonetheless. bdrv_iterate_format() should report them, too. > > Signed-off-by: Max Reitz > --- > block.c | 18 ++ > 1 file changed, 18 insertions(+) > Reviewed-by: Eric Blake -- Eric Blake eblake redhat com+1-919-301-3266 Libvirt virtualization library http://libvirt.org signature.asc Description: OpenPGP digital signature
