Mark Shannon's presentation at the 2017 Language Summit

@ilevkivskyi

Mark observed that the typing module uses classes to represent types. This can be expensive, since e.g. the type List[int] really ought to be the tuple (List, int) but it's actually a class object which has a fair amount of overhead (though not as much as early versions of typing.py, since we now cache these class objects).

If we changed to tuples (or at least objects simpler than class object), we'd have a problem: The simpler object couldn't be subclassed from. But who subclasses List[int]? Then again, maybe simpler objects aren't the point?

Mark also pointed out that after

from typing import List
class C(List[int]): pass
print(C.__mro__)

We find that C.__mro__ has 17 items!

I confirmed this. The roughly equivalent code using collections.abc

from collections.abc import MutableMapping
class C(MutableMapping): pass
print(C.__mro__)

has only 7 items. And subclassing builtins.list

class C(list): pass
print(C.__mro__)

has only three.

This affects performance, e.g. which is faster?

class C(list, Sequence[int]): pass
C().append(1)
class D(Sequence[int], list): pass
D().append(1)

One append() call is 10% faster than the other.

I agree with Mark that this is a problem and can be a blocker for adopting type annotations for some projects. We are mostly shielded from the problem at Dropbox because we use comment annotations, but once we migrate to Python 3 we'd potentially have problems with the current approach as well.

Inheriting from List[int] (or, say Dict[str, Foo]) is occasionally useful and probably worth supporting, but Mark's suggestion to use a different syntax for this seems like a reasonable compromise. I think his suggestion was to do something like this, since List[int] is not a class:

from typing import implements, List

@implements(List[int])
class MyList(list): ...

It's unclear whether this would also affect user-defined generic classes. For example, consider this code that works currently:

class Box(Generic[T]): ...

class SpecialBox(Box[int]): ...

class AnotherBox(Box[T]): ...

def do_stuff(box: Box[int], box2: AnotherBox[str]) -> None: ...

If I understood things right, this would be written like this based on Mark's proposal:

class Box(Generic[T]): ...

@implements(Box[int])
class SpecialBox(Box): ...

@implements(Box[T])
class AnotherBox(Box): ...

def do_stuff(box: Box[int], box2: AnotherBox[str]) -> None: ... # No change

This would still mean that user-defined classes may trigger metaclass conflicts due to Generic. This would mostly happen with user-defined generic classes -- just inheriting from Iterable[str], for example, would no longer imply any metaclass restrictions.

These things should probably also work:

@implements(Tuple[int, str])
class MyTuple(tuple): ...

@implements(Tuple[int, ...])
class MyUniformTuple(tuple): ...

@implements('List[int]')  # Still slightly more efficient
class MyList(list): ...

Personally I think this part of the proposal is not workable. E.g. inheriting from Sequence (an existing ABC repurposed as a type) also adds some concrete default implementations, such as __iter__ and __contains__. You'd have to write

@implements(typing.Sequence[T])
class MyList(collections.abc.Sequence):
    ...

Maybe that could written like this:

@implements(typing.Sequence[T])
class MyList(typing.Sequence):
    ...

There would still be a duality -- Sequence and other ABCs would be both classes (for things like inheritance, isinstance, etc.) and types. However, indexing a generic class would result in an object that is only a type, not a class. So these would all be true:

typing.Sequence is both a class and a type (the latter would be equivalent to typing.Sequence[Any] in a type context).
typing.Sequence[int] is a type but not a class.
An annotation, a cast and @implements would work with arbitrary types.
Base classes must all be classes. They can only be types if the type is also a class.
A custom generic class MyList would be both a class and a type, but Mylist[int] would only be a type.
Generic type aliases like List[int] and also bare List are only types, not classes.
Each context where a type or a class is valid would always be either a type or a class context, not both. We'd have to document all of these. For example, the second argument to isinstance would be a class context, whereas the first argument to cast would be a type context.
String literal escaping is only valid in a type context.
Any, Union[...], None, Optional[...] and Callable[...] are types but not classes.

