4 ms·

Is there a list of common language poison pills? I'd like to learn more.

saagarjha 8y ago
I'd assume anything that breaks expectations and speculative execution. Weak typing, dynamic function calls, etc.
jerf 8y ago
Well, I can't do a full list, but: Memory non-locality. On modern systems, thrashing through RAM just kills you on performance. I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". For JITs, any time the JIT has the ability to make an assumption, but then you break it. The obvious one is "this function always returns an int", which the JIT can nicely optimize, but if once you ever return a string, the JIT will have to do something to deoptimize that case again, possibly permanently. More subtly, things like "returning an object that always has these three keys that map to these three values of a certain type", which a JIT can optimize to a struct under the hood, until you change a type or add a field for a particular call. Just in general, any assumption the JIT can make for performance that you might break in a function. You should generally program your performance-sensitive JS as if it were statically typed, even if it isn't. Indirection for the user's convenience; one of the reasons CPython is sooo slooooow is that there's a ton of indirection going on. For the code x.y(), you can change x by directly overriding "y" on the specific x you are using, or it can be set at the class level, or it can be set by any of the superclasses, or the dot operator may be a function that does arbitrary things up to and including arbitrary mutation of whatever it gets its hands on, etc., plus even without overridding getattr there's this whole "property" thing, plus it could be a __slot__, and I'm pretty sure I'm missing at least one thing here, and CPython is hopping through all these hoops for every such lookup. The fact that "x.y()" translates to dozens or hundreds of C lines of code is what Python so convenient, but at the same time, what makes it so slow, too. I understand the value of being able to override things; I question the need of dynamic scripting languages to provide so many places to override things.
- blattimwind 8y ago
  > I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". Rule of Python: Everything is at least two pointers away. -- > and CPython is hopping through all these hoops for every such lookup. Actually CPython has a cache for that. This becomes apparent if you improperly replace methods in the class dictionary. I think the bane of Python specifically is a bit different. It's not so much that it's very dynamic, because JITs can clearly deal with that. It's that CPython exposes all kinds of interpreter state that's off-limits in other languages, which makes it way harder to JIT. In JavaScript there are at most a handful ways how you can mutate a prototype, but in CPython you don't have enough fingers to count them, even if you only consider Python and not the C API.
  - jerf 8y ago
    "Actually CPython has a cache for that." My apologies for my unclarity. In my head, "hopping through all these hoops" included using caching, but that is completely unclear. It is true that there is a lot of caching being done, because it would simply be unusable if there isn't. But it is also true that there is still a lot of work to do for "x.y()", even when all caches are used fully.
    - blattimwind 8y ago
      Yes... and most of it is even part of stable APIs.
- arghwhat 8y ago
  I'd like to add: Don't define your array as nothing but a hashmap with strings as array indexes, with two assignment hooks: One that on assignment updates that sets length = max(length, ToUint32(assigned key)), and one on "length" assignment that iterates over all keys in the hashmap, and for those that can be parsed as uint32's, delete those that have a numerical value larger than the value assigned to length. That is how JavaScript "Array" objects work. Array indexes are coerced to a strings, as they are for all objects. For the curious, here is full definition from ECMA-262 1st edition, which describe what browsers currently implement (https://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262,%201st%20edition,%20June%201997.pdf https://www.ecma-international.org/publications/files/ECMA-S..., page 65): Array objects give special treatment to a certain class of property names. A property name P (in the form of a string value) is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 232−1. Every Array object has a length property whose value is always an integer with positive sign and less than 232. It is always the case that the length property is numerically greater than the name of every property whose name is an array index; whenever a property of an Array object is created or changed, other properties are adjusted as necessary to maintain this invariant. Specifically, whenever a property is added whose name is an array index, the length property is changed, if necessary, to be one more than the numeric value of that array index; and whenever the length property is changed, every property whose name is an array index whose value is not smaller than the new length is automatically deleted. This constraint applies only to properties of the Array object itself and is unaffected by length or array index properties that may be inherited from its prototype.
kodablah 8y ago
Anything that has to be interpreted or un-JIT'd for the most part. Runtime eval, runtime struct memory layout redefining, runtime type change, etc. Basically it's a trade off between pre-compiled immutable omniscience and developer friendliness. Targeting the former often increases perf due to the assumptions you can make, targeting the latter increases comfort and adoption and usability and simplicity.
gameswithgo 8y ago
a JIT is one! time is wasted doing compiling while running, the compiler has strict time constraints so can't do as many optimizations, claims about theoretical benefits from runtime data collection and-recompilation for optimization are rarely reazlied in the actual world and profile guided optimizations can achieve similar things for AOT compiled programs. soooooooooooo AOT master race
- TomMarius 8y ago
  What about WebAssembly? How would you provide the same guarantees and benefits without JITing or interpreting?
