[bug#45893] Hint for package name: too slow!

[zimoun <zimon.toutoune@gmail.com>]

Hi Ludo,

> Next up is package names, right?  :-)

As said I have tried to hint typo about packages for “guix show” but it
is too slow.  So, in procrastinating mood, I have tried to investigate a
bit.

Currently, the cache would be read 2 times, once by
’find-packages-by-name’ and then if the returned list is empty, again
with ’fold-available-packages’ to find the closest name.  Read the cache
only once implies a lot of work.

However, the first improvement is to speed up ’string-distance’.  Well,
the naive recursive implementation is well-known to be really slow.

Well, one question is: what is the status of Stream in Guile?  Without
drifting the initial topic, I am interested by  the answer because it
could be useful for “guix git log” (avoid to traverse all the history
tree before displaying but traverse when it is required, somehow).


Cheers,
simon

--8<---------------cut here---------------start------------->8---
scheme@(guix-user)> 
(use-modules (gnu packages)
             (guix utils))

(define (read-the-cache guess)
  (map (lambda (name)
         (identity name))
       (fold-available-packages
        (lambda* (name version result
                       #:key supported? deprecated?
                       #:allow-other-keys)
          (if (and supported? (not deprecated?))
              (cons name result)
              result))
        '())))

(define (compute-distance guess)
  (map (lambda (name)
         (string-distance guess name))
       (fold-available-packages
        (lambda* (name version result
                       #:key supported? deprecated?
                       #:allow-other-keys)
          (if (and supported? (not deprecated?))
              (cons name result)
              result))
        '())))
scheme@(guix-user)> ,time (define foo (read-the-cache "macs-mgit"))
;; 3.492591s real time, 4.523108s run time.  1.530055s spent in GC.
scheme@(guix-user)> ,time (define foo (read-the-cache "macs-mgit"))
;; 0.125346s real time, 0.123948s run time.  0.000000s spent in GC.
scheme@(guix-user)> ,time (define foo (compute-distance "macs-mgit"))
;; 3.813699s real time, 6.051472s run time.  3.256658s spent in GC.
scheme@(guix-user)> ,profile (define foo (compute-distance "macs-mgit"))
%     cumulative   self             
time   seconds     seconds  procedure
 44.68     51.86      1.83  guix/memoization.scm:100:0
 17.55      0.72      0.72  hash-set!
 12.23      0.54      0.50  guix/utils.scm:863:2:mproc
  9.04      0.37      0.37  hash-ref
  4.26     47.60      0.17  guix/utils.scm:863:2
  3.19      0.13      0.13  list?
  2.13      0.09      0.09  string->list
  1.60      0.07      0.07  min
  1.06      0.04      0.04  ice-9/popen.scm:183:0:reap-pipes
  1.06      0.04      0.04  length
  0.53      0.26      0.02  guix/combinators.scm:37:2:fold2
  0.53      0.02      0.02  equal?
  0.53      0.02      0.02  gnu/packages.scm:246:32
  0.53      0.02      0.02  char=?
  0.53      0.02      0.02  pointer->string
  0.53      0.02      0.02  srfi/srfi-1.scm:951:15
  0.00  30583.00      0.00  ice-9/boot-9.scm:220:5:map1
  0.00      4.08      0.00  <current input>:31:9
  0.00      0.15      0.00  <current input>:17:0:compute-distance
  0.00      0.13      0.00  guix/discovery.scm:177:0:fold-module-public-variables
  0.00      0.11      0.00  guix/discovery.scm:184:19
  0.00      0.09      0.00  gnu/packages.scm:224:21
  0.00      0.09      0.00  guix/utils.scm:860:0:string-distance
  0.00      0.04      0.00  guix/packages.scm:933:0:supported-package?
  0.00      0.04      0.00  srfi/srfi-1.scm:734:0:find-tail
  0.00      0.04      0.00  %after-gc-thunk
  0.00      0.04      0.00  anon #x227d190
  0.00      0.02      0.00  ice-9/boot-9.scm:1673:4:with-exception-handler
  0.00      0.02      0.00  guix/discovery.scm:43:0:scheme-files
  0.00      0.02      0.00  gnu/packages.scm:237:0:fold-packages
  0.00      0.02      0.00  srfi/srfi-1.scm:452:2:fold
  0.00      0.02      0.00  guix/discovery.scm:137:8
  0.00      0.02      0.00  guix/build/syscalls.scm:993:4
  0.00      0.02      0.00  guix/discovery.scm:59:14
  0.00      0.02      0.00  guix/discovery.scm:100:0:scheme-modules
  0.00      0.02      0.00  guix/discovery.scm:148:0:all-modules
  0.00      0.02      0.00  guix/build/syscalls.scm:1014:0:scandir*
  0.00      0.02      0.00  srfi/srfi-1.scm:487:0:fold-right
---
Sample count: 188
Total time: 4.084680487 seconds (2.659723098 seconds in GC)
scheme@(guix-user)>
--8<---------------cut here---------------end--------------->8---