[Python-Dev] pre-PEP on optimized global names

[Jeremy Hylton]

I've been hoping to work on optimized global and builtin name support
for Python 2.2.  I'm not sure if I'll have time, but thought I'd
circulate a draft with some notes on the subject now.  Anyone
interested in this work?

Jeremy

PEP: ???
Title: Optimized Access to Module and Builtin Names
Author: jeremy@digicool.com (Jeremy Hylton)
Status: Draft
Type: Standards Track
Python-Version: 2.2
Created: 23-May-2001

Abstract

    This PEP proposes a new implementation of global module namespaces
    and the builtin namespace that speeds name resolution.  The
    implementation would use an array of object pointers for most
    operations in these namespaces.  The compiler would assign indices
    for global variables at compile time.

    The current implementation represents these namespaces as
    dictionaries.  A global name incurs a dictionary lookup each time
    it is used; a builtin name incurs two dictionary lookups, a failed
    lookup in the global namespace and a second lookup in the builtin
    namespace. 

    This implementation should speed Python code that uses
    module-level functions and variables.  It should also eliminate
    awkward coding styles that have evolved to speed access to these
    names.

    The implementation is complicated because the global and builtin
    namespaces can be modified dynamically in ways that are impossible
    for the compiler to detect.  (Example: A module's namespace is
    modified by a script after the module is imported.)  As a result,
    the implementation must maintain several auxillary data structures
    to preserve these dynamic features.

Introduction

    [expand on the basic ideas in the abstract]

    [describe the key parts of the design: dlict, compiler support,
    stupid name trick workarounds, optimization of other module's
    globals] 

DLict design

    The namespaces are implemented using a data structure that has
    sometimes gone under the name dlict.  It is a dictionary that has
    numbered slots for some dictionary entries.  The type must be
    implemented in C to achieve acceptable performance.  A Python
    implementation is included here to explain the basic design:

"""A dictionary-list hybrid"""

import types

class DLict:
    def __init__(self, names):
        assert isinstance(names, types.DictType)
        self.names = {}
        self.list = [None] * size
        self.empty = [1] * size
        self.dict = {}
        self.size = 0

    def __getitem__(self, name):
        i = self.names.get(name)
        if i is None:
            return self.dict[name]
        if self.empty[i] is not None:
            raise KeyError, name
        return self.list[i]

    def __setitem__(self, name, val):
        i = self.names.get(name)
        if i is None:
            self.dict[name] = val
        else:
            self.empty[i] = None
            self.list[i] = val
            self.size += 1

    def __delitem__(self, name):
        i = self.names.get(name)
        if i is None:
            del self.dict[name]
        else:
            if self.empty[i] is not None:
                raise KeyError, name
            self.empty[i] = 1
            self.list[i] = None
            self.size -= 1

    def keys(self):
        if self.dict:
            return self.names.keys() + self.dict.keys()
        else:
            return self.names.keys()

    def values(self):
        if self.dict:
            return self.names.values() + self.dict.values()
        else:
            return self.names.values()

    def items(self):
        if self.dict:
            return self.names.items()
        else:
            return self.names.items() + self.dict.items()

    def __len__(self):
        return self.size + len(self.dict)

    def __cmp__(self, dlict):
        c = cmp(self.names, dlict.names)
        if c != 0:
            return c
        c = cmp(self.size, dlict.size)
        if c != 0:
            return c
        for i in range(len(self.names)):
            c = cmp(self.empty[i], dlict.empty[i])
            if c != 0:
                return c
            if self.empty[i] is None:
                c = cmp(self.list[i], dlict.empty[i])
                if c != 0:
                    return c
        return cmp(self.dict, dlict.dict)
    
    def clear(self):
        self.dict.clear()
        for i in range(len(self.names)):
            if self.empty[i] is None:
                self.empty[i] = 1
                self.list[i] = None

    def update(self):
        pass

    def load(self, index):
        """dlict-special method to support indexed access"""
        if self.empty[index] is None:
            return self.list[index]
        else:
            raise KeyError, index # XXX might want reverse mapping

    def store(self, index, val):
        """dlict-special method to support indexed access"""
        self.empty[index] = None
        self.list[index] = val

    def delete(self, index):
        """dlict-special method to support indexed access"""
        self.empty[index] = 1
        self.list[index] = None


Compiler issues

    The compiler currently collects the names of all global variables
    in a module.  These are names bound at the module level or bound
    in a class or function body that declares them to be global.

    The compiler would assign indices for each global name and add the
    names and indices of the globals to the module's code object.
    Each code object would then be bound irrevocably to the module it
    was defined in.  (Not sure if there are some subtle problems with
    this.)

Enhancement: Optimized access to other module's globals

    If one module imports another and binds a name in the global
    namespace, the compiler currently detects that the particular
    global is bound to a module.  The compiler also note access to any
    attribute of a module, and emit special opcodes for accessing
    these names.

    At runtime the implementation can lookup the index of the module
    attribute in the module's namespace.  In the current namespace,
    a pointer to the foreign module's dlict can be recorded along with
    the name's offset in the dlict.  This would allow names,
    e.g. types.StringType, to be used with the same efficiency as
    globals. 

Backwards compatibility

    The dlict will need to maintain metainformation about whether a
    slot is currently used or not.  It will also need to maintain a
    pointer to the builtin namespace.  When a name is not currently
    used in the global namespace, the lookup will have to fail over to
    the builtin namespace.

    In the reverse case, each module may need a special accessor
    function for the builtin namespace that checks to see if a global
    shadowing the builtin has been added dynamically.  This check
    would only occur if there was a dynamic change to the module's
    dlict, i.e. when a name is bound that wasn't discovered at
    compile-time. 

    These mechanisms would have little if any cost for the common case
    whether a module's global namespace is not modified in strange
    ways at runtime.  They would add overhead for modules that did
    unusual things with global names, but this is an uncommon practice
    and probably one worth discouraging.

    It may be desirable to disable dynamic additions to the global
    namespace in some future version of Python.  If so, the new
    implementation could provide warnings.
    

Local Variables:
mode: indented-text
indent-tabs-mode: nil
End: