Commit: patch 9.2.0937: sort() with a numeric option converts each item on every comparison

patch 9.2.0937: sort() with a numeric option converts each item on every comparison

Commit: https://github.com/vim/vim/commit/c8c59db9dfdc2db5f17aa0a78ea1464f035bdf5e
Author: Samuel Schlesinger <[email protected]>
Date:   Tue Aug 11 19:03:55 2026 +0000

    patch 9.2.0937: sort() with a numeric option converts each item on every comparison
    
    Problem:  sort() with "n", "N" or "f" converts an item to its number on
              every comparison.  For "n" that is a tv2string() plus strtod()
              per comparison, so sorting a list of numbers turns each number
              into a string and back O(n log n) times, dwarfing the sort.
    Solution: Compute the numeric key of each item once, before the sort,
              and compare the stored key (Samuel Schlesinger).  Only the
              builtin numeric compare modes are affected; uniq(), which
              passes a bare list item to the compare function, and the
              string and user-function paths are unchanged.
    
    Sorting a list of 100000 numbers (min of 3, macOS arm64):
    - sort(l, 'n'):  0.205s -> 0.017s
    - sort(l, 'N'):  0.017s -> 0.010s
    - sort(l, 'f'):  0.014s -> 0.010s
    The result is identical, including that a string is still treated as 0
    in "n" mode and that "N" keeps full 64-bit precision.
    
    Add Test_sort_numeric_precomputed(): a large shuffled list sorted with
    "n", mixed integers and floats, int64 values beyond the exact range of
    a double for "N", and uniq() over the non-precomputed path.
    
    closes: #21003
    
    Co-Authored-By: Claude <[email protected]>
    Signed-off-by: Samuel Schlesinger <[email protected]>
    Signed-off-by: Christian Brabandt <[email protected]>

diff --git a/src/list.c b/src/list.c
index 82243c82b..792612874 100644
--- a/src/list.c
+++ b/src/list.c
@@ -2077,6 +2077,14 @@ typedef struct
 {
     listitem_T	*item;
     int		idx;
+    // Sort key precomputed once per item for the numeric compare modes, so
+    // item_compare() does not convert the value on every comparison.  Only
+    // valid when sortinfo->item_compare_keys_ready is set (the sort() path);
+    // uniq() passes a bare listitem_T pointer and must not read this.
+    union {
+	varnumber_T	inum;	// for item_compare_numbers ("N")
+	double		fnum;	// for item_compare_numeric ("n") and _float ("f")
+    } key;
 } sortItem_T;
 
 // struct storing information about current sort
@@ -2092,6 +2100,7 @@ typedef struct
     dict_T	*item_compare_selfdict;
     int		item_compare_func_err;
     int		item_compare_keep_zero;
+    int		item_compare_keys_ready;  // ptrs[].key is precomputed
 } sortinfo_T;
 static sortinfo_T	*sortinfo = NULL;
 #define ITEM_COMPARE_FAIL 999
@@ -2117,20 +2126,35 @@ item_compare(const void *s1, const void *s2)
 
     if (sortinfo->item_compare_numbers)
     {
-	varnumber_T	v1 = tv_to_number(tv1);
-	varnumber_T	v2 = tv_to_number(tv2);
+	varnumber_T	v1 = sortinfo->item_compare_keys_ready
+					? si1->key.inum : tv_to_number(tv1);
+	varnumber_T	v2 = sortinfo->item_compare_keys_ready
+					? si2->key.inum : tv_to_number(tv2);
 
 	return v1 == v2 ? 0 : v1 > v2 ? 1 : -1;
     }
 
     if (sortinfo->item_compare_float)
     {
-	float_T	v1 = tv_get_float(tv1);
-	float_T	v2 = tv_get_float(tv2);
+	float_T	v1 = sortinfo->item_compare_keys_ready
+					? si1->key.fnum : tv_get_float(tv1);
+	float_T	v2 = sortinfo->item_compare_keys_ready
+					? si2->key.fnum : tv_get_float(tv2);
 
 	return v1 == v2 ? 0 : v1 > v2 ? 1 : -1;
     }
 
+    if (sortinfo->item_compare_numeric && sortinfo->item_compare_keys_ready)
+    {
+	double	n1 = si1->key.fnum;
+	double	n2 = si2->key.fnum;
+
+	res = n1 == n2 ? 0 : n1 > n2 ? 1 : -1;
+	if (res == 0 && !sortinfo->item_compare_keep_zero)
+	    res = si1->idx > si2->idx ? 1 : -1;
+	return res;
+    }
+
     // tv2string() puts quotes around a string and allocates memory.  Don't do
     // that for string variables. Use a single quote when comparing with a
     // non-string to do what the docs promise.
@@ -2240,6 +2264,51 @@ item_compare2(const void *s1, const void *s2)
     return res;
 }
 
