master 45941a62c79 5/9: Faster non-destructive list sorting

[Mattias Engdegård]

branch: master
commit 45941a62c799f9685fae296079304ae0898920cc
Author: Mattias Engdegård <mattiase@acm.org>
Commit: Mattias Engdegård <mattiase@acm.org>

    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.
---
 src/fns.c | 65 ++++++++++++++++++++++++++++++++++-----------------------------
 1 file 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