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

[Stefan Monnier via "Bug reports for GNU Emacs, the Swiss army knife of text editors" <bug-gnu-emacs@gnu.org>]

> Yes, introducing this new variable will increase the complexity to the
> end user.

Exactly, and I think we should first try to solve the problem without
exposing the user to such complexity.

>> Here's the idea: the `<PKG>-autoloads.el` file can registers the longest
>> common prefix of all the `.el` files for its own `load-path` entry, with
>> say:
>>
>>     (load-prefix-register <DIR> <PREFIX>)
>>
>> where we'd define this function along the lines of
>>
>>     (defconst load-prefix-directories (make-hash-table :test 'equal))
>>       "Set of entries from `load-path` for which we have prefix info.")
>>
>>     (defconst load-prefix-map radix-tree-empty
>>       "Table associating file prefixes to directories.")
>>
>>     (defun load-prefix-register (dir prefix)
>>       (puthash dir t load-prefix-directories)
>>       (let ((dirs (radix-tree-lookup load-prefix-map prefix)))
>>         (unless (member dir dirs)
>>           (setq load-prefix-map (radix-tree-insert load-prefix-map prefix
>>                                                    (cons dir dirs))))))
>>
>>     (defun load-prefix-trim-load-path (file)
>>       "Return a trimmed `load-path` to use for FILE."
>>       (if (file-name-directory file)
>>           ;; If there's a `/` in FILE, fallback on the safe default.
>>           load-path
>>         (let* ((prefixes (radix-tree-prefixes load-prefix-map file))
>>                (dirs (apply #'append (mapcar #'cdr prefixes))))
>>           ;; Remove from `load-path` the entries which can't possibly
>>           ;; have FILE because their prefixes doesn't match.
>>           (cl-remove-if (lambda (dir)
>>                           (and (gethash dir load-prefix-directories)
>>                                (not (member dir dirs))))
>>                         load-path))))
>>
>> and then `load` can use `load-prefix-trim-load-path` to iterate on
>> a much shorter `load-path`.

Note that this above proposal should be transparent to the end user (tho
it requires extra work on the `package.el` side): e.g. funny changes
to `load-path` would be handled without fuss.

>> I'm not completely sure if it's a good idea, tho: I'd really prefer
>> a solution that doesn't require any change to any package management
>> code, which instead uses a cache (updated/filled automatically) of all
>> the files found in all the `load-path` directories.
> If that, we have to track the file/path changes in each entry of
> load-path, it may not be possible for all the supported OSs.

We can easily detect changes to `load-path` itself, of course, but as
for changes to the content of the directories in `load-path` that would
be more difficult&costly, admittedly.  My plan was to do nothing
about it (i.e. allow the cache to go stale): if we use the cache only to
tell `load` in which directory to look for the file, it should usually
be safe because IME it's rare for files to be added/removed from
directories such that it changes from which directory a given ELisp file
is loaded.  But of course we could also make efforts to try and keep our
cache consistent, e.g. via OS-level notification infrastructure or
by flushing the cache after a N seconds.


        Stefan