GNU logs - #77942, boring messages

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Sun, 20 Apr 2025 15:30:07 +0000
Resent-Message-ID: <handler.77942.B.174516295130527 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 77942 <at> debbugs.gnu.org
From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Date: Sun, 20 Apr 2025 17:28:51 +0200
Message-ID: <m2zfga4zt8.fsf@HIDDEN>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Received-SPF: pass client-ip=2a00:1450:4864:20::430;
 envelope-from=gerd.moellmann@HIDDEN; helo=mail-wr1-x430.google.com
X-Spam_score_int: -20
X-Spam_score: -2.1
X-Spam_bar: --
X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1,
 DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001 autolearn=ham autolearn_force=no
X-Spam_action: no action
X-Spam-Score: 1.0 (+)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -0.0 (/)

To reproduce with emacs -Q, define this function

(defun elb-replace-region-contents-entry ()
  (with-temp-buffer
    (let ((step (apply #'concat (make-list 2000 "=F0=9F=99=82=C3=A9t=C3=A9=
=F0=9F=91=B6=F0=9F=8F=BF "))))
      (dotimes (_ (/ 10000000 (length step)))
        (insert step)))

    (dotimes (_ 100)
      (let* ((a (1+ (random (point-max))))
	     (b (1+ (random (point-max))))
	     (beg (min a b))
	     (end (max a b)))
	(replace-region-contents beg end "=F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=F0=
=9F=8F=BF =F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=F0=9F=8F=BF ")))))

and evaluate

  /elb-replace-region-contents-entry)

This enters an (infinite?) loop that cannot be interrupted with C-g in
the GUI version. If started with -nw, C-g eventually crashes Emacs,
without printing anything on stdout or stderr.


In GNU Emacs 31.0.50 (build 1, aarch64-apple-darwin24.4.0, NS
 appkit-2575.50 Version 15.4.1 (Build 24E263)) of 2025-04-20 built on
 pro2
Repository revision: 6fb2a4691f4d53473c0a326d3a6c23df9008b6e8
Repository branch: master
System Description:  macOS 15.4.1

Configured using:
 'configure --cache-file
 /var/folders/1d/k_6t25f94sl83szqbf8gpkrh0000gn/T//config.cache.master
 --enable-checking=3Dyes --with-native-compilation=3Dno CC=3Dclang
 'CFLAGS=3D-Wgnu-imaginary-constant -Wunused-result -g -g -O0 -F
 /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Devel=
oper/SDKs/MacOSX.sdk/System/Library/Frameworks
 -Wno-ignored-attributes -Wno-flag-enum -Wno-missing-method-return-type
 -Wno-variadic-macros -Wno-strict-prototypes -Wno-availability
 -Wno-nullability-completeness''

Configured features:
ACL DBUS GLIB GNUTLS LCMS2 LIBXML2 MODULES NOTIFY KQUEUE NS PDUMPER PNG
RSVG SQLITE3 THREADS TOOLKIT_SCROLL_BARS TREE_SITTER WEBP XIM ZLIB

Important settings:
  value of $LANG: en_US.UTF-8
  locale-coding-system: utf-8-unix

Message sent:

Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Mailer: MIME-tools 5.505 (Entity 5.505)
Content-Type: text/plain; charset=utf-8
X-Loop: help-debbugs@HIDDEN
From: help-debbugs@HIDDEN (GNU bug Tracking System)
To: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Subject: bug#77942: Acknowledgement (31.0.50; replace-region-contents gets
 stuck)
Message-ID: <handler.77942.B.174516295130527.ack <at> debbugs.gnu.org>
References: <m2zfga4zt8.fsf@HIDDEN>
X-Gnu-PR-Message: ack 77942
X-Gnu-PR-Package: emacs
Reply-To: 77942 <at> debbugs.gnu.org
Date: Sun, 20 Apr 2025 15:30:08 +0000

Thank you for filing a new bug report with debbugs.gnu.org.

This is an automatically generated reply to let you know your message
has been received.

Your message is being forwarded to the package maintainers and other
interested parties for their attention; they will reply in due course.

Your message has been sent to the package maintainer(s):
 bug-gnu-emacs@HIDDEN

If you wish to submit further information on this problem, please
send it to 77942 <at> debbugs.gnu.org.

Please do not send mail to help-debbugs@HIDDEN unless you wish
to report a problem with the Bug-tracking system.

--=20
77942: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D77942
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Eli Zaretskii <eliz@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Sun, 20 Apr 2025 16:07:05 +0000
Resent-Message-ID: <handler.77942.B77942.174516522112307 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, Stefan Monnier <monnier@HIDDEN>
Cc: 77942 <at> debbugs.gnu.org
Date: Sun, 20 Apr 2025 19:06:44 +0300
Message-Id: <86plh66cmj.fsf@HIDDEN>
From: Eli Zaretskii <eliz@HIDDEN>
In-Reply-To: <m2zfga4zt8.fsf@HIDDEN> (message from Gerd =?UTF-8?Q?M=C3=B6llmann?= on Sun, 20 Apr 2025 17:28:51 +0200)
References: <m2zfga4zt8.fsf@HIDDEN>
MIME-version: 1.0
Content-type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

> From: Gerd Möllmann <gerd.moellmann@HIDDEN>
> Date: Sun, 20 Apr 2025 17:28:51 +0200
> 
> To reproduce with emacs -Q, define this function
> 
> (defun elb-replace-region-contents-entry ()
>   (with-temp-buffer
>     (let ((step (apply #'concat (make-list 2000 "🙂été👶🏿 "))))
>       (dotimes (_ (/ 10000000 (length step)))
>         (insert step)))
> 
>     (dotimes (_ 100)
>       (let* ((a (1+ (random (point-max))))
> 	     (b (1+ (random (point-max))))
> 	     (beg (min a b))
> 	     (end (max a b)))
> 	(replace-region-contents beg end "🙂été👶🏿 🙂été👶🏿 ")))))
> 
> and evaluate
> 
>   /elb-replace-region-contents-entry)
> 
> This enters an (infinite?) loop that cannot be interrupted with C-g in
> the GUI version. If started with -nw, C-g eventually crashes Emacs,
> without printing anything on stdout or stderr.

Adding Stefan.

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Stefan Monnier <monnier@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 17:24:02 +0000
Resent-Message-ID: <handler.77942.B77942.17452562306170 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Cc: 77942 <at> debbugs.gnu.org
From: Stefan Monnier <monnier@HIDDEN>
In-Reply-To: <m2zfga4zt8.fsf@HIDDEN>
Message-ID: <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN>
Date: Mon, 21 Apr 2025 13:23:34 -0400
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

> To reproduce with emacs -Q, define this function
>
> (defun elb-replace-region-contents-entry ()
>   (with-temp-buffer
>     (let ((step (apply #'concat (make-list 2000 "=F0=9F=99=82=C3=A9t=C3=
=A9=F0=9F=91=B6=F0=9F=8F=BF "))))
>       (dotimes (_ (/ 10000000 (length step)))
>         (insert step)))
>
>     (dotimes (_ 100)
>       (let* ((a (1+ (random (point-max))))
> 	       (b (1+ (random (point-max))))

[ Side note: This should use (+ (point-min) (random (buffer-size)))  ]

> 	     (beg (min a b))
> 	     (end (max a b)))

And this should not be necessary because `replace-region-contents`
should accept positions in any order, like `delete-region`.

> 	(replace-region-contents beg end "=F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=
=F0=9F=8F=BF =F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=F0=9F=8F=BF ")))))
>
> and evaluate
>
>   (elb-replace-region-contents-entry)
>
> 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*.

> that cannot be interrupted with C-g in the GUI version.

Apparently the MAX-SECS argument doesn't help either.  =F0=9F=99=81

> If started with -nw, C-g eventually crashes Emacs,
> without printing anything on stdout or stderr.

That's even worse.

Eli wrote:
> Adding Stefan.

FWIW, this problem also shows up in Emacs-28 with:

    (require 'subr-x)
=20=20=20=20
    (defun elb-replace-region-contents-entry ()
      (with-temp-buffer
        (let ((step (apply #'concat (make-list 2000 "=F0=9F=99=82=C3=A9t=C3=
=A9=F0=9F=91=B6=F0=9F=8F=BF "))))
          (dotimes (_ (/ 10000000 (length step)))
            (insert step)))
=20=20=20=20
        (dotimes (_ 100)
          (let* ((a (+ (point-min) (random (buffer-size))))
                 (b (+ (point-min) (random (buffer-size)))))
            (message "replace-region-contents %S %S ..." a b)
            (replace-region-contents a b (lambda () "=F0=9F=99=82=C3=A9t=C3=
=A9=F0=9F=91=B6=F0=9F=8F=BF =F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=F0=9F=8F=
=BF "))
            (message "replace-region-contents...done")))))



- Stefan

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 18:02:01 +0000
Resent-Message-ID: <handler.77942.B77942.174525851517821 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Stefan Monnier <monnier@HIDDEN>
Cc: 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174525851517821
          (code B ref 77942); Mon, 21 Apr 2025 18:02:01 +0000
Received: (at 77942) by debbugs.gnu.org; 21 Apr 2025 18:01:55 +0000
Received: from localhost ([127.0.0.1]:38208 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u6vSt-0004dM-CA
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 14:01:55 -0400
Received: from mail-wr1-x436.google.com ([2a00:1450:4864:20::436]:49616)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
 (Exim 4.84_2) (envelope-from <gerd.moellmann@HIDDEN>)
 id 1u6vSp-0004ct-G5
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 14:01:52 -0400
Received: by mail-wr1-x436.google.com with SMTP id
 ffacd0b85a97d-39ee5a5bb66so2927447f8f.3
 for <77942 <at> debbugs.gnu.org>; Mon, 21 Apr 2025 11:01:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1745258504; x=1745863304; darn=debbugs.gnu.org;
 h=mime-version:user-agent:message-id:date:references:in-reply-to
 :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to;
 bh=s7sN7h6ncdsb1xl7mX2CRIaYFi40LnoT3YprG5kU/a8=;
 b=Vji0MtiUlQWLFcYHDAdAYvSYxStbwkQfbOXVCp51lH61jm/1EtKtbywpBqsXxRkcqe
 6zzLY+6vEcu1ggpQhQpc4fk/gvTwqSJTA9cyzybs3kSczg2sm+YrU3nulSkdZecB5qb0
 zyXx6Z2weHUcXXTzT0eCVJZTfuYEYuYEmyHOv2KPThK55+cYOpi0pdGMpkxvTUzkNDvi
 qxb9GNDQoff+zwMcNyf/aPVVLz7g+fpKo0PwX3Bndbj5rSWS9jVK2TldS9JrK2lS+Z8y
 PrOe0GLSqw9zWBhjXqydsNXX467t+OHtyT65GwesULorr0FpS+V+kKFSA65yxLqXvFSZ
 19SA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1745258504; x=1745863304;
 h=mime-version:user-agent:message-id:date:references:in-reply-to
 :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date
 :message-id:reply-to;
 bh=s7sN7h6ncdsb1xl7mX2CRIaYFi40LnoT3YprG5kU/a8=;
 b=LP2pPW6s67AkI0dWp9IcU61gA1SX0X+OtKby1cSGsg5BUwcwx/qtavA1QW8LHPXg3k
 IZXXahJyZjiKf6SQXMOOOL8aWjiHIWcSTt9RKR3uQSx9FFwh6skb0mcYaKHMTjNOyu5k
 hvyiYk7ukHz1cb56DuLj+tyfDA3xH44+cObgZhlSmL0Mq9Q8QCrPO+YiaAuO0+CilIDh
 QNWJhILJh9DNDVmAXPv48VKhX6MZVPR5w6ytDP0E1DfiY2Gufqr6084H0mF/bJtMpsUO
 DeLZABfT1Tur/r+9aU4aOffDKDTSjQMmUtx0G75mqXh1oCqOJ6JPS0FzlEtRxdIVuYw8
 WOLA==
X-Gm-Message-State: AOJu0YzvmYSsInrqkav832PqaDkXbR2mcXkZ6G7DyNmP6ABURyNfQRdI
 VVhZFgHCFdUEVYKWhfbg6854aY5v6WN4ix6o/X4FBEJ/bOa1NyW4X1W7lxid
X-Gm-Gg: ASbGncuDJ1Cx0vPL9J88d7eLuQ1X62fTy6UrDF3zAY9RIvah3mV1R6bvFWxVktt36uU
 VSFiUjHh6NPXoaZ2WtmLwCMTK4EGg5/aBf071iOK6bmqNCuDBgoYCryQxD/00dExILvEplB9p3Z
 6oJlMazDZ458SeQg9A4k6EFQGvhD7Hti1u8kOthSDANzlBncdgF7sN7kAIVDY4G2K1Oo19nYEPI
 t9yyRj0vc5xiZR0EqLRUp7JHDFYM+GTtoAJ/hzIOj58RKl07L6TjTMjvqILUIue+0jz1eJcRjtd
 u20d1v4jNAZjZKtXRuZMAj0Y4p3VDhN1ihHNdAnpAOVyLdYuIU53jS5Wwo+D/y+jK0JxNQhmsVk
 2COIQck5C6eA5eHbSrM69ePqg63VQ91B0OBvdVCcJ7g==
X-Google-Smtp-Source: AGHT+IFZTUaraJ0BXWdkAo+EXzaf5You8lLSYIh6dwl/GD+aaaAgBLIli9g4kZ6vSaj1s4yGyvvhww==
X-Received: by 2002:a5d:6da1:0:b0:39a:ca0c:fc90 with SMTP id
 ffacd0b85a97d-39efba3c6e4mr10853114f8f.14.1745258504459; 
 Mon, 21 Apr 2025 11:01:44 -0700 (PDT)
Received: from pro2 (p200300e0b728b60058490051f8c259a0.dip0.t-ipconnect.de.
 [2003:e0:b728:b600:5849:51:f8c2:59a0])
 by smtp.gmail.com with ESMTPSA id
 ffacd0b85a97d-39efa4207d0sm12738557f8f.11.2025.04.21.11.01.43
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Mon, 21 Apr 2025 11:01:44 -0700 (PDT)
From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
In-Reply-To: <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
Date: Mon, 21 Apr 2025 20:01:43 +0200
Message-ID: <m2wmbde6m0.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Stefan Monnier <monnier@HIDDEN> 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.

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Stefan Monnier <monnier@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 20:32:02 +0000
Resent-Message-ID: <handler.77942.B77942.174526752017403 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Cc: 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174526752017403
          (code B ref 77942); Mon, 21 Apr 2025 20:32:02 +0000
Received: (at 77942) by debbugs.gnu.org; 21 Apr 2025 20:32:00 +0000
Received: from localhost ([127.0.0.1]:39362 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u6xo8-0004Wb-5p
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 16:32:00 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:17288)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <monnier@HIDDEN>)
 id 1u6xo2-0004WG-LC
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 16:31:57 -0400
Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1])
 by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 6F74F4412DA;
 Mon, 21 Apr 2025 16:31:48 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
 s=mail; t=1745267507;
 bh=wldJA46r3LE0DSzgD+mEOU0s/u9VYZ2uHi0+EPJVkxU=;
 h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
 b=ew8l3gyvjcL1j2mxlvA1hGfkXbe1aOyVYTfsRB6zbjbfGRgIN6ZCfgfZfERzCANG2
 ffXz4xaRg6mPJKVStF4OB1PgpOWawHp2kvjtKWmODlYgmPrq/6nBWlvjQUpmdnad2N
 24iq+rg1pehOfcJYUGwf64w7oHCGD6UlKBXycKYOKbd+BSWentSs3HMtT/P2Wta7Ha
 sbf3EX3xnJB+nKyoU+QCTuUgp2bBfQK615KbDBY/qBCdm6U2cE9tGm6+ObX+wEhAhK
 TLG4WdAwUtNM3JqyfYXm+pzsm2fWiAcM0emU7INzLe91NT1raLJ5/fLb/uLKd/cL7O
 8SOYkCQwIpdLg==
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
 by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 45CDB44071A;
 Mon, 21 Apr 2025 16:31:47 -0400 (EDT)
Received: from pastel (104-195-208-18.cpe.teksavvy.com [104.195.208.18])
 by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 1DF54120497;
 Mon, 21 Apr 2025 16:31:47 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
In-Reply-To: <m2wmbde6m0.fsf@HIDDEN>
Message-ID: <jwv5xix8dix.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN>
Date: Mon, 21 Apr 2025 16:31:45 -0400
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-SPAM-INFO: Spam detection results:  0
 ALL_TRUSTED                -1 Passed through trusted hosts only via SMTP
 AWL -0.019 Adjusted score from AWL reputation of From: address
 BAYES_00                 -1.9 Bayes spam probability is 0 to 1%
 DKIM_SIGNED               0.1 Message has a DKIM or DK signature,
 not necessarily valid
 DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
 DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
 domain
 DKIM_VALID_EF -0.1 Message has a valid DKIM or DK signature from envelope-from
 domain
X-SPAM-LEVEL: 
X-Spam-Score: -2.3 (--)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -3.3 (---)

Gerd M=C3=B6llmann [2025-04-21 20:01:43] wrote:
> Stefan Monnier <monnier@HIDDEN> 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.

For the first round, how fast is it depends on your luck with the random
number generator since the time depends on the size of the region on
which you perform the replace.

Try just

    (require 'subr-x)
=20=20=20=20
    (defun elb-replace-region-contents-entry ()
      (with-temp-buffer
        (let ((step (apply #'concat (make-list 2000 "=F0=9F=99=82=C3=A9t=C3=
=A9=F0=9F=91=B6=F0=9F=8F=BF "))))
          (dotimes (_ (/ 1000000 (length step)))
            (insert step)))
=20=20=20=20
        (replace-region-contents 123 (- (point-max) 123)
                                 (lambda () "=F0=9F=99=82=C3=A9t=C3=A9=F0=
=9F=91=B6=F0=9F=8F=BF =F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=F0=9F=8F=BF "))=
))


- Stefan

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 20:40:01 +0000
Resent-Message-ID: <handler.77942.B77942.174526799219256 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Stefan Monnier <monnier@HIDDEN>
Cc: 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174526799219256
          (code B ref 77942); Mon, 21 Apr 2025 20:40:01 +0000
Received: (at 77942) by debbugs.gnu.org; 21 Apr 2025 20:39:52 +0000
Received: from localhost ([127.0.0.1]:39425 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u6xvk-00050W-8o
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 16:39:52 -0400
Received: from mail-wr1-x42a.google.com ([2a00:1450:4864:20::42a]:44117)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
 (Exim 4.84_2) (envelope-from <gerd.moellmann@HIDDEN>)
 id 1u6xvh-00050F-00
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 16:39:49 -0400
Received: by mail-wr1-x42a.google.com with SMTP id
 ffacd0b85a97d-39c1efc4577so2356002f8f.0
 for <77942 <at> debbugs.gnu.org>; Mon, 21 Apr 2025 13:39:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1745267982; x=1745872782; darn=debbugs.gnu.org;
 h=content-transfer-encoding:mime-version:user-agent:message-id:date
 :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date
 :message-id:reply-to;
 bh=xymGMANU8jvTxxhSvHPoprylVGkr1CUDXOZq8kdp+H8=;
 b=i1H5r/Up8W3rVS/qQukfFcH1+T31o/Tz1zJwykrk77rbjZznLWIdZukWlOd1SKipxJ
 WJnVMDmrtGLHxD80K13YaYIfmvmBCad5V6pNJD53RwOfYQSA4u0oe4HJDIjI4vDywAot
 zSRNw5ppqQ6ASwqzHdEie/IVIDjttUKjNDQgNEyXxm3Rl1aj7He9uEFb7Emzzes3Boae
 kEdLnNjTDAKc7gE0TZUc27fuv1sUSovZSZLiz5Wyw8si5g4uhz0iT7N25+H+NR3yqvSF
 uvzDQPguQ7IpX14On80TLPGihiunMdQ97pHm6hVJLE3hwsxkaSm3iRhowcJNMRg4xv8r
 wD+Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1745267982; x=1745872782;
 h=content-transfer-encoding:mime-version:user-agent:message-id:date
 :references:in-reply-to:subject:cc:to:from:x-gm-message-state:from
 :to:cc:subject:date:message-id:reply-to;
 bh=xymGMANU8jvTxxhSvHPoprylVGkr1CUDXOZq8kdp+H8=;
 b=K+7LezHx+Q32OL4Pvtf9hM+ciOdqyHvv7qVQZZmETQ2zdhoHoyZtnQXQrkcakykTJF
 /6fRa4oDpyJC9HKesrFOPgnkaqMoANN1v5lo6oZpatuaMTxx0RX0ss5ActeQwWbgcaZj
 g7g9TZo3bT8JR0NTPMMTO14yVyz3BHRNJahxibeu1RBWh9idTfZkIfaXibMAcSF7RdqX
 /lSGaOOxiVhUaeHmLl1RIKWL/rlloVDA8iNL0sNXoZk3HNvcvUX5v83sQ/9z5WaqOStw
 cJt691LTsxZnL1eFQyQsvMB7ZxyCOZ9yfmVPsdPinRj9MHNu0J92dWfjpRyb9uXaGCpO
 V5rQ==
X-Gm-Message-State: AOJu0YwCl4v+rMPrmRqdrp/NjuJMZbwLRdfoTHbyKQU9oFMqj4CMrZ6s
 Fc/FROXazdFuHpVM30Rv/KLFhsKw21IpVPMoBjcPKeQ2FaIb8IqY4h/BFOY7
X-Gm-Gg: ASbGncvgNOf3ZcZ+26HbTOTmM7+308LYLNrL3KDs/cXQrASAgLsZgrebqx2Se9z1Hxh
 qHKYOysr292kBo5qYuUtamlXCGvEFbtWAX9lc3oikdtGGs5q4kLH/COn/3M0i+hzo0myEY++Aqc
 lxzMnl8hA/3o+qmp70E+ZXQh38DTkgB9PusGeo/bbNkGkEtnYP7vERMGyZ0wHgv/aS7awAh0O3Y
 RdZ/WGkIGUAkjygKElTjOl7wuIrg9CnMNmaKpI3lv36dvhZlJrem5bYVTKIwzlaSAXT8Nj1CWJf
 7RTCnnUYZylb/5SUkHZgYMayAPjHbBTRvRtYATtCkNTXWNZofPVWlngJIDFg0rBa5JWBbnb1N9c
 RKAl+mwT3Lt7nmqi8jBZu+DphHVJxoog10Ez56e+/aQ==
X-Google-Smtp-Source: AGHT+IHLUSkhKpNXtiZEVz4/67cAsKyZu5ijYQPU87/j66fw91D89yjJqihGd6ZhxDICa/812QG+qA==
X-Received: by 2002:a5d:6daf:0:b0:39a:c9cb:819f with SMTP id
 ffacd0b85a97d-39efbae0e1fmr8938048f8f.37.1745267981880; 
 Mon, 21 Apr 2025 13:39:41 -0700 (PDT)
Received: from pro2 (p200300e0b728b60058490051f8c259a0.dip0.t-ipconnect.de.
 [2003:e0:b728:b600:5849:51:f8c2:59a0])
 by smtp.gmail.com with ESMTPSA id
 5b1f17b1804b1-4406d5cf313sm147806335e9.30.2025.04.21.13.39.40
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Mon, 21 Apr 2025 13:39:41 -0700 (PDT)
From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
In-Reply-To: <m2wmbde6m0.fsf@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN>
Date: Mon, 21 Apr 2025 22:39:39 +0200
Message-ID: <m2jz7ddzas.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Gerd M=C3=B6llmann <gerd.moellmann@HIDDEN> writes:

> Stefan Monnier <monnier@HIDDEN> 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.

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 20:43:03 +0000
Resent-Message-ID: <handler.77942.B77942.174526816620280 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Stefan Monnier <monnier@HIDDEN>
Cc: 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174526816620280
          (code B ref 77942); Mon, 21 Apr 2025 20:43:03 +0000
Received: (at 77942) by debbugs.gnu.org; 21 Apr 2025 20:42:46 +0000
Received: from localhost ([127.0.0.1]:39451 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u6xyX-0005Gw-Hg
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 16:42:45 -0400
Received: from mail-wm1-x332.google.com ([2a00:1450:4864:20::332]:43025)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
 (Exim 4.84_2) (envelope-from <gerd.moellmann@HIDDEN>)
 id 1u6xyC-0005Da-0G
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 16:42:25 -0400
Received: by mail-wm1-x332.google.com with SMTP id
 5b1f17b1804b1-43cf680d351so31266665e9.0
 for <77942 <at> debbugs.gnu.org>; Mon, 21 Apr 2025 13:42:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1745268137; x=1745872937; darn=debbugs.gnu.org;
 h=content-transfer-encoding:mime-version:user-agent:message-id:date
 :references:in-reply-to:subject:cc:to:from:from:to:cc:subject:date
 :message-id:reply-to;
 bh=fp1kT3MAtomxeuw2i/f0LujMPIpFqk3xI90zOtsjSK0=;
 b=TiIsAlPIHCbxoFFFde20HnrwEV9O3yr20xIxNqDpnzP8K1Ufms55Eydc1T8b7mb6oj
 UG3GsZAzMn2+6eaxLVkW+QpyOMlV50s3B1OVlPJUOUUTBvNQXhm5BSb8bCJxHa2I41VP
 /b/TiFnnF4R1ZbFebmQUuLneK8I6BigMxwhsU3CtOOvD3TBzn2lyH8xapbc7uwU4Ein9
 oIGcjiJ37AednVkQEKqMTPbEeXRd9cZTao4oGn+/WfrDhKiCLxyAZcO2PLtxPJ6nkFx1
 yUhy7o+j/LkOM/96AdKhC/j38GpDOaPnrQaCqiSUIWFId4iyy7BPOfrIihF1v9PX9J47
 ZezA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1745268137; x=1745872937;
 h=content-transfer-encoding:mime-version:user-agent:message-id:date
 :references:in-reply-to:subject:cc:to:from:x-gm-message-state:from
 :to:cc:subject:date:message-id:reply-to;
 bh=fp1kT3MAtomxeuw2i/f0LujMPIpFqk3xI90zOtsjSK0=;
 b=S6xn82aDgOzDfdNWLheo2aAAxsn4iHnG2MpVWrfFzYWvFLyZo88IHGJnUyiE6Sv3Fy
 9npdmgxNaYTCmWIZnGQmqg4+ql1LnEOdMMj/SGkg+W4apTR9WHDfcEvdqgPRlIh+BFu+
 tbPC0rOvNcH17NNR8qDCzPMtAesB+VBRYuc5/rVAz38ocP9LkJnuv+IJZRNiOINarydf
 3oBSZtRpi+ZKCnPiFr1ybq9TMrthVg9Mss9A8WI/mp+82OceQh6gjXVmZ743Nn8/A3SE
 Lnwh5Gx7tzSZw18eiDJjHTbrn2i54fdE46U9ZE8+0FsiatiiRFrV3BcN0PEhf6aFTUdh
 wWww==
X-Gm-Message-State: AOJu0YxiUDmMtSr2Lr5Jd5DR3xieNA7STYe+yfGLZaVse8Fz81zYH5xZ
 DZVmid6Q02t/LLFrDHcMfpC8uX3sAj6/GMSqmcQRqAqDeqbwfQYSL1tCmebh
X-Gm-Gg: ASbGncu+aV1PtB7i0mGc6sXs1z6DBsIHLQeHUvGm8iniIugAqqcp+6Go7rwCRUPih7a
 ib3TQ2Rj9ekG57vwhGANGg643hpDjrKdf9r6Dr/IO11fP6oOoNkNr/v0r+JBCy839GGCyuwGOfA
 T+mJPKiZ5ZDaFq2/lnPgUD5cbCnT7l4qs8ZcQO5SzjMu0N1nux+N2pMyQL1rlCeGKDAuA1XiqiV
 AuJC57lU4MKYje/o7+odNECPpoA36yUSk4K78ozcI7IwZO2vgu7+z0kOSpgEJ8q3wSR3Di2fxb7
 2+4AezbNIgumM6vTSuXU+fZm6VAStIuycoGSJNsbKJfNfFHGaXhzd2oQqrE9s/I0SVMfDwCZAUR
 ewhONeffps8k0vbaQWf7WJdAFd6UguBm7rr5OpCqYgw==
X-Google-Smtp-Source: AGHT+IHBaKH6C12/p5bg0ier4G0mvpmFFwAoA4iggT257B/+TXckL4tlmtHiN6e++tPwzYqFom2nxQ==
X-Received: by 2002:a05:6000:40db:b0:39c:1efb:eec9 with SMTP id
 ffacd0b85a97d-39efbd68416mr10529141f8f.13.1745268137293; 
 Mon, 21 Apr 2025 13:42:17 -0700 (PDT)
Received: from pro2 (p200300e0b728b60058490051f8c259a0.dip0.t-ipconnect.de.
 [2003:e0:b728:b600:5849:51:f8c2:59a0])
 by smtp.gmail.com with ESMTPSA id
 ffacd0b85a97d-39efa4330bfsm12830847f8f.23.2025.04.21.13.42.16
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Mon, 21 Apr 2025 13:42:16 -0700 (PDT)
From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
In-Reply-To: <jwv5xix8dix.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN> <jwv5xix8dix.fsf-monnier+emacs@HIDDEN>
Date: Mon, 21 Apr 2025 22:42:16 +0200
Message-ID: <m2fri1dz6f.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Stefan Monnier <monnier@HIDDEN> writes:

> Gerd M=C3=B6llmann [2025-04-21 20:01:43] wrote:
>> Stefan Monnier <monnier@HIDDEN> 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.
>
> For the first round, how fast is it depends on your luck with the random
> number generator since the time depends on the size of the region on
> which you perform the replace.
>
> Try just
>
>     (require 'subr-x)
>=20=20=20=20=20
>     (defun elb-replace-region-contents-entry ()
>       (with-temp-buffer
>         (let ((step (apply #'concat (make-list 2000 "=F0=9F=99=82=C3=A9t=
=C3=A9=F0=9F=91=B6=F0=9F=8F=BF "))))
>           (dotimes (_ (/ 1000000 (length step)))
>             (insert step)))
>=20=20=20=20=20
>         (replace-region-contents 123 (- (point-max) 123)
>                                  (lambda () "=F0=9F=99=82=C3=A9t=C3=A9=F0=
=9F=91=B6=F0=9F=8F=BF =F0=9F=99=82=C3=A9t=C3=A9=F0=9F=91=B6=F0=9F=8F=BF "))=
))
>

Yep, I've read the code now, and the O(ND) diffing was, well, a bit
suprising :-).

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Stefan Monnier <monnier@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 21:13:03 +0000
Resent-Message-ID: <handler.77942.B77942.174526993128221 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Cc: Paul Eggert <eggert@HIDDEN>, 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174526993128221
          (code B ref 77942); Mon, 21 Apr 2025 21:13:03 +0000
Received: (at 77942) by debbugs.gnu.org; 21 Apr 2025 21:12:11 +0000
Received: from localhost ([127.0.0.1]:39667 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u6yR0-0007L6-PV
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 17:12:11 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:33038)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <monnier@HIDDEN>)
 id 1u6yQv-0007KV-UP
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 17:12:07 -0400
Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id BBA4C80898;
 Mon, 21 Apr 2025 17:11:58 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
 s=mail; t=1745269917;
 bh=OiN9I074ZsED58/qbRqLAJfVOe4bnUIOPJ7sD7EWExo=;
 h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
 b=hzY6Za1SDoxhD8QBZboJkSFH36awmrOocrlSceSVNxayePwBa+rWiQu/CWEhq3Sin
 n/EIC7mQOBytKkBED37cCAYRBM/5ej1d8OVcURwjD/jLMIW4CJ0s57dzDkol7+fz9S
 QjM6ckpEhRIqQu0aw5C40W+UJWsmRFDLrEvakCEKJzcrR5mJKpCaDnPaXDpW91mCQl
 EqifHXegQlITpJOaSeQMZ3YZtB/xlWSppY+iLra6GT6pn63SYZLM+BYRYh61edjM+C
 muBbovygtcMMBX2nZ8keocaFwzG0XxxcmeuXfupH79mUloIFmr94zIbfQiOiebGKhD
 pRUe9T3TjiAwg==
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
 by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id E04B88045E;
 Mon, 21 Apr 2025 17:11:57 -0400 (EDT)
Received: from pastel (104-195-208-18.cpe.teksavvy.com [104.195.208.18])
 by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id B180F12064D;
 Mon, 21 Apr 2025 17:11:57 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
In-Reply-To: <m2jz7ddzas.fsf@HIDDEN>
Message-ID: <jwvtt6h6xhu.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN> <m2jz7ddzas.fsf@HIDDEN>
Date: Mon, 21 Apr 2025 17:11:57 -0400
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-SPAM-INFO: Spam detection results:  0
 ALL_TRUSTED                -1 Passed through trusted hosts only via SMTP
 AWL -0.065 Adjusted score from AWL reputation of From: address
 BAYES_00                 -1.9 Bayes spam probability is 0 to 1%
 DKIM_SIGNED               0.1 Message has a DKIM or DK signature,
 not necessarily valid
 DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
 DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
 domain
 DKIM_VALID_EF -0.1 Message has a valid DKIM or DK signature from envelope-from
 domain
X-SPAM-LEVEL: 
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -3.3 (---)

> 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.

And the fun thing is that in your test case, the "inner function"
`buffer_chars_equal` which compares two chars (which is the part where
the diff code hands us back control so we can check the time against
MAX_SECS, and that's also the place where we probably spend too much
time doing charpos->bytepos conversion) is called only 74 times, at the
very beginning, afterwards there's just a very long processing inside
the diff code itself without looking at the buffer contents (or the
replacement string for that matter).

I actually haven't checked the way the algorithm works, but I get the
impression that this is a case that can be optimized further.  =F0=9F=99=82
Paul, IIUC you've played with this algorithm.  Would you be tempted to
try and improve that situation where the replacement text is *much*
smaller the text it replaces?

Gerd, IIUC you're trying to use this to benchmark the charpos->bytepos
code, in which case you should be better served by a call where the text
and its replacement are of fairly similar size.


        Stefan

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Paul Eggert <eggert@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Mon, 21 Apr 2025 22:33:01 +0000
Resent-Message-ID: <handler.77942.B77942.174527474818081 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Stefan Monnier <monnier@HIDDEN>
Cc: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174527474818081
          (code B ref 77942); Mon, 21 Apr 2025 22:33:01 +0000
Received: (at 77942) by debbugs.gnu.org; 21 Apr 2025 22:32:28 +0000
Received: from localhost ([127.0.0.1]:40589 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u6zgh-0004hY-TI
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 18:32:28 -0400
Received: from mail.cs.ucla.edu ([131.179.128.66]:35594)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <eggert@HIDDEN>)
 id 1u6zge-0004hG-Mi
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 18:32:25 -0400
Received: from localhost (localhost [127.0.0.1])
 by mail.cs.ucla.edu (Postfix) with ESMTP id 678FB3C010860;
 Mon, 21 Apr 2025 15:32:18 -0700 (PDT)
Received: from mail.cs.ucla.edu ([127.0.0.1])
 by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10032) with ESMTP
 id EMdqQuk9znGo; Mon, 21 Apr 2025 15:32:18 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1])
 by mail.cs.ucla.edu (Postfix) with ESMTP id 406513C01086B;
 Mon, 21 Apr 2025 15:32:18 -0700 (PDT)
DKIM-Filter: OpenDKIM Filter v2.10.3 mail.cs.ucla.edu 406513C01086B
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cs.ucla.edu;
 s=9D0B346E-2AEB-11ED-9476-E14B719DCE6C; t=1745274738;
 bh=aXsP4gTrK/HoWSPDpo29K72hqw9ac9dQINrxdbpR4Tc=;
 h=Message-ID:Date:MIME-Version:To:From;
 b=JlZM3LQGg+8a0pplisuoZT9lYOS80KXmDjYJOGDUBIJ+0vrkEv9/+Q2K67DdSs/VB
 siwiHuxuPuqg0Y/9eqV/NR075JaHm3aNSDL8kx1CmHJsfwduMz0Q+pRluatE2gjzPb
 iR2oXgkdKPSHNNx5m3lcM+GvTxfmfzDG7FZWnD4AerOIcwok/0Sc9hO5A/N+LHyfS1
 OfotTnZuCjYvBpFSZR8wU6HKh4a5Hw0DEei0yyjBKWLMxLGIjLM4LD261bDFexNyOg
 kkNg3KSUZNeUKt3AqT0IVLgty/arhgsljJXVSnKwGhSUz/3N+0KhugwQirDTqUx9Yg
 X/Tpa8rzZEz7A==
X-Virus-Scanned: amavis at mail.cs.ucla.edu
Received: from mail.cs.ucla.edu ([127.0.0.1])
 by localhost (mail.cs.ucla.edu [127.0.0.1]) (amavis, port 10026) with ESMTP
 id oboQNOxcYPak; Mon, 21 Apr 2025 15:32:18 -0700 (PDT)
Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200])
 by mail.cs.ucla.edu (Postfix) with ESMTPSA id 14CDE3C010860;
 Mon, 21 Apr 2025 15:32:18 -0700 (PDT)
Message-ID: <473f2b98-5962-49cb-ae9b-db6c410043bd@HIDDEN>
Date: Mon, 21 Apr 2025 15:32:17 -0700
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN> <m2jz7ddzas.fsf@HIDDEN>
 <jwvtt6h6xhu.fsf-monnier+emacs@HIDDEN>
Content-Language: en-US
From: Paul Eggert <eggert@HIDDEN>
Autocrypt: addr=eggert@HIDDEN; keydata=
 xsFNBEyAcmQBEADAAyH2xoTu7ppG5D3a8FMZEon74dCvc4+q1XA2J2tBy2pwaTqfhpxxdGA9
 Jj50UJ3PD4bSUEgN8tLZ0san47l5XTAFLi2456ciSl5m8sKaHlGdt9XmAAtmXqeZVIYX/UFS
 96fDzf4xhEmm/y7LbYEPQdUdxu47xA5KhTYp5bltF3WYDz1Ygd7gx07Auwp7iw7eNvnoDTAl
 KAl8KYDZzbDNCQGEbpY3efZIvPdeI+FWQN4W+kghy+P6au6PrIIhYraeua7XDdb2LS1en3Ss
 mE3QjqfRqI/A2ue8JMwsvXe/WK38Ezs6x74iTaqI3AFH6ilAhDqpMnd/msSESNFt76DiO1ZK
 QMr9amVPknjfPmJISqdhgB1DlEdw34sROf6V8mZw0xfqT6PKE46LcFefzs0kbg4GORf8vjG2
 Sf1tk5eU8MBiyN/bZ03bKNjNYMpODDQQwuP84kYLkX2wBxxMAhBxwbDVZudzxDZJ1C2VXujC
 OJVxq2kljBM9ETYuUGqd75AW2LXrLw6+MuIsHFAYAgRr7+KcwDgBAfwhPBYX34nSSiHlmLC+
 KaHLeCLF5ZI2vKm3HEeCTtlOg7xZEONgwzL+fdKo+D6SoC8RRxJKs8a3sVfI4t6CnrQzvJbB
 n6gxdgCu5i29J1QCYrCYvql2UyFPAK+do99/1jOXT4m2836j1wARAQABzSBQYXVsIEVnZ2Vy
 dCA8ZWdnZXJ0QGNzLnVjbGEuZWR1PsLBlQQTAQgAPwIbAwYLCQgHAwIGFQgCCQoLBBYCAwEC
 HgECF4AWIQR+N5Kp2Kz31jO8FYjtl+kOYqp+NAUCZiLOewUJHWQLDAAKCRDtl+kOYqp+NHGE
 D/9Wmbk+cAaQsYLPGBvyzIjZIRzo/V2p3ZwckVA1VEQivx5azu1cs86qDoVIe45AtwmKOvdV
 wTQd/QeglkZR6D2YPW7UR/7emajyJZZcy+etVTDKoaw1i6/hmd/CpGjUeUSvgoPs6nYR+1lo
 pSXTpaGrh1W0qQHalSkOOwCHG3HtGk9Ve2AERDUYxmcn8/eZHb7xpUJEJMBBI1bx/zcw1EtB
 rjsQ1R1faJ/r/7LPAyV36RLvnbX69PylHKQEbJoaY9aUb2Vpm63ni3FeTA7/3jpPvaSRWHJh
 vPYx6Fm2Ln8pI0Yf/W2B8QMiPTnF/LnH2kvUcf9VXm+1mQJ3fBFU25HZwBhuqZ24IeKymPEt
 BUMQAum97Dto0jSgR2OUvX7z+twhpQEgRGBzPHYwDi4SxF5Z4Q5Y7B7a++HP9tIxG6CVFIwI
 4xVaZud18bPa0YBL+cISmMgxq7h7yoVXl6u3pm9Yiv+W6Lp9QGN8Rw1VuJMOoFCYuoxG8mXO
 TA5b1jvlQ32gHFFhqErDAhNJRsfgrpe9Gok4Ycp+rWljbvS5Wrl0uth5MP7FbaHN2kmTZibq
 KXAd//IqczhDyU6qnW6ao+h4iDBDgYgRbQjmToX/vmIdEMzvPGqWXKhe/q1TYMuOO+IfP+bI
 fyPFH29nVN/o9c4J7myeKvv3HKSXdSVjlh2V787BTQRMgHJkARAApoXrvxP3DIfjCNOtXU/P
 dwMShKdX/RlSs5PfunV1wbKP8herXHrvQdFVqECaTSxmlhzbk8X0PkY9gcVaU2O49T3qsOd1
 cHeF52YFGEt0LhsBeMjgNX5uZ1V76r8gyeVlFpWWb0SIwJUBHrDXexF67upeRb2vdHBjYDNe
 ySn+0B7gFEqvVmZu+LadudDp6kQLjatFvHQHUSGNshBnkkcaTbiI9Pst0GCc2aiznBiPPA2W
 QxAPlPRh3OGTsn5THADmbjqY6FEMLasVX8DSCblMvLwNeO/8SxziBidhqLpJCqdQRWHku5Xx
 gIkGeKOz5OLDvXHWJyafrEYjjkS6Ak6B5z6svKliClWnjHQcjlPzyoFFgKTEfcqDxCj4RY0D
 0DgtFD0NfyeOidrSB/SzTe2hwryQE3rpSiqo+0cGdzh4yAHKYJ+UrXZ4p93ZhjGfKD1xlrNY
 DlWyW9PGmbvqFuDmiIAQf9WD/wzEfICc+F+uDDI+uYkRxUFp92ykmdhDEFg1yjYsU8iGU69a
 Hyvhq36z4zctvbqhRNzOWB1bVJ/dIMDvsExGcXQVDIT7sDNXv0wE3jKSKpp7NDG1oXUXL+2+
 SF99Kjy753AbQSAmH617fyBNwhJWvQYg+mUvPpiGOtses9EXUI3lS4v0MEaPG43flEs1UR+1
 rpFQWVHo1y1OO+sAEQEAAcLBfAQYAQgAJgIbDBYhBH43kqnYrPfWM7wViO2X6Q5iqn40BQJm
 Is58BQkdZAsMAAoJEO2X6Q5iqn40Q68QAJ9GubS/ej30Vc4idoZdc0IyMcL7kQJbMohF+Tyn
 ZE+TGn9WvzP10yLyzoI0vNlcNfP92d2MS//pFjOuANb5mwyiEYA+rDZIdS4ZZpHxCs2sxMC4
 afLCf3kv4aMnTeBvb9na403dlczz9cAacvsmniSFdpb1+BzMpYbybglU5oYMGhYT2nnCRjXN
 6S2nKYt4mjJeeOuxHrdeqQQdVBNYeNfTcPePeqvZ2+bD6u9yxZtaV+wxdpqglosQvjqhOYz7
 h50/ZTSq70/npoCq44TzdJKttaYvlW6ziRz0g4RRAqZyoxjYXiy5qj8r8zXJuB11ApZCGuKn
 /usbji9RYbflAhxFeh4LMmpDVi6BrF30b73Md59K7PuEKN1NxzlWiqqQHZZ9momN0GXLPcGq
 4uyfq7yVEy7wP5PMOh6oqscKklE3gFQtq0P1Ki0xqdF6Fq5LPJc+0Db2CYkVIy7Xaa/f74I3
 sOfQfEeDylVXR5iDfUJEYv/0DYhOr7q5/0b1kh3M4wkrB4C5jVNHjIIj+RsAK90c3t38OhAl
 jiSN7Bkwy24Afy8eIu6wWzvhnsQGpZPB+IffmxT1wkTy8UxZKjUWV0C82iphVgCUUi2f9sDV
 Q/tNcwVWmOS+gdv9Wk6tdGeM+Ee+Qs6YG05jcSoajzF0TL07ajLcayRq2j1Os2CtQ8qu
Organization: UCLA Computer Science Department
In-Reply-To: <jwvtt6h6xhu.fsf-monnier+emacs@HIDDEN>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

On 4/21/25 14:11, Stefan Monnier wrote:
> Paul, IIUC you've played with this algorithm.  Would you be tempted to
> try and improve that situation where the replacement text is*much*
> smaller the text it replaces?

My quick reaction is that you'd need a different algorithm than the 
Myers-Ukkonen algorithm used by GNU diff etc. A good place to start 
might be here:

A. Andoni, R. Krauthgamer and K. Onak, "Polylogarithmic Approximation 
for Edit Distance and the Asymmetric Query Complexity," FOCS 2010, 
377-386, <https://doi.org/10.1109/FOCS.2010.43>.

... though this is just the tip of an iceberg that I haven't had time to 
look into. If there's real interest in this (it'd be some work) I can 
ask a colleague who's more of an expert....

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Stefan Monnier <monnier@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Tue, 22 Apr 2025 02:48:02 +0000
Resent-Message-ID: <handler.77942.B77942.174529008129261 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Paul Eggert <eggert@HIDDEN>
Cc: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>, 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174529008129261
          (code B ref 77942); Tue, 22 Apr 2025 02:48:02 +0000
Received: (at 77942) by debbugs.gnu.org; 22 Apr 2025 02:48:01 +0000
Received: from localhost ([127.0.0.1]:42133 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u73g0-0007br-Jw
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 22:48:01 -0400
Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:31282)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <monnier@HIDDEN>)
 id 1u73fy-0007ba-5A
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 22:47:59 -0400
Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1])
 by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id DBBF6442531;
 Mon, 21 Apr 2025 22:47:51 -0400 (EDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca;
 s=mail; t=1745290050;
 bh=UnzWPZGfv4H7ox9xzb+O9WCPBFf/jWati9Lq5r2iTW0=;
 h=From:To:Cc:Subject:In-Reply-To:References:Date:From;
 b=XcJRppUknvYE5B0JjUVh0kHvZWrXiW2kB3M+QH9ewYZQrPo74SXogxcqCJDJh7I2P
 4vSVtuVvQmzGB7cG/n5Q3i4pCZ0qKmHYmKN2Ou+mpK3lD+Wel8aOhTDJe5qsFYHATG
 IpGC7qR3Av295hX/CqljddeKZoonU92Ahkjsa5LRpnpXp7btfJA14H6hFMZ1wykdEA
 wC+oYnafKJv/Q0UuV82k3rkspwvO2ds2OZ9b9phHtEY4dpi0NZFUzYJEO7mgXEe+V+
 gLGLPCDD5Gn4adi36m28Q46w/JdupBmL9if1x8MlYuLq4xv6+npCinJtuC2viz7XK2
 jBSbWwghWRx8A==
Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1])
 by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id B7769442297;
 Mon, 21 Apr 2025 22:47:30 -0400 (EDT)
Received: from pastel (104-195-208-18.cpe.teksavvy.com [104.195.208.18])
 by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 88EF71201DE;
 Mon, 21 Apr 2025 22:47:30 -0400 (EDT)
From: Stefan Monnier <monnier@HIDDEN>
In-Reply-To: <473f2b98-5962-49cb-ae9b-db6c410043bd@HIDDEN>
Message-ID: <jwvy0vt547i.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN> <m2jz7ddzas.fsf@HIDDEN>
 <jwvtt6h6xhu.fsf-monnier+emacs@HIDDEN>
 <473f2b98-5962-49cb-ae9b-db6c410043bd@HIDDEN>
Date: Mon, 21 Apr 2025 22:47:22 -0400
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain
X-SPAM-INFO: Spam detection results:  0
 ALL_TRUSTED                -1 Passed through trusted hosts only via SMTP
 AWL -0.019 Adjusted score from AWL reputation of From: address
 BAYES_00                 -1.9 Bayes spam probability is 0 to 1%
 DKIM_SIGNED               0.1 Message has a DKIM or DK signature,
 not necessarily valid
 DKIM_VALID -0.1 Message has at least one valid DKIM or DK signature
 DKIM_VALID_AU -0.1 Message has a valid DKIM or DK signature from author's
 domain
 DKIM_VALID_EF -0.1 Message has a valid DKIM or DK signature from envelope-from
 domain
 KAM_SHORT               0.001 Use of a URL Shortener for very short URL
X-SPAM-LEVEL: 
X-Spam-Score: -1.3 (-)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -2.3 (--)

>> Paul, IIUC you've played with this algorithm.  Would you be tempted to
>> try and improve that situation where the replacement text is*much*
>> smaller the text it replaces?
>
> My quick reaction is that you'd need a different algorithm than the
> Myers-Ukkonen algorithm used by GNU diff etc. A good place to start might be
> here:
>
> A. Andoni, R. Krauthgamer and K. Onak, "Polylogarithmic Approximation for
>  Edit Distance and the Asymmetric Query Complexity," FOCS 2010, 377-386,
> <https://doi.org/10.1109/FOCS.2010.43>.
>
> ... though this is just the tip of an iceberg that I haven't had time to
>  look into. If there's real interest in this (it'd be some work) I can ask
> a colleague who's more of an expert....

I don't think I have the time&energy to look into it.

But the issue at hand is that in Gerd's example, the diff code takes
a *really* long time (even though it has already found an optimal
answer, AFAICT), and more importantly: without calling the
XVECREF_YVECREF_EQUAL function, which prevents us from aborting the
operation with a timeout.

For example, if I interrupt the execution I found it is in `diag` in the
following loop:

      for (d = fmax; d >= fmin; d -= 2)
        {
          OFFSET x;
          OFFSET y;
          OFFSET tlo = fd[d - 1];
          OFFSET thi = fd[d + 1];
          OFFSET x0 = tlo < thi ? thi : tlo + 1;

          for (x = x0, y = x0 - d;
               x < xlim && y < ylim && XREF_YREF_EQUAL (x, y);
               x++, y++)
            continue;
          if (x - x0 > SNAKE_LIMIT)
            big_snake = true;
          fd[d] = x;
          if (odd && bmin <= d && d <= bmax && bd[d] <= x)
            {
              part->xmid = x;
              part->ymid = y;
              part->lo_minimal = part->hi_minimal = true;
              return;
            }
        }

where (in our case when we replace a very large region with
a short string), the `y < ylim` is apparently always false (once the
first 74 calls to `XVECREF_YVECREF_EQUAL` took place):

    (gdb) p x
    $1 = 51823
    (gdb) p xlim
    $2 = 489755
    (gdb) p y
    $3 = <optimized out>
    (gdb) p ylim
    $4 = 14
    (gdb) p x0
    $5 = 51823
    (gdb) p d
    $6 = 41094
    (gdb) p x0 - d
    $7 = 10729

I don't understand this code enough, but I get the impression that we
might be able to streamline this loop once we get to that state because
every iteration seems to do very little useful work that does not change
between iterations (clearly this depends on being able to detect "that
state", which depends on the `tlo` and `thi` we read from the array, so
it might require keeping track somewhere of the min/max values stored in
the `fd` array?).

The same probably happens for the loop that follows (and does the same
but for "the bottom-up search", according to the comment).

I'm hoping you understand enough of the algorithm and of what I'm saying
to be able to tell me if I'm making sense.


        Stefan

Message sent to bug-gnu-emacs@HIDDEN:

X-Loop: help-debbugs@HIDDEN
Subject: bug#77942: 31.0.50; replace-region-contents gets stuck
Resent-From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Tue, 22 Apr 2025 03:49:02 +0000
Resent-Message-ID: <handler.77942.B77942.174529370611801 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
X-GNU-PR-Message: followup 77942
X-GNU-PR-Package: emacs
X-GNU-PR-Keywords: 
To: Stefan Monnier <monnier@HIDDEN>
Cc: Paul Eggert <eggert@HIDDEN>, 77942 <at> debbugs.gnu.org
Received: via spool by 77942-submit <at> debbugs.gnu.org id=B77942.174529370611801
          (code B ref 77942); Tue, 22 Apr 2025 03:49:02 +0000
Received: (at 77942) by debbugs.gnu.org; 22 Apr 2025 03:48:26 +0000
Received: from localhost ([127.0.0.1]:42561 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u74cU-00034G-G3
	for submit <at> debbugs.gnu.org; Mon, 21 Apr 2025 23:48:26 -0400
Received: from mail-wr1-x42e.google.com ([2a00:1450:4864:20::42e]:53577)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
 (Exim 4.84_2) (envelope-from <gerd.moellmann@HIDDEN>)
 id 1u74cR-00033y-Lx
 for 77942 <at> debbugs.gnu.org; Mon, 21 Apr 2025 23:48:25 -0400
Received: by mail-wr1-x42e.google.com with SMTP id
 ffacd0b85a97d-391342fc0b5so3789498f8f.3
 for <77942 <at> debbugs.gnu.org>; Mon, 21 Apr 2025 20:48:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1745293697; x=1745898497; darn=debbugs.gnu.org;
 h=mime-version:user-agent:message-id:date:references:in-reply-to
 :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to;
 bh=0ILVcbIRzVj4pDoIpWwy0KO2u10/toVUV8ySsinkCbU=;
 b=XC9oq3SLwcivQrT5N2rwqR2Ds9EGHCdchhTtBR86OH43yLuWAxA9L3RYtnErGkLkiV
 9F63kcKB1aVmzP1WRSoiXVmpUwBsVOxdBSmMsy4B3QInE2BbJAxyFdVSA+i9D2SlrKJg
 HM9/CQsBrJ8vCGk3DFIg8icfNE+uCiyeFiZ1dE/aMNmKL6ZHE75+MFxuGpEBpI9AoXzI
 uCZBM2kjvIUOgMUufNqkwQ9F6uXGO5jvx+/l531sk+fp8KhBOAPEX57/LHSCtY9BaLr7
 ok5MkvXRnB9jYQYaKmHp0abjUAHsi5V1BcwEEM4NsO2NX52ajzR+PLMa+3pykzeAvOFa
 ny3g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1745293697; x=1745898497;
 h=mime-version:user-agent:message-id:date:references:in-reply-to
 :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date
 :message-id:reply-to;
 bh=0ILVcbIRzVj4pDoIpWwy0KO2u10/toVUV8ySsinkCbU=;
 b=E8m8lHCjG+tUMs2mjQbfPMoItqa123dB4Y5Fg+cIKvp+0oMvi5ndaRGagRJCR+f2Jb
 bJdg2uHZTyrPD0REt+GaKPASZOmQK8fFyUP/hmo+sfurCFwuQ+U4HNgED+MAwz43HV/3
 DfyCqNcDnaP2XQ97EzKoU/qVtP4o7EdgfzNldXw1GqTfHU8P4CTW2hWIg4qQooQIH0WQ
 MN+3sL4u/YeRCbWqhKJWKM/n59L5XdQPSzJjAC32tH1GTAXCiqaxpjTKABShkJe9Pkip
 TXZOu5MW9CLp8rqQi21lRkMMlwiPxtDmkdfjy8pcxwT1FMourXEIf6J+I/BUir7r0iiW
 u7Zg==
X-Gm-Message-State: AOJu0Yw2bApZMI7TW9USMGEW7406RoX9TqdA/jZtd/fsFC8PdIf+Ts20
 yR9avvsa0+zF/Lxfy6L8XZ2R3ksulEoEN3L5PbjvIvQ3W1h8fJiK
X-Gm-Gg: ASbGnctad6S0JgFcxQ3CGMiiXxkWxOxd1i/pU82C9r+mlHO+W4LvGsNPqSeWbj/gxJ3
 yM7zdkZ8RobL6Q3UlFTnxPJXBPcsuhNEifSDAExvqVoug1SdS121hhUiJv9uRSJWpySdie+Y92e
 x/O41vgja7s9Rbr+CCl6sVofcEg0a3X6qnvst8mL7QYu36RPkusCrO7uS/PuXER9mKXHpngAdp1
 rPr22dXFFLPx9T5v/fImss9198Pg+sfnMjajz1qBRvIo1aSC+REsnE2g/MKNxoRRqhJyHSULY5T
 0n1CDHymGdl5aElhALsT3lY3CoZCKhtmpv2Lj30JJqpKTP/Yaw8DaUnwXDx/ybWlf/JPAotUgXR
 ab+RhPzDbosjwaGmvAvgfE3TLc54gAnUzQqie8X0lt2z8thAbzS/5AdU=
X-Google-Smtp-Source: AGHT+IH0h3e+1SP3dD4jFh5yY+GFYQ5jQO5DF4uQq5n8dLz7FYCTdv7LVV5sillOFgXuUwGzbs/vYg==
X-Received: by 2002:a05:6000:240c:b0:39c:1257:cc25 with SMTP id
 ffacd0b85a97d-39efbb0938emr11748378f8f.56.1745293697046; 
 Mon, 21 Apr 2025 20:48:17 -0700 (PDT)
Received: from pro2 (p200300e0b7301900b98b74cfc94b2689.dip0.t-ipconnect.de.
 [2003:e0:b730:1900:b98b:74cf:c94b:2689])
 by smtp.gmail.com with ESMTPSA id
 ffacd0b85a97d-39efa4332b2sm13861994f8f.30.2025.04.21.20.48.14
 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
 Mon, 21 Apr 2025 20:48:16 -0700 (PDT)
From: Gerd =?UTF-8?Q?M=C3=B6llmann?= <gerd.moellmann@HIDDEN>
In-Reply-To: <jwvtt6h6xhu.fsf-monnier+emacs@HIDDEN>
References: <m2zfga4zt8.fsf@HIDDEN> <jwvjz7d8mus.fsf-monnier+emacs@HIDDEN>
 <m2wmbde6m0.fsf@HIDDEN> <m2jz7ddzas.fsf@HIDDEN>
 <jwvtt6h6xhu.fsf-monnier+emacs@HIDDEN>
Date: Tue, 22 Apr 2025 05:48:14 +0200
Message-ID: <m2bjsoeu0x.fsf@HIDDEN>
User-Agent: Gnus/5.13 (Gnus v5.13)
MIME-Version: 1.0
Content-Type: text/plain
X-Spam-Score: 0.0 (/)
X-BeenThere: debbugs-submit <at> debbugs.gnu.org
X-Mailman-Version: 2.1.18
Precedence: list
List-Id: <debbugs-submit.debbugs.gnu.org>
List-Unsubscribe: <https://debbugs.gnu.org/cgi-bin/mailman/options/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=unsubscribe>
List-Archive: <https://debbugs.gnu.org/cgi-bin/mailman/private/debbugs-submit/>
List-Post: <mailto:debbugs-submit <at> debbugs.gnu.org>
List-Help: <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=help>
List-Subscribe: <https://debbugs.gnu.org/cgi-bin/mailman/listinfo/debbugs-submit>, 
 <mailto:debbugs-submit-request <at> debbugs.gnu.org?subject=subscribe>
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
X-Spam-Score: -1.0 (-)

Stefan Monnier <monnier@HIDDEN> writes:

> Gerd, IIUC you're trying to use this to benchmark the charpos->bytepos
> code, in which case you should be better served by a call where the text
> and its replacement are of fairly similar size.

That's right, it's for a bencnmark that helps me to get an impression if
avoiding the binary search in the charpos -> bytepos case is worth it.
Now that I know what replace-region-contents does, that's no problem.

But honestly, what the heck? Does someone know what this diffing is
about in the first place? I mean, that replacing a region takes O(ND) is
not something that I would have thought possible.

Last modified: Tue, 22 Apr 2025 04:00:02 UTC

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