+/*
+ * Precompute the numeric sort key of each item, so that item_compare() can
+ * compare the stored value instead of converting the item on every one of the
+ * O(n log n) comparisons.  Only for the builtin numeric compare modes; each
+ * key is computed exactly as item_compare() would have, once per item.
+ */
+    static void
+sort_compute_keys(sortItem_T *ptrs, long len, sortinfo_T *info)
+{
+    long	i;
+
+    if (info->item_compare_numbers)
+    {
+	for (i = 0; i < len; ++i)
+	    ptrs[i].key.inum = tv_to_number(&ptrs[i].item->li_tv);
+    }
+    else if (info->item_compare_float)
+    {
+	for (i = 0; i < len; ++i)
+	    ptrs[i].key.fnum = tv_get_float(&ptrs[i].item->li_tv);
+    }
+    else // info->item_compare_numeric
+    {
+	for (i = 0; i < len; ++i)
+	{
+	    typval_T	*tv = &ptrs[i].item->li_tv;
+
+	    // A string is compared as a single quote in numeric mode, which
+	    // strtod() reads as 0; only numbers contribute a value.
+	    if (tv->v_type == VAR_STRING)
+		ptrs[i].key.fnum = 0.0;
+	    else
+	    {
+		char_u	numbuf[NUMBUFLEN];
+		char_u	*tofree = NULL;
+		char_u	*p = tv2string(tv, &tofree, numbuf, 0);
+
+		ptrs[i].key.fnum = p == NULL ? 0.0 : strtod((char *)p, NULL);
+		vim_free(tofree);
+	    }
+	}
+    }
+    info->item_compare_keys_ready = TRUE;
+}
+
 /*
  * sort() List "l"
  */
@@ -2268,6 +2337,13 @@ do_sort(list_T *l, sortinfo_T *info)
 
     info->item_compare_func_err = FALSE;
     info->item_compare_keep_zero = FALSE;
+    info->item_compare_keys_ready = FALSE;
+    // For the builtin numeric compares, precompute each item's key once
+    // instead of converting it on every comparison.
+    if (info->item_compare_func == NULL && info->item_compare_partial == NULL
+	    && (info->item_compare_numbers || info->item_compare_float
+						|| info->item_compare_numeric))
+	sort_compute_keys(ptrs, len, info);
     // test the compare function
     if ((info->item_compare_func != NULL
 		|| info->item_compare_partial != NULL)
@@ -2369,6 +2445,7 @@ parse_sort_uniq_args(typval_T *argvars, sortinfo_T *info)
     info->item_compare_func = NULL;
     info->item_compare_partial = NULL;
     info->item_compare_selfdict = NULL;
+    info->item_compare_keys_ready = FALSE;
 
     if (argvars[1].v_type == VAR_UNKNOWN)
 	return OK;
diff --git a/src/testdir/test_sort.vim b/src/testdir/test_sort.vim
index 1c60e8e42..8ec89f25a 100644
--- a/src/testdir/test_sort.vim
+++ b/src/testdir/test_sort.vim
@@ -53,6 +53,9 @@ func Test_sort_numeric()
   call assert_equal([3, 13, 28], sort([13, 28, 3], 'n'))
   " strings are not sorted
   call assert_equal(['13', '28', '3'], sort(['13', '28', '3'], 'n'))
+  " a string sorts as 0 in "n" mode, even a numeric-looking one
+  call assert_equal(['a', 0, 1], sort([1, 'a', 0], 'n'))
+  call assert_equal(['10', 2], sort([2, '10'], 'n'))
 endfunc
 
 func Test_sort_numbers()
@@ -66,6 +69,34 @@ func Test_sort_float()
   call assert_equal([0.28, 3, 13.5], sort([13.5, 0.28, 3], 'f'))
 endfunc
 
+" The numeric compare modes precompute a sort key per item; exercise that on
+" larger lists (many comparisons), with mixed int/float, negatives, and
+" int64 values that do not fit in a double for 'N'.
+func Test_sort_numeric_precomputed()
+  " 'n' on a large shuffled list, compared against the known order.
+  let expected = range(500)
+  let shuffled = copy(expected)
+  " deterministic shuffle
+  let s = 7
+  for i in range(len(shuffled) - 1, 1, -1)
+    let s = (s * 1103515245 + 12345) % 2147483648
+    let j = s % (i + 1)
+    let [shuffled[i], shuffled[j]] = [shuffled[j], shuffled[i]]
+  endfor
+  call assert_equal(expected, sort(shuffled, 'n'))
+
+  " 'n' with mixed integers and floats and negatives.
+  call assert_equal([-3, -1.5, 0, 0.5, 2, 7.25], sort([7.25, -1.5, 2, 0, -3, 0.5], 'n'))
+
+  " 'N' with int64 values beyond the exact range of a double: keys must not
+  " be rounded through a double.
+  call assert_equal([9007199254740992, 9007199254740993, 9007199254740994],
+        \ sort([9007199254740994, 9007199254740992, 9007199254740993], 'N'))
+
+  " uniq() uses the non-precomputed path; it must still work.
+  call assert_equal([1, 2, 3], uniq(sort([3, 1, 2, 2, 3, 1], 'n')))
+endfunc
+
 func Test_sort_nested()
   " test ability to call sort() from a compare function
   call assert_equal([1, 3, 5], sort([3, 1, 5], 'Compare1'))
diff --git a/src/version.c b/src/version.c
index 2cbf92a2e..a5cb9e1dd 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 */
+/**/
+    937,
 /**/
     936,
 /**/

-- 
-- 
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/E1wtrwG-007Z4z-IO%40256bit.org.