A faster derived-mode-p

A faster derived-mode-p

[Lars Ingebrigtsen]

There are only 11K commands in the Emacs tree, so I don't know whether
the current default completion predicate is going to turn out to be
problematically slow or not.

It basically calls `provided-mode-derived-p' for all annotated commands,
and this is a loop that chases mode parenthood back to its ultimate
ancestor.

It seems like this could done more efficiently by just resolving the
chain at `define-derived-mode' time.  That is, in addition to putting
`derived-mode-parent', it could put `derived-mode-parents', too, where
it chases the chain upwards.  Then we'd just have to look at a single
property list...

Does anybody see any disadvantages to doing it this way?  (This would
speed up `derived-mode-p', which we use all over Emacs, in general.)

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: A faster derived-mode-p

[Dmitry Gutov]

On 14.02.2021 22:22, Lars Ingebrigtsen wrote:
> There are only 11K commands in the Emacs tree, so I don't know whether
> the current default completion predicate is going to turn out to be
> problematically slow or not.

I just evaluated

   (length (cl-delete-if-not #'commandp obarray))

in a running Emacs session with a bunch of third-party packages 
installed and loaded, and that still evaluated only to 1083.

So if derived-mode-p only needs to run 1000 times or so, perhaps it can 
still be fast enough, however inefficient it might look. I'd also 
recommend benchmarking with both implementations, if it's really too slow.

Also see the whole other implementation approach I mentioned in another 
thread.

Re: A faster derived-mode-p

[Basil L. Contovounesios]

Dmitry Gutov <dgutov@yandex.ru> writes:

> On 14.02.2021 22:22, Lars Ingebrigtsen wrote:
>> There are only 11K commands in the Emacs tree, so I don't know whether
>> the current default completion predicate is going to turn out to be
>> problematically slow or not.
>
> I just evaluated
>
>   (length (cl-delete-if-not #'commandp obarray))
>
> in a running Emacs session with a bunch of third-party packages installed and
> loaded, and that still evaluated only to 1083.

That's not counting the obarray's buckets.  I get ~6x as many results in
my session with (length (all-completions "" obarray #'commandp)).

-- 
Basil

Re: A faster derived-mode-p

[Óscar Fuentes]

"Basil L. Contovounesios" <contovob@tcd.ie> writes:

> Dmitry Gutov <dgutov@yandex.ru> writes:
>
>> On 14.02.2021 22:22, Lars Ingebrigtsen wrote:
>>> There are only 11K commands in the Emacs tree, so I don't know whether
>>> the current default completion predicate is going to turn out to be
>>> problematically slow or not.
>>
>> I just evaluated
>>
>>   (length (cl-delete-if-not #'commandp obarray))
>>
>> in a running Emacs session with a bunch of third-party packages installed and
>> loaded, and that still evaluated only to 1083.
>
> That's not counting the obarray's buckets.  I get ~6x as many results in
> my session with (length (all-completions "" obarray #'commandp)).

~10000 here.

Can't we memoize derived-mode-p ? It doesn't look like something that
could take a lot of space.

Re: A faster derived-mode-p

[Stefan Monnier]

> There are only 11K commands in the Emacs tree, so I don't know whether
> the current default completion predicate is going to turn out to be
> problematically slow or not.

Here's my suggestion:
Instead of trying to speed up those 10K predicates we're going to have
to evaluate, we could try to take advantage of the fact that there
should be a lot of redundancy there.

So we could do something like:

    (let ((cmds (make-hash-table :test #'equal)))
      (mapatom (lambda (sym)
                 (when (commandp sym)
                   (push sym (gethash (command-predicate sym) cmds)))))
      (let (active-cmds)
        (maphash (lambda (pred syms)
                   (when (funcall pred)
                     (cl-callf nconc active-cmds syms)))
                 cmds)
        active-cmds))

The only problem I can foresee here is that we have no guarantee that

    (equal (lambda () (derived-mode-p 'foo-mode))
           (lambda () (derived-mode-p 'foo-mode)))

To reduce the risk of such problems we could change the "predicate"
from being a function that takes 0 arguments, to being a list
a list (FUN . ARGS), so instead of

    (funcall pred)

we'd have to do:

    (apply pred)

So instead of

    (lambda () (derived-mode-p 'foo-mode))

the internal representation of the "predicate" would be

    (derived-mode-p foo-mode)

it should also make equality testing (within `gethash`) faster.

Of course, if we can arrange for the command predicates to be written
(in the source file) a single time for groups of commands (which would
also be beneficial to reduce the amount of redundancy in the source code
and the amount of work needed by authors), then we could even use `eq`
comparisons and still get most of the benefit.


        Stefan

Re: A faster derived-mode-p

[Dmitry Gutov]

On 15.02.2021 00:45, Basil L. Contovounesios wrote:
> That's not counting the obarray's buckets.  I get ~6x as many results in
> my session with (length (all-completions "" obarray #'commandp))

Oh, you're right, thanks. Still, that gives an estimate of how many 
times the function will be called in an average session.

And

   (benchmark 10000 '(derived-mode-p 'prog-mode))

prints ~0.01s here (unless caught in a GC).

Re: A faster derived-mode-p

[Lars Ingebrigtsen]

Dmitry Gutov <dgutov@yandex.ru> writes:

> Oh, you're right, thanks. Still, that gives an estimate of how many
> times the function will be called in an average session.
>
> And
>
>   (benchmark 10000 '(derived-mode-p 'prog-mode))
>
> prints ~0.01s here (unless caught in a GC).

Oh, thanks.  Then I guess my worries about the speed of that bit, at
least, were premature.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: A faster derived-mode-p

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Here's my suggestion:
> Instead of trying to speed up those 10K predicates we're going to have
> to evaluate, we could try to take advantage of the fact that there
> should be a lot of redundancy there.
>
> So we could do something like:
>
>     (let ((cmds (make-hash-table :test #'equal)))
>       (mapatom (lambda (sym)
>                  (when (commandp sym)
>                    (push sym (gethash (command-predicate sym) cmds)))))
>       (let (active-cmds)
>         (maphash (lambda (pred syms)
>                    (when (funcall pred)
>                      (cl-callf nconc active-cmds syms)))
>                  cmds)
>         active-cmds))

Hm, right...  As Dmitry showed, my worries about the inefficiency of
derived-mode-p seem exaggerated, but if it turns out to be a problem (or
we have more complex predicates), then doing something like this seems
promising.

However, the vast, vast number of the predicates basically devolve to
this (on the happy path):

(or (derived-mode-p 'foo-mode)
    (memq 'foo-mode minor-modes)
    (memq 'foo-mode global-minor-modes))

The derived-mode-p is fast, `minor-modes' is typically less than four
elements, and the same with `global-minor-modes'.  I'm not sure that
it's likely that looping over the symbols and entering the predicates
into a hash table has much scope for improving the speed much -- it'll
already be quite speedy.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no