[vim/vim] perf: list_concat() use single allocation with list_alloc_with_items (PR #19495)
mattn
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.
Before: 0.4190s
After: 0.2333s
let s:list_size = 100000 let s:iterations = 100 let s:l1 = range(s:list_size) let s:l2 = range(s:list_size) " Warm up for i in range(3) let _ = s:l1 + s:l2 endfor let s:start = reltime() for i in range(s:iterations) let _ = s:l1 + s:l2 endfor let s:elapsed = reltimefloat(reltime(s:start)) echo printf('list len: %d + %d, iterations: %d, total: %.4f s, per-op: %.6f s', \ len(s:l1), len(s:l2), s:iterations, s:elapsed, s:elapsed / s:iterations)
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/19495
Commit Summary
- 41200fa perf: list_concat() use single allocation with list_alloc_with_items
File Changes
(1 file)
- M src/list.c (55)
Patch Links:
—
Reply to this email directly, view it on GitHub.
You are receiving this because you are subscribed to this thread.
Christian Brabandt
@chrisbra commented on this pull request.
In src/list.c:
> 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; + } + + // allocate all items at once for efficiency + l = list_alloc_with_items(len1 + len2);
len1 + len2 can potentially overflow here
—
Reply to this email directly, view it on GitHub, or unsubscribe.
You are receiving this because you are subscribed to this thread.
mattn
@mattn pushed 1 commit.
- 6b5a181 Fixes buffer overflow within the parts having same problem.
—
View it on GitHub or unsubscribe.
You are receiving this because you are subscribed to this thread.
mattn
@mattn commented on this pull request.
In src/list.c:
> 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; + } + + // allocate all items at once for efficiency + l = list_alloc_with_items(len1 + len2);
Thank you. Fixed.
—
Reply to this email directly, view it on GitHub, or unsubscribe.
You are receiving this because you are subscribed to this thread.