This is still a usability regressions and a backward compatibility break, as defining subclasses of generic classes would become different and slightly harder. However, maybe we can live with this, since after we have protocols, using Iterable[x] and other common ABCs as base classes would no longer be necessary. Also, by making the distinction between types and classes explicit, things may be less confusing for users.

Finally, generic types such as Dict[int, T] would have to be real objects, since we need to be able to index them, due to generic type aliases.

Does anyone actually define their own generics, or even inherit from a type?

As a data point, Zulip makes no use of inheritance to define a class and a type at the same time. In other words there is no code of the form class C(T): ... where T is a class in the typing module does not exist in the Zulip code base.

https://lgtm.com/query/1957210066/project:140750185/lang:python/

I've done both things (define own generics and inheriting from something lice Dict[str, str]) in the context of writing stubs for popular libraries, and I've done the second (inheriting from a specific realization of a generic) in application code

How often, though? I expect that it is a very rare thing to do.
For the first case (stub files):
Stub files are special, we never run them, so it might be OK to allow a type as a base class in stub files.
For the second (application code):
Is the code open source? It would be good to have some real world examples.

Mypy itself has three examples:

$ ag 'class.*\(Dict' mypy
mypy/binder.py
18:class Frame(Dict[Key, Type]):

mypy/nodes.py
2351:class SymbolTable(Dict[str, SymbolTableNode]):

mypy/test/testsemanal.py
215:class TypeInfoMap(Dict[str, TypeInfo]):

Also our internal Dropbox codebases have dozens of examples of dict subclasses. Subclassing list seems pretty rare though.

As a user, I'm not too bothered with the current state of things, since it's rare that I need to subclass a generic. (I found only a single inheritance from Generic[T] in my codebase.) I hope we won't switch to suboptimal APIs like @implements just to improve performance in rare cases.

@JelleZijlstra

@JelleZijlstra
It isn't just performance. Less code, means fewer bugs.
Also, keeping types and classes distinct in the implementation helps user maintain mental separation.

@JukkaL

@JukkaL
class Frame(Dict[Key, Type]): would be better (IMO) as

@implements(Mapping[Key, Type])
class Frame(dict):

That way the type (mapping) can be kept separate from the implementation (dict).

Similarly for the other two examples.

@markshannon

@markshannon What would then happen to methods defined in dict but not in Mapping, such as __init__? In particular:

Are they available through Frame (I suppose so, as otherwise there's no way to construct an instance)?
What will the signature of __init__ etc. be (with respect to type variables of dict)?

@gvanrossum I wonder if there would be a way to simplify the MROs even if we inherit from List[int] etc.? Could we filter out the cruft, and maybe have a separate __typed_mro__ attribute or something that would have all the generic base classes? Then we could use an inspection API to access the full MRO. This wouldn't directly help with the space usage of generic type objects, though, but maybe this would help with the slower method calls.

Here are my comments:

Is there an actual proposal, what exactly is proposed to change and why? This is completely unclear from the current discussion.
It is probably too late for any backward incompatible changes. I just checked and FWIW typing is downloaded from PyPI at around 580k downloads/month, and searching for typing imports on GitHub gives more than 25k files. Also my experience is that people complained even about small incompatible changes in internal API in 3.6.0.
I already mentioned few times in February that I did some profiling and have some ideas about how to speed-up typing. Unfortunately, I didn't have time to implement them.
It looks like protocols will resolve several problems mentioned above. For example, it will be not necessary to subclass Mapping[int, str] if a class implements it.

Yeah, migration would already be tricky. On the other hand, two years from now it would be still much harder, so if we are going change something fundamental, we should do it as soon as possible.

@gvanrossum

First of all a bit of history. In the run up to accepting PEP 484, in an email thread with @gvanrossum and @JukkaL I specifically requested that all isinstance() and issubclass() implementations be removed. Looking back, however, it looks as if I didn't make that public. My bad.

I have consistently been of the opinion that equating types and classes is a bad idea.
What has changed is that we now have evidence that doing so is complex and slow and that inheriting from a type is very rare.

@ilevkivskyi The specific proposal is that no classes representing types should inherit from type.
This would simplify the typing module and reduce its performance impact by a large amount.
But performance is not the only problem; coupling types to classes impairs understanding of an already subtle topic.

As the use of type-hints spread, I expect that applications that declare types will remain a (small?) minority, but that applications that use at least one module that uses type-hints will become common.
Therefore, most applications will pay the performance cost of loading the typing module plus the cost of creating types in their library code. We should keep that cost as small as possible, ideally zero.

FWIW isinstance() was indeed removed, per your request. issubclass() remains because there were problems with removing it. There's still an issue open about removing it.

@gvanrossum

OK, I have a POC implementation. Here are observations:

I use PyType_Check() to search for __base_subclass__ only on bases that are not class objects. Otherwise, this gives some speed penalty for normal classes (up to 20% for an empty class with four bases). If I search for __base_subclass__ only on non-classes, then the speed penalty is negligible.
In the case when at least one base has __base_subclass__ I save the original unmodified bases in the namespace under name __orig_bases__ before the class creation (this is the same that we do now with the help of the metaclass but done much faster).
I can't get rid of GenericMeta completely for one simple reason: __getitem__ (as other special methods) are searched immediately on the class (i.e. metaclass in our case).

Concerning the last point, there are two possible options:

a) go with a simple solution (it will already give great speed-up) and keep GenericMeta (I will document it then). There is a problem with this solution: many libraries use metaclasses, this means that users who want generic classes that subclass library classes will need to manually pass metaclass=... to all such classes, I could imagine this is annoying, and already have seen this complain several times.

b) We could modify PyObject_GetItem inserting a fallback for classes right before "object is not subscriptable". For example something like this (plus some safety checks):

...
PyObject_GetItem(PyObject *o, PyObject *key)
{
    ...
    if (PyType_Check(o)){
        fallback = PyObject_GetAttrString(o, "__class_getitem__")
        if (fallback == NULL){
            goto error;
        }
        esle{
            /* pack 'o' and 'key' into 'args'*/
            return _PyObject_FastCall(fallback, args, 2);
        }
    }
    ...
}

My idea is that people rarely subscript random things inside try: ... except TypeError: ... so that the speed penalty will be negligible.

@gvanrossum @ncoghlan what do you think? Should we go with option (a) or (b)?
(I like (b) a bit more since it is quite simple, however it introduces a new dunder.)

I'm not sure I'm entirely following the problem:

having typing.List be both a type & a class seems OK, and for backwards compatibility, you want the class AlsoGeneric(BaseGeneric): case to continue to work. So in that case, keeping the metaclass intact is fine.
the case to be changed is typing.List[int], and that already has a check in __getitem__ to throw TypeError, so dropping the metaclass just makes that more efficient (since GenericMeta.__getitem__ never gets called in the first place)
given the change, if folks want to type a subclass as a list wvia inheritance ithout making it a generic type, they can inherit from typing.List[Any] (and similarly for any other generic type, filling in as many 'Any's as are needed)

@ncoghlan

@ncoghlan
GenericMeta.__getitem__ is needed to make this work:

class Custom(Generic[T]): ...
Custom[int]  # Should be OK
Another(Custom[T]): ...
Another[int]  # Should be also OK

Everything else seems to be possible without a metaclass (only with __init_subclass__).

Concerning the performance there are two major slow-downs currently:

On subscription: Custom[int] creates a new class object (very expensive), this is necessary to make Custom[int] subclassable.
On member access: instantiation and all method calls on instances are slower for generic types because of complex MROs.

Both above problems will be fixed by __base_subclass__, the problem with metaclass is orthogonal, but the point is that if we go with __base_subclass__ then avoiding metaclass is possible (and easy) otherwise it would be a non-starter.

Two additional notes:

The old sys._getframe hack could be easily removed with help of __base_subclass__.
If we get rid of GenericMeta then in definitions like class Mapping(Iterable[KT], Generic[KT, VT]): ... the Generic[...] should always be the last base, otherwise a consistent MRO is not always possible.

