Received: (at submit) by debbugs.gnu.org; 10 Apr 2025 00:13:27 +0000
From debbugs-submit-bounces <at> debbugs.gnu.org Wed Apr 09 20:13:27 2025
Received: from localhost ([127.0.0.1]:42760 helo=debbugs.gnu.org)
by debbugs.gnu.org with esmtp (Exim 4.84_2)
(envelope-from <debbugs-submit-bounces <at> debbugs.gnu.org>)
id 1u2fXq-0001o6-VE
for submit <at> debbugs.gnu.org; Wed, 09 Apr 2025 20:13:27 -0400
Received: from lists.gnu.org ([2001:470:142::17]:36426)
by debbugs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.84_2) (envelope-from <krisbalintona@HIDDEN>)
id 1u2fXn-0001nn-NM
for submit <at> debbugs.gnu.org; Wed, 09 Apr 2025 20:13:24 -0400
Received: from eggs.gnu.org ([2001:470:142:3::10])
by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256)
(Exim 4.90_1) (envelope-from <krisbalintona@HIDDEN>)
id 1u2fXh-0005eM-LK
for bug-gnu-emacs@HIDDEN; Wed, 09 Apr 2025 20:13:17 -0400
Received: from mail-lf1-x134.google.com ([2a00:1450:4864:20::134])
by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128)
(Exim 4.90_1) (envelope-from <krisbalintona@HIDDEN>)
id 1u2fXf-0004Gk-Gu
for bug-gnu-emacs@HIDDEN; Wed, 09 Apr 2025 20:13:17 -0400
Received: by mail-lf1-x134.google.com with SMTP id
2adb3069b0e04-5499614d3d2so277278e87.3
for <bug-gnu-emacs@HIDDEN>; Wed, 09 Apr 2025 17:13:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1744243992; x=1744848792; darn=gnu.org;
h=to:subject:message-id:date:mime-version:from:from:to:cc:subject
:date:message-id:reply-to;
bh=5IJfhZrLjjQ2/m7KpOlT6y/uUZT2czLG5wJJ5Gs72EA=;
b=LqRxeIJKC++3HhA477Ynga/VT8POzVu/z7oKGlXWDgRT2HRlRv82PKMa+VZFBiBq8v
HPyGh1OQF8cQF57ANtk6MtyvB5+4NnqMKWFsCQeBRwJkYzbT/MtH4wXE0NvytRl4e6QQ
OYCoog525jiukkDACZ1IkQoaNiYp/CI++PUQs3bTlcD9HrCztTVQIa6NfD0D3Txe471H
Gb8n3kNGwecCmFFMLO/JkN2B+JqoKDbVMSel9ytEaZufB3D4H/fCtD7LHgFHWiwooReN
AeTd1nftdWWKOz3JQ17Loc5fN+Ly5woCwjZZkwLs5d67v/8VrE5tTt2LrhcvTUObxze7
ySTA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1744243992; x=1744848792;
h=to:subject:message-id:date:mime-version:from:x-gm-message-state
:from:to:cc:subject:date:message-id:reply-to;
bh=5IJfhZrLjjQ2/m7KpOlT6y/uUZT2czLG5wJJ5Gs72EA=;
b=CJAUrX/UGSaQam2usTPgrGyeXItrOCLhqWgYKYxBuKgVEn6BqjTXu9Od38BqS6HUAi
3iZqSWW5g77E6ch4d1pwL3jC3pFFRH2NHtmbLatFfYrY9uH+b5eyQ8h6LGZMIIdb02NW
1SFQM8ClRe3qfxK9rbQyTdyY6YLtmYzdQXRoLnzUyAY4zEjavKl8CSFk9g6EaB7IynvF
IyWJI41G3cJi99UL7HEQUxBx/RXsg580Yc65BroOCBnWRNnHWZxHyk2BxNaQcYNjQwII
3wnC+oEy95gfBvNfCI6u6+BLFQ+7IykgKvbhdKPF22mFlNlq17yVG/v0mC2w9Wuz2XW0
d5Bg==
X-Gm-Message-State: AOJu0YzvG55BrXh8ACq8Z5b19KzEYQcNWnjNGigUADr8ChAaS6mFHvC3
Svg6J07Fr/NQ0uT9GMVgzrnQpCi+2h1xj8guNuSO54wP33luDngZ7qJ1jNn1Ja9UwTyEJs/36bN
6uJlqfw8ZIEctN4+asaeKPXA7A+Ud7g==
X-Gm-Gg: ASbGncuIhB6u6KkAi70zNMxYv6gqUY/UFkCe/OHSqP5gRbNr2HhBe5yCtvTWRkbutRb
8BQDAuoESlP9A5KweQ/rzDL+Ow0RxUS37pVcPBjyYM3TvEPQI43YWRA+7/091GpA5UgzpYBgTlO
re9U+B4OR642t2IcL0ODUlhQ==
X-Google-Smtp-Source: AGHT+IGSpLs89BlNPV9Ngl7IbMPnZ4hkV1atPX3gGAONK/zfOz7lhlnFENshUWI3mTtTfZwVOODujlTQ08HNuKG8f6U=
X-Received: by 2002:a05:6512:3b8b:b0:54b:117c:118b with SMTP id
2adb3069b0e04-54d3c646691mr54554e87.56.1744243992261; Wed, 09 Apr 2025
17:13:12 -0700 (PDT)
Received: from 753933720722 named unknown by gmailapi.google.com with
HTTPREST; Wed, 9 Apr 2025 17:13:10 -0700
Received: from 753933720722 named unknown by gmailapi.google.com with
HTTPREST; Wed, 9 Apr 2025 17:13:10 -0700
From: Kristoffer Balintona <krisbalintona@HIDDEN>
MIME-Version: 1.0
Date: Wed, 9 Apr 2025 17:13:10 -0700
X-Gm-Features: ATxdqUH40e5l3gnjl701dLORx0NrDJWbfG3YJf0TQ-9d4ZIQx-CkE5HZ07ZBseA
Message-ID: <CANVbq5=7SGJyjjrsSVxJ6WXssua96iYonyY=bsAYk0Q1X_K9tQ@HIDDEN>
Subject: [PATCH] ; * lisp/emacs-lisp/vtable.el (vtable--limit-string): Use
binary search
To: bug-gnu-emacs@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-Debbugs-Envelope-To: submit
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--
Kristoffer Balintona <krisbalintona@HIDDEN>:bug-gnu-emacs@HIDDEN.
Full text available.bug-gnu-emacs@HIDDEN:bug#77684; Package emacs.
Full text available.
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997 nCipher Corporation Ltd,
1994-97 Ian Jackson.