[Python-Dev] Third milestone of FAT Python
Franklin? Lee
leewangzhong+python at gmail.com
Thu Dec 17 05:54:39 EST 2015
On Wed, Dec 16, 2015 at 2:01 AM, Victor Stinner
<victor.stinner at gmail.com> wrote:
> Le mercredi 16 décembre 2015, Franklin? Lee <leewangzhong+python at 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
More information about the Python-Dev
mailing list