4 ms·

> Python can quickly check to see if they are using the dynamic features I don't understand how this is supposed to be "quickly" verifiable? Nothing prevents

> Python can quickly check to see if they are using the dynamic features I don't understand how this is supposed to be "quickly" verifiable? Nothing prevents you from doing eval('gl' + 'obals')()['len'] = ...; how is the interpreter supposed to quickly check that this isn't the case when you're calling a function that might not even be in the current module? Doing this correctly would seem to require a ton of static analysis on the source or bytecode that I imagine will at best be slow, and at worst impossible due to the halting problem.

gpderetta 4y ago
One possibility is to move the cost to the assignment, so the code that assigns a new value to the global 'len' function is going to track and invalidate all cached lookups. Hopefully you are changing the binding of 'len' less often than you are calling it :)
- kmod 4y ago
  Cinder does this (invalidation), and both Faster CPython and Pyston use guarding.
  - gpderetta 4y ago
    Right, of course, guarded devirtualization is a common technique.
deleted 4y ago
[deleted]
bootwoot 4y ago
I was reading this as an undetailed description of state available WITHIN the interpreter. Probably there is a table of globals that you can simply check last modification on or something like this. Whether you hit it with eval or some other tricky code, you can't modify a global without the interpreter knowing about it.
- dataflow 4y ago
  If that's what they mean, how would that be any faster than what's going on right now? I thought normally when you hit a callable, the interpreter would just look up its name, check to see if it's a built-in, and then call the built-in if so... whereas in this case you'd still have to look up the name of the callable (is the idea to bypass this somehow? what do they do currently?), check to see if it's different than the built-in you'd expect from the name (i.e. if it's ever been reassigned to), then call that expected built-in if it's not... which seems like the same thing? At best it would seem to convert 1 indirect call to a direct call, which would be negligible for something like Python. Is the current implementation somehow much slower than I'm imagining? What am I missing?
  - the-lazy-guy 4y ago
    You could do something like primitive inline cache. Store "version" of the globals in another variable. Each time globals are modified - bump the version. For each call-site and/or keep what the global name is resolved to + version of "globals object" in a static variable. Now you can avoid name resolution if version hasn't changed between two executions of the line. Now in fast-path you just pay the price of (easily predicted, because globals almost never change) single compare and jump vs full hash-table lookup.
    - dataflow 4y ago
      I think the core of the optimization you're mentioning hinges on a normal lookup being a slow hashtable lookup (of a string?)... whereas I imagined the first thing the interpreter would do would be to intern each name and assign it a unique ID (as soon as during parsing, say) and use that thereafter whenever they're not forced to use a string (like with globals()). That integer could literally be a global integer index into a table of interned strings, so you could either avoid hashing entirely (if the table isn't too big) or reduce it to hashing an int, both of which are much faster than hashing a string. Do they not do that already? Any idea why? I feel like that's the real optimization you'd need if checking a key in a hashtable is the slow part (and it's independent of whether the value is being modified).
blagie 4y ago
I don't think the world is quite so bad. x86 processors solve this by speculating about what's going on. If you suddenly run into a 1976-era operation, everything slows down dramatically for a bit (but still goes faster than an 8086). If you have a branch or cache miss, things slow down a little bit. One has a few possibilities: - A static analysis /proves/ something. print is print. You optimize a lot. - A static analysis /suggests/ something. print is print, unless redefined in an eval. You just need to go into a slow path in operations like `eval`, so if print is modified, you invalidate the static analysis. - A static or dynamic analysis suggests something probabilistically. You can make the fast path fast, and the slow path eventually work. If print isn't print, you raise an internal exception, do some recovery, and get back to it. I'm also okay with this analysis being run in prod and not in dev. As a footnote, JITs, especially in Java, show that this kind of analysis can be pretty fast. You don't need it to work 100% of the time. The case of a variable being redefined in a dozen places, you just ignore. The case where I call a function from three places which increments an integer each time, I can find with hardly any overhead at all. The latter tends to be where most of the bottlenecks are.
marcosdumay 4y ago
Hum... You are getting lost on theoretical undecidability. On the real world, when faced with a generally undecidable problem, we don't run away and lose all hope. We decide the cases that can be decided, and do something safe when they can't be decided. On your example, Python can just re-optimize everything after an eval. That doesn't stop it from running optimized code if the eval does not happen. It can do even more and only re-optimize things that the eval touched, what has some extra benefits and costs, so may or may not be better. Besides, when there isn't an eval on the code, the interpreter can just ignore anything about it.
- dataflow 4y ago
  > You are getting lost on theoretical undecidability. [...] We decide the cases that can be decided, and do something safe when they can't be decided. I'm not lost on that at all; I'm well aware of that. that's precisely why I wrote >> [...] require a ton of static analysis on the source or bytecode that I imagine will at best be slow, and at worst impossible due to the halting problem and not >> static analysis is impossible in the general case so we run away and lose all hope. I'm not sure how you read that sentiment from my comment.
  - marcosdumay 4y ago
    Hum... Ok. Then the answer is that most cases do not demand as much analysis time as you expect, and the ones that demand more still can gain something from dynamic behavior analysis in a JIT. Also, you can combine the two to get something better than any single analysis alone.
deleted 4y ago
[deleted]
chrisseaton 4y ago
> I don't understand how this is supposed to be "quickly" verifiable? You don’t verify, and instead you run assuming no verification is needed. Then if someone wants to violate that assumption, it’s their problem to stop everyone who may have made that assumption, and to ask them to not make it going forward. You shift the cost to the person who’s doing the metaprogramming and keep it free for everyone who isn’t. https://chrisseaton.com/truffleruby/deoptimizing/ https://chrisseaton.com/truffleruby/deoptimizing/
kmod 4y ago
Python dictionaries now have version counters that track how many times they were modified, so the quick check is to ask "was len not overidden last time and is the number of modifications to the globals the same as it was last time".

gpderetta 4y ago

One possibility is to move the cost to the assignment, so the code that assigns a new value to the global 'len' function is going to track and invalidate all cached lookups. Hopefully you are changing the binding of 'len' less often than you are calling it :)

