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>]

>> The downside is that it can break existing setups for users who use
>> `package.el` but also modify their `load-path` "by hand" in the
>> init file, and it doesn't help users who don't use `package.el`.
> The `load-hints' do nothing with its default value nil.

No, but if `package.el` adds elements to `load-hints` and then in your
init file you add more elements to `load-path`, the `load-hints` may end
up taking precedence over the new elements of `load-path` in some cases
and thus change which file shadows which.

> I had checked the radix-tree at the beginning, it's not user-friendly,
> or it's not easy to dump the radix tree for an end user to understand
> which is obviously matching the entry or not.

You're not "supposed" to look at the representation of the radix tree,
indeed (unless you're working on `radix-tree.el`, of course).
Feel free to ask for help using it.

> The `load-hints' in the list are easy to understand / maintain by the
> end user.

I don't think we need to burden end users with load hints.

>> But your prefix idea makes me think maybe we can aim for a significantly
>> smaller table, where we basically record only one entry per
>> package/directory, like for "~/.emacs.d/elpa/helm-core-VERSION/" we just
>> record "helm" because all the `.el` files share the "helm" prefix.
>> I.e. keep for each dir the corresponding longest-common-prefix.
>> If we're careful to consider only those files with a `.el` suffix, then
>> I think we can reduce the hint to such a longest-common-prefix.  I.e. an
>> info which doesn't say just "you can find FOO* files here" but "you can
>> find *only* FOO* files here".
>
> I had searched all 200+ packages in my test env, most of the packages
> use their feature name as the prefix, only 11 packages have
> exceptions. But I didn't understand how it works toward the
> `load-hints'.

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`.

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.

>> Is that with or without using `package-quickstart`?
> The `package-quickstart' does not help in this scenario,

AFAICT your scenario includes Emacs startup with packages installed, so
`package-quickstart' can definitely make a difference.  But maybe you're
right that it will affect both cases equally.

>> Similarly, I wasn't able to convince myself that your patch does the
>> right thing when `require` or `load` is used such that MUST_SUFFIX is
>> not specified.
> The `load-hints` just put the matched paths on the top of `load-path`,
> still following the `load-path' mechanism, and won't affect any other
> features (Or someone already has some code to adjust the `load-path'
> orders, can just ignore the `load-hints', everything work like before,
> no break changes).

But if FOO is in one dir and FOO.el is in another dir, adding entries
to the load path can change which file we end up loading.


        Stefan