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

Previous Next

Full log

View this message in rfc822 format

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: bug#77725: 31.0.50; Add support for types accepted by `cl-typep' to cl-generic?
Date: Tue, 29 Apr 2025 17:49:51 +0200

On 2025-04-29 16:49, Stefan Monnier wrote:
>> ;; FIXME: This global operation is a bit worrisome, because it
>> ;; scales poorly with the number of types.  I guess it's OK
>> ;; for now because `cl-deftype' is not very popular, but it'll
>> ;; probably need to be replaced at some point.  Maybe we
>> ;; should simply require that the parents be defined already,
>> ;; then we can just `push' the new type, knowing it's in
>> ;; topological order by construction.
>>
>> It's not clear to me how "simply require that the parents be defined
>> already", makes the new type "in topological order by construction".
> 
> If they're already defined, it means they're already in the list, so if
> you add the new type at the head of the list you know this "child" comes
> before all its parents in the list.  If the list is constructed only by
> making such additions where we make sure the parents are already there,
> then the property is valid over the whole list.
> 
> Note, there's no magic: we should push the responsibility of topological
> sorting onto the programmers (who now have to define their types in
> topological order).

Of course, it makes much sense.  If I am not wrong, the constructor of the
class `cl-type-class' already ensures that parent types must be defined
before their "child" types (i.e. already added to the `cl--type-list' for
types defined with `cl-deftype").  So it should work to simply push a new
type at the beginning of the list.  And, when a type is redefined, move it
at the beginning of the list?

>> Also, as all this is done only at type (re)definition, which should
>> not happen so often, I am curious to know why you think "this global
>> operation is a bit worrisome"?
> 
> The algorithmic complexity of merge-ordered-list is O(N²), in the number
> of types IIRC, so while it may seem fine with 10 types, it could take
> more than a minute given enough type declarations.

I understand now, thanks!

> 
>> In `cl-types-of', I liked your idea to avoid calls to
>> `cl--type-parents' and `merge-ordered-list' before we do the
>> `gethash'.  I've gone a bit further in this direction (hopefully not
>> too far!) by doing all the type list computation just before creating
>> a new entry in the hash table. There's a slight overhead to determine
>> the types of objects not yet processed, but determining the types of
>> similar objects should be faster, which should be the most common case
>> (or at least the one to favor) when using types to dispatch methods.
> 
> +1
> 
> I notice that the `(null (assq type found))` is now ineffective, tho.
> Maybe it's OK and we should just remove it.

Good catch :-)  I think it's OK to just remove this test.

> Why all the `defsubst`?  Have you measured a noticeable speed difference
> by using them?  I have a hard time seeing how that could happen.
> All 3 `defsubst` in your patch are for function which contain
> a non-trivial loop, so I'd expect the overhead of a function call to be
> negligible.

Sorry, that's a bit paranoid of me, as I've heard many times that function
calls are inefficient in ELisp.  You're certainly right: in this case, the
overhead of a function call should be negligible.  I'll replace those
"defsubst" with "defun".

David

Previous Next

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