GNU logs - #77684, boring messages

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#77684: [PATCH] ; * lisp/emacs-lisp/vtable.el (vtable--limit-string): Use binary search
Resent-From: Kristoffer Balintona <krisbalintona@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Thu, 10 Apr 2025 00:14:02 +0000
Resent-Message-ID: <handler.77684.B.17442440076955 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: 77684 <at> debbugs.gnu.org
From: Kristoffer Balintona <krisbalintona@HIDDEN>
MIME-Version: 1.0
Date: Wed, 9 Apr 2025 17:13:10 -0700
Message-ID: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@HIDDEN>
Content-Type: multipart/mixed; boundary="0000000000008f99b406326173b5"
Received-SPF: pass client-ip=2a00:1450:4864:20::134;
 envelope-from=krisbalintona@HIDDEN; helo=mail-lf1-x134.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 (/)

--0000000000008f99b406326173b5
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Tags: patch

Hello,

Attached is a patch to vtable.el that improves the performance of
vtable-limit-string. This is because of the expensive calls to
string-pixel-width.

The current implementation of the function is O(n), whereas the version
in the attached patch uses a binary search, which has an improved time
complexity of O(n).

I discovered how expensive vtable-limit-string is when working on a
personal project of mine that creates vtables with hundreds of rows.
According to profiler-report, it was by far the largest bottleneck.

Below are two basic benchmarks that show the markedly improved
performance of the version in the attached patch:

        (benchmark-run-compiled 10
          (let ((buf-name "*temp*"))
            (get-buffer-create buf-name)
            ;; The function below is defined by my own project.  It
creates a vtable
            ;; in buffer named BUF-NAME
            (org-roam-folgezettel-list buf-name)
            (kill-buffer buf-name)))
        ;; Original (with GC): (16.77486223 17 6.687552347000008)
        ;; Proposed (with GC): (4.469360591 5 1.919122549000008)


        (let ((gc-cons-threshold most-positive-fixnum))
          (benchmark-run-compiled 10
            (let ((buf-name "*temp*"))
              (get-buffer-create buf-name)
              ;; The function below is defined by my own project.  It
creates a vtable
              ;; in buffer named BUF-NAME
              (org-roam-folgezettel-list buf-name)
              (kill-buffer buf-name))))
        ;; Original (no GC): (10.767429898 0 0.0)
        ;; Proposed (no GC): (2.299831031 0 0.0)


This is my first patch to Emacs, so please let me know if I=E2=80=99ve miss=
ed
any conventions for properly contributing.



In GNU Emacs 31.0.50 (build 1, x86_64-pc-linux-gnu, GTK+ Version
 3.24.49, cairo version 1.18.4) of 2025-03-31 built on UnoriginalName
Windowing system distributor 'Microsoft Corporation', version 11.0.12010000
System Description: Arch Linux

Configured using:
 'configure 'CFLAGS=3D-O2 -march=3Dnative -mtune=3Dnative
 -fomit-frame-pointer' --with-mailutils --with-gtk --with-dbus
 --with-native-compilation'


--=20
With appreciation,
Kristoffer

--0000000000008f99b406326173b5
Content-Type: text/patch; charset="US-ASCII"; 
	name="0001-lisp-emacs-lisp-vtable.el-vtable-limit-string-Use-bi.patch"
Content-Disposition: attachment; 
	filename="0001-lisp-emacs-lisp-vtable.el-vtable-limit-string-Use-bi.patch"
Content-Transfer-Encoding: base64
X-Attachment-Id: 49a071b019e95f75_0.1

