patch 9.2.0053: Vims list concatenation is inefficient
Commit:
https://github.com/vim/vim/commit/048079f6dab8f0eb96f7d8090ccc2b8797ea4a09
Author: Yasuhiro Matsumoto <[email protected]>
Date: Wed Feb 25 19:31:37 2026 +0000
patch 9.2.0053: Vims list concatenation is inefficient
Problem: Vims list concatenation is inefficient
Solution: Use a single allocation of len1 + len2 using
list_alloc_with_items() (Yasuhiro Matsumoto).
Replace list_copy() + list_extend() (N+1 individual mallocs) with a
single list_alloc_with_items(len1+len2) call. This reduces the number
of memory allocations from O(N) to O(1) for the list '+' operator.
closes: #19495
Signed-off-by: Yasuhiro Matsumoto <[email protected]>
Signed-off-by: Christian Brabandt <[email protected]>
diff --git a/src/list.c b/src/list.c
index 253b1be9f..310d8516b 100644
--- a/src/list.c
+++ b/src/list.c
@@ -1232,22 +1232,62 @@ list_extend(list_T *l1, list_T *l2, listitem_T *bef)
list_concat(list_T *l1, list_T *l2, typval_T *tv)
{
list_T *l;
+ int len1 = l1 == NULL ? 0 : l1->lv_len;
+ int len2 = l2 == NULL ? 0 : l2->lv_len;
+ long totallen = (long)len1 + (long)len2;
+ int i;
+ listitem_T *item;
- // make a copy of the first list.
- if (l1 == NULL)
+ if (totallen == 0)
+ {
l = list_alloc();
- else
- l = list_copy(l1, FALSE, TRUE, 0);
+ if (l == NULL)
+ return FAIL;
+ ++l->lv_refcount;
+ tv->v_type = VAR_LIST;
+ tv->v_lock = 0;
+ tv->vval.v_list = l;
+ return OK;
+ }
+ if (totallen > INT_MAX)
+ return FAIL;
+
+ // allocate all items at once for efficiency
+ l = list_alloc_with_items((int)totallen);
if (l == NULL)
return FAIL;
+
+ i = 0;
+ if (len1 > 0)
+ {
+ CHECK_LIST_MATERIALIZE(l1);
+ for (item = l1->lv_first; item != NULL && !got_int;
+ item = item->li_next)
+ {
+ typval_T new_tv;
+
+ copy_tv(&item->li_tv, &new_tv);
+ list_set_item(l, i++, &new_tv);
+ }
+ }
+ if (len2 > 0)
+ {
+ CHECK_LIST_MATERIALIZE(l2);
+ for (item = l2->lv_first; item != NULL && !got_int;
+ item = item->li_next)
+ {
+ typval_T new_tv;
+
+ copy_tv(&item->li_tv, &new_tv);
+ list_set_item(l, i++, &new_tv);
+ }
+ }
+
+ ++l->lv_refcount;
tv->v_type = VAR_LIST;
tv->v_lock = 0;
tv->vval.v_list = l;
- if (l1 == NULL)
- ++l->lv_refcount;
-
- // append all items from the second list
- return list_extend(l, l2, NULL);
+ return OK;
}
list_T *
@@ -1482,7 +1522,7 @@ list_join_inner(
{
int i;
join_T *p;
- int sumlen = 0;
+ long sumlen = 0;
int first = TRUE;
char_u *tofree;
char_u numbuf[NUMBUFLEN];
@@ -1500,7 +1540,7 @@ list_join_inner(
return FAIL;
s.length = STRLEN(s.string);
- sumlen += (int)s.length;
+ sumlen += (long)s.length;
(void)ga_grow(join_gap, 1);
p = ((join_T *)join_gap->ga_data) + (join_gap->ga_len++);
@@ -1526,8 +1566,8 @@ list_join_inner(
// multiple copy operations. Add 2 for a tailing ']' and NUL.
seplen = STRLEN(sep);
if (join_gap->ga_len >= 2)
- sumlen += (int)seplen * (join_gap->ga_len - 1);
- if (ga_grow(gap, sumlen + 2) == FAIL)
+ sumlen += (long)seplen * (join_gap->ga_len - 1);
+ if (sumlen > INT_MAX - 2 || ga_grow(gap, (int)sumlen + 2) == FAIL)
return FAIL;
for (i = 0; i < join_gap->ga_len && !got_int; ++i)
@@ -1847,11 +1887,16 @@ f_list2str(typval_T *argvars, typval_T *rettv)
}
ga_append(&ga, NUL);
}
- else if (ga_grow(&ga, list_len(l) + 1) == OK)
+ else
{
- FOR_ALL_LIST_ITEMS(l, li)
- ga_append(&ga, tv_get_number(&li->li_tv));
- ga_append(&ga, NUL);
+ long len = (long)list_len(l) + 1;
+
+ if (len <= INT_MAX && ga_grow(&ga, (int)len) == OK)
+ {
+ FOR_ALL_LIST_ITEMS(l, li)
+ ga_append(&ga, tv_get_number(&li->li_tv));
+ ga_append(&ga, NUL);
+ }
}
rettv->v_type = VAR_STRING;
diff --git a/src/version.c b/src/version.c
index 36d32a15a..fe8ce15a1 100644
--- a/src/version.c
+++ b/src/version.c
@@ -734,6 +734,8 @@ static char *(features[]) =
static int included_patches[] =
{ /* Add new patch number below this line */
+/**/
+ 53,
/**/
52,
/**/
--
--
You received this message from the "vim_dev" maillist.
Do not top-post! Type your reply below the text you are replying to.
For more information, visit http://www.vim.org/maillist.php
---
You received this message because you are subscribed to the Google Groups
"vim_dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion visit
https://groups.google.com/d/msgid/vim_dev/E1vvKoh-00CsbJ-O8%40256bit.org.
