Bug 109254 - [Algorithms] Compare causes entire machine to hang when comparing large files
Summary: [Algorithms] Compare causes entire machine to hang when comparing large files
Status: VERIFIED FIXED
Alias: None
Product: Platform
Classification: Eclipse Project
Component: Compare (show other bugs)
Version: 3.1   Edit
Hardware: PC Windows 2000
: P3 normal (vote)
Target Milestone: 3.3 M4   Edit
Assignee: Michael Valenta CLA
QA Contact:
URL:
Whiteboard:
Keywords: contributed, performance
: 61879 (view as bug list)
Depends on:
Blocks:
 
Reported: 2005-09-11 12:02 EDT by Oyvind Harboe CLA
Modified: 2006-12-12 09:32 EST (History)
2 users (show)

See Also:

Attachments
O(N+M) space LCS implementation (19.08 KB, text/plain)
2006-11-28 14:35 EST, Dmitry Karasik CLA 		no flags Details
View All Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Oyvind Harboe CLA 2005-09-11 12:02:19 EDT 
1. Commit a file of >50k lines.
2. Compare it against a similar local file.

Result:

- a progress requester comes up, as expected.
- the machine is churning.
- After a while I give up and press Cancel.
- Eclipse and all other applications are unresponsive
- after a long time(somewhere between 2-20 minutes, I didn't check)
  the requester goes away and Eclipse puts up an error dialog that it
  was unable to compare the files.

Comparing two files which have on the order of 40-50k lines can be quite useful.

I would like to use it to compare execution traces of complicated programs as
one of the regression testing schemes.
Comment 1 Oyvind Harboe CLA 2005-09-11 12:16:20 EDT 
When comparing the same files with WinMerge, it takes <1 second before the
visual diff is displayed, so obviously this is an algorithmic problem and not a
performance limitation of Java.

http://winmerge.sourceforge.net/
Comment 2 Dmitry Karasik CLA 2006-11-28 14:35:33 EST 
Created attachment 54664 [details]
O(N+M) space LCS implementation

Needs a bit of work to make it use IRangeComparator
Comment 3 Michael Valenta CLA 2006-11-28 15:10:10 EST 
Thanks for the patch. I'll have a look at it soon (hopefully tomorrow).
Comment 4 Michael Valenta CLA 2006-11-30 10:32:50 EST 
Fix released to HEAD. Thanks again for the contribution.
Comment 5 Michael Valenta CLA 2006-12-07 09:12:38 EST 
*** Bug 61879 has been marked as a duplicate of this bug. ***
Comment 6 Michael Valenta CLA 2006-12-12 09:32:59 EST 
verified