New subject: Optimizing global names via dict references

Dec. 20, 2015

      (Sent this from the wrong email and it got rejected. Sorry, Victor, for the
double post.)

On Dec 20, 2015 2:03 AM, "Franklin?" <redacted> wrote:
...
Oops, that was supposed to private. No point now.
Anyway, after I read Tim's remark, I realized that I overestimated the
cost of dict lookups. It's not the complexity, but the constant factor in
terms of branches and dereferences. It means that if I want to make an
improvement, it would have to be very optimized C. They were discussing
tricks like having a cell consider itself as its own parent, just to avoid
a branch, which is not the level at which I was thinking.
...
I think that normal dict operations won't have to slow down, except
resize/destruction. I don't use registry, so there is no O(n) notification.
This is an important difference from Neil Toronto's original method.
...
Reading PEP 266, and rethinking your own work, I'm now considering a
separate idea for temporary registries. But I think it'd be reaching into
JIT territory, and I'm not confident at all in my JIT knowledge. I can't
say that this idea would be an improvement. I'm just putting this out there
in the hope that it can make some sense and inspire someone to have a real
idea.
...
The idea is, when code is running, if a function is called (within a
loop?), load its global names into an array and register them with the
globals/builtins (which can be done with user dicts by temporarily swapping
out their get/set/del). Then replace the function with one that does
LOAD_CONSTANT (like in FAT Python) and replace its function calls with
"compile the functions the same way before calling" bytecodes.
...
This array is for the whole stack. As I imagine it, it will be used
during an execution. So for the REPL, it can be a new array per eval, or
just globally.
...
The trick is, each name will be added to the array once, so the registry
will slow down the normal dict operations but each dict change only needs
(at most) one notification per stack.
...
This can be made to (only) slow down the dicts which are used as scopes,
by dynamically swapping out its function pointers upon (temporary?)
conversion.
...
(You sent this as private?)
On Dec 19, 2015 7:09 PM, "Victor Stinner" <victor.stinner@gmail.com>
wrote:
...
...
Le 19 déc. 2015 21:07, "Franklin? Lee" <leewangzhong+python@gmail.com> a
écrit :
...
...
Tim Peters points out how it might be more expensive than a lookup.
Your whole idea rely on the assumption than a dict lookup (two lookups
for builtins) is slow. Remember that a dict lookup has a complexity of
O(1)! That's why I suggested you to start to benchmark, especially know the
time in nanoseconds of a dict lookup.
...
He ended up using versioning, because the notification was expensive.
Yeah I also began with notification with a registry of functions before
moving to versionning:
http://faster-cpython.readthedocs.org/readonly.html
Versionning is simple to implement and doesn't make dict operations
slower.
Victor

Re: [Python-ideas] Optimizing global names via dict references

Franklin? Lee

Guido van Rossum

Guido van Rossum

tags

participants (2)