Regarding the name, while Jelle's right that the implemented name is __init_subclass__ (we went back and forth enough times during the design process that I often forget where we ended up), the new API should still be __subclass_base__, as __base_subclass__ sounds like we're requesting a subclass of the base class, which isn't what's happening.

The TypeVar case is an interesting one, but it seems to me that it could potentially be addressed by:

Always calling __subclass_base__ on GenericMeta instances
Duplicating the current _check_generic call from getitem, and returning the class itself from __subclass_base__ if it's actually still generic

If the isinstance check also proves to be too slow (or otherwise impractical), then I'd suggest we look at ways of optimising that before going down the __class_getitem__ path.

@ncoghlan

@ncoghlan

Regarding the name ...

OK

The TypeVar case is an interesting one, but it seems to me that it could potentially be addressed by...

Yes, it works perfectly if we keep the GenericMeta, the only problem is that keeping GenericMeta will cause metaclass conflicts, this is why I am not 100% happy with it. But anyway, it seems to me the best strategy is to do this in two steps:

First add __subclass_base__ that will fix all major performance issues (plus an old sys._getframe hack). At the same time keep GenericMeta but simplify its code significantly.
If people will continue complaining about metaclass conflicts, then consider adding __class_getitem__.

I'm a little lost. Ivan, if you have an implementation somewhere, can you link to it? I presume it's modifications to the C code of CPython? If we're going that route, what will happen on Python 3.5 and before? (Or on 3.6 and before if we decide this is too invasive to go into CPython 3.6.3.) I suppose you can fall back to metaclasses.

If we want Custom[int] without a metaclass, and we're changing C code anyways, could we add a __getitem__ implementation to type itself that defers to __class_getitem__?

Another solution to the 3rd party metaclass problem (which is real) could be to just recommend people inherit their metaclass from abc.ABCMeta instead of directly from type -- would that work in most cases? (I realize it would slow things down.)

Why is this still in the "Mark Shannon" thread? I think I missed a part of the conversation.

@gvanrossum

@gvanrossum

I'm a little lost

Sorry, probably we went to fast. Here is a short summary:

Some time ago Mark complained about several performance issues with typing
One of the possible solutions is to make a small change to CPython allowing non-classes to be present in the base classes list (so that List[int] will not be a class). This solution also has several other pluses like removing an old sys._getframe hack.
My POC is here Reference implementation of __class_getitem__ and __mro_entries__ ilevkivskyi/cpython#2 (only the C part).
An important conclusion that we get from POC implementation is that it will not cause any visible slow-downs for normal (non-generic) classes.
Then there appeared an idea that we can also fix the metaclass conflicts with a bit extended version of the same change plus __class_getitem__.

If we're going that route, what will happen on Python 3.5 and before? (Or on 3.6 and before if we decide this is too invasive to go into CPython 3.6.3.) I suppose you can fall back to metaclasses.

Most probably we will need to have a separate source file for newer versions (like we now have for Python 2 and 3). I think there will be so many fallbacks so that the code will be hard to read. I expect that __subclass_base__ will really simplify the code. I am going to invest more time to show how it will look.

...could we add a __getitem__ implementation to type itself that defers to __class_getitem__?

This is actually another possibility that I was thinking about. Maybe it is even better (it is a more "local" change anyway).

recommend people inherit their metaclass from abc.ABCMeta instead of directly from type -- would that work in most cases?

It will probably fix vast majority of metaclass conflicts. I think we should start from a simple solution (i.e. have very minimal changes to CPython and keep GenericMeta), this will already fix most performance issues. Then (if people will continue to complain about metaclass conflicts) we may remove GenericMeta, this is a quite independent problem.

I've gotta focus elsewhere for a while, but I'd like to note that I was probably wrong about recommending people inherit their metaclasses from ABCMeta -- it'll still be a metaclass conflict.

it'll still be a metaclass conflict

Yes, sorry, you are right, I was confused by the fact that this works:

class C(typing.List[int], collections.abc.Sequence): ...

Anyway, I am still not sure what to do. If you think we might go with __class_getitem__, then I will come up with an extended POC implementation.

