bug#41646: Startup in Windows is very slow when load-path contains many

[Stefan Monnier]

> In both GNU ELPA and NonGNU ELPA only about 10% of the packages had
> a non-empty common prefix, which means that `load` would be able to
> skip about 90% of the package directories.

Hmm.. so I tried to build a table (represented as a radix tree) that
maps prefixes to the corresponding list of directories where such files
can be found:

    (defun load--build-filter-map (path suffixes)
      (let ((prefix-map radix-tree-empty)
            (completion-regexp-list
             ;; Note 1: Ignore hidden files to weed out `.dir-locals.el'.
             (list (concat "\\`[^.].*" (regexp-opt suffixes) "\\'"))))
        (dolist (dir (reverse path))
          (when (file-directory-p dir)
            ;; FIXME: `prefix' may be *too long* because it includes a suffix,
            ;; as is the case for `leim-list.el' in `lisp/leim'!
            (let* ((prefix (or (ignore-errors (file-name-completion "" dir))
                               ""))
                   (subtree (radix-tree-subtree prefix-map prefix)))
              (unless (radix-tree-lookup subtree "")
                (let ((ps (car (radix-tree-prefixes prefix-map prefix))))
                  (unless (or (null ps) (< (length (car ps)) (length prefix)))
                    (message "prefix=%S   ps = %S" prefix ps))
                  (setq prefix-map (radix-tree-insert prefix-map prefix
                                                      (cons dir (cdr ps))))))
              (radix-tree-iter-mappings
               subtree
               (lambda (subprefix dirs)
                 (setq prefix-map (radix-tree-insert
                                   prefix-map (concat prefix subprefix)
                                   (cons dir dirs))))))))
        prefix-map))

That seems to work.  E.g. in `emacs -Q` we see that the table has a few
different prefixes ("o" for org, "u" for url, "calc" for calc, "mh-" for
mh-e, "e" for eshell, and "" for the rest) and e.g. the prefix "" is
mapped to the list of all dirs except those with a non-empty prefix,
whereas the "o" prefix is mapped to that same list plus the org
subdirectory, ...  Then `load` can use this table to quickly (a single
lookup) replace the full `load-path` with a shorter list.

In my "normal" Emacs, where I have more than 800 entries in `load-path`,
most prefixes are mapped to lists of ~90 entries, which is
a nice improvement.

But there are two problems:

- The above function takes too much time to build the table.  With my
  800 entries it takes ~0.5s to build the table.  This might be
  acceptable if we can make sure it's run only once, but if the table is
  built "on demand" and flushed whenever `load-path` changes, then in my
  config it's called 10 times in a normal startup, presumably because
  it's called at different stages of building `load-path` (I have not
  dug deeper to find the actual source).

- The above table doesn't scale nicely.  The problem is that the number
  of prefixes is more or less proportional to the number of directories,
  but the length of the directories lists associated to each prefix is
  also basically proportional to the number of directories.  So in an
  `emacs -Q` (with a 24-element `load-path`), that table occupies a mere
  4kB but in my full config with 800 elements in `load-path` that grows
  to 500kB.

Maybe the "full table" approach will work better:

    (defun load--build-file-map (path suffixes)
      (let ((map (make-hash-table :test 'equal))
            (completion-regexp-list
             ;; Note 1: Ignore hidden files to weed out `.dir-locals.el'.
             (list (concat "\\`[^.].*" (regexp-opt suffixes) "\\'"))))
        (dolist (dir (reverse path))
          (when (file-directory-p dir)
            ;; FIXME: `prefix' may be *too long* because it includes a suffix,
            ;; as is the case for `leim-list.el' in `lisp/leim'!
            (let* ((files (ignore-errors (file-name-all-completions "" dir)))
                   (dirs (list dir)))
              (dolist (file files) (puthash file dirs map)))))
        map))

this function doesn't try to mess with prefixes and instead collects all
the files in all the directories and builds a "reverse" table which maps
filenames to the directory in which they're found.

- It's much faster to build (~0.1s).
- It filters the `load-path` even more effectively: N hash-table lookups
  (for each of the N suffixes) will return at most N directories where
  the file can be found, and in most cases it returns N times the same
  directory so `load` will typically need to look only at
  a single directory.
- It takes more space: in an `emacs -Q` the table uses up already
  around 180kB.  But it scales better: with my full config the table
  grows "only" to ~730kB.

I get the impression that these tables are too big, tho.  So maybe
a better approach is one that leaves a bit more work to `load`,
e.g. where we build a table that just maps directories to their longest
common prefix (that can be done quickly and doesn't take up
significantly more space than `load-path` itself), and then in `load` or
`openp` we lookup this table to dynamically filter out the elements of
`load-path` that don't apply to the current file: i.e. we still have to
loop through the whole 800-element `load-path` but we'd only touch the
filesystem in the ~90 directories that are not excluded by
their prefix.


        Stefan