kmod 4y ago
Cinder does this (invalidation), and both Faster CPython and Pyston use guarding.
- gpderetta 4y ago
  Right, of course, guarded devirtualization is a common technique.

deleted 4y ago

[deleted]

bootwoot 4y ago

I was reading this as an undetailed description of state available WITHIN the interpreter. Probably there is a table of globals that you can simply check last modification on or something like this. Whether you hit it with eval or some other tricky code, you can't modify a global without the interpreter knowing about it.

dataflow 4y ago
If that's what they mean, how would that be any faster than what's going on right now? I thought normally when you hit a callable, the interpreter would just look up its name, check to see if it's a built-in, and then call the built-in if so... whereas in this case you'd still have to look up the name of the callable (is the idea to bypass this somehow? what do they do currently?), check to see if it's different than the built-in you'd expect from the name (i.e. if it's ever been reassigned to), then call that expected built-in if it's not... which seems like the same thing? At best it would seem to convert 1 indirect call to a direct call, which would be negligible for something like Python. Is the current implementation somehow much slower than I'm imagining? What am I missing?
- the-lazy-guy 4y ago
  You could do something like primitive inline cache. Store "version" of the globals in another variable. Each time globals are modified - bump the version. For each call-site and/or keep what the global name is resolved to + version of "globals object" in a static variable. Now you can avoid name resolution if version hasn't changed between two executions of the line. Now in fast-path you just pay the price of (easily predicted, because globals almost never change) single compare and jump vs full hash-table lookup.
  - dataflow 4y ago
    I think the core of the optimization you're mentioning hinges on a normal lookup being a slow hashtable lookup (of a string?)... whereas I imagined the first thing the interpreter would do would be to intern each name and assign it a unique ID (as soon as during parsing, say) and use that thereafter whenever they're not forced to use a string (like with globals()). That integer could literally be a global integer index into a table of interned strings, so you could either avoid hashing entirely (if the table isn't too big) or reduce it to hashing an int, both of which are much faster than hashing a string. Do they not do that already? Any idea why? I feel like that's the real optimization you'd need if checking a key in a hashtable is the slow part (and it's independent of whether the value is being modified).

blagie 4y ago

I don't think the world is quite so bad. x86 processors solve this by speculating about what's going on. If you suddenly run into a 1976-era operation, everything slows down dramatically for a bit (but still goes faster than an 8086). If you have a branch or cache miss, things slow down a little bit. One has a few possibilities: - A static analysis /proves/ something. print is print. You optimize a lot. - A static analysis /suggests/ something. print is print, unless redefined in an eval. You just need to go into a slow path in operations like `eval`, so if print is modified, you invalidate the static analysis. - A static or dynamic analysis suggests something probabilistically. You can make the fast path fast, and the slow path eventually work. If print isn't print, you raise an internal exception, do some recovery, and get back to it. I'm also okay with this analysis being run in prod and not in dev. As a footnote, JITs, especially in Java, show that this kind of analysis can be pretty fast. You don't need it to work 100% of the time. The case of a variable being redefined in a dozen places, you just ignore. The case where I call a function from three places which increments an integer each time, I can find with hardly any overhead at all. The latter tends to be where most of the bottlenecks are.

marcosdumay 4y ago

Hum... You are getting lost on theoretical undecidability. On the real world, when faced with a generally undecidable problem, we don't run away and lose all hope. We decide the cases that can be decided, and do something safe when they can't be decided. On your example, Python can just re-optimize everything after an eval. That doesn't stop it from running optimized code if the eval does not happen. It can do even more and only re-optimize things that the eval touched, what has some extra benefits and costs, so may or may not be better. Besides, when there isn't an eval on the code, the interpreter can just ignore anything about it.

dataflow 4y ago
> You are getting lost on theoretical undecidability. [...] We decide the cases that can be decided, and do something safe when they can't be decided. I'm not lost on that at all; I'm well aware of that. that's precisely why I wrote >> [...] require a ton of static analysis on the source or bytecode that I imagine will at best be slow, and at worst impossible due to the halting problem and not >> static analysis is impossible in the general case so we run away and lose all hope. I'm not sure how you read that sentiment from my comment.
- marcosdumay 4y ago
  Hum... Ok. Then the answer is that most cases do not demand as much analysis time as you expect, and the ones that demand more still can gain something from dynamic behavior analysis in a JIT. Also, you can combine the two to get something better than any single analysis alone.

deleted 4y ago

[deleted]

chrisseaton 4y ago

> I don't understand how this is supposed to be "quickly" verifiable? You don’t verify, and instead you run assuming no verification is needed. Then if someone wants to violate that assumption, it’s their problem to stop everyone who may have made that assumption, and to ask them to not make it going forward. You shift the cost to the person who’s doing the metaprogramming and keep it free for everyone who isn’t. https://chrisseaton.com/truffleruby/deoptimizing/ https://chrisseaton.com/truffleruby/deoptimizing/

kmod 4y ago

Python dictionaries now have version counters that track how many times they were modified, so the quick check is to ask "was len not overidden last time and is the number of modifications to the globals the same as it was last time".