(It probably makes sense to break this tangent out into a new issue, but I'll continue here for now)

I think it makes sense to break exploration of this idea into 3 phases:

See how far you can get by doing something like this in typing.TypingMeta.__new__ before calling super().__new__:

    def _keep_base(x):
        return x
    new_bases = tuple(getattr(base, "__subclass_base__", _keep_base)() for base in bases)
    if new_bases != bases:
        # Bases list changed, check if that changes the metaclass
        orig_meta = type(cls)
        unhinted_meta, __, __ = types.prepare_class(name, bases)
        if orig_meta is unhinted_meta:
            # Original metaclass matched the one derived from the bases list, so recalculate it
            new_meta, __, __ = types.prepare_class(name, new_bases)
            if new_meta is not orig_meta:
                # Start the class creation over again with the new metaclass
                # and no keyword arguments (disallowing `typing.TypingMeta` subclasses)
                return new_meta(name, new_bases, namespace)

That is, allowing non-classes in a subclass bases list would be a feature of typing.TypingMeta, not a generally available Python level feature. As a result, it can't have a performance impact on standard class definitions, at the price of making derivation from typing.TypingMeta a bit slower.

1a. Potentially look at exposing better building blocks (e.g. a types.recalculate_metaclass function) for metaclasses wanting to get up to these kinds of tricks (OTOH, it's not exactly the sort of thing we want to encourage, since it can break in all sorts of interesting and exciting ways if you're not careful with it)

Look at how feasible it would be to make __subclass_base__ support a standard feature of the type system in 3.7+, rather than something specific to typing.TypingMeta. This would avoid the triple calculation of the derived metaclass from the list of bases, the double execution of parts of the metaclass instantiation process, and the incompatibility between the use of __subclass_base__ and keyword arguments in class definitions.
Look at how feasible it would be to add a type.__getitem__ implementation in 3.7+ that delegates to __class_getitem__ on the instance (potentially eliminating the need for typing.GenericMeta entirely).

@ncoghlan

@ncoghlan

See how far you can get by doing something like this in typing.TypingMeta.__new__ before calling super().__new__

The problem is to get TypingMeta.__new__ called in the first place. The problem is that cases like this:

class C(<a class>, <not a class>):
    ...

will fail soon in _PyType_CalculateMetaclass so that I don't think we can do something without modifying the C code.

@ilevkivskyi

@ilevkivskyi Ah, you're right, I completely forgot that the initial metaclass determination step itself would fail. D'oh :(

The original performance issue is now addressed by PEP 560.

Navigation Menu

Repository navigation

Mark Shannon's presentation at the 2017 Language Summit #432

24 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Mark Shannon's presentation at the 2017 Language Summit #432

Description

Activity

JukkaL commented on May 18, 2017

gvanrossum commented on May 18, 2017

JukkaL commented on May 18, 2017

markshannon commented on May 18, 2017

dmoisset commented on May 18, 2017

markshannon commented on May 18, 2017

JukkaL commented on May 18, 2017

JelleZijlstra commented on May 18, 2017

markshannon commented on May 18, 2017

markshannon commented on May 18, 2017

JukkaL commented on May 18, 2017

ilevkivskyi commented on May 18, 2017

JukkaL commented on May 18, 2017

markshannon commented on May 19, 2017

gvanrossum commented on May 19, 2017

24 remaining items

ilevkivskyi commented on Jul 19, 2017

ncoghlan commented on Jul 19, 2017

ilevkivskyi commented on Jul 19, 2017

ilevkivskyi commented on Jul 19, 2017

ncoghlan commented on Jul 19, 2017

ilevkivskyi commented on Jul 19, 2017

gvanrossum commented on Jul 19, 2017

ilevkivskyi commented on Jul 19, 2017

gvanrossum commented on Jul 19, 2017

ilevkivskyi commented on Jul 19, 2017

ncoghlan commented on Jul 20, 2017

ilevkivskyi commented on Jul 20, 2017

ncoghlan commented on Jul 20, 2017

ilevkivskyi commented on Jun 4, 2018

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions