Deferral

While this PEP is a nice idea, no-one has yet emerged to do the work ofhashing out the differences between this PEP,PEP 266 andPEP 280.Hence, it is being deferred.

Abstract

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

The current implementation represents these namespaces asdictionaries. A global name incurs a dictionary lookup each timeit is used; a builtin name incurs two dictionary lookups, a failedlookup in the global namespace and a second lookup in the builtinnamespace.

This implementation should speed Python code that usesmodule-level functions and variables. It should also eliminateawkward coding styles that have evolved to speed access to thesenames.

The implementation is complicated because the global and builtinnamespaces can be modified dynamically in ways that are impossiblefor the compiler to detect. (Example: A module’s namespace ismodified by a script after the module is imported.) As a result,the implementation must maintain several auxiliary data structuresto preserve these dynamic features.

Introduction

This PEP proposes a new implementation of attribute access formodule objects that optimizes access to module variables known atcompile time. The module will store these variables in an arrayand provide an interface to lookup attributes using array offsets.For globals, builtins, and attributes of imported modules, thecompiler will generate code that uses the array offsets for fastaccess.

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

The implementation will preserve existing semantics for modulenamespaces, including the ability to modify module namespaces atruntime in ways that affect the visibility of builtin names.

DLict design

The namespaces are implemented using a data structure that hassometimes gone under the namedlict. It is a dictionary that hasnumbered slots for some dictionary entries. The type must beimplemented in C to achieve acceptable performance. The newtype-class unification work should make this fairly easy. TheDLict will presumably be a subclass of dictionary with analternate storage module for some keys.

A Python implementation is included here to illustrate the basicdesign:

"""A dictionary-list hybrid"""importtypesclassDLict:def__init__(self,names):assertisinstance(names,types.DictType)self.names={}self.list=[None]*sizeself.empty=[1]*sizeself.dict={}self.size=0def__getitem__(self,name):i=self.names.get(name)ifiisNone:returnself.dict[name]ifself.empty[i]isnotNone:raiseKeyError,namereturnself.list[i]def__setitem__(self,name,val):i=self.names.get(name)ifiisNone:self.dict[name]=valelse:self.empty[i]=Noneself.list[i]=valself.size+=1def__delitem__(self,name):i=self.names.get(name)ifiisNone:delself.dict[name]else:ifself.empty[i]isnotNone:raiseKeyError,nameself.empty[i]=1self.list[i]=Noneself.size-=1defkeys(self):ifself.dict:returnself.names.keys()+self.dict.keys()else:returnself.names.keys()defvalues(self):ifself.dict:returnself.names.values()+self.dict.values()else:returnself.names.values()defitems(self):ifself.dict:returnself.names.items()else:returnself.names.items()+self.dict.items()def__len__(self):returnself.size+len(self.dict)def__cmp__(self,dlict):c=cmp(self.names,dlict.names)ifc!=0:returncc=cmp(self.size,dlict.size)ifc!=0:returncforiinrange(len(self.names)):c=cmp(self.empty[i],dlict.empty[i])ifc!=0:returncifself.empty[i]isNone:c=cmp(self.list[i],dlict.empty[i])ifc!=0:returncreturncmp(self.dict,dlict.dict)defclear(self):self.dict.clear()foriinrange(len(self.names)):ifself.empty[i]isNone:self.empty[i]=1self.list[i]=Nonedefupdate(self):passdefload(self,index):"""dlict-special method to support indexed access"""ifself.empty[index]isNone:returnself.list[index]else:raiseKeyError,index# XXX might want reverse mappingdefstore(self,index,val):"""dlict-special method to support indexed access"""self.empty[index]=Noneself.list[index]=valdefdelete(self,index):"""dlict-special method to support indexed access"""self.empty[index]=1self.list[index]=None

Compiler issues

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

The compiler would assign indices for each global name and add thenames and indices of the globals to the module’s code object.Each code object would then be bound irrevocably to the module itwas defined in. (Not sure if there are some subtle problems withthis.)

For attributes of imported modules, the module will store anindirection record. Internally, the module will store a pointerto the defining module and the offset of the attribute in thedefining module’s global variable array. The offset would beinitialized the first time the name is looked up.

Runtime model

The PythonVM will be extended with new opcodes to access globalsand module attributes via a module-level array.

A function object would need to point to the module that definedit in order to provide access to the module-level global array.

For module attributes stored in thedlict (call them staticattributes), the get/delattr implementation would need to trackaccess to these attributes using the old by-name interface. If astatic attribute is updated dynamically, e.g.:

mod.__dict__["foo"]=2

The implementation would need to update the array slot instead ofthe backup dict.

Backwards compatibility

Thedlict will need to maintain meta-information about whether aslot is currently used or not. It will also need to maintain apointer to the builtin namespace. When a name is not currentlyused in the global namespace, the lookup will have to fail over tothe builtin namespace.

In the reverse case, each module may need a special accessorfunction for the builtin namespace that checks to see if a globalshadowing the builtin has been added dynamically. This checkwould only occur if there was a dynamic change to the module’sdlict, i.e. when a name is bound that wasn’t discovered atcompile-time.

These mechanisms would have little if any cost for the common casewhether a module’s global namespace is not modified in strangeways at runtime. They would add overhead for modules that didunusual things with global names, but this is an uncommon practiceand probably one worth discouraging.

It may be desirable to disable dynamic additions to the globalnamespace in some future version of Python. If so, the newimplementation could provide warnings.

Related PEPs

PEP 266, Optimizing Global Variable/Attribute Access, proposes adifferent mechanism for optimizing access to global variables aswell as attributes of objects. The mechanism uses two new opcodesTRACK_OBJECT andUNTRACK_OBJECT to create a slot in the localvariables array that aliases the global or object attribute. Ifthe object being aliases is rebound, the rebind operation isresponsible for updating the aliases.

The objecting tracking approach applies to a wider range ofobjects than just module. It may also have a higher runtime cost,because each function that uses a global or object attribute mustexecute extra opcodes to register its interest in an object andunregister on exit; the cost of registration is unclear, butpresumably involves a dynamically resizable data structure to holda list of callbacks.

The implementation proposed here avoids the need for registration,because it does not create aliases. Instead it allows functionsthat reference a global variable or module attribute to retain apointer to the location where the original binding is stored. Asecond advantage is that the initial lookup is performed once permodule rather than once per function call.

Copyright

This document has been placed in the public domain.