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

[Stefan Monnier]

> ;; 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).

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

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

> WDYT

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.


        Stefan