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 267.Hence, it is being deferred.
This PEP describes yet another approach to optimizing access tomodule globals, providing an alternative toPEP 266 (OptimizingGlobal Variable/Attribute Access by Skip Montanaro) andPEP 267(Optimized Access to Module Namespaces by Jeremy Hylton).
The expectation is that eventually one approach will be picked andimplemented; possibly multiple approaches will be prototypedfirst.
(Note: Jason Orendorff writes: “””I implemented this once, longago, for Python 1.5-ish, I believe. I got it to the point whereit was only 15% slower than ordinary Python, then abandoned it.;) In my implementation, “cells” were real first-class objects,and “celldict” was a copy-and-hack version of dictionary. Iforget how the rest worked.””” Reference:https://mail.python.org/pipermail/python-dev/2002-February/019876.html)
Let a cell be a really simple Python object, containing a pointerto a Python object and a pointer to a cell. Both pointers may beNULL. A Python implementation could be:
classcell(object):def__init__(self):self.objptr=NULLself.cellptr=NULL
The cellptr attribute is used for chaining cells together forsearching built-ins; this will be explained later.
Let a celldict be a mapping from strings (the names of a module’sglobals) to objects (the values of those globals), implementedusing a dict of cells. A Python implementation could be:
classcelldict(object):def__init__(self):self.__dict={}# dict of cellsdefgetcell(self,key):c=self.__dict.get(key)ifcisNone:c=cell()self.__dict[key]=creturncdefcellkeys(self):returnself.__dict.keys()def__getitem__(self,key):c=self.__dict.get(key)ifcisNone:raiseKeyError,keyvalue=c.objptrifvalueisNULL:raiseKeyError,keyelse:returnvaluedef__setitem__(self,key,value):c=self.__dict.get(key)ifcisNone:c=cell()self.__dict[key]=cc.objptr=valuedef__delitem__(self,key):c=self.__dict.get(key)ifcisNoneorc.objptrisNULL:raiseKeyError,keyc.objptr=NULLdefkeys(self):return[kfork,cinself.__dict.iteritems()ifc.objptrisnotNULL]defitems(self):return[k,c.objptrfork,cinself.__dict.iteritems()ifc.objptrisnotNULL]defvalues(self):preturn[c.objptrforcinself.__dict.itervalues()ifc.objptrisnotNULL]defclear(self):forcinself.__dict.values():c.objptr=NULL# Etc.
It is possible that a cell exists corresponding to a given key,but the cell’s objptr isNULL; let’s call such a cell empty. Whenthe celldict is used as a mapping, it is as if empty cells don’texist. However, once added, a cell is never deleted from acelldict, and it is possible to get at empty cells using thegetcell() method.
The celldict implementation never uses the cellptr attribute ofcells.
We change the module implementation to use a celldict for its__dict__. The module’s getattr, setattr and delattr operationsnow map to getitem, setitem and delitem on the celldict. The typeof<module>.__dict__ andglobals() is probably the only backwardsincompatibility.
When a module is initialized, its__builtins__ is initialized fromthe__builtin__ module’s__dict__, which is itself a celldict.For each cell in__builtins__, the new module’s__dict__ adds acell with aNULL objptr, whose cellptr points to the correspondingcell of__builtins__. Python pseudo-code (ignoring rexec):
import__builtin__classmodule(object):def__init__(self):self.__dict__=d=celldict()d['__builtins__']=bd=__builtin__.__dict__forkinbd.cellkeys():c=self.__dict__.getcell(k)c.cellptr=bd.getcell(k)def__getattr__(self,k):try:returnself.__dict__[k]exceptKeyError:raiseIndexError,kdef__setattr__(self,k,v):self.__dict__[k]=vdef__delattr__(self,k):delself.__dict__[k]
The compiler generatesLOAD_GLOBAL_CELL<i> (andSTORE_GLOBAL_CELL<i> etc.) opcodes for references to globals, where<i> is a smallindex with meaning only within one code object like the constindex inLOAD_CONST. The code object has a new tuple,co_globals,giving the names of the globals referenced by the code indexed by<i>. No new analysis is required to be able to do this.
When a function object is created from a code object and a celldict,the function object creates an array of cell pointers by asking thecelldict for cells corresponding to the names in the code object’sco_globals. If the celldict doesn’t already have a cell for aparticular name, it creates and an empty one. This array of cellpointers is stored on the function object asfunc_cells. When afunction object is created from a regular dict instead of acelldict,func_cells is aNULL pointer.
When the VM executes aLOAD_GLOBAL_CELL<i> instruction, it getscell number<i> fromfunc_cells. It then looks in the cell’sPyObject pointer, and if notNULL, that’s the global value. If itisNULL, it follows the cell’s cell pointer to the next cell, if itis notNULL, and looks in thePyObject pointer in that cell. Ifthat’s alsoNULL, or if there is no second cell,NameError israised. (It could follow the chain of cell pointers until aNULLcell pointer is found; but I have no use for this.) Similar forSTORE_GLOBAL_CELL<i>, except it doesn’t follow the cell pointerchain – it always stores in the first cell.
There are fallbacks in the VM for the case where the function’sglobals aren’t a celldict, and hencefunc_cells isNULL. In thatcase, the code object’sco_globals is indexed with<i> to find thename of the corresponding global and this name is used to index thefunction’s globals dict.
func_cell aNULL pointer; instead, make up an arrayof empty cells, so thatLOAD_GLOBAL_CELL can indexfunc_cellswithout aNULL check.c.cellptr equal to c when a cell is created, so thatLOAD_GLOBAL_CELL can always dereferencec.cellptr without aNULLcheck.With these two additional ideas added, here’s Python pseudo-codeforLOAD_GLOBAL_CELL:
defLOAD_GLOBAL_CELL(self,i):# self is the framec=self.func_cells[i]obj=c.objptrifobjisnotNULL:returnobj# Existing globalreturnc.cellptr.objptr# Built-in or NULL
There are two points to this: (1) Simplify and speed access, whichis the most common operation. (2) Support faithful emulation ofextreme existing corner cases.
WRT #2, the set of builtins in the scheme above is captured at thetime a module dict is first created. Mutations to the set of builtinnames following that don’t get reflected in the module dicts. Example:consider filesmain.py andcheater.py:
[main.py]importcheaterdeff():cheater.cheat()returnpachinko()printf()[cheater.py]defcheat():import__builtin____builtin__.pachinko=lambda:666
Ifmain.py is run under Python 2.2 (or before), 666 is printed. Butunder the proposal,__builtin__.pachinko doesn’t exist at the timemain’s__dict__ is initialized. When the function object forf is created,main.__dict__ grows a pachinko cell mapping to twoNULLs. Whencheat() is called,__builtin__.__dict__ grows a pachinkocell too, butmain.__dict__ doesn’t know– and will never know –aboutthat. When f’s return stmt references pachinko, in will still findthe double-NULLs inmain.__dict__’spachinko cell, and so raiseNameError.
A similar (in cause) break in compatibility can occur if a moduleglobal foo is del’ed, but a builtin foo was created prior to thatbut after the module dict was first created. Then the builtin foobecomes visible in the module under 2.2 and before, but remainsinvisible under the proposal.
Mutating builtins is extremely rare (most programs never mutate thebuiltins, and it’s hard to imagine a plausible use for frequentmutation of the builtins – I’ve never seen or heard of one), so itdoesn’t matter how expensive mutating the builtins becomes. OTOH,referencing globals and builtins is very common. Combining thoseobservations suggests a more aggressive caching of builtins in moduleglobals, speeding access at the expense of making mutations of thebuiltins (potentially much) more expensive to keep the caches insynch.
Much of the scheme above remains the same, and most of the rest isjust a little different. A cell changes to:
classcell(object):def__init__(self,obj=NULL,builtin=0):self.objptr=objself.builtinflag=builtin
and a celldict maps strings to this version of cells.builtinflagis true when and only when objptr contains a value obtained fromthe builtins; in other words, it’s true when and only when a cellis acting as a cached value. Whenbuiltinflag is false, objptr isthe value of a module global (possiblyNULL). celldict changes to:
classcelldict(object):def__init__(self,builtindict=()):self.basedict=builtindictself.__dict=d={}fork,vinbuiltindict.items():d[k]=cell(v,1)def__getitem__(self,key):c=self.__dict.get(key)ifcisNoneorc.objptrisNULLorc.builtinflag:raiseKeyError,keyreturnc.objptrdef__setitem__(self,key,value):c=self.__dict.get(key)ifcisNone:c=cell()self.__dict[key]=cc.objptr=valuec.builtinflag=0def__delitem__(self,key):c=self.__dict.get(key)ifcisNoneorc.objptrisNULLorc.builtinflag:raiseKeyError,keyc.objptr=NULL# We may have unmasked a builtin. Note that because# we're checking the builtin dict for that *now*, this# still works if the builtin first came into existence# after we were constructed. Note too that del on# namespace dicts is rare, so the expense of this check# shouldn't matter.ifkeyinself.basedict:c.objptr=self.basedict[key]assertc.objptrisnotNULL# else "in" liedc.builtinflag=1else:# There is no builtin with the same name.assertnotc.builtinflagdefkeys(self):return[kfork,cinself.__dict.iteritems()ifc.objptrisnotNULLandnotc.builtinflag]defitems(self):return[k,c.objptrfork,cinself.__dict.iteritems()ifc.objptrisnotNULLandnotc.builtinflag]defvalues(self):preturn[c.objptrforcinself.__dict.itervalues()ifc.objptrisnotNULLandnotc.builtinflag]defclear(self):forcinself.__dict.values():ifnotc.builtinflag:c.objptr=NULL# Etc.
The speed benefit comes from simplifyingLOAD_GLOBAL_CELL, whichI expect is executed more frequently than all other namespaceoperations combined:
defLOAD_GLOBAL_CELL(self,i):# self is the framec=self.func_cells[i]returnc.objptr# may be NULL (also true before)
That is, accessing builtins and accessing module globals are equallyfast. For module globals, a NULL-pointer test+branch is saved. Forbuiltins, an additional pointer chase is also saved.
The other part needed to make this fly is expensive, propagatingmutations of builtins into the module dicts that were initializedfrom the builtins. This is much like, in 2.2, propagating changesin new-style base classes to their descendants: the builtins need tomaintain a list of weakrefs to the modules (or module dicts)initialized from the builtin’s dict. Given a mutation to the builtindict (adding a new key, changing the value associated with anexisting key, or deleting a key), traverse the list of module dictsand make corresponding mutations to them. This is straightforward;for example, if a key is deleted from builtins, executereflect_bltin_del in each module:
defreflect_bltin_del(self,key):c=self.__dict.get(key)assertcisnotNone# else we were already out of synchifc.builtinflag:# Put us back in synch.c.objptr=NULLc.builtinflag=0# Else we're shadowing the builtin, so don't care that# the builtin went away.
Note thatc.builtinflag protects from us erroneously deleting amodule global of the same name. Adding a new (key, value) builtinpair is similar:
defreflect_bltin_new(self,key,value):c=self.__dict.get(key)ifcisNone:# Never heard of it before: cache the builtin value.self.__dict[key]=cell(value,1)elifc.objptrisNULL:# This used to exist in the module or the builtins,# but doesn't anymore; rehabilitate it.assertnotc.builtinflagc.objptr=valuec.builtinflag=1else:# We're shadowing it already.assertnotc.builtinflag
Changing the value of an existing builtin:
defreflect_bltin_change(self,key,newvalue):c=self.__dict.get(key)assertcisnotNone# else we were already out of synchifc.builtinflag:# Put us back in synch.c.objptr=newvalue# Else we're shadowing the builtin, so don't care that# the builtin changed.
a) install new builtins in the__builtin__ namespace and havethem available in all already loaded modules right away ?
b) override builtins (e.g.open()) with my own copies(e.g. to increase security) in a way that makes these newcopies override the previous ones in all modules ?
A: Yes, this is the whole point of this design. In the originalapproach, whenLOAD_GLOBAL_CELL finds aNULL in the secondcell, it should go back to see if the__builtins__ dict hasbeen modified (the pseudo code doesn’t have this yet). Tim’s“more aggressive” alternative also takes care of this.
A: It is intended to support that fully.
A: The module’s celldict would have a cell with aNULL objptr forthat key. This is true in both variations, but the “aggressive”variation goes on to see whether this unmasks a builtin of thesame name, and if so copies its value (just a pointer-copy of theultimatePyObject*) into the cell’s objptr and sets the cell’sbuiltinflag to true.
LOAD_GLOBAL_CELL look like?A: The first version, with the first two bullets under “Additionalideas” incorporated, could look like this:
caseLOAD_GLOBAL_CELL:cell=func_cells[oparg];x=cell->objptr;if(x==NULL){x=cell->cellptr->objptr;if(x==NULL){...errorrecovery...break;}}Py_INCREF(x);PUSH(x);continue;
We could even write it like this (idea courtesy of Ka-Ping Yee):
caseLOAD_GLOBAL_CELL:cell=func_cells[oparg];x=cell->cellptr->objptr;if(x!=NULL){Py_INCREF(x);PUSH(x);continue;}...errorrecovery...break;
In modern CPU architectures, this reduces the number ofbranches taken for built-ins, which might be a really goodthing, while any decent memory cache should realize thatcell->cellptr is the same as cell for regular globals and hencethis should be very fast in that case too.
For the aggressive variant:
caseLOAD_GLOBAL_CELL:cell=func_cells[oparg];x=cell->objptr;if(x!=NULL){Py_INCREF(x);PUSH(x);continue;}...errorrecovery...break;
func_cells array?A: We could do some code analysis and create afunc_cells array,or we could useLOAD_NAME which should usePyMapping_GetItem onthe globals dict.
Ka-Ping Yee supplied a drawing of the state of things after“import spam”, wherespam.py contains:
importeggsi=-2max=3deffoo(n):y=abs(i)+maxreturneggs.ham(y+n)
The drawing is athttp://web.lfw.org/repo/cells.gif; a largerversion is athttp://lfw.org/repo/cells-big.gif; the source is athttp://lfw.org/repo/cells.ai.
XXX Here, a comparison of the three approaches could be added.
This document has been placed in the public domain.
Source:https://github.com/python/peps/blob/main/peps/pep-0280.rst
Last modified:2025-02-01 08:55:40 GMT
