master c0d761bf7f: Further seq-uniq speed-ups for lists

[Lars Ingebrigtsen]

branch: master
commit c0d761bf7f441f8ab9792351a493dc6bd5525dc1
Author: Lars Ingebrigtsen <larsi@gnus.org>
Commit: Lars Ingebrigtsen <larsi@gnus.org>

    Further seq-uniq speed-ups for lists
    
    * lisp/emacs-lisp/seq.el (seq-uniq): Speed up more for long lists
    (bug#57079).
---
 lisp/emacs-lisp/seq.el            | 20 +++++++++++++++-----
 test/lisp/emacs-lisp/seq-tests.el |  7 ++++++-
 2 files changed, 21 insertions(+), 6 deletions(-)

diff --git a/lisp/emacs-lisp/seq.el b/lisp/emacs-lisp/seq.el
index 6ddd8de6e8..b6f0f66e5b 100644
--- a/lisp/emacs-lisp/seq.el
+++ b/lisp/emacs-lisp/seq.el
@@ -458,11 +458,21 @@ TESTFN is used to compare elements, or `equal' if TESTFN 
is nil."
 (cl-defmethod seq-uniq ((sequence list) &optional testfn)
   (let ((result nil))
     (if (not testfn)
-        ;; Fast path.
-        (while sequence
-          (unless (member (car sequence) result)
-            (push (car sequence) result))
-          (pop sequence))
+        ;; Fast path.  If the list is long, use a hash table to speed
+        ;; things up even more.
+        (let ((l (length sequence)))
+          (if (> l 100)
+              (let ((hash (make-hash-table :test #'equal :size l)))
+                (while sequence
+                  (unless (gethash (car sequence) hash)
+                    (setf (gethash (car sequence) hash) t)
+                    (push (car sequence) result))
+                  (setq sequence (cdr sequence))))
+            ;; Short list.
+            (while sequence
+              (unless (member (car sequence) result)
+                (push (car sequence) result))
+              (pop sequence))))
       ;; Slower path.
       (while sequence
         (unless (seq-find (lambda (elem)
diff --git a/test/lisp/emacs-lisp/seq-tests.el 
b/test/lisp/emacs-lisp/seq-tests.el
index a655377e6c..1a27467d29 100644
--- a/test/lisp/emacs-lisp/seq-tests.el
+++ b/test/lisp/emacs-lisp/seq-tests.el
@@ -570,7 +570,12 @@ Evaluate BODY for each created sequence.
                     (substring "2")
                     (substring "1"))))
     (should (equal (seq-uniq list) '("1" "2" "3")))
-    (should (equal (seq-uniq list #'eq) '("1" "2" "3" "2" "1")))))
+    (should (equal (seq-uniq list #'eq) '("1" "2" "3" "2" "1"))))
+  ;; Long lists have a different code path.
+  (let ((list (seq-map-indexed (lambda (_ i) i)
+                              (make-list 10000 nil))))
+    (should (= (length list) 10000))
+    (should (= (length (seq-uniq (append list list))) 10000))))
 
 (provide 'seq-tests)
 ;;; seq-tests.el ends here