Does Python (or psyco) already do this optimisation?

[Mike C. Fletcher]

General idea:
    Have namespaces provide pointer-addresses in which the current 
PyObject * of a given name is stored.  Provide hooks on namespaces which 
catch set/del of names to update cached values.  Have compiled methods 
store an index into the local namespace's array of pointer-addresses in 
which to look for a name (going up the lexical namespace chain) rather 
than using hashtable lookups.

Simplistic approach:

    * For each namespace:
          o table [N*M pointer-to-pointers] (N=number of names,
            M=lexical depth, stores local-namespace pointer-location and
            all parent-namespace's pointer-locations (yes, that's
            inefficient when it could just point to the parent's
            pointer-to-pointer location, but that seems a little
            convoluted))
          o Hash-map { name: tableOffset }  (tableOffset being index
            into table, all items added to the hash must be present in
            the table)
          o Parent-namespace-pointer (for use during standard
            name-resolution passes)
    * For each name in a code object, store the tableOffset for the name
      into the namespace's table for that name. Note that you must
      ensure the name exists in all parent tables as well
    * To resolve, each compiled method checks each namespace's pointer
      in turn.  If the pointer is NULL, it tries the next namespace in
      the chain.  If none of the pointers is non-NULL, do a full
      namespace lookup and cache the result in the appropriate
      namespace-pointer (or raise a NameError on failing).  If a pointer
      is non-NULL, go ahead and use it.
    * Assign to a variable:
          o update address in pointer-to-pointer for the local
            namespace's record to point to the new object.
          o do reference-count handling
    * Delete a variable:
          o update address in pointer-to-pointer to be NULL (this may
            result in there being no non-NULL entries in the tables (a
            NameError if anything tries to access the name from those
            namespaces))
          o do reference-count handling

Imagined impact:

    * namespace memory overhead is increased (considerably), you wind up
      with caches similar to the local-namespace one for all levels with
      entries for all names in all namespaces at the highest level.
    * external accesses still need hashtable lookup and
      new-name-assignment available, so you can't do away with it. You
      must cache each resolved name in each lexical namespace, so figure
      (numberOfNames*lexical-depth) pointers, plus the hashed-string to
      pointer-to-pointer table.
    * function compilation overhead is increased as you wind up with
      N(names) * M(namespaces) required lookups for _every_ name in the
      namespace.  This should be a (largely) static single-time charge.
    * name lookup should be faster, as a simple array of known length
      (lexical depth) is being searched for the first non-NULL entry.
    * assignment and deletion in namespaces will be slower
          o assignment to previously unknown values needs to extend the
            size of the table for the given namespace and all parent
            namespace's tables where the name doesn't already exist
    * you cannot delete name-entries from a namespace table once created
      (since there may be large numbers of other namespaces which use
      the pointers defined by that namespace).  You could probably
      create a simple scan to get rid of this limitation (or just use
      reference-counting), but I doubt the benefits would be worth the
      cost, save in rare corner cases.
          o (rare-corner-case-description) would be a potential
            bottleneck in cases where exec/eval is used a lot in a
            particular namespace (as it might, for instance, have
            thousands (or millions) of variables created in the exec'd
            namespaces, with NULL entries in the parent namespace not
            getting cleaned up between iterations.)

Anyway, would be interested to know if someone C-knowledgable has done 
this already and 1) integrated it into Python or psyco already, or 2) 
decided it just isn't a feasible approach?
Mike

_______________________________________
  Mike C. Fletcher
  Designer, VR Plumber, Coder
  http://members.rogers.com/mcfletch/