Closed tschw closed 8 years ago
My understanding is that if you have { a: 1, b: undefined }, and then you do b = 2, the javascript engine will allocate two different objects because they have different structure.
I'm not sure on this one...
var o = { a: 1 }
followed by o.b = 2
is definitely two different object types.
However, { a: 1, b: undefined }
or var o = { a: 1, b: 2 }
followed by o.b = undefined
may be the same object; just with one of its values set to undefined.
On the other hand using delete
to remove a property definitely causes it not to be the same object type; but I think it goes further than just causing a new object type (hidden class) and moves it permanently to a slower hashtable object due to this change.
Edit: Ah you address this with the for loop example :)
What do you mean by "object type"?
When a constructor does like this.that = ...
and this.another = ...
it creates many "object types" along the way, then...
var o = { a: 1 } followed by o.b = 2 is definitely two different object types.
under the hood is most probably just an insertion into a dynamic hashtable, which may or may not require rehashing, depending on the number of free slots left when .b
is added.
I think it goes further than just causing a new object type (hidden class) and moves it permanently to a slower hashtable object due to this change.
I don't buy it. Any benchmarks or pointer to code of an actual JS implementation confirming this theory?
[ ... delete ] I think it goes further than just causing a new object type (hidden class) and moves it permanently to a slower hashtable object due to this change.
I don't buy it. Any benchmarks or pointer to code of an actual JS implementation confirming this theory?
In SpiderMonkey, what you call "object type" is called a "shape lineage". Adding properties to an object grows a tree structure of "shapes" where the path from the root to a leaf is the "lineage" IOW the property structure of one or more objects. However, once an object gets too large or any but the last-added property is deleted, the object switches to "dictionary mode" in which case it will behave differently, optimizing for more frequent changes of the object structure.
It's explained in vm/Shape.h in the SpiderMonkey source code.
Conslusions:
delete
. It can confuse the VM on class instances, making it optimize for the wrong case. Luckily we can always assign undefined
instead.WebKit uses descriptions of objects' "structures" organized into a graph, where the edges describe "transitions" from one structure to another (see Source/JavaScriptCore/runtime/Structure.h). Structures provide the meta model for mapping object properties into arrays. There is the typical over-allocation going on, so only every n-th added property causes an allocation, where n grows with the number of properties in the object (much like std::vector
in C++ or ArrayList
in Java). There are different modes for indexing, but it appears they are only used for arrays.
V8 uses a similar approach but appears to know various array-mapped representation of the property map. It also has a dictionary mode like SpiderMonkey. I didn't really figure out where it swiches, but I do not worry that it will handle the case I describe (and probably dozens of other ones) quite well. Those masses of code must be good for something...
There are no obvious show-stoppers in the JS implementations. C/C++ programmers would have to go great lengths for such a flexible data model and are often stuck with bloat or crutches as software grows.
I think we should try it for Object3D
and Mesh
to benchmark a test case with several thousand objects, changing some properties every frame and measuring time spent for object construction. I bet there will be a way to take advantage of what JavaScript can give us, and we'll see much better performance at scale.
All defaults that will not certainly change their value should go on the prototype ....
So, you are promoting this pattern? https://github.com/mrdoob/three.js/blob/master/src/math/Color.js#L21
All optional properties should simply not be defined - especially not on the object itself, as opposed to its prototype
One drawback: I always look at assignment of properties in the constructor to understand the API of the object. It's hard to reason about the capabilities of an objects when properties are assigned to it in the dark corners of the library.
I think we should try it for Object3D and Mesh to benchmark a test case with several thousand objects
What is your main goal?
Object3D
? This should be easy to measure - just remove the properties you'd consider optional and use the dev tools. No need to render the scene, it just adds constant size.Let's say we save a 1 kB per Object3D
and cut traversal time in half (that seems generous). Even with tens of thousands of objects, won't this be dwarfed by the allocation/manipulation of buffers in the renderer?
Still, I curious about your findings.
Semi related - I proposed in #6782 a plugin system to dynamically extend objects with
capabilities. Different goal however: my main objective was to add runtime features (get rid of instanceof
and simplify the renderer), not create a dynamic lightweight objects per say.
One drawback: I always look at assignment of properties in the constructor to understand the API of the object.
I understand. I do think we should keep a complete reference (in comments and/or code) of all supported properties, optional or not. When constructors are mostly empty, you won't even have to scroll down to see stuff in the prototype. Best docs have always been the headers :-)
Speed of traversal? Dynamic objects means smaller footprint, hence better cache usage,
Yes. And better scalability and memory efficiency in general:
Many optional properties are tested every frame. If those all represent unused features and we pull an "off" state from diverse memory locations, we are wasting cache space that could be spent elsewhere.
but potentially more irregular hidden classes, hence worst cache usage.
I don't believe in that part. The client will end up with a small amount of specializations that suit hir case. In some implementations the memory representation of the metadata will even overlap between different structures. Either way, it's tiny and gets shared among all objects with the same structure (unless using the delete operator in Firefox), so I don't see how this could have much of a negative impact on caching.
Let's say we save a 1 kB per Object3D and cut traversal time in half (that seems generous). Even with tens of thousands of objects, won't this be dwarfed by the allocation/manipulation of buffers in the renderer?
No. Buffers reside on the GPU. Once uploaded they are referenced by a single integer (and there will be some bookkeeping in the driver, but let's put our own house in order).
If you are talking about dynamic data structures used by the renderer internally, well, those should of course become as lean as possible too. But let's make it another ticket :-).
If you are pumping lots of data every frame, then yes. But I consider this a resource-intense corner case that should be avoided, especially in WebGL. It's often possible to get away with switching index buffers and an appropriate vertex shader.
I think it goes further than just causing a new object type (hidden class) and moves it permanently to a slower hashtable object due to this change.
I don't buy it. Any benchmarks or pointer to code of an actual JS implementation confirming this theory?
Its from quite a few years ago, can have a dig; there were also some Google talks about it - may have changed. but was why lots of the V8 advice was 'set it all up in constructor' as the if you change it too much later you also get the double whammy of switching object type and causing the optimised jitted code to bail back to interpreted code as its assumptions are violated (assuming you've used the object for a bit, then add new properties).
You've looked into V8 & SpiderMonkey
Other engines will need to be investigated.
Chakra to complete the big 3 for WebGL: from http://blogs.msdn.com/b/ie/archive/2014/10/09/announcing-key-advances-to-javascript-performance-in-windows-10-technical-preview.aspx
Chakra’s Multi-tiered Pipeline: Historical background
While the interpreter is executing the bytecode, it collects data such as type information and invocation counts to create a profile of the functions being executed. This profile data is used to generate highly optimized machine code (a.k.a. JIT’ed code) as a part of the JIT compilation of the function. ... Given the dynamic nature of JavaScript code, if the code gets executed in a way that breaks the profile assumptions, the JIT’ed code “bails out” to the interpreter where the slower bytecode execution restarts while continuing to collect more profile data.
and
Fast JavaScript Execution: JIT compiler optimizations
Previewing Equivalent Object Type Specialization
The internal representation of an object’s property layout in Chakra is known as a “Type.” Based on the number of properties and layout of an object, Chakra creates either a Fast Type or a Slower Property Bag Type for each different object layout encountered during script execution. As properties are added to an object, its layout changes and a new type is created to represent the updated object layout. Most objects, which have the exact same property layout, share the same internal Fast Type.
Also over at new blog: http://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/ when referring to the advantages of asm.js
Predictable performance by removal of bailouts from compiled asm.js code. Given the dynamic nature of JavaScript, all modern JavaScript engines support some form of migration to non-optimized code execution, called bailouts, when they determine that the assumptions made by the JIT compilers are no longer valid for the compiled code. Bailouts not only impact performance but also make it unpredictable.
For V8 (from 2012) http://www.html5rocks.com/en/tutorials/speed/v8/
This might lead you to question how JavaScript performance could ever get anywhere close to C++. However, V8 has hidden types created internally for objects at runtime; objects with the same hidden class can then use the same optimized generated code. ...
- Initialize all object members in constructor functions (so the instances don't change type later)
- Always initialize object members in the same order
...
De-optimization
Finally, the optimization performed by this compiler is speculative - sometimes it doesn't work out, and we back off. The process of "deoptimization" throws away optimized code, and resumes execution at the right place in "full" compiler code. Reoptimization might be triggered again later, but for the short term, execution slows down. In particular, causing changes in the hidden classes of variables after the functions have been optimized will cause this deoptimization to occur.
Therefore:
Avoid hidden class changes in functions after they are optimized
Following up its not that the constructor is important; its that doing things in the constructor ensures the same number of same named items are allocated in the same order. So if you always used object literals { a: 1, b: 2 } and always did them the same, or always added a new property immediately after construction that would work as well - its just harder to make sure you never do it differently.
More recent docs for V8: https://developers.google.com/v8/design#prop_access
To reduce the time required to access JavaScript properties, V8 does not use dynamic lookup to access properties. Instead, V8 dynamically creates hidden classes behind the scenes. ... In V8, an object changes its hidden class when a new property is added.
...
During initial execution of the code for accessing a property of a given object, V8 determines the object's current hidden class. V8 optimizes property access by predicting that this class will also be used for all future objects accessed in the same section of code and uses the information in the class to patch the inline cache code to use the hidden class. If V8 has predicted correctly the property's value is assigned (or fetched) in a single operation. If the prediction is incorrect, V8 patches the code to remove the optimisation.
Thanks for digging it all up, @benaadams. Seems the term hidden class was coined by Google. I'm still impressed you knew about that switch to dictionary mode when using delete
in Firefox. Was it ever documented anywhere but in that header?
It's important to put any performance advice into context.
OK, let's do exactly that.
What are the assumptions?
instanceof
use, but we'll get rid of it over time), or at least by consistent copypasta, not randomly permuting the order in which properties are being added,Is there some kind of constructor magic?
More recent docs for V8: https://developers.google.com/v8/design#prop_access
show the transitions between different structures going on inside a constructor. It also states that functions are JIT compiled on first use. The other article on V8 states that optimizing JIT compilation is performed on the hot spots, based on information gathered at runtime.
Concluding: It appears to make no difference whether you grow your object inside the constructor or immediately after it has completed, although we can't be entirely sure. Constructors give people writing articles a failsafe named anchor for "a point before an object is ever being used", so could be just that...
What if the article is oversimplified and there was some magic, grouping subsequent extending transitions in constructors and/or copy loops (see (1)), somehow making them more efficient?
There are two alternative solutions:
instanceof
for that one to become feasible).What about hidden class divergence?
Let's say we have objects a
and b
, both originating from the same base, but with divergent properties defined and a function f(x)
that gets called sometimes with a
and sometimes with b
. Are we being punished?
Easiest solution is to simply recommend using only one object structure per class in one application.
Considering the fact that extension of objects is very common practice in JavaScript libraries and frameworks (1) and that given that the infrastructure possessed by today's JS implementations appears to make it fairly easy to detect that case, we may find out that it isn't really required. But it remains to be seen when benchmarking it.
(1) jQuery promotes the use of extend
(which is essentially Object.assign
) and Google's closure technology heavily promotes subclassing, which should be rather prominent examples.
What about hidden class divergence?
V8:
The goal of Inline Caches is to handle types efficiently, by caching type-dependent code for operations; when the code runs, it will validate type assumptions first, then use the inline cache to shortcut the operation. However, this means that operations that accept multiple types will be less performant.
- Monomorphic use of operations is preferred over polymorphic operations
Operations are monomorphic if the hidden classes of inputs are always the same - otherwise they are polymorphic, meaning some of the arguments can change type across different calls to the operation.
Chakra
When a monomorphic inline cache (one which stores info for only a single type) miss occurs, Chakra needs to find the location of the property by accessing a property dictionary on the new type. This path is slower than getting the location from the inline cache when a match occurs. In IE11, Chakra delivered several type system enhancements, including the ability to create polymorphic inline caches for a given property access. Polymorphic caches provide the ability to store the type information of more than one Fast Type at a given call site, such that if multiple object types come repetitively to a call site, they continue to perform fast by utilizing the property slot information from the inlined cache for that type.
Despite the speedup provided by polymorphic inline caches for multiple types, from a performance perspective, polymorphic caches are somewhat slower than monomorphic (or a single) type cache, as the compiler needs to do a hash lookup for a type match for every access.
(With some info about improvements in Edge...)
So having multiple types to the same function isn't as good; though I assume inheritance is ok, and will work as an equivalent type; assuming the subtype constructor is the first item in the constructor; so properties are added in same order.
... that gets called sometimes with a and sometimes with b. Are we being punished?
I think so yes.
Considering the fact that extension of objects is very common practice in JavaScript libraries and frameworks
However, most frameworks try to do things fast; but not really fast and consistently so; they are generally worried about reacting to user input in a way that is perceived as fast; rather than trying to get lots of heavy work done in under 16ms; 60 times a second for every second possibility for hours; where even a GC over that timeline will cause issue.
Considering the fact that extension of objects is very common practice in JavaScript libraries and frameworks
However, most frameworks try to do things fast; but not really fast and consistently so; they are generally worried about reacting to user input in a way that is perceived as fast; rather than trying to get lots of heavy work done in under 16ms; 60 times a second for every second possibility for hours; where even a GC over that timeline will cause issue.
True. Yet there are masses of code built on top of these libraries, so they will certainly be looked at by implementors when considering the cases to consider during optimization.
... that gets called sometimes with a and sometimes with b. Are we being punished?
I think so yes.
Think about this case:
function f(x) {
// optimized-out (including the lookup) when x.opt1 not present:
if ( x.opt1 !== undefined ) {
// [...]
}
// [...]
// optimized-out (including the lookup) when x.opt2 not present:
if ( x.opt2 !== undefined) {
// [...]
}
// [...]
}
At some point, the one additional lookup for polymorphic dispatch will actually start paying off, which is why I left it an open question. Too much splintering will increase the rate of instruction cache misses, though.
Another one
function f(x) {
// [...]
g(x);
// JIT can hard-wire the call target slot when generating code for a specific x
// or even inline - but it won't always do that
// - to keep the code cache-friendly when 'g' is being used in other places
// - so it can replace it independently from 'f'
// [...]
}
so the dispatch cost may not apply so broadly.
...though I assume inheritance is ok
Itl's likely to be taken care of - in one way or another. For that reason I believe that megamighty base objects are unnecessary and will only cause the library to get slower and slower as it keeps growing.
Reading the stuff on Chakra, it seems that an initialization to 0
should actually be 0.0
for a floatingpoint property, or maybe needs to be -0
so doesn't get eaten up when building, maybe still does...
I might be splitting hairs a little :)
If its something like a Mesh, a Material or even a Geometry which there might be at most hundreds per frame; it probably doesn't really matter. If it was a Vector where there are tens of thousands its probably important; but I doubt the Vector would be being extended outside the constructor?
// pulling a value into a local avoids redundant lookup. var optionalProperty = object.optionalProperty; // JIT compilers can't automate it, unless there are no side effects, which is not at all // easy to ensure when looking over real-world code in a hurry if ( optionalProperty !== undefined ) { // [ ... ] optional code using optionalProperty }
b771d2ae19e8447366883b53dd49fb4a285225eb 😊
Reading the stuff on Chakra, it seems that an initialization to 0 should actually be 0.0 for a floatingpoint property, or maybe needs to be -0 so doesn't get eaten up when building, maybe still does...
Yep. 0.0
gets eaten up, but -0
passes the build.
... If it was a Vector where there are tens of thousands its probably important
I don't really have a clue what this message of yours actually refers to as a whole, but the "zeroes story" was aimed at Vector and friends:
When there are really different structures for .x
/ y
/ z
being integers or floats, we better make sure we get floats by default. Otherwise we get polymorphism and multiply code by a factor up to 8 for each Vector3
parameter (and 16 for a Vector4
or Quaternion
) all over the place.
Subtle "function poisoning" when a Vector4
is passed in place of a Vector3
seems also to be something to watch out for...
I don't really have a clue what this message of yours actually refers to as a whole
Just meant polymorphism on a geometry call might not effect that much as the function wouldn't be called that much per frame. Whereas a function processing Vector types that might get called 100k+ per frame it would be important not to trigger polymorphism,
When there are really different structures for .x / y / z being integers or floats, we better make sure we get floats by default.
asm.js puts +
in front of the types to force types to double and | 0
to force 32 bit int so maybe that would work? Which would mean we'd want to change things like Vector to:
THREE.Vector3 = function ( x, y, z ) {
this.x = +x || +0;
this.y = +y || +0;
this.z = +z || +0;
};
THREE.Vector3.prototype = {
constructor: THREE.Vector3,
set: function ( x, y, z ) {
this.x = +x;
this.y = +y;
this.z = +z;
return this;
},
The build keeps the unary plus on the variables, but eats away the plus of +0
, which might as well be an integer.
BUT: I just double-checked the articles. It was in fact in the V8 recommendations, and I may have just jumped to conclusions:
Prefer numeric values that can be represented as 31-bit signed integers.
Will it really induce a new type and cause polymorphism on an exponential scale? I guess not - it would be super weird, especially given the fact that Google's own compiler technology apparently doesn't account for the case. It may still cause some overhead:
The concept appears to be called a Representation
in the V8 source (see objects.h / objects.cc) and applies to some kind of elements vector (see elements-kind.h) that (I guess from what I read scattered all over the place) backs both arrays and objects unless in dictionary mode. If our Vector gets an all-SMI (the name for small, 31bit integers in V8) elements kind, the representation will need to be switched, but that would happen for all properties at once.
It's a huge amount of code and I don't really have enought time for digging deep into it right now, as fascinating as it is. I'm sure there are lots of treasures to be found...
I don't really have a clue what this message of yours actually refers to as a whole
Just meant polymorphism on a geometry call might not effect that much as the function wouldn't be called that much per frame.
A Geometry (or let's say IGeometry
as an imaginary interface absracting it - Geometry
actually being concrete) is a polymorphic entity to begin with, since it has different concrete representations. So we have to dispatch somewhere and there are different ways to implement it: Calling differently defined methods, checking whether certain properties are defined, or doing the if
... instanceof
thing.
Using methods is quite clean and the right thing to do when it comes handy. But it's not always that practical / flexible, often needs careful planning, and buying into full-blown "trueschool cleanish OO design" can also cause quite an abstraction penalty and lead to over-engineered code.
Checking for properties seems to work out quite well in Three.js, especially for Material
. Given all the options of that class it qualifies as "megamorphic by nature". Now, from what I have learned about modern JS implementations throughout this discussion, the JIT actually runs per structure (or hidden class if you prefer that term). So it can't know whether an existing property has a nonempty value in genereal, but it can know that it must have a value of undefined
in case the property doesn't exist in given structure. This means that it can optimize-out code that depends on the presence of a property and automatically then build a dispatcher for that case. It also means that less code will need to processed, so JITting becomes faster.
Using instanceof can be very practical to check for a certain constructor and make assumption on that basis. However, as many of us may have actually experienced, it can seriously complicate maintenance and making assumptions based on the (most derived) constructor is bad for extensibility. Wise use is limited to "final" classes.
Whereas a function processing Vector types that might get called 100k+ per frame it would be important not to trigger polymorphism,
Whether vectors of different dimensionality are in fact polymorphic is a rather philosophical question. Passing vectors of different dimenionality to the same function will most certainly induce a dispatcher. Whether making their protoypes inherit from another will help in that case is an interesting theoretical question, but I hope the case is rare enough to not really matter in practice.
Considering that
most frameworks try to do things fast; but not really fast and consistently so; they are generally worried about reacting to user input in a way that is perceived as fast; rather than trying to get lots of heavy work done in under 16ms,
the "zeoes story" might actually be worth it. At machine level, 16ms are quite an eternity today, especially on a desktop machine...
I still think a "pay for what you use" policy keeping the memory footprint as low as possible by letting some properties be optional would be a good thing.
All JS engines cache type transitions, so when extension happens before methods are called, reallocation is the worst to worry about. At least in open source JS implementations it's technically the same thing as creating an object that has a superclass.
However, the suggestion may collide with stylistic considerations. I'm closing this thread after being dormant for a long time,
Reading (and referring to) the discussion on commit 91569e4c1277323991029eb1456bfeba42787083, I see Wirth's Law kicking in as the library keeps growing. Luckily, we're not in C, where a dynamic property system would need to be built in order to avoid data structures from bloating up over time - JavaScript actually gives us all we need for (almost) free.
On the philosophy of emptiness and unintuitive specifications
Yes, it makes sense to use
null
for preallocation, to distinguish it from the "property exists on-demand" case.I guess it's quite in line with the intention behind these two values for emptiness. One could say that
undefined
represents something that simply isn't there, whilenull
represents something not in its place.Exactly. Relational databases have a fixed structure, thus everything has its place.
Technically, although quite unintuitive,
"b" in { a: 1, b: undefined }
must givetrue
and afor...in
loop must find"b"
too, so the map entry exists whenever we define a property, regardless of the value we assign - the structure is put in place either way. Assigningundefined
and usingdelete
are two different things - JavaScript is not Lua....
The question becomes: "Does it make sense to preallocate the property?"
On optional properties of model class objects
From a perspective rotated by 180°, we could just allocate
{ a: 1 }
and add.b
later to deliberately avoid preallocation.I really think we should make use of this opportunity more often, especially for model classes with potentially many instances: Frequently checked, preallocated property values will cause more unique memory locations to be read and just needlessly pollute the data caches.
Preallocation of optional properties should be up to the client who actually intends to use a certain feature. In terms of memory efficiency, right now, everyone has to pay everywhere for everything that anyone might eventually use. Once the client decides to mess with an optionally defined property at runtime, the object structure will change exactly once, which does not necessarily imply reallocation (1), and the client can set a value at initialization time to force the potential reallocation to that point.
In fact, once we have a constructor, properties are added piecemail until browsers implement
Object.assign
, that will potentially allow a "bluk add" operation (that is, to emphasize the intent). A Javascript JIT may optimize subsequent assignments likethis.that = ...
andthis.another = ...
, but the problem with relying on such optimizations is usually that the targets that would need them most are the ones least likely to implement them. So "a fixed object structure" does not really exist for objects created by a constructor and efficient construction gives us just another good reason not to add unnecessary properties on the objects in the first place.JavaScript has quite a bloat factor, so it's not a crime to be generally concerned about the memory footprint of objects either. Keep in mind that numbers are at least 8 bytes, any JS property can hold anything - so the type info must also go somewhere.
Only nonoptional properties, ones that will most probably be set to a nonempty value at a later point, should be preallocated and assigned a value of
null
. All optional properties should simply not be defined - especially not on the object itself, as opposed to its prototype. An example of a property that is very likely to be set to a nonempty value is the.parent
property ofObject3D
(which, as a matter of oddness, is currently initialized toundefined
).On default values of properties of model class objects
Properties with a (non-empty) default value are just as optional, as we could simply interpret
undefined
as the default value. This approach might actually be the fastest (except for putting them on every instance, which is bloaty and scales poorly due to cache pollution, as mentioned above) and is flexible enough to allow default values that depend on other properties.The most straightforward way for constant-valued defaults is to set them on the prototype (2). The value will only occupy one memory location for all instances. The access is syntactically transparent, but the data structure remains cache-friendly.
All defaults that will not certainly change their value should go on the prototype, or exist implicitly without any property being defined at all. One example of a property that will certainly change its value is a reference counter, and I'm finding it difficult to come up with a second example.
I am suggesting a "diet" for the data model of the scene graph. Afterwards the classes should look somwhat like e.g.
Footnotes
(1) Dynamic hashtables and array-mapped data structures over-allocate by definition and only cause a reallocation when the number of free slots goes below a certain threshold. Pool allocation is very likely used with other data structures that don't do it by nature.
(2) Surprisingly, prototype lookup is relatively fast. JS implementations specifically optimize that case. Yes it's a little bit slower than finding a property on the object itself, but that fact becomes of mere theoretical value once there can be many instances. Bloaty objects don't scale! However, property lookup is rather slow in general and should be avoided where possible. In particular