From: Guido van Rossum <guido@python.org>
To: Tim Peters <tim.one@comcast.net>
cc: python-dev@python.org
Subject: Re: [Python-Dev] Accessing globals without dict lookup
Date: Mon, 11 Feb 2002 23:30:43 -0500

[Ping, suggesting to always dereference the cell twice]
> But hey... in that case the cellptr is always two steps away from
> the object.  So why not just use PyObject**s instead of cells?

[Tim, sketching a scheme that always dereferences the cell once]
> The sole big change is requiring that mutations to builtins
> propagate at once to their cached values in module celldicts.

Let's combine these ideas.  Suppose there's a vector of pointers to
pointers to objects, indexed by some index calculated by the compiler.
Then the fast track in LOAD_GLOBAL_CELL could look like this:

    case LOAD_GLOBAL_CELL:
        x = *globals_vector[oparg];
        if (x != NULL) {
            Py_INCREF(x);
            continue;
        }
        ... handle uncommon cases and errors here ...

Here, globals_vector[i] is usually the address of the me_value slot of
a PyDictEntry in either the globals dict or the builtins dict.  These
are subclasses of dict that trap assignment, deletion, and rehashing.

There's a special C-global variable

    PyObject *unfilled = NULL;

whose contents is always NULL; when globals_vector is initalized,
every element of it is set to &unfilled.

The code to handle uncommon cases and errors does a "lookdict"
operation on the globals dict using the name of the global variable,
which it gets from (e.g.) globals_names[oparg].  This requires some
opening up of the dict implementation; lookdict is an internal routine
that returns a PyDictEntry *, call it e.  If e->me_value != NULL, we
set globals_vector[oparg] to &e->me_value, and we're done.  Otherwise,
we do another lookdict on the builtins dict, and again if e->me_value
!= NULL, set globals_vector[oparg] to &e->me_value.  Otherwise, we
raise a NameError.

Now we need to take care of a number of additional special cases that
could invalidate the pointers we're collecting in globals_vector.
The following things may invalidate those pointers:

- globals_vector[i] points to a builtin, and a global with the same
  name is created

- globals_vector[i] points to either a builtin or a global, and the
  dict into whose hashtable it points is rehashed (as the result of
  adding an item)

- globals_vector[i] points to a builtin or global, which is deleted

- globals_vector[i] points to a builtin, and the special global named
  __builtins__ is assigned to (switching to a different builtins dict)

To deal with all these cases, our dict subclass keeps a list of weak
references.  The builtins dict has weak references pointing to all
globals dicts that shadow this builtins dict (because of rexec there
can be multiple builtins dicts); each globals dict has weak references
pointing to all the globals_vector structures that reference it.

On a rehash, all entries in each affected globals_vector are reset to
&unfilled.  The uncommon case handling code will gradually populate
them again.  On assignment or deletion it might pay off to be a little
more careful and only invalidate the entry in the globals_vector
corrsponding to the affected name.  (In particular, assignment to a
global that's already set, and deletion of a global that doesn't
shadow a built-in, should probably be handled somewhat efficiently.)

The globals_vector structure should contain a pointer to the
corresponding globals_names array, and it should also contain a
reference to the globals dict into whose hashtable it may point, to
keep it alive.  So it should probably be an object that contains a
vector of pointers to pointers in addition to some other stuff.

The globals_vector may be shared by all code objects compiled
together; this makes it similar to the dlict.  But the overflow
handling is quite different, and by pointing directly into the hash
table it is possible to handle all globals and builtins uniformly.

I expect that the implementation won't be particularly hard; the
lookdict operation already exists and we can easily subclass dict to
trap the setitem and delitem operations.  We will have to be careful
not to use PyDict_SetItem() and PyDict_DelItem() on these subclasses,
but that should be easy: I think that the only offenders here are
STORE_NAME and friends, and these are exactly the operations that
we're going to change anyway.  (STORE_NAME or STORE_GLOBAL will become
a bit slower, because of the check whether it needs to update any
globals_vector structures; but that's OK since we're speeding up the
corresponding LOAD operation quite a bit.)

(I'd add this to PEP 280 but I'll wait for Tim to shoot holes in it
first. :-)

--Guido van Rossum (home page: http://www.python.org/~guido/)

_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev