GNU bug report logs - #77725
31.0.50; Add support for types accepted by `cl-typep' to cl-generic?

Previous Next

Full log

Message #257 received at 77725 <at> debbugs.gnu.org (full text, mbox):

From: David Ponce <da_vid <at> orange.fr>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 77725 <at> debbugs.gnu.org, Eli Zaretskii <eliz <at> gnu.org>
Subject: Re: bug#77725: 31.0.50; Add support for types accepted by `cl-typep'
 to cl-generic?
Date: Sat, 24 May 2025 12:52:08 +0200

[Message part 1 (text/plain, inline)]

Hello Stefan,

Please find below the proposal for a new approach to speed up dispatch
of methods with derived type specializers.

Currently, to dispatch a method with derived type specializers, all
the derived types of all such methods are checked.  This is not very
efficient when the number of methods using derived types becomes high.

My reasoning is that to achieve the same only the method specializers
of the called generic function need to be checked.  For instance to
dispatch the below generic function `foo:

(cl-defmethod foo ((arg1 A) (arg2 B))
  ...
  )
(cl-defmethod foo ((arg1 A) (arg2 C))
  ...
  )

It is enough to test that the type of the objects passed to `foo'
belongs to the list of derived types (A B C).
              
Thus, the number of types to check will depend on the number of
different derived types "specializers" used in methods defined for one
generic function.  IMO, this number should remain very reasonable for
a given generic function.

The other advantage of this approach is that it limits the impact of
an ill-defined type to only the methods that use it, making error
handling in `cl-types-of' unnecessary.

It turns out that the dispatcher produced by the function
`cl--generic-get-dispatcher' already captures the list of methods of
the called generic function in its lexical environment.  So I modified
`cl--generic-get-dispatcher' to be able to pass this method list to
the tagcode function via an optional additional argument.  Then, I
modified the tagcode function of `cl--derived-type-generalizer' to
compute a "dispatch" list from the list of methods defined for the
called generic function.  This calculation is memoized to save time,
since the methods of a generic function shouldn't change much, except
perhaps during development.  Finally, I simplified the `cl-types-of'
function by removing error handling, no longer really useful here.

The tests in `cl-types-test' pass with the new implementation, which
also works well in some of my libraries I use daily :-)

I hope I didn't miss anything important!
Your opinion will obviously be more than welcome ;-)

Patch attached and a possible change log below.

Thanks!
David

2025-05-24  David Ponce  <da_vid <at> orange.fr>

	To speed up dispatch of methods with derived types specializers,
	limit the list of types that need to be checked to those used in
	methods specializers of the called generic function.

	* lisp/emacs-lisp/cl-generic.el (cl--generic-get-dispatcher): Add
	an optional second argument to the tagcode function to receive the
	methods of the called generic function.
        (cl--generic-derived-generalizer): Fix arglist of the tagcode
	function.

	* lisp/emacs-lisp/cl-extra.el (cl-types-of): There is no need to
	filter out errors: we can assume that the dispatch method is used
	only on sanely-defined types; when "cl-types-of" is called
	directly, whe can use the usual debugging tools to analyze and fix
	ill-defined types.
	(cl--derived-type-dispatch-memo): New variable.
	(cl--derived-type-dispatch-list): Replace variable by a function.
	(cl--derived-type-generalizer): Call it in the tagcode function.
	(cl--derived-type-generalizers): Simplify.

[cl-types-V0.patch (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.