GNU bug report logs - #32993
Pathologically slow operation

Previous Next

Full log

Message #8 received at 32993 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Stefan Monnier <monnier <at> IRO.UMontreal.CA>, 32993 <at> debbugs.gnu.org
Subject: Re: [bug-diffutils] bug#32993: Pathologically slow operation
Date: Mon, 8 Oct 2018 15:49:09 -0700

On 10/8/18 2:34 PM, Stefan Monnier wrote:
> Is there a chance this performance behavior is the
> result of a performance bug, or is the algorithm really that costly?

It's O(N*D), where N is the input length and D is the number of 
differences. In your case that might be about 10*11, which is getting up 
there.

> tries to do word-level diffs (by basically turning every word
> into N copies of this word, each one on its own line (where N is the
> number of chars in the word, used to indicate to `diff` that long words
> are "more costly" than short ones)

Ouch. That's a really inefficient way of mucking with the cost 
algorithm. Diff should be able to do taht directly, without your having 
to repeat the words. (Just a simple matter of programming....)

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.