Move to a metaclass for handling __module__.

This offers the absolute best performance at what seems like reasonable complexity.

+-------------------------------------------------------------+----------------+-------------------------------+
| Benchmark                                                   | 38-master-full | 38-faster-meta                |
+=============================================================+================+===============================+
| read __module__                                             | 41.8 ns        | 40.9 ns: 1.02x faster (-2%)   |
+-------------------------------------------------------------+----------------+-------------------------------+
| read __name__                                               | 41.8 ns        | 39.9 ns: 1.05x faster (-5%)   |
+-------------------------------------------------------------+----------------+-------------------------------+
| read providedBy                                             | 56.9 ns        | 58.4 ns: 1.03x slower (+3%)   |
+-------------------------------------------------------------+----------------+-------------------------------+
| query adapter (no registrations)                            | 3.85 ms        | 2.95 ms: 1.31x faster (-24%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| query adapter (all trivial registrations)                   | 4.62 ms        | 3.63 ms: 1.27x faster (-21%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| query adapter (all trivial registrations, wide inheritance) | 51.8 us        | 42.2 us: 1.23x faster (-19%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| query adapter (all trivial registrations, deep inheritance) | 52.0 us        | 41.7 us: 1.25x faster (-20%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| sort interfaces                                             | 234 us         | 29.9 us: 7.84x faster (-87%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| sort mixed                                                  | 569 us         | 340 us: 1.67x faster (-40%)   |
+-------------------------------------------------------------+----------------+-------------------------------+
| contains (empty dict)                                       | 135 ns         | 55.2 ns: 2.44x faster (-59%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| contains (populated dict: interfaces)                       | 137 ns         | 56.1 ns: 2.45x faster (-59%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| contains (populated list: interfaces)                       | 39.7 us        | 2.96 us: 13.42x faster (-93%) |
+-------------------------------------------------------------+----------------+-------------------------------+
| contains (populated dict: implementedBy)                    | 137 ns         | 55.2 ns: 2.48x faster (-60%)  |
+-------------------------------------------------------------+----------------+-------------------------------+
| contains (populated list: implementedBy)                    | 40.6 us        | 24.1 us: 1.68x faster (-41%)  |
+-------------------------------------------------------------+----------------+-------------------------------+

Not significant (2): read __doc__; sort implementedBy

2 files changed, 203 insertions, 71 deletions

diff --git a/benchmarks/micro.py b/benchmarks/micro.py
index 779298c..a9527db 100644
--- a/benchmarks/micro.py
+++ b/benchmarks/micro.py
@@ -2,6 +2,7 @@ import pyperf
 
 from zope.interface import Interface
 from zope.interface import classImplements
+from zope.interface import implementedBy
 from zope.interface.interface import InterfaceClass
 from zope.interface.registry import Components
 
@@ -12,6 +13,30 @@ ifaces = [
     for i in range(100)
 ]
 
+class IWideInheritance(*ifaces):
+    """
+    Inherits from 100 unrelated interfaces.
+    """
+
+class WideInheritance(object):
+    pass
+classImplements(WideInheritance, IWideInheritance)
+
+def make_deep_inheritance():
+    children = []
+    base = Interface
+    for iface in ifaces:
+        child = InterfaceClass('IDerived' + base.__name__, (iface, base,), {})
+        base = child
+        children.append(child)
+    return children
+
+deep_ifaces = make_deep_inheritance()
+
+class DeepestInheritance(object):
+    pass
+classImplements(DeepestInheritance, deep_ifaces[-1])
+
 def make_implementer(iface):
     c = type('Implementer' + iface.__name__, (object,), {})
     classImplements(c, iface)
@@ -37,7 +62,21 @@ def bench_in(loops, o):
 
     return pyperf.perf_counter() - t0
 
-def bench_query_adapter(loops, components):
+def bench_sort(loops, objs):
+    import random
+    rand = random.Random(8675309)
+
+    shuffled = list(objs)
+    rand.shuffle(shuffled)
+
+    t0 = pyperf.perf_counter()
+    for _ in range(loops):
+        for _ in range(INNER):
+            sorted(shuffled)
+
+    return pyperf.perf_counter() - t0
+
+def bench_query_adapter(loops, components, objs=providers):
     # One time through to prime the caches
     for iface in ifaces:
         for provider in providers:
@@ -46,10 +85,11 @@ def bench_query_adapter(loops, components):
     t0 = pyperf.perf_counter()
     for _ in range(loops):
         for iface in ifaces:
-            for provider in providers:
+            for provider in objs:
                 components.queryAdapter(provider, iface)
     return pyperf.perf_counter() - t0
 
+
 def bench_getattr(loops, name, get=getattr):
     t0 = pyperf.perf_counter()
     for _ in range(loops):
@@ -68,10 +108,6 @@ def bench_getattr(loops, name, get=getattr):
 
 runner = pyperf.Runner()
 
-# TODO: Need benchmarks of adaptation, etc, using interface inheritance.
-# TODO: Need benchmarks of sorting (e.g., putting in a BTree)
-# TODO: Need those same benchmarks for implementedBy/Implements objects.
-
 runner.bench_time_func(
     'read __module__', # stored in C, accessed through __getattribute__
     bench_getattr,
@@ -108,7 +144,6 @@ runner.bench_time_func(
 )
 
 def populate_components():
-
     def factory(o):
         return 42
 
@@ -127,6 +162,43 @@ runner.bench_time_func(
 )
 
 runner.bench_time_func(
+    'query adapter (all trivial registrations, wide inheritance)',
+    bench_query_adapter,
+    populate_components(),
+    [WideInheritance()],
+    inner_loops=1
+)
+
+runner.bench_time_func(
+    'query adapter (all trivial registrations, deep inheritance)',
+    bench_query_adapter,
+    populate_components(),
+    [DeepestInheritance()],
+    inner_loops=1
+)
+
+runner.bench_time_func(
+    'sort interfaces',
+    bench_sort,
+    ifaces,
+    inner_loops=INNER,
+)
+
+runner.bench_time_func(
+    'sort implementedBy',
+    bench_sort,
+    [implementedBy(p) for p in implementers],
+    inner_loops=INNER,
+)
+
+runner.bench_time_func(
+    'sort mixed',
+    bench_sort,
+    [implementedBy(p) for p in implementers] + ifaces,
+    inner_loops=INNER,
+)
+
+runner.bench_time_func(
     'contains (empty dict)',
     bench_in,
     {},
@@ -134,15 +206,29 @@ runner.bench_time_func(
 )
 
 runner.bench_time_func(
-    'contains (populated dict)',
+    'contains (populated dict: interfaces)',
     bench_in,
     {k: k for k in ifaces},
     inner_loops=INNER
 )
 
 runner.bench_time_func(
-    'contains (populated list)',
+    'contains (populated list: interfaces)',
     bench_in,
     ifaces,
     inner_loops=INNER
 )
+
+runner.bench_time_func(
+    'contains (populated dict: implementedBy)',
+    bench_in,
+    {implementedBy(p): 1 for p in implementers},
+    inner_loops=INNER
+)
+
+runner.bench_time_func(
+    'contains (populated list: implementedBy)',
+    bench_in,
+    [implementedBy(p) for p in implementers],
+    inner_loops=INNER
+)
diff --git a/src/zope/interface/interface.py b/src/zope/interface/interface.py
index aa66c22..3818b89 100644
--- a/src/zope/interface/interface.py
+++ b/src/zope/interface/interface.py
@@ -20,7 +20,6 @@ from types import FunctionType
 import weakref
 
 from zope.interface._compat import _use_c_impl
-from zope.interface._compat import PYTHON3 as PY3
 from zope.interface.exceptions import Invalid
 from zope.interface.ro import ro as calculate_ro
 from zope.interface import ro
@@ -239,56 +238,6 @@ class NameAndModuleComparisonMixin(object):
         return c >= 0
 
 
-class _ModuleDescriptor(str):
-    # Descriptor for ``__module__``, used in InterfaceBase and subclasses.
-    #
-    # We store the module value in ``__ibmodule__`` and provide access
-    # to it under ``__module__`` through this descriptor. This is
-    # because we want to store ``__module__`` in the C structure (for
-    # speed of equality and sorting), but it's very hard to do
-    # that. Using PyMemberDef or PyGetSetDef (the C
-    # versions of properties) doesn't work without adding
-    # metaclasses: creating a new subclass puts a ``__module__``
-    # string in the class dict that overrides the descriptor that
-    # would access the C structure data.
-    #
-    # We must also preserve access to the *real* ``__module__`` of the
-    # class.
-    #
-    # Our solution is to watch for new subclasses and manually move
-    # this descriptor into them at creation time. We could use a
-    # metaclass, but this seems safer; using ``__getattribute__`` to
-    # alias the two imposed a 25% penalty on every attribute/method
-    # lookup, even when implemented in C.
-
-    # type.__repr__ accesses self.__dict__['__module__']
-    # and checks to see if it's a native string. If it's not,
-    # the repr just uses the __name__. So for things to work out nicely
-    # it's best for us to subclass str.
-    if PY3:
-        # Python 2 doesn't allow non-empty __slots__ for str
-        # subclasses.
-        __slots__ = ('_class_module',)
-
-    def __init__(self, class_module):
-        str.__init__(self)
-        self._class_module = class_module
-
-    def __get__(self, inst, kind):
-        if inst is None:
-            return self._class_module
-        return inst.__ibmodule__
-
-    def __set__(self, inst, val):
-        # Setting __module__ after construction is undefined. There are
-        # numerous things that cache based on it, either directly or indirectly.
-        # Nonetheless, it is allowed.
-        inst.__ibmodule__ = val
-
-    def __str__(self):
-        return self._class_module
-
-
 @_use_c_impl
 class InterfaceBase(NameAndModuleComparisonMixin, SpecificationBasePy):
     """Base class that wants to be replaced with a C base :)
@@ -307,7 +256,10 @@ class InterfaceBase(NameAndModuleComparisonMixin, SpecificationBasePy):
     def _call_conform(self, conform):
         raise NotImplementedError
 
-    __module__ = _ModuleDescriptor(__name__)
+    @property
+    def __module_property__(self):
+        # This is for _InterfaceMetaClass
+        return self.__ibmodule__
 
     def __call__(self, obj, alternate=_marker):
         """Adapt an object to the interface
@@ -578,7 +530,105 @@ class Specification(SpecificationBase):
         return default if attr is None else attr
 
 
-class InterfaceClass(InterfaceBase, Element, Specification):
+class _InterfaceMetaClass(type):
+    # Handling ``__module__`` on ``InterfaceClass`` is tricky. We need
+    # to be able to read it on a type and get the expected string. We
+    # also need to be able to set it on an instance and get the value
+    # we set. So far so good. But what gets tricky is that we'd like
+    # to store the value in the C structure (``__ibmodule__``) for
+    # direct access during equality, sorting, and hashing. "No
+    # problem, you think, I'll just use a property" (well, the C
+    # equivalents, ``PyMemberDef`` or ``PyGetSetDef``).
+    #
+    # Except there is a problem. When a subclass is created, the
+    # metaclass (``type``) always automatically puts the expected
+    # string in the class's dictionary under ``__module__``, thus
+    # overriding the property inherited from the superclass. Writing
+    # ``Subclass.__module__`` still works, but
+    # ``instance_of_subclass.__module__`` fails.
+    #
+    # There are multiple ways to workaround this:
+    #
+    # (1) Define ``__getattribute__`` to watch for ``__module__`` and return
+    # the C storage.
+    #
+    # This works, but slows down *all* attribute access (except,
+    # ironically, to ``__module__``) by about 25% (40ns becomes 50ns)
+    # (when implemented in C). Since that includes methods like
+    # ``providedBy``, that's probably not acceptable.
+    #
+    # All the other methods involve modifying subclasses. This can be
+    # done either on the fly in some cases, as instances are
+    # constructed, or by using a metaclass. These next few can be done on the fly.
+    #
+    # (2) Make ``__module__`` a descriptor in each subclass dictionary.
+    # It can't be a straight up ``@property`` descriptor, though, because accessing
+    # it on the class returns a ``property`` object, not the desired string.
+    #
+    # (3) Implement a data descriptor (``__get__`` and ``__set__``) that
+    # is both a string, and also does the redirect of ``__module__`` to ``__ibmodule__``
+    # and does the correct thing with the ``instance`` argument to ``__get__`` is None
+    # (returns the class's value.)
+    #
+    # This works, preserves the ability to read and write
+    # ``__module__``, and eliminates any penalty accessing other
+    # attributes. But it slows down accessing ``__module__`` of instances by 200%
+    # (40ns to 124ns).
+    #
+    # (4) As in the last step, but make it a non-data descriptor (no ``__set__``).
+    #
+    # If you then *also* store a copy of ``__ibmodule__`` in
+    # ``__module__`` in the instances dict, reading works for both
+    # class and instance and is full speed for instances. But the cost
+    # is storage space, and you can't write to it anymore, not without
+    # things getting out of sync.
+    #
+    # (Actually, ``__module__`` was never meant to be writable. Doing
+    # so would break BTrees and normal dictionaries, as well as the
+    # repr, maybe more.)
+    #
+    # That leaves us with a metaclass. Here we can have our cake and
+    # eat it too: no extra storage, and C-speed access to the
+    # underlying storage. The only cost is that metaclasses tend to
+    # make people's heads hurt. (But still less than the descriptor-is-string, I think.)
+
+    def __new__(cls, name, bases, attrs):
+        try:
+            # Figure out what module defined the interface.
+            # This is how cPython figures out the module of
+            # a class, but of course it does it in C. :-/
+            __module__ = sys._getframe(1).f_globals['__name__']
+        except (AttributeError, KeyError): # pragma: no cover
+            pass
+        # Get the C optimized __module__ accessor and give it
+        # to the new class.
+        moduledescr = InterfaceBase.__dict__['__module__']
+        if isinstance(moduledescr, str):
+            # We're working with the Python implementation,
+            # not the C version
+            moduledescr = InterfaceBase.__dict__['__module_property__']
+        attrs['__module__'] = moduledescr
+        kind = type.__new__(cls, name, bases, attrs)
+        kind.__module = __module__
+        return kind
+
+    @property
+    def __module__(cls):
+        return cls.__module
+
+    def __repr__(cls):
+        return "<class '%s.%s'>" % (
+            cls.__module,
+            cls.__name__,
+        )
+
+_InterfaceClassBase = _InterfaceMetaClass(
+    'InterfaceClass',
+    (InterfaceBase, Element, Specification),
+    {}
+)
+
+class InterfaceClass(_InterfaceClassBase):
     """
     Prototype (scarecrow) Interfaces Implementation.
 
@@ -591,15 +641,11 @@ class InterfaceClass(InterfaceBase, Element, Specification):
     #
     #implements(IInterface)
 
-    def __new__(cls, *args, **kwargs):
-        if not isinstance(
-                cls.__dict__.get('__module__'),
-                _ModuleDescriptor):
-            cls.__module__ = _ModuleDescriptor(cls.__dict__['__module__'])
-        return super(InterfaceClass, cls).__new__(cls)
-
     def __init__(self, name, bases=(), attrs=None, __doc__=None,  # pylint:disable=redefined-builtin
                  __module__=None):
+        # We don't call our metaclass parent directly
+        # pylint:disable=non-parent-init-called
+        # pylint:disable=super-init-not-called
         if not all(isinstance(base, InterfaceClass) for base in bases):
             raise TypeError('Expected base interfaces')
 
@@ -620,9 +666,9 @@ class InterfaceClass(InterfaceBase, Element, Specification):
                     pass
 
         InterfaceBase.__init__(self, name, __module__)
-
         assert '__module__' not in self.__dict__
-        assert self.__module__ == __module__, (self.__module__, __module__, self.__ibmodule__)
+        assert self.__ibmodule__ is self.__module__ is __module__
+
         d = attrs.get('__doc__')
         if d is not None:
             if not isinstance(d, Attribute):