703788 - Improve performance of diff_arrays() with large arrays

Status: RESOLVED FIXED

(Bugzilla :: Bugzilla-General, enhancement)

Description

[Frédéric Buclin]

Attachment: patch, v1

In order to fix bug 644281 and to detect changes between two buglists, which can both contain thousands of bug IDs, I need to rewrite diff_arrays() to make it work efficiently with large arrays. The difference is already noticeable with only a few items in both arrays: the improvement is 2-3x faster! With two arrays of 10,000 items each, the improvement is huge: 49 seconds (old) vs 0.03 second (new)!! And with 100,000 items, my rewrite makes diff_arrays() to complete in 0.35 second only (and probably several tens of minutes or hours with the old code)!

I included a test in t/007util.t to validate my code.

Comment 1

[Max Kanat-Alexander]

Comment on attachment 575588 [details] [diff] [review]
patch, v1

Review of attachment 575588 [details] [diff] [review]:
-----------------------------------------------------------------

Awesome. Wow, what a remarkable speedup! I bet this was biting us in places we didn't even know.

::: t/007util.t
@@ +83,5 @@
> +# Removed (in this order): gamma alpha gamma.
> +# Added (in this order): delta
> +my ($removed, $added) = diff_arrays(\@old_array, \@new_array);
> +is(join(":", @$removed), 'gamma:alpha:gamma', 'diff_array(\@old, \@new) (check removal)');
> +is(join(":", @$added), 'delta', 'diff_array(\@old, \@new) (check addition)');

You can use is_deeply here instead of doing an is with a join.

Comment 2

[Frédéric Buclin]

I replaced is() by is_deeply(), as suggested.

Committing to: bzr+ssh://[e-mail]/bugzilla/trunk/
modified Bugzilla/Util.pm
modified t/007util.t
Committed revision 8006.

Committing to: bzr+ssh://[e-mail]/bugzilla/4.2/
modified Bugzilla/Util.pm
modified t/007util.t
Committed revision 7957.