On Wed, Dec 16, 2015 at 2:01 AM, Victor Stinner <victor.stin...@gmail.com> wrote: > Le mercredi 16 décembre 2015, Franklin? Lee <leewangzhong+pyt...@gmail.com> > a écrit : >> >> I am confident that the time overhead and the savings will beat the >> versioning dict. The versioning dict method has to save a reference to >> the variable value and a reference to the name, and regularly test >> whether the dict has changed. > > > The performance of guards matters less than the performance of regular usage > of dict. If we have to make a choice, I prefer "slow" guard but no impact on > regular dict methods. It's very important that enabling FAT mode doesn't > kill performances. Remember that FAT python is a static optimizer and so can > only optimize some patterns, not all Python code. > > In my current implementation, a lookup is only needed when aguard is checked > if the dict was modified. The dict version doesn't change if a mutable > object was modified in place for example. I didn't benchmark, but I expect > that the lookup is avoided in most cases. You should try FAT python and > implement statistics before going too far in your idea.
My suggestion should improve *all* function calls which refer to outside names. Each function keeps an indirect, automagically updated reference to the current value of the names they use, and will never need to look things up again.[*] There wouldn't be a need to save global names as default arguments (`def f(x, list=list):`). [*]: Not exactly true. Nested scopes can cause an issue. I'm not sure what happens if you redefine the __builtin__ name after these functions are defined. My suggestion would not know that the __builtin__ was switched out, since it saves a ref into the original __builtin__. I'm not sure about how to deal with nested scopes (for example, class inheritance). I think the "chained RefCells" idea works. Chained Refcell idea: There are three cases where we can have nested scopes: 1. An object's __dict__ nests its class. 2. A class's __dict__ nests its superclasses. 3. globals() nests __builtin__. 4? Does a package nest its modules? 5?. Does `from module import *` nest the module's __dict__? (Nonlocal variables in nested functions, and probably nested classes, are not a case of nested scope, since scope of each name is determined during compilation of the function/class.) RefCells of nested scopes will have a pointer to their value (or NULL), and an array/linkedlist of pointers to refcells from their parent dicts (or to their parent dicts if a refcell wasn't successfully acquired yet). When you request a RefCell from a nested Scope, it will return its value if it exists. Otherwise, it requests refcells from each parent (parents won't create refcells unless there's a value) until it gets one. When you ask a RefCell to resolve, it will check its own value, then ask each parent for a value (creating intermediate refcells *if* value exist). It will not need to do lookups in parents if it got a refcell before (though the refcell might be null). Problem: If you have class A(B, C), and you resolve a refcell for a name which exists in C but not B, you will look things up through B's dict every single time. It will fail, every single time. We can't skip B, since B is allowed to get such a name later, but I don't want to add refs to names that might never exist. This can be solved either through versioning or by checking whether a dict is read-only (such as for built-in types). In fact, in the code I wrote at the end of this email, RefCell.resolve() might even look things up in a shared ancestor multiple times. However, this would be incorrect anyway, since it doesn't respect Python's MRO resolution. So we can just fix that. RefCell.resolve would need a `search_parents: bool` parameter. >> I've read it again. By subclass, I mean that it implements the same >> interface. But at the C level, I want to have it be a fork(?) of the >> current dict implementation. As for `exec`, I think it might be okay >> for it to be slower at the early stages of this game. > > > Be careful, dict methods are hardcoded in the C code. If your type is not a > subtype, there is risk of crashes. Not exactly, and this is important. Many functions are called via pointer. It's like C++'s virtual methods, but more dynamic, since they can be changed per object. See https://github.com/python/cpython/blob/master/Objects/dict-common.h#L17. For example, the lookup method for str-only dicts swaps itself for a general object lookup method if it finds a non-string key. See https://github.com/python/cpython/blob/master/Objects/dictobject.c#L549. I'm now suggesting that there be additional space in the dict object itself to hold more function pointers (get_ref and get_hash_table_index), which would slightly increase memory cost and creation time. It won't have extra cost for running normal methods. When the dict gets a request for a reference, it will swap in methods that knows how to handle metadata, which WILL make (a few) things (a little) slower upon resizing. You only pay for what you ask for (except the extra dict API methods, which will slightly increase the cost and creation time). A few more pointers shouldn't hurt, since PyObjects are already big (see the overhead of dicts here: https://github.com/python/cpython/blob/master/Objects/dictobject.c#L2748). I'm not sure that get_hash_table_index is necessary. (I misunderstood something when rereading the lookup functions.) It should be possible to calculate the index in the hash table by subtracting the lookup's return value by the base index. == Some pseudocode == Notes: - A lot of repeated lookups are made in the code below. No repeated lookups (in a single call) are necessary in C. - I made a few style choices which wouldn't be Pythonic (e.g. explicitly testing for key) to make it easier to see what the C would do. - I wrote it as a subclass. It doesn't have to be. - We can ask for getref to become standard. It could be useful for a few purposes. (Namely, implementing scope dicts when writing interpreters for other languages, and for pass-by-reference in those interpreters.) - `parents` can be a special thing for nested scope dicts (such as those listed above). - Like I said before, we can plug in the more expensive functions the first time getref is called. A dict can dynamically become a dict_with_refs. - I'm being sloppy with self.refs. Sorry. Sometimes I write `self.refs[key] is NULL` and sometimes I write `key not in self.refs`. It's the same thing. - `NULL` might be `dummy` (which is used in the dict implementation). - `delete` means `Py_XDECREF` or `Py_DECREF`. This is only used when I feel like emphasizing the memory management. - I remembered that class dicts already use shared keys. I should look into that to see if we can leverage the mechanisms there. - We can decide instead that RefCells only own their value if they don't belong to a living scope. Meaning, they don't try to delete anything when they're deleted unless their owning scope is dead. - NestedRefCells can be a subclass. It would save a pointer in some cases. (But it's a PyObject, so it'd not save much.) - In C, the KeyErrors would instead return NULL. The code follows. class ScopeDict(dict): __slots__ = { '__inner__': Dict[Any, Nullable[Any]], # == super(). 'refs': SharedDict[Any, Nullable[RefCells]], # Shares keys with __inner__. 'parents': List[ScopeDict], } class RefCell: __slots__ = { 'key': Nullable[str], # Or not nullable? 'value_ptr': Pointer[Nullable[Any]], # Pointer to the pointer to the value object. 'parents': Nullable[ScopeDict | RefCell], 'indirect': bool, # True: # The owning dict is alive. # value_ptr is reference to pointer to value. # This is the normal case. # False: # The owning dict is gone. # value_ptr is counted reference to value. # The cell owns the reference. # This bit can be packed into the value_ptr. # In fact, this isn't necessary: # The .resolve function can be dynamic. } def ScopeDict.getref(self, key, create_if_none=True): """ Get a ref to a key. Raise KeyError if it doesn't exist and if not create_if_none. """ if self.refs[key] is not NULL: # refcell exists return self.refs[key] if key in self: #value exists, refcell doesn't # Create refcell to the value pointer return self.create_ref(key) # Value does not exist. Search direct parents. # Stop at the first parent cell, even if it doesn't # have a value. One parent cell is enough to justify # the creation of a cell. for i, parent in enumerate(self.parents if self.parents else ()): try: ref = parent.getref(key, create_if_none=False) index = i break except KeyError: pass else: #No parent has the key if create_if_none: # Create ref return self.create_ref(key) else: #Give up raise KeyError(key) # Found a parent with a refcell. # Save a reference to it. cell = self.create_ref(key) cell.parents[index] = ref return cell def ScopeDict.create_ref(self, key): """ Create a refcell. """ # Add key to inner dict if it doesn't exist. if key not in self.__inner__: self.__inner__[key] = NULL # Wrap the address of the value pointer in a refcell. cell = RefCell(&(self.__inner__.value_pointer(key))) self.refs[key] = cell if self.parents: # Save the parents. # This is in case value == NULL # and it needs to look it up in the parents. cell.parents = self.parents.copy() else: cell.parents = NULL # Not necessary if no parents. # (Except for tracebacks?) cell.key = key return cell def RefCell.resolve(self): """ Resolve cell to a value. Will not return NULL. Will raise KeyError if fail. (In C, it would return NULL instead.) """ if not self.indirect: if self.value_ptr is not NULL: return self.value_ptr elif self.value_ptr.deref() is not NULL: return self.value_ptr.deref() # No parents to search if self.parents is NULL: raise KeyError # Search parents for value. for i, parent in enumerate(self.parents): # We want the parent CELL. if not isinstance(parent, RefCell): # Try to ask for a ref from parent. assert isinstance(parent, ScopeDict) try: parent = parent.getref(self.key, create_if_none=False) except KeyError: continue # Give up on this parent. self.parents[i] = parent # Try to get parent cell to resolve. try: return parent.resolve() except KeyError: continue raise KeyError Here are some of the wrapper algorithms for the dict methods. # No change. ScopeDict.__setitem__ = dict.__setitem__ def ScopeDict.keys(self): # Example of iteration. # This is already the algorithm, probably, so there's no extra cost. for key, value in self.__inner__.items(): if value is not NULL: yield key def ScopeDict.__getitem__(self, key): result = self.__inner__.get(key, NULL) # This is an extra check. if result is not NULL: return result if key in self.refs: # This is an extra check. # Only necessary for nested scopes. # So a regular dict doesn't even need this. # In fact, for class dicts, you don't want it, # since it skips the MRO. try: self.refs[key].resolve() except KeyError: pass raise KeyError(key) def ScopeDict.__delitem__(self, key): if self.__inner__.get(key, NULL) is NULL: # extra check? raise KeyError(key) delete self.__inner__[key] self.__inner__[key] = NULL def ScopeDict.__del__(self): """ Delete this dict. """ for key in self.__inner__: ref = self.refs[key] if ref is NULL: # no ref (standard dict case) delete self.__inner__[key] # DecRef the value else: if ref.__refcount > 1: #ref is exposed # Make it point directly to the value. ref.value_ptr = self.__inner__[key] ref.indirect = True self.refs[key] = NULL delete ref # DecRef, not dict removal def ScopeDict.compact(self): """ Compact the dictionary. (Similarly for expanding.) """ new_table = {} new_refs = {} # Remove unnecessary entries # Let dict.__table be the internal entry table for key in self.__inner__: ref = self.refs[key] if ref is not NULL and ref.__refcount == 1: # Ref exists but is not exposed. # Delete unused reference. ref.value_ptr = NULL delete ref ref = NULL if value is not NULL or ref is not NULL: # Add it to the new table using normal dict # compact algorithm. (I don't know it.) new_table[key] = value new_refs[key] = ref # Can add a check here: If there are no live refs, # convert to a regular dict. self.__inner__ = new_table self.refs = new_refs def RefCell.__del__(self): if self.indirect: #pointing at the pointer delete self.value_ptr.deref() else: #pointing at the value delete self.value_ptr delete self.key delete self.parents _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
