GNU bug report logs - #77684
[PATCH] ; * lisp/emacs-lisp/vtable.el (vtable--limit-string): Use binary search

Please note: This is a static page, with minimal formatting, updated once a day.
Click here to see this page with the latest information and nicer formatting.

Package: emacs; Reported by: Kristoffer Balintona <krisbalintona@HIDDEN>; Keywords: patch; Done: Eli Zaretskii <eliz@HIDDEN>; Maintainer for emacs is bug-gnu-emacs@HIDDEN.

Message received at 77684-done <at> debbugs.gnu.org:

Received: (at 77684-done) by debbugs.gnu.org; 23 Apr 2025 12:06:31 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Apr 23 08:06:30 2025
Received: from localhost ([127.0.0.1]:55217 helo=debbugs.gnu.org)
	by debbugs.gnu.org with esmtp (Exim 4.84_2)
	(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
	id 1u7Ys1-0002Vu-Iu
	for submit <at> debbugs.gnu.org; Wed, 23 Apr 2025 08:06:30 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10]:51752)
 by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.84_2) (envelope-from <eliz@HIDDEN>) id 1u7Yrx-0002UF-Dd
 for 77684-done <at> debbugs.gnu.org; Wed, 23 Apr 2025 08:06:26 -0400
Received: from fencepost.gnu.org ([2001:470:142:3::e])
 by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
 (Exim 4.90_1) (envelope-from <eliz@HIDDEN>)
 id 1u7Yrr-0000XW-Dq; Wed, 23 Apr 2025 08:06:19 -0400
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org;
 s=fencepost-gnu-org; h=References:Subject:In-Reply-To:To:From:Date:
 mime-version; bh=UEhim9tqNPN228BU+hi58YlhLsbrwCAImIuWZoMkv0U=; b=pnOUU33SUUrQ
 i3QnqxlRTtLyhwbYGt2FJ//VSgykBwi90tZD1K4Upfl1+zGIkBF1Tp3z2XFIzAbOQsaSXPFhBRIvH
 7W60znZXIBEWKJOu3YRmwq/WglNhZ3T0fbXKfYgqwiyZc7atCyWPWKJKC8c9y79WTbEK4P3hFieYc
 XGpt59IFxkPRvx1yuRIUfJvWvq/Yo3rWMGUInY9jnKGV4+9ftc4Odk1pdObaeUi75PZT+/vBhsmM+
 iznXAEZ/FgtIiFCQBAd9VhOHUikzBwBrfB8AZoQ2rSPcW9eoy2V5Of6vh9NBUE4S5kI0BEPLfHqxU
 Y9H9ZjWBARV43ne1j0eIug==;
Date: Wed, 23 Apr 2025 15:06:07 +0300
Message-Id: <86frhz13rk.fsf@HIDDEN>
From: Eli Zaretskii <eliz@HIDDEN>
To: Kristoffer Balintona <krisbalintona@HIDDEN>
In-Reply-To: <CANVbq5kykGQsBiitCzPnXpWMc3BXzB2J=KH01O-L6n5BqY8Gxw@HIDDEN>
 (message from Kristoffer Balintona on Tue, 22 Apr 2025 17:36:32 -0400)
Subject: Re: bug#77684: [PATCH] ; * lisp/emacs-lisp/vtable.el
 (vtable--limit-string): Use binary search
References: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@HIDDEN>
 <861ptwl8dd.fsf@HIDDEN>
 <CANVbq5kzNPJaAHr5YhnsAWkzF=YVm_DEkZ7Ei8Mf5CMJ=1gg0w@HIDDEN>
 <861pttj2wn.fsf@HIDDEN>
 <CANVbq5kykGQsBiitCzPnXpWMc3BXzB2J=KH01O-L6n5BqY8Gxw@HIDDEN>
X-Spam-Score: -2.3 (--)
X-Debbugs-Envelope-To: 77684-done
Cc: 77684-done <at> debbugs.gnu.org
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 (---)

> From: Kristoffer Balintona <krisbalintona@HIDDEN>
> Date: Tue, 22 Apr 2025 17:36:32 -0400
> Cc: 77684 <at> debbugs.gnu.org
> 
> On Tue, Apr 15 2025, Eli Zaretskii wrote:
> 
> > Perhaps we could still use binary search, but augment it as follows:
> > when a match is found by binary search, run an additional loop, which
> > adds back one character at a time, as long as string-pixel-width
> > returns the same value.  The last character added which still yields
> > the same value will be the point where to truncate the string.
> >
> > For long enough strings, this might still be a win, even if characters
> > are composed.  And for the simple case of characters that are not
> > composed, this adds just one extra call to string-pixel-width.
> 
> Thank you for the suggestion, Eli. Unfortunately, I wasn't able to find
> an implementation that worked exhaustively. I ran into trouble I
> couldn't resolve when the match returned by the binary search landed
> within a ligature/emoji (which can span multiple characters without
> necessarily changing the pixel width in predictable, monotonic ways).
> 
> Aside from those cases, I think the binary search works quite well.
> However, since it doesn't cover all the cases the current implementation
> does, I think the current implementation should be kept.
> 
> I may return to this in the future, but for now I think if developers
> need performance, they should set the displayer themselves (which I will
> do for my own personal projects).

Thanks.  So let's close this bug for now.  If someone has clever ideas
how to speed up vtable--limit-string, we can always reopen.

Notification sent to Kristoffer Balintona <krisbalintona@HIDDEN>:
bug acknowledged by developer. Full text available.

Reply sent to Eli Zaretskii <eliz@HIDDEN>:
You have taken responsibility. Full text available.