[vim/vim] sort() with a numeric option converts each item on every comparison (PR #21003)
Samuel Schlesinger
Problem
sort() with the "n", "N" or "f" option converts each item to its
number on every comparison. For "n" that is a tv2string() followed by
strtod() per comparison, so sorting a list of numbers turns each number into
a string and parses it back O(n log n) times, which dwarfs the sort itself.
Solution
Compute the numeric key of each item once, before the sort, and compare the
stored key. Only the builtin numeric compare modes are touched; uniq(),
which passes a bare list item to the compare function rather than the array
element, and the string and user-function paths are unchanged.
Sorting a list of 100000 numbers (min of 3, macOS arm64):
| sort | before | after |
|---|---|---|
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 (the key is a
varnumber_T, not a double).
vim9script var shuffled: list<number> = [] var seed = 12345 for x in range(100000) seed = (seed * 1103515245 + 12345) % 2147483648 shuffled->add(seed % 1000000) endfor var t0 = reltime() call copy(shuffled)->sort('n') echo reltimefloat(reltime(t0))
Adds 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.
AI assistance is acknowledged with Co-Authored-By trailers on the commit,
per AGENTS.md.
You can view, comment on, or merge this pull request online at:
https://github.com/vim/vim/pull/21003
Commit Summary
- 2f828eb sort() with a numeric option converts each item on every comparison
File Changes
(2 files)
- M src/list.c (85)
- M src/testdir/test_sort.vim (28)
Patch Links:
—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!
You are receiving this because you are subscribed to this thread.