patch 8.2.2065: using map() and filter() on a range() is inefficient
Problem: Using map() and filter() on a range() is inefficient.
Solution: Do not materialize the range. (closes #7388)
diff --git a/src/list.c b/src/list.c
index e75a2a7..c364fa7 100644
--- a/src/list.c
+++ b/src/list.c
@@ -2173,43 +2173,95 @@
// set_vim_var_nr() doesn't set the type
set_vim_var_type(VV_KEY, VAR_NUMBER);
- CHECK_LIST_MATERIALIZE(l);
if (filtermap != FILTERMAP_FILTER && l->lv_lock == 0)
l->lv_lock = VAR_LOCKED;
- for (li = l->lv_first; li != NULL; li = nli)
- {
- typval_T newtv;
- if (filtermap != FILTERMAP_FILTER
- && value_check_lock(li->li_tv.v_lock, arg_errmsg, TRUE))
- break;
- nli = li->li_next;
- set_vim_var_nr(VV_KEY, idx);
- if (filter_map_one(&li->li_tv, expr, filtermap,
- &newtv, &rem) == FAIL)
- break;
- if (did_emsg)
+ if (l->lv_first == &range_list_item)
+ {
+ varnumber_T val = l->lv_u.nonmat.lv_start;
+ int len = l->lv_len;
+ int stride = l->lv_u.nonmat.lv_stride;
+
+ // List from range(): loop over the numbers
+ l->lv_first = NULL;
+ l->lv_u.mat.lv_last = NULL;
+ l->lv_len = 0;
+ l->lv_u.mat.lv_idx_item = NULL;
+
+ for (idx = 0; idx < len; ++idx)
{
- clear_tv(&newtv);
- break;
- }
- if (filtermap == FILTERMAP_MAP)
- {
- // map(): replace the list item value
- clear_tv(&li->li_tv);
- newtv.v_lock = 0;
- li->li_tv = newtv;
- }
- else if (filtermap == FILTERMAP_MAPNEW)
- {
- // mapnew(): append the list item value
- if (list_append_tv_move(l_ret, &newtv) == FAIL)
+ typval_T tv;
+ typval_T newtv;
+
+ tv.v_type = VAR_NUMBER;
+ tv.v_lock = 0;
+ tv.vval.v_number = val;
+ set_vim_var_nr(VV_KEY, idx);
+ if (filter_map_one(&tv, expr, filtermap, &newtv, &rem)
+ == FAIL)
break;
+ if (did_emsg)
+ {
+ clear_tv(&newtv);
+ break;
+ }
+ if (filtermap != FILTERMAP_FILTER)
+ {
+ // map(), mapnew(): always append the new value to the
+ // list
+ if (list_append_tv_move(filtermap == FILTERMAP_MAP
+ ? l : l_ret, &newtv) == FAIL)
+ break;
+ }
+ else if (!rem)
+ {
+ // filter(): append the list item value when not rem
+ if (list_append_tv_move(l, &tv) == FAIL)
+ break;
+ }
+
+ val += stride;
}
- else if (filtermap == FILTERMAP_FILTER && rem)
- listitem_remove(l, li);
- ++idx;
}
+ else
+ {
+ // Materialized list from range(): loop over the items
+ for (li = l->lv_first; li != NULL; li = nli)
+ {
+ typval_T newtv;
+
+ if (filtermap != FILTERMAP_FILTER && value_check_lock(
+ li->li_tv.v_lock, arg_errmsg, TRUE))
+ break;
+ nli = li->li_next;
+ set_vim_var_nr(VV_KEY, idx);
+ if (filter_map_one(&li->li_tv, expr, filtermap,
+ &newtv, &rem) == FAIL)
+ break;
+ if (did_emsg)
+ {
+ clear_tv(&newtv);
+ break;
+ }
+ if (filtermap == FILTERMAP_MAP)
+ {
+ // map(): replace the list item value
+ clear_tv(&li->li_tv);
+ newtv.v_lock = 0;
+ li->li_tv = newtv;
+ }
+ else if (filtermap == FILTERMAP_MAPNEW)
+ {
+ // mapnew(): append the list item value
+ if (list_append_tv_move(l_ret, &newtv) == FAIL)
+ break;
+ }
+ else if (filtermap == FILTERMAP_FILTER && rem)
+ listitem_remove(l, li);
+ ++idx;
+ }
+ }
+
l->lv_lock = prev_lock;
}
diff --git a/src/testdir/test_functions.vim b/src/testdir/test_functions.vim
index fb0b193..d6e408a 100644
--- a/src/testdir/test_functions.vim
+++ b/src/testdir/test_functions.vim
@@ -2302,6 +2302,7 @@
" filter()
call assert_equal([1, 3], filter(range(5), 'v:val % 2'))
+ call assert_equal([1, 5, 7, 11, 13], filter(filter(range(15), 'v:val % 2'), 'v:val % 3'))
" funcref()
call assert_equal([0, 1], funcref('TwoArgs', range(2))())
@@ -2358,6 +2359,9 @@
" map()
call assert_equal([0, 2, 4, 6, 8], map(range(5), 'v:val * 2'))
+ call assert_equal([3, 5, 7, 9, 11], map(map(range(5), 'v:val * 2'), 'v:val + 3'))
+ call assert_equal([2, 6], map(filter(range(5), 'v:val % 2'), 'v:val * 2'))
+ call assert_equal([2, 4, 8], filter(map(range(5), 'v:val * 2'), 'v:val % 3'))
" match()
call assert_equal(3, match(range(5), 3))
diff --git a/src/version.c b/src/version.c
index ec0fabc..dac3d5c 100644
--- a/src/version.c
+++ b/src/version.c
@@ -751,6 +751,8 @@
static int included_patches[] =
{ /* Add new patch number below this line */
/**/
+ 2065,
+/**/
2064,
/**/
2063,