RnJvbSA0MWEyNWYxNGMzMGI2NzI0MTU2YzNhNWFjYzM5N2NhYTZmM2FlYWM1IE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBLcmlzdG9mZmVyIEJhbGludG9uYSA8a3Jpc2JhbGludG9uYUBn
bWFpbC5jb20+CkRhdGU6IFdlZCwgOSBBcHIgMjAyNSAxODo1MDo0OCAtMDUwMApTdWJqZWN0OiBb
UEFUQ0hdIDsgKiBsaXNwL2VtYWNzLWxpc3AvdnRhYmxlLmVsICh2dGFibGUtLWxpbWl0LXN0cmlu
Zyk6IFVzZQogYmluYXJ5IHNlYXJjaC4KCi0tLQogbGlzcC9lbWFjcy1saXNwL3Z0YWJsZS5lbCB8
IDE5ICsrKysrKysrKysrKysrKy0tLS0KIDEgZmlsZSBjaGFuZ2VkLCAxNSBpbnNlcnRpb25zKCsp
LCA0IGRlbGV0aW9ucygtKQoKZGlmZiAtLWdpdCBhL2xpc3AvZW1hY3MtbGlzcC92dGFibGUuZWwg
Yi9saXNwL2VtYWNzLWxpc3AvdnRhYmxlLmVsCmluZGV4IDAwNzg1MTEzZWRiLi4yNjY1Nzc0NDJm
OCAxMDA2NDQKLS0tIGEvbGlzcC9lbWFjcy1saXNwL3Z0YWJsZS5lbAorKysgYi9saXNwL2VtYWNz
LWxpc3AvdnRhYmxlLmVsCkBAIC04NDAsMTAgKzg0MCwyMSBAQCB2dGFibGUtLXNldC1oZWFkZXIt
bGluZQogICAodnRhYmxlLWhlYWRlci1tb2RlIDEpKQogCiAoZGVmdW4gdnRhYmxlLS1saW1pdC1z
dHJpbmcgKHN0cmluZyBwaXhlbHMpCi0gICh3aGlsZSAoYW5kIChsZW5ndGg+IHN0cmluZyAwKQot
ICAgICAgICAgICAgICAoPiAoc3RyaW5nLXBpeGVsLXdpZHRoIHN0cmluZykgcGl4ZWxzKSkKLSAg
ICAoc2V0cSBzdHJpbmcgKHN1YnN0cmluZyBzdHJpbmcgMCAoMS0gKGxlbmd0aCBzdHJpbmcpKSkp
KQotICBzdHJpbmcpCisgICJSZXR1cm4gdGhlIGxvbmdlc3QgcHJlZml4IG9mIFNUUklORyB3aG9z
ZSBwaXhlbCB3aWR0aCBpcyA8PSBQSVhFTFMuIgorICA7OyBQZXJmb3JtIGEgYmluYXJ5IHNlYXJj
aC4gIFRoaXMgaXMgbW9yZSBwZXJmb3JtYW50IHRoYW4gaXRlcmF0aW5nCisgIDs7IHRocm91Z2gg
ZWFjaCBjaGFyYWN0ZXIgaW4gc2VxdWVuY2UuCisgIChsZXQgKChsb3cgMCkKKyAgICAgICAgKGhp
Z2ggKDEtIChsZW5ndGggc3RyaW5nKSkpCisgICAgICAgIHJlc3VsdCkKKyAgICAod2hpbGUgKDw9
IGxvdyBoaWdoKQorICAgICAgKGxldCogKChtaWQgKGZsb29yICgrIGxvdyBoaWdoKSAyKSkKKyAg
ICAgICAgICAgICAoY2FuZGlkYXRlIChzdWJzdHJpbmcgc3RyaW5nIDAgbWlkKSkKKyAgICAgICAg
ICAgICAod2lkdGggKHN0cmluZy1waXhlbC13aWR0aCBjYW5kaWRhdGUpKSkKKyAgICAgICAgKGlm
ICg8PSB3aWR0aCBwaXhlbHMpCisgICAgICAgICAgICAoc2V0cSByZXN1bHQgY2FuZGlkYXRlCisg
ICAgICAgICAgICAgICAgICBsb3cgKDErIG1pZCkpCisgICAgICAgICAgKHNldHEgaGlnaCAoMS0g
bWlkKSkpKSkKKyAgICByZXN1bHQpKQogCiAoZGVmdW4gdnRhYmxlLS1jaGFyLXdpZHRoICh0YWJs
ZSkKICAgKHN0cmluZy1waXhlbC13aWR0aCAocHJvcGVydGl6ZSAieCIgJ2ZhY2UgKHZ0YWJsZS1m
YWNlIHRhYmxlKSkpKQotLSAKMi40OS4wCgo=
--0000000000008f99b406326173b5--

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: Kristoffer Balintona <krisbalintona@HIDDEN>
Subject: bug#77684: Acknowledgement ([PATCH] ; * lisp/emacs-lisp/vtable.el
 (vtable--limit-string): Use binary search)
Message-ID: <handler.77684.B.17442440076955.ack <at> debbugs.gnu.org>
References: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@HIDDEN>
X-Gnu-PR-Message: ack 77684
X-Gnu-PR-Package: emacs
X-Gnu-PR-Keywords: patch
Reply-To: 77684 <at> debbugs.gnu.org
Date: Thu, 10 Apr 2025 00:14:02 +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 77684 <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
77684: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D77684
GNU Bug Tracking System
Contact help-debbugs@HIDDEN with problems

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#77684: [PATCH] ; * lisp/emacs-lisp/vtable.el (vtable--limit-string): Use binary search
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, 13 Apr 2025 09:28:03 +0000
Resent-Message-ID: <handler.77684.B77684.174453644130272 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Kristoffer Balintona <krisbalintona@HIDDEN>
Cc: 77684 <at> debbugs.gnu.org
Date: Sun, 13 Apr 2025 12:26:54 +0300
Message-Id: <861ptwl8dd.fsf@HIDDEN>
From: Eli Zaretskii <eliz@HIDDEN>
In-Reply-To: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@HIDDEN>
 (message from Kristoffer Balintona on Wed, 9 Apr 2025 17:13:10 -0700)
References: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@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: Kristoffer Balintona <krisbalintona@HIDDEN>
> Date: Wed, 9 Apr 2025 17:13:10 -0700
> 
> Attached is a patch to vtable.el that improves the performance of
> vtable-limit-string. This is because of the expensive calls to
> string-pixel-width.
> 
> The current implementation of the function is O(n), whereas the version
> in the attached patch uses a binary search, which has an improved time
> complexity of O(n).
> 
> I discovered how expensive vtable-limit-string is when working on a
> personal project of mine that creates vtables with hundreds of rows.
> According to profiler-report, it was by far the largest bottleneck.

Binary search will only work if adding or removing a character will
always change the result of string-pixel-width.  But this is not true
in general, due to character composition and other Emacs display
features.  Here's a simple example of such an issue:

  (string-pixel-width "a")
   => 9
  (string-pixel-width (concat "a" "́"))
   => 9

So adding a character doesn't affect the result of string-pixel-width,
in this case because the two characters will be displayed by a single
glyph that combines the base character 'a' and the acute accent.

Did you try your modified code in such situations, or did you only try
it with simple characters that never combine?

Message sent to bug-gnu-emacs@HIDDEN:

Subject: bug#77684: [PATCH] ; * lisp/emacs-lisp/vtable.el (vtable--limit-string): Use binary search
Resent-From: Ship Mints <shipmints@HIDDEN>
Original-Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>
Resent-CC: bug-gnu-emacs@HIDDEN
Resent-Date: Sun, 13 Apr 2025 11:16:05 +0000
Resent-Message-ID: <handler.77684.B77684.17445429324761 <at> debbugs.gnu.org>
Resent-Sender: help-debbugs@HIDDEN
To: Eli Zaretskii <eliz@HIDDEN>
Cc: 77684 <at> debbugs.gnu.org, Kristoffer Balintona <krisbalintona@HIDDEN>
MIME-Version: 1.0
References: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@HIDDEN>
 <861ptwl8dd.fsf@HIDDEN>
In-Reply-To: <861ptwl8dd.fsf@HIDDEN>
From: Ship Mints <shipmints@HIDDEN>
Date: Sun, 13 Apr 2025 07:15:11 -0400
Message-ID: <CAN+1HbrHQUGyg0BEMVQpHocCUNqmW=PsVjLe7mTu8haRa7mk7w@HIDDEN>
Content-Type: multipart/alternative; boundary="00000000000032ec690632a70df7"
Precedence: list
Errors-To: debbugs-submit-bounces <at> debbugs.gnu.org
Sender: "Debbugs-submit" <debbugs-submit-bounces <at> debbugs.gnu.org>

--00000000000032ec690632a70df7
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Sun, Apr 13, 2025 at 5:28=E2=80=AFAM Eli Zaretskii <eliz@HIDDEN> wrote:

> > From: Kristoffer Balintona <krisbalintona@HIDDEN>
> > Date: Wed, 9 Apr 2025 17:13:10 -0700
> >
> > Attached is a patch to vtable.el that improves the performance of
> > vtable-limit-string. This is because of the expensive calls to
> > string-pixel-width.
> >
> > The current implementation of the function is O(n), whereas the version
> > in the attached patch uses a binary search, which has an improved time
> > complexity of O(n).
> >
> > I discovered how expensive vtable-limit-string is when working on a
> > personal project of mine that creates vtables with hundreds of rows.
> > According to profiler-report, it was by far the largest bottleneck.
>
> Binary search will only work if adding or removing a character will
> always change the result of string-pixel-width.  But this is not true
> in general, due to character composition and other Emacs display
> features.  Here's a simple example of such an issue:
>
>   (string-pixel-width "a")
>    =3D> 9
>   (string-pixel-width (concat "a" "=CC=81"))
>    =3D> 9
>
> So adding a character doesn't affect the result of string-pixel-width,
> in this case because the two characters will be displayed by a single
> glyph that combines the base character 'a' and the acute accent.
>
> Did you try your modified code in such situations, or did you only try
> it with simple characters that never combine?
>

You can avoid the cost of this string metric by supplying your own global
displayer function for the table or a column-specific displayer function.

Apropos timing as I've been spending some time with vtable and I have a
bunch of bug fixes and a few enhancements coming.  One will slow down that
function a little more...vtable breaks under remapped fonts; e.g., when
using text-scale-adjust so I've fixed that (I have some pixel adjustments
left on the header which still gets out of alignment a little).

--00000000000032ec690632a70df7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"fon=
t-family:monospace"><span style=3D"font-family:Arial,Helvetica,sans-serif">=
On Sun, Apr 13, 2025 at 5:28=E2=80=AFAM Eli Zaretskii &lt;<a href=3D"mailto=
:eliz@HIDDEN">eliz@HIDDEN</a>&gt; wrote:</span></div></div><div class=3D"=
gmail_quote gmail_quote_container"><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">&gt; From: Kristoffer Balintona &lt;<a href=3D"mailto:krisbalint=
ona@HIDDEN" target=3D"_blank">krisbalintona@HIDDEN</a>&gt;<br>
&gt; Date: Wed, 9 Apr 2025 17:13:10 -0700<br>
&gt; <br>
&gt; Attached is a patch to vtable.el that improves the performance of<br>
&gt; vtable-limit-string. This is because of the expensive calls to<br>
&gt; string-pixel-width.<br>
&gt; <br>
&gt; The current implementation of the function is O(n), whereas the versio=
n<br>
&gt; in the attached patch uses a binary search, which has an improved time=
<br>
&gt; complexity of O(n).<br>
&gt; <br>
&gt; I discovered how expensive vtable-limit-string is when working on a<br=
>
&gt; personal project of mine that creates vtables with hundreds of rows.<b=
r>
&gt; According to profiler-report, it was by far the largest bottleneck.<br=
>
<br>
Binary search will only work if adding or removing a character will<br>
always change the result of string-pixel-width.=C2=A0 But this is not true<=
br>
in general, due to character composition and other Emacs display<br>
features.=C2=A0 Here&#39;s a simple example of such an issue:<br>
<br>
=C2=A0 (string-pixel-width &quot;a&quot;)<br>
=C2=A0 =C2=A0=3D&gt; 9<br>
=C2=A0 (string-pixel-width (concat &quot;a&quot; &quot;=CC=81&quot;))<br>
=C2=A0 =C2=A0=3D&gt; 9<br>
<br>
So adding a character doesn&#39;t affect the result of string-pixel-width,<=
br>
in this case because the two characters will be displayed by a single<br>
glyph that combines the base character &#39;a&#39; and the acute accent.<br=
>
<br>
Did you try your modified code in such situations, or did you only try<br>
it with simple characters that never combine?<br></blockquote><div><br></di=
v><div class=3D"gmail_default" style=3D"font-family:monospace">You can avoi=
d the cost of this string metric by supplying your own global displayer fun=
ction for the table or a column-specific displayer function.</div><div clas=
s=3D"gmail_default" style=3D"font-family:monospace"><br></div><div class=3D=
"gmail_default" style=3D"font-family:monospace">Apropos timing as I&#39;ve =
been spending some time with vtable and I have a bunch of bug fixes and a f=
ew enhancements coming.=C2=A0 One will slow down that function a little mor=
e...vtable breaks under remapped fonts; e.g., when using text-scale-adjust =
so I&#39;ve fixed that (I have some pixel adjustments left on the header wh=
ich still gets out of alignment a little).</div></div></div>

--00000000000032ec690632a70df7--

Last modified: Sun, 13 Apr 2025 11:30:04 UTC

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