Commit: patch 9.2.1042: sign: placing many signs is slower than necessary

[Christian Brabandt]

patch 9.2.1042: sign: placing many signs is slower than necessary

Commit: https://github.com/vim/vim/commit/5feaa6c6c201d4d05b833a7230d07da44bf2504b
Author: Julien Voisin <julien...@dustri.org>
Date: Mon Sep 7 20:21:18 2026 +0000

patch 9.2.1042: sign: placing many signs is slower than necessary

Problem: Placing many signs, for example with sign_placelist(), is
slower than necessary because buf_addsign() rescans the
buffer's sign list from its head for every sign to find the
insertion point, which is quadratic in the number of signs.
Solution: Remember the last inserted sign and resume the search from it
when the next sign is on a later line (Julien Voisin).

buf_addsign() inserts signs in line-number order, so when signs are
placed on distinct, ascending lines (the common case for
sign_placelist() and for plugins that place many signs) resuming each
search from the previously inserted sign instead of the head makes the
total work linear rather than quadratic. Signs placed on the same line
still fall back to a scan from the head.

Placing 16000 signs with explicit ids in ascending order drops from
about a quarter of a second to a few milliseconds.

closes: #21237

Signed-off-by: Julien Voisin <julien...@dustri.org>
Signed-off-by: Christian Brabandt <c...@256bit.org>

diff --git a/src/sign.c b/src/sign.c
index fc701d1ed..9dbb3d4df 100644
--- a/src/sign.c
+++ b/src/sign.c
@@ -261,6 +261,10 @@ insert_sign(buf_T *buf, // buffer to store sign in
{
prev->se_next = newsign;
}
+
+ // Remember the newly inserted sign so a following insert on a later line
+ // can resume the search from here.
+ buf->b_sign_finger = newsign;
}

/*
@@ -418,7 +422,16 @@ buf_addsign(buf_T *buf, // buffer to store sign in
{
sign_entry_T *sign = NULL; // a sign in the signlist
sign_entry_T *prev = NULL; // the previous sign
- FOR_ALL_SIGNS_IN_BUF(buf, sign)
+
+ // The list is sorted by line number. When the last inserted sign is on a
+ // strictly earlier line, resume the search from there instead of the head;
+ // this makes placing many signs on distinct, ascending lines close to
+ // linear. Signs on the same line fall back to a scan from the head.
+ if (buf->b_sign_finger != NULL && buf->b_sign_finger->se_lnum < lnum)
+ prev = buf->b_sign_finger;
+
+ for (sign = (prev == NULL) ? buf->b_signlist : prev->se_next; sign != NULL;
+ sign = sign->se_next)
{
if (lnum == sign->se_lnum && id == sign->se_id &&
sign_in_group(sign, groupname))
@@ -568,6 +581,7 @@ buf_delsign(buf_T *buf, // buffer sign is stored in
int id, // sign id
char_u *group) // sign group
{
+ buf->b_sign_finger = NULL; // a removal invalidates the insertion finger
// pointer to pointer to current sign
sign_entry_T **lastp = &buf->b_signlist;
sign_entry_T *next = NULL; // the next sign in a b_signlist
@@ -732,6 +746,7 @@ buf_signcount(buf_T *buf, linenr_T lnum)
void
buf_delete_signs(buf_T *buf, char_u *group)
{
+ buf->b_sign_finger = NULL; // a removal invalidates the insertion finger
// When deleting the last sign need to redraw the windows to remove the
// sign column. Not when curwin is NULL (this means we're exiting).
if (buf->b_signlist != NULL && curwin != NULL)
@@ -829,6 +844,7 @@ sign_mark_adjust(
long amount,
long amount_after)
{
+ curbuf->b_sign_finger = NULL; // line changes may reorder, drop the finger
sign_entry_T *sign = NULL; // a sign in a b_signlist
FOR_ALL_SIGNS_IN_BUF(curbuf, sign)
{
diff --git a/src/structs.h b/src/structs.h
index 216857de9..0e9981c81 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -3713,6 +3713,8 @@ struct file_buffer

#ifdef FEAT_SIGNS
sign_entry_T *b_signlist; // list of placed signs
+ sign_entry_T *b_sign_finger; // last sign inserted, used to speed up
+ // inserting signs in ascending line order
# ifdef FEAT_NETBEANS_INTG
bool b_has_sign_column; // Flag that is set when a first sign is
// added and remains set until the end of
diff --git a/src/version.c b/src/version.c
index 958bd7990..6752df82b 100644
--- a/src/version.c
+++ b/src/version.c
@@ -763,6 +763,8 @@ static char *(features[]) =

static int included_patches[] =
{ /* Add new patch number below this line */
+/**/
+ 1042,
/**/
1041,
/**/