[Emacs-diffs] master 1f052a5: lisp/subr.el (delete-dups): Use a hash table

[Oleh Krehel]

branch: master
commit 1f052a5f26250d726618570a816ddb6fd0cc11a0
Author: Oleh Krehel <address@hidden>
Commit: Oleh Krehel <address@hidden>

    lisp/subr.el (delete-dups): Use a hash table
    
    * lisp/subr.el (delete-dups): When there are more than 100 candidates,
      use a hash table. This can result in ~500 times speed-up for typical
      collections of size 5000, like that of `load-library'.
---
 lisp/subr.el |   18 +++++++++++++-----
 1 files changed, 13 insertions(+), 5 deletions(-)

diff --git a/lisp/subr.el b/lisp/subr.el
index 0fec29c..591980d 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -417,11 +417,19 @@ If N is omitted or nil, remove the last element."
 Store the result in LIST and return it.  LIST must be a proper list.
 Of several `equal' occurrences of an element in LIST, the first
 one is kept."
-  (let ((tail list))
-    (while tail
-      (setcdr tail (delete (car tail) (cdr tail)))
-      (setq tail (cdr tail))))
-  list)
+  (if (> (length list) 100)
+      (let ((hash (make-hash-table :test #'equal))
+            res)
+        (dolist (elt list)
+          (unless (gethash elt hash)
+            (puthash elt elt hash)
+            (push elt res)))
+        (nreverse res))
+    (let ((tail list))
+      (while tail
+        (setcdr tail (delete (car tail) (cdr tail)))
+        (setq tail (cdr tail))))
+    list))
 
 ;; See http://lists.gnu.org/archive/html/emacs-devel/2013-05/msg00204.html
 (defun delete-consecutive-dups (list &optional circular)