diff options
author | Mattias EngdegÄrd <mattiase@acm.org> | 2024-03-22 11:54:09 +0100 |
---|---|---|
committer | Mattias EngdegÄrd <mattiase@acm.org> | 2024-03-29 11:39:38 +0100 |
commit | 45941a62c799f9685fae296079304ae0898920cc (patch) | |
tree | cfe060f171b70752334b0ff2306fadeff1ec6754 | |
parent | deae311281522864ebabaf56adafbe37032cc8a9 (diff) | |
download | emacs-45941a62c799f9685fae296079304ae0898920cc.tar.gz |
Faster non-destructive list sorting
Postpone the creation of a new list to after sorting which turns out to
be a lot faster (1.1x - 1.5x speedup).
* src/fns.c (sort_list, sort_vector, Fsort):
Create the new list when moving the data out from the temporary array.
-rw-r--r-- | src/fns.c | 65 |
1 files changed, 35 insertions, 30 deletions
diff --git a/src/fns.c b/src/fns.c index bf7c0920750..8d8783713ab 100644 --- a/src/fns.c +++ b/src/fns.c @@ -2347,18 +2347,17 @@ See also the function `nreverse', which is used more often. */) } -/* Stably sort LIST ordered by PREDICATE using the TIMSORT - algorithm. This converts the list to a vector, sorts the vector, - and returns the result converted back to a list. The input list - is destructively reused to hold the sorted result. */ - +/* Stably sort LIST ordered by PREDICATE and KEYFUNC, optionally reversed. + This converts the list to a vector, sorts the vector, and returns the + result converted back to a list. If INPLACE, the input list is + reused to hold the sorted result; otherwise a new list is returned. */ static Lisp_Object sort_list (Lisp_Object list, Lisp_Object predicate, Lisp_Object keyfunc, - bool reverse) + bool reverse, bool inplace) { ptrdiff_t length = list_length (list); if (length < 2) - return list; + return inplace ? list : list1 (XCAR (list)); else { Lisp_Object *result; @@ -2372,31 +2371,40 @@ sort_list (Lisp_Object list, Lisp_Object predicate, Lisp_Object keyfunc, } tim_sort (predicate, keyfunc, result, length, reverse); - ptrdiff_t i = 0; - tail = list; - while (CONSP (tail)) + if (inplace) { - XSETCAR (tail, result[i]); - tail = XCDR (tail); - i++; + /* Copy sorted vector contents back onto the original list. */ + ptrdiff_t i = 0; + tail = list; + while (CONSP (tail)) + { + XSETCAR (tail, result[i]); + tail = XCDR (tail); + i++; + } + } + else + { + /* Create a new list for the sorted vector contents. */ + list = Qnil; + for (ptrdiff_t i = length - 1; i >= 0; i--) + list = Fcons (result[i], list); } SAFE_FREE (); return list; } } -/* Stably sort VECTOR ordered by PREDICATE using the TIMSORT - algorithm. */ - -static void +/* Stably sort VECTOR in-place ordered by PREDICATE and KEYFUNC, + optionally reversed. */ +static Lisp_Object sort_vector (Lisp_Object vector, Lisp_Object predicate, Lisp_Object keyfunc, bool reverse) { ptrdiff_t length = ASIZE (vector); - if (length < 2) - return; - - tim_sort (predicate, keyfunc, XVECTOR (vector)->contents, length, reverse); + if (length >= 2) + tim_sort (predicate, keyfunc, XVECTOR (vector)->contents, length, reverse); + return vector; } DEFUN ("sort", Fsort, Ssort, 1, MANY, 0, @@ -2455,18 +2463,15 @@ usage: (sort SEQ &key KEY LESSP REVERSE IN-PLACE) */) signal_error ("Invalid keyword argument", args[i]); } - /* FIXME: for lists it may be slightly faster to make the copy after - sorting? Measure. */ - if (!inplace) - seq = Fcopy_sequence (seq); - if (CONSP (seq)) - seq = sort_list (seq, lessp, key, reverse); + return sort_list (seq, lessp, key, reverse, inplace); + else if (NILP (seq)) + return seq; else if (VECTORP (seq)) - sort_vector (seq, lessp, key, reverse); - else if (!NILP (seq)) + return sort_vector (inplace ? seq : Fcopy_sequence (seq), + lessp, key, reverse); + else wrong_type_argument (Qlist_or_vector_p, seq); - return seq; } Lisp_Object |