diff options
| author | Lars Ingebrigtsen <larsi@gnus.org> | 2022-08-12 15:15:11 +0200 |
|---|---|---|
| committer | Lars Ingebrigtsen <larsi@gnus.org> | 2022-08-12 15:16:39 +0200 |
| commit | c0d761bf7f441f8ab9792351a493dc6bd5525dc1 (patch) | |
| tree | b22c7d181d29f4ebff37aae7bae1da2db0fe854b | |
| parent | f947b20a1926ffc5b0553297dfc26d8390bcb328 (diff) | |
| download | emacs-c0d761bf7f441f8ab9792351a493dc6bd5525dc1.tar.gz emacs-c0d761bf7f441f8ab9792351a493dc6bd5525dc1.tar.bz2 emacs-c0d761bf7f441f8ab9792351a493dc6bd5525dc1.zip | |
Further seq-uniq speed-ups for lists
* lisp/emacs-lisp/seq.el (seq-uniq): Speed up more for long lists
(bug#57079).
| -rw-r--r-- | lisp/emacs-lisp/seq.el | 20 | ||||
| -rw-r--r-- | 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 6ddd8de6e8d..b6f0f66e5b1 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 a655377e6cc..1a27467d292 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 |