Re: [STUMP] shell command tab completion takes 6 seconds!

[Rupert Swarbrick]

Lionel Flandrin <address@hidden> writes:

> Hi,
>
> Does it happen every time or only the first time? Stumpwm caches the
> binaries in PATH, so it should only be slow (albeit indeed very slow)
> the first time.
>
> On Fri, Apr 09, 2010 at 03:54:34PM -0400, Yuliang Wang wrote:
>> This doesn't happen in ratpoison.

Hmm, I had a look at this, and it takes so long because we're merging
two lists of a few thousand pathnames with string=. But we can be much
more efficient, since we know that the lists are

 (a) In the same order.
 (b) Almost identical

I've attached a patch with a faster implementation. Advert to prove it
works:

Before:

STUMPWM> (time (progn (programs-in-path) (values)))
Evaluation took:
  4.896 seconds of real time
  4.900000 seconds of total run time (4.800000 user, 0.100000 system)
  [ Run times consist of 0.060 seconds GC time, and 4.840 seconds non-GC time. ]
  100.08% CPU
  9,768,276,160 processor cycles
  18,614,672 bytes consed

After:

STUMPWM> (time (progn (programs-in-path) (values)))

Evaluation took:
  0.495 seconds of real time
  0.490000 seconds of total run time (0.400000 user, 0.090000 system)
  [ Run times consist of 0.020 seconds GC time, and 0.470 seconds non-GC time. ]
  98.99% CPU
  986,540,340 processor cycles
  18,441,576 bytes consed



Hope this is of some use,

Rupert


diff --git a/user.lisp b/user.lisp
index 2c334d9..4c22923 100644
--- a/user.lisp
+++ b/user.lisp
@@ -104,6 +104,34 @@ location. Note: this function rarely works."
   (when (current-window)
     (send-fake-click (current-window) button)))
 
+(defun merge-ident-sorted (lst-a lst-b &optional (test #'equal))
+  "Take two lists, neither of which contain duplicates, with the property that
+if x and y occur in both lists and x<y in lst-a then x<y in lst-b. Return the
+union of the two lists. This should be particularly efficient if the two
+lists are almost the same."
+  (do ((acc nil)
+       (a lst-a)
+       (b lst-b (cdr b)))
+      ((null b) (nconc acc lst-a))
+    (let ((hit? (do ((a2 a (cdr a2)))
+                    ((null a2) nil)
+                  (when (funcall test (car a2) (car b))
+                    (return a2)))))
+      (if hit?
+          (setf a (cdr hit?))
+          (push (car b) acc)))))
+
+(defun all-files-in-directory (dir)
+  ;; SBCL doesn't match files with types if type is not wild and CLISP won't
+  ;; match files without a type when type is wild. So cover all the
+  ;; bases. Taking the union of the lists would be slow, but we can assume that
+  ;; they are both sorted in the same order, and thus can be much more
+  ;; efficient.
+  (merge-ident-sorted
+   (directory-no-deref (merge-pathnames (make-pathname :name :wild) dir))
+   (directory-no-deref (merge-pathnames
+                        (make-pathname :name :wild :type :wild) dir))))
+
 (defun programs-in-path (&optional full-path (path (split-string (getenv 
"PATH") ":")))
   "Return a list of programs in the path. if @var{full-path} is
 @var{t} then return the full path, otherwise just return the
@@ -116,13 +144,7 @@ seperated by a colon."
       for dir = (probe-path p)
       when dir
       nconc (loop
-               for file in (union
-                            ;; SBCL doesn't match files with types if type
-                            ;; is not wild and CLISP won't match files
-                            ;; without a type when type is wild. So cover all 
the bases
-                            (directory-no-deref (merge-pathnames 
(make-pathname :name :wild) dir))
-                            (directory-no-deref (merge-pathnames 
(make-pathname :name :wild :type :wild) dir))
-                            :test 'equal)
+               for file in (all-files-in-directory dir)
                for namestring = (file-namestring file)
                when (pathname-is-executable-p file)
                collect (if full-path

pgpcbA_BAJ5Bp.pgp
Description: PGP signature