PEP 280 – Optimizing access to globals | peps.python.org (original) (raw)

Author:

Guido van Rossum

Status:

Deferred

Type:

Standards Track

Created:

10-Feb-2002

Python-Version:

2.3

Post-History:

Table of Contents

Deferral

While this PEP is a nice idea, no-one has yet emerged to do the work of hashing out the differences between this PEP, PEP 266 and PEP 267. Hence, it is being deferred.

Abstract

This PEP describes yet another approach to optimizing access to module globals, providing an alternative to PEP 266 (Optimizing Global Variable/Attribute Access by Skip Montanaro) and PEP 267(Optimized Access to Module Namespaces by Jeremy Hylton).

The expectation is that eventually one approach will be picked and implemented; possibly multiple approaches will be prototyped first.

Description

(Note: Jason Orendorff writes: “””I implemented this once, long ago, for Python 1.5-ish, I believe. I got it to the point where it 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. I forget 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 pointer to a Python object and a pointer to a cell. Both pointers may beNULL. A Python implementation could be:

class cell(object):

def __init__(self):
    self.objptr = NULL
    self.cellptr = NULL

The cellptr attribute is used for chaining cells together for searching built-ins; this will be explained later.

Let a celldict be a mapping from strings (the names of a module’s globals) to objects (the values of those globals), implemented using a dict of cells. A Python implementation could be:

class celldict(object):

def __init__(self):
    self.__dict = {} # dict of cells

def getcell(self, key):
    c = self.__dict.get(key)
    if c is None:
        c = cell()
        self.__dict[key] = c
    return c

def cellkeys(self):
    return self.__dict.keys()

def __getitem__(self, key):
    c = self.__dict.get(key)
    if c is None:
        raise KeyError, key
    value = c.objptr
    if value is NULL:
        raise KeyError, key
    else:
        return value

def __setitem__(self, key, value):
    c = self.__dict.get(key)
    if c is None:
        c = cell()
        self.__dict[key] = c
    c.objptr = value

def __delitem__(self, key):
    c = self.__dict.get(key)
    if c is None or c.objptr is NULL:
        raise KeyError, key
    c.objptr = NULL

def keys(self):
    return [k for k, c in self.__dict.iteritems()
            if c.objptr is not NULL]

def items(self):
    return [k, c.objptr for k, c in self.__dict.iteritems()
            if c.objptr is not NULL]

def values(self):
    preturn [c.objptr for c in self.__dict.itervalues()
            if c.objptr is not NULL]

def clear(self):
    for c in self.__dict.values():
        c.objptr = NULL

# Etc.

It is possible that a cell exists corresponding to a given key, but the cell’s objptr is NULL; let’s call such a cell empty. When the celldict is used as a mapping, it is as if empty cells don’t exist. However, once added, a cell is never deleted from a celldict, and it is possible to get at empty cells using thegetcell() method.

The celldict implementation never uses the cellptr attribute of cells.

We change the module implementation to use a celldict for its__dict__. The module’s getattr, setattr and delattr operations now map to getitem, setitem and delitem on the celldict. The type of <module>.__dict__ and globals() is probably the only backwards incompatibility.

When a module is initialized, its __builtins__ is initialized from the __builtin__ module’s __dict__, which is itself a celldict. For each cell in __builtins__, the new module’s __dict__ adds a cell with a NULL objptr, whose cellptr points to the corresponding cell of __builtins__. Python pseudo-code (ignoring rexec):

import builtin

class module(object):

def __init__(self):
    self.__dict__ = d = celldict()
    d['__builtins__'] = bd = __builtin__.__dict__
    for k in bd.cellkeys():
        c = self.__dict__.getcell(k)
        c.cellptr = bd.getcell(k)

def __getattr__(self, k):
    try:
        return self.__dict__[k]
    except KeyError:
        raise IndexError, k

def __setattr__(self, k, v):
    self.__dict__[k] = v

def __delattr__(self, k):
    del self.__dict__[k]

The compiler generates LOAD_GLOBAL_CELL <i> (and STORE_GLOBAL_CELL <i> etc.) opcodes for references to globals, where <i> is a small index with meaning only within one code object like the const index in LOAD_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 the celldict for cells corresponding to the names in the code object’sco_globals. If the celldict doesn’t already have a cell for a particular name, it creates and an empty one. This array of cell pointers is stored on the function object as func_cells. When a function object is created from a regular dict instead of a celldict, func_cells is a NULL pointer.

When the VM executes a LOAD_GLOBAL_CELL <i> instruction, it gets cell number <i> from func_cells. It then looks in the cell’sPyObject pointer, and if not NULL, that’s the global value. If it is NULL, it follows the cell’s cell pointer to the next cell, if it is not NULL, and looks in the PyObject pointer in that cell. If that’s also NULL, or if there is no second cell, NameError is raised. (It could follow the chain of cell pointers until a NULLcell pointer is found; but I have no use for this.) Similar forSTORE_GLOBAL_CELL <i>, except it doesn’t follow the cell pointer chain – it always stores in the first cell.

There are fallbacks in the VM for the case where the function’s globals aren’t a celldict, and hence func_cells is NULL. In that case, the code object’s co_globals is indexed with <i> to find the name of the corresponding global and this name is used to index the function’s globals dict.

Additional Ideas

and a celldict maps strings to this version of cells. builtinflagis true when and only when objptr contains a value obtained from the builtins; in other words, it’s true when and only when a cell is acting as a cached value. When builtinflag is false, objptr is the value of a module global (possibly NULL). celldict changes to:
class celldict(object):
def init(self, builtindict=()):
self.basedict = builtindict
self.__dict = d = {}
for k, v in builtindict.items():
d[k] = cell(v, 1)
def getitem(self, key):
c = self.__dict.get(key)
if c is None or c.objptr is NULL or c.builtinflag:
raise KeyError, key
return c.objptr
def setitem(self, key, value):
c = self.__dict.get(key)
if c is None:
c = cell()
self.__dict[key] = c
c.objptr = value
c.builtinflag = 0
def delitem(self, key):
c = self.__dict.get(key)
if c is None or c.objptr is NULL or c.builtinflag:
raise KeyError, key
c.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.
if key in self.basedict:
c.objptr = self.basedict[key]
assert c.objptr is not NULL # else "in" lied
c.builtinflag = 1
else:
# There is no builtin with the same name.
assert not c.builtinflag
def keys(self):
return [k for k, c in self.__dict.iteritems()
if c.objptr is not NULL and not c.builtinflag]
def items(self):
return [k, c.objptr for k, c in self.__dict.iteritems()
if c.objptr is not NULL and not c.builtinflag]
def values(self):
preturn [c.objptr for c in self.__dict.itervalues()
if c.objptr is not NULL and not c.builtinflag]
def clear(self):
for c in self.__dict.values():
if not c.builtinflag:
c.objptr = NULL
# Etc.
The speed benefit comes from simplifying LOAD_GLOBAL_CELL, which I expect is executed more frequently than all other namespace operations combined:
def LOAD_GLOBAL_CELL(self, i):
# self is the frame
c = self.func_cells[i]
return c.objptr # may be NULL (also true before)
That is, accessing builtins and accessing module globals are equally fast. For module globals, a NULL-pointer test+branch is saved. For builtins, an additional pointer chase is also saved.
The other part needed to make this fly is expensive, propagating mutations of builtins into the module dicts that were initialized from the builtins. This is much like, in 2.2, propagating changes in new-style base classes to their descendants: the builtins need to maintain a list of weakrefs to the modules (or module dicts) initialized from the builtin’s dict. Given a mutation to the builtin dict (adding a new key, changing the value associated with an existing key, or deleting a key), traverse the list of module dicts and make corresponding mutations to them. This is straightforward; for example, if a key is deleted from builtins, executereflect_bltin_del in each module:
def reflect_bltin_del(self, key):
c = self.__dict.get(key)
assert c is not None # else we were already out of synch
if c.builtinflag:
# Put us back in synch.
c.objptr = NULL
c.builtinflag = 0
# Else we're shadowing the builtin, so don't care that
# the builtin went away.
Note that c.builtinflag protects from us erroneously deleting a module global of the same name. Adding a new (key, value) builtin pair is similar:
def reflect_bltin_new(self, key, value):
c = self.__dict.get(key)
if c is None:
# Never heard of it before: cache the builtin value.
self.__dict[key] = cell(value, 1)
elif c.objptr is NULL:
# This used to exist in the module or the builtins,
# but doesn't anymore; rehabilitate it.
assert not c.builtinflag
c.objptr = value
c.builtinflag = 1
else:
# We're shadowing it already.
assert not c.builtinflag
Changing the value of an existing builtin:
def reflect_bltin_change(self, key, newvalue):
c = self.__dict.get(key)
assert c is not None # else we were already out of synch
if c.builtinflag:
# Put us back in synch.
c.objptr = newvalue
# Else we're shadowing the builtin, so don't care that
# the builtin changed.

FAQs

Graphics

Ka-Ping Yee supplied a drawing of the state of things after “import spam”, where spam.py contains:

import eggs

i = -2 max = 3

def foo(n): y = abs(i) + max return eggs.ham(y + n)

The drawing is at http://web.lfw.org/repo/cells.gif; a larger version is at http://lfw.org/repo/cells-big.gif; the source is athttp://lfw.org/repo/cells.ai.

Comparison

XXX Here, a comparison of the three approaches could be added.

This document has been placed in the public domain.