- bjoli 8y ago
  As someone who has ported racket's for loops to guile scheme (or at least, re-implemented them without looking at the source of the original racket macros), a JIT has several benefits. There are some things that you just can't know at compile time, and hot paths/inline caches solve a lot of those things. for example (for/list ([a (in-range a b c)]) (+ a 100)). Since in-range has to check when to end the loop, it has to know whether the loop goes in negative or positive direction (ie: to check the loop using < or >). If the values of a b c isn't known at compile time, the comparator has to be checked for each loop. This can potentially be very expensive, especially in an inner loop. There are loads of optimizations that can be done much more efficiently/easily by a JIT. Store sinking, store/load forwarding, array bounds check elimination, value-range propagation and hyperblock scheduling to name a few. LuaJIT is still the fastest dynamic language out there, but the complexity of the codebase surely makes you wish that wasn't the case.
  - ufo 8y ago
    You can avoid the test by generating two loops (one that goes up and one that goes down). But that can lead to code bloat...
beagle3 8y ago
Mike Pall of LuaJIT fame opined on that on the luajit mailing list a few years back. Can't find the discussion right now, but only https://news.ycombinator.com/item?id=8605225 https://news.ycombinator.com/item?id=8605225 which is somewhat relevant.
bjoli 8y ago
Redefining things are generally a no-no, especially top level things. Knowing what things are and where they are makes things much easier to implement. For inline caches it is much better if you don't redefine things, which applies to JITs. I remember reading that Mike Pall said about pypy that most of the optimizations he did for luajit were possible for python, but just a lot more work. Using mutation is a really good way to make most scheme implementations run slowly, since mutation is generally avoided, and thus most flow analysis is spent on checking recursion. A while-loop using set! is generally a lot slower than a recursive named let loop. Flow analysis is simply easier without mutation, even though it might not look easier for the person reading the code.
ufo 8y ago
The poison-pills are implementation dependent. At the end of the day it is just a matter of the JIT not optimizing a certain programming pattern. Sometimes it is just because the authors didn't get around to that yet. Sometimes there is a more fundamental reason why optimizing that pattern would be hard. I am most familiar with LuaJIT. It has wiki page with a list of things that force it to fall back to the interpreter http://wiki.luajit.org/NYI http://wiki.luajit.org/NYI
- TomMarius 8y ago
  Sure. I was interested in known patterns that make optimization hard, because I'm toying with implementing a language myself. Thank you for your link!

I'd assume anything that breaks expectations and speculative execution. Weak typing, dynamic function calls, etc.

jerf 8y ago

Well, I can't do a full list, but: Memory non-locality. On modern systems, thrashing through RAM just kills you on performance. I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". For JITs, any time the JIT has the ability to make an assumption, but then you break it. The obvious one is "this function always returns an int", which the JIT can nicely optimize, but if once you ever return a string, the JIT will have to do something to deoptimize that case again, possibly permanently. More subtly, things like "returning an object that always has these three keys that map to these three values of a certain type", which a JIT can optimize to a struct under the hood, until you change a type or add a field for a particular call. Just in general, any assumption the JIT can make for performance that you might break in a function. You should generally program your performance-sensitive JS as if it were statically typed, even if it isn't. Indirection for the user's convenience; one of the reasons CPython is sooo slooooow is that there's a ton of indirection going on. For the code x.y(), you can change x by directly overriding "y" on the specific x you are using, or it can be set at the class level, or it can be set by any of the superclasses, or the dot operator may be a function that does arbitrary things up to and including arbitrary mutation of whatever it gets its hands on, etc., plus even without overridding getattr there's this whole "property" thing, plus it could be a __slot__, and I'm pretty sure I'm missing at least one thing here, and CPython is hopping through all these hoops for every such lookup. The fact that "x.y()" translates to dozens or hundreds of C lines of code is what Python so convenient, but at the same time, what makes it so slow, too. I understand the value of being able to override things; I question the need of dynamic scripting languages to provide so many places to override things.

blattimwind 8y ago
> I don't know that you have to hand full control over to the programmer, but if you're randomly flinging values on the heap everywhere (a.k.a. "hash tables"), you're gonna hit a wall long before you get to "C performance". Rule of Python: Everything is at least two pointers away. -- > and CPython is hopping through all these hoops for every such lookup. Actually CPython has a cache for that. This becomes apparent if you improperly replace methods in the class dictionary. I think the bane of Python specifically is a bit different. It's not so much that it's very dynamic, because JITs can clearly deal with that. It's that CPython exposes all kinds of interpreter state that's off-limits in other languages, which makes it way harder to JIT. In JavaScript there are at most a handful ways how you can mutate a prototype, but in CPython you don't have enough fingers to count them, even if you only consider Python and not the C API.
- jerf 8y ago
  "Actually CPython has a cache for that." My apologies for my unclarity. In my head, "hopping through all these hoops" included using caching, but that is completely unclear. It is true that there is a lot of caching being done, because it would simply be unusable if there isn't. But it is also true that there is still a lot of work to do for "x.y()", even when all caches are used fully.
  - blattimwind 8y ago
    Yes... and most of it is even part of stable APIs.
arghwhat 8y ago
I'd like to add: Don't define your array as nothing but a hashmap with strings as array indexes, with two assignment hooks: One that on assignment updates that sets length = max(length, ToUint32(assigned key)), and one on "length" assignment that iterates over all keys in the hashmap, and for those that can be parsed as uint32's, delete those that have a numerical value larger than the value assigned to length. That is how JavaScript "Array" objects work. Array indexes are coerced to a strings, as they are for all objects. For the curious, here is full definition from ECMA-262 1st edition, which describe what browsers currently implement (https://www.ecma-international.org/publications/files/ECMA-ST-ARCH/ECMA-262,%201st%20edition,%20June%201997.pdf https://www.ecma-international.org/publications/files/ECMA-S..., page 65): Array objects give special treatment to a certain class of property names. A property name P (in the form of a string value) is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 232−1. Every Array object has a length property whose value is always an integer with positive sign and less than 232. It is always the case that the length property is numerically greater than the name of every property whose name is an array index; whenever a property of an Array object is created or changed, other properties are adjusted as necessary to maintain this invariant. Specifically, whenever a property is added whose name is an array index, the length property is changed, if necessary, to be one more than the numeric value of that array index; and whenever the length property is changed, every property whose name is an array index whose value is not smaller than the new length is automatically deleted. This constraint applies only to properties of the Array object itself and is unaffected by length or array index properties that may be inherited from its prototype.

kodablah 8y ago

Anything that has to be interpreted or un-JIT'd for the most part. Runtime eval, runtime struct memory layout redefining, runtime type change, etc. Basically it's a trade off between pre-compiled immutable omniscience and developer friendliness. Targeting the former often increases perf due to the assumptions you can make, targeting the latter increases comfort and adoption and usability and simplicity.

gameswithgo 8y ago

a JIT is one! time is wasted doing compiling while running, the compiler has strict time constraints so can't do as many optimizations, claims about theoretical benefits from runtime data collection and-recompilation for optimization are rarely reazlied in the actual world and profile guided optimizations can achieve similar things for AOT compiled programs. soooooooooooo AOT master race

TomMarius 8y ago
What about WebAssembly? How would you provide the same guarantees and benefits without JITing or interpreting?
bjoli 8y ago
As someone who has ported racket's for loops to guile scheme (or at least, re-implemented them without looking at the source of the original racket macros), a JIT has several benefits. There are some things that you just can't know at compile time, and hot paths/inline caches solve a lot of those things. for example (for/list ([a (in-range a b c)]) (+ a 100)). Since in-range has to check when to end the loop, it has to know whether the loop goes in negative or positive direction (ie: to check the loop using < or >). If the values of a b c isn't known at compile time, the comparator has to be checked for each loop. This can potentially be very expensive, especially in an inner loop. There are loads of optimizations that can be done much more efficiently/easily by a JIT. Store sinking, store/load forwarding, array bounds check elimination, value-range propagation and hyperblock scheduling to name a few. LuaJIT is still the fastest dynamic language out there, but the complexity of the codebase surely makes you wish that wasn't the case.
- ufo 8y ago
  You can avoid the test by generating two loops (one that goes up and one that goes down). But that can lead to code bloat...

beagle3 8y ago

Mike Pall of LuaJIT fame opined on that on the luajit mailing list a few years back. Can't find the discussion right now, but only https://news.ycombinator.com/item?id=8605225 https://news.ycombinator.com/item?id=8605225 which is somewhat relevant.

bjoli 8y ago

Redefining things are generally a no-no, especially top level things. Knowing what things are and where they are makes things much easier to implement. For inline caches it is much better if you don't redefine things, which applies to JITs. I remember reading that Mike Pall said about pypy that most of the optimizations he did for luajit were possible for python, but just a lot more work. Using mutation is a really good way to make most scheme implementations run slowly, since mutation is generally avoided, and thus most flow analysis is spent on checking recursion. A while-loop using set! is generally a lot slower than a recursive named let loop. Flow analysis is simply easier without mutation, even though it might not look easier for the person reading the code.

ufo 8y ago

The poison-pills are implementation dependent. At the end of the day it is just a matter of the JIT not optimizing a certain programming pattern. Sometimes it is just because the authors didn't get around to that yet. Sometimes there is a more fundamental reason why optimizing that pattern would be hard. I am most familiar with LuaJIT. It has wiki page with a list of things that force it to fall back to the interpreter http://wiki.luajit.org/NYI http://wiki.luajit.org/NYI

TomMarius 8y ago
Sure. I was interested in known patterns that make optimization hard, because I'm toying with implementing a language myself. Thank you for your link!