gnats/598: diff-prs can be very slow

[bug-gnats]

>Number:         598
>Category:       gnats
>Synopsis:       diff-prs can be very slow
>Confidential:   no
>Severity:       serious
>Priority:       low
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Fri Apr 28 16:23:46 -0500 2006
>Originator:     Michael van Elst
>Release:        
>Organization:
>Environment:
>Description:
diff-prs uses O(N^2) operations to collect fields
in a PR because it "appends" lines to a linebuffer
by replacing the linebuffer with the augmented version
line by line.

If a PR contains fields consisting of many lines
this can be very slow.

In this case the field Audit-Trail contained about
17000 lines of a CVS log from a gcc4 import.
>How-To-Repeat:
add ten thousand lines to a field in a PR
(say Audit-Trail) and diff old and new version.
This will take several minutes even on a 2GHz Athlon.
>Fix:
Do not append linebuffers but store them in an array
and don't bother to compare field contents if the number
of lines already differs.

A diff is attached.
>Notify-List:    
>Unformatted:
 ----gnatsweb-attachment----
 Content-Type: application/octet-stream; name="diff-prs.diff"
 Content-Transfer-Encoding: base64
 Content-Disposition: attachment; filename="diff-prs.diff"