On 2013-01-31 03:51, Guillem Jover wrote:
> On Wed, 2013-01-30 at 16:17:31 +0100, Niels Thykier wrote:
>> Package: libdpkg-perl
>> Version: 1.16.9
>> Severity: minor
>
>> Iterating over the fields in a Dpkg::Control object (e.g. keys
>> %{$dctrl}) has an O(n^2) performance. This is apparent in the code,
>> where FIRSTKEY and NEXTKEY loops over the "in-order" list (hinting
>> performance of at least O(n*m) code):
>
> Yeah, when going over the code to optimize it I noticed those
> functions to be fishy, but I did not go further because, I've enabled
> the user to request an object w/ direct access to the underlaying hash
> and/or w/o ordering; and because I've concluded that the tie is really
> not a good idea, and I'm planning to replace it with explicit member
> functions and possibly to eventually get rid of it.
>
Ah, that might be a good idea - I just noticed that DELETE appears to be
O(n) per key removed[1], so a destructive iteration would probably still
be O(n^2) even if the iterator was fixed.
>> The bug is of minor severity, because it takes an "obscence" number of
>> fields before the O(n^2) behaviour degrades the performance visibly in
>> the benchmark[1].
>
> Still, good to have it spotted and filed. Thanks!
>
> Regards,
> Guillem
~Niels
[1] @$in_order = grep { lc($_) ne $key } @$in_order;
--
To UNSUBSCRIBE, email to debian-bugs-dist-requ...@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmas...@lists.debian.org
