GNU bug report logs - #77942
31.0.50; replace-region-contents gets stuck

Previous Next

Full log

View this message in rfc822 format

From: Gerd Möllmann <gerd.moellmann <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77942 <at> debbugs.gnu.org
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Date: Mon, 21 Apr 2025 22:39:39 +0200

Gerd Möllmann <gerd.moellmann <at> gmail.com> writes:

> Stefan Monnier <monnier <at> iro.umontreal.ca> writes:
>
>>> This enters an (infinite?) loop
>>
>> AFAICT it's not infinite.  At least, it does end for me when the buffer
>> is smaller (100000) and it does take more time (but still end) with
>> a buffer of 500000, so I think it would end *eventually*.
>
> Just as an observation: I started with 1 run and that seemed reasonably
> fast, a few seconds, so I made it 100, which had this effect.

Just found that replace-region-contents apparently uses a diff
algorithm from diffseq.h, and that says

   The basic algorithm is described in:
   "An O(ND) Difference Algorithm and its Variations", Eugene W. Myers,
   Algorithmica Vol. 1, 1986, pp. 251-266,

If N is the buffer size and D is the diff size, and both are large, good
luck with that. And indeed, reducing the buffer size by 2 orders of
magnitude makes things acceptable for my use case.

Previous Next

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