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: