[Python-Dev] Type of range object members (original) (raw)

"Martin v. Löwis" martin at v.loewis.de
Wed Aug 16 22:21:54 CEST 2006

Neal Norwitz schrieb:

I was playing around with a little patch to avoid that penalty. It doesn't take any additional memory, just a handful of bits we aren't using. :-)

There are common schemes that allow constant-time issubclass tests, although they do require more memory:

  1. give each base class a small unique number, starting with 1 (0 means no number has been assigned). Give each class a bitmap of all base classes, plus a field for the maximum-numbered base class. Then,

    def issubclass(C, B): return B.classnum and (B.classnum < C.maxbasenum) and
    bit_set(C.basenums, B.classnum) Supports multiple inheritance, space requirement linear with the number of classes that are used as base classes. Numbering should recycle class numbers when a class is gced.

  2. restrict optimization to single-inheritance. Give each class a "depth" (distance from object, 0 for object and multiply-inherited classes). Also give each class an array of bases, ordered by depth. Then,

    def issubclass(C, B): if not C.depth: return expensive_issubclass(C, B) return B.depth < C.depth and (C.bases[B.depth] is B)

    Space requirement is linear with the depth of the class (but I think tp_mro could be used, if the formula is changed to (C.bases[C.depth-B.depth] is B))

Regards, Martin

More information about the Python-Dev mailing list