On 12/08/15 05:23, Chris Muller wrote:
[1] -- A Partial Read Barrier for Efficient Support of Live Object-oriented Programming http://conf.researchr.org/event/ismm-2015/ismm-2015-papers-a-partial-read-ba... http://conf.researchr.org/event/ismm-2015/ismm-2015-papers-a-partial-read-barrier-for-efficient-support-of-live-object-oriented-programming
For the paywall-free version: https://hal.inria.fr/hal-01152610 https://hal.inria.fr/hal-01152610
Stephan
I’m going to take a stab at explaining what I just read (as far as I read it).
You’re an instance of Rectangle. You have an ivar with a Point in it. The point has ivars x and y. This great because you can get the values of the instance of Point’s x and y when you need to. Funny thing, though, Point was just recompiled to add methods or change ivars. Now all the instances, including yours, are junk. Not to worry, the system has a plan and two tools to deal with it: two primitives fronted by #allInstances and #become:. The system will find all the instances of Point with #allInstances. It will then find each and apply #become: to switch the old version with the new.
In Rectangle we get a new number in our ivar slot for the Point instance. And things are caught up. But how does that actually work? The #become: part? I think that’s the story of three approaches to the problem with the last one being Spur.
The first way is the way used by Cincom’s VisualWorks now. It’s a two step process. To get from Rectangle to the value of x in an instance of Point we need to make two object pointer calls. The first goes to the head object of the class Point. A second goes from there to the “body” which is a basket of slots, which in our case includes x an y. The beauty of this is that it gives #become: a focal point. a become: b at the location of the header object and you’ve neatly swapped the address from Rectangle’s ivar to where the x and y values are.
There’s a problem. There’s trouble in paradise. We are not happy. It could be faster. We don’t want two steps. We don’t want a bridge between Rectangle and the “body” of values with the header object as the cornerstone. We want one step, not two. That’s faster. To do that, the first thing we do is fuse the header object with the “body”. They are no longer in separate places. One word for the header and the next word is slot 1, which is for us x. The next word will have y.
The system is faster, but we have a problem. Where are all those references we need to renumber? We no longer have a neat nexus in the header object that #become: can use. No problem, we’ll sweep all of memory (aka “the heap”) to find them again. We’re getting such a boost from one step instead of two that we can afford to brute force the problem with a sweep.
And we’re happy. For a while. And then we’re not. This does not scale. We find that the larger the memory gets, then the closer we get to where sweeping the heap becomes more expensive than the gains we’re getting. There’s a plateau point, a location on the graph beyond which the memory sweep is so costly it’s eating our gains.
What to do? We want the speed of the one-step process, but we want it to scale. We create a solution called Spur.
The salient passage here in the paper is:
"This paper describes the design and implementation of efficient schema migration using direct pointers [That’s the “one step” business I’ve been talking about above], which consists mainly in hiding the cost of checking for forwarding pointers behind other checking operations that the system performs as part of its normal processing.”
Did you get that part? Let’s repeat it:
"hiding the cost of checking for forwarding pointers behind other checking operations that the system performs as part of its normal processing.”
Normal processing. We want to be prepared. We want to do as much as we can in anticipation of the requirement that slows things down when the memory gets big. Anticipate. Do as much as you can beforehand.
A little vague? OK, I’ll try again. Read this:
"Become is therefore implemented lazily; copies of the pair of objects are created, and each original is forwarded to the matching copy; the forwarding pointer is followed when the object is encountered.”
I don’t understand all of that, but I did catch “lazily”. In the first of our three systems, the system is preparing all possible avenues. In Spur, I think, it is only opening avenues that need to be opened when they need to be opened. They are being opened “lazily.”
There seems to me a commonality to Spur, Cog and Sista. Don’t set the table for ten people. Wait to see how many show up. Don’t do unnecessary work. I think that’s what “lazily” means. These three also like to pay attention to what is happening over and over again and cache it for speed.
One last thing. It seems to me the reason Spur and 64-bit are related has to do with fusing the header object with the “body” object. By definition that requires a new object format, does it not?
That’s as far as I could make out. I’m sort of a big picture guy, so the details of “forwarding objects” and “partial read barriers” doesn’t interest me all that much. I like it more as a story of three versions with the last one being Spur.
FWIW, Chris
Hello,
I'm glad so many people read the paper and enjoyed it :-).
Firstly I'd like to say the implementation is mainly Eliot's work, I am a co-author because I was the guy telling Eliot every week 'Write something about Spur and the partial read barrier', and in the end, Eliot wrote a draft, I improved it so it looks like a paper, and Eliot made a few more reviews on top to fix the details.
I think you understood well the point. Just one detail: *Point was just recompiled to add methods or change ivars. Now all the instances, including yours, are junk. *
In fact the problem happens only when an inst var is added / removed. The
size allocated in memory for each instance is not correct any more. Adding / Removing methods is fine as you just change the method dictionary of the class and you don't need to use become: and allInstances.
I heard recently that the implementation used by Cincom Smalltalk, splitting the object in 2 (header + fields), is also used in Pypy and the Dart VM as Python and Dart allow the user to add instance variables to objects at runtime which leads to the same problem.
On the other hand, the one memory chunk objects are used in the JVM and in Self.
The forwarding object implementation is interesting because theoretically one would need to check each time it reads an object if it's a forwarding object or not, whereas this computation in practice only happen on uncommon cases.
*One last thing. It seems to me the reason Spur and 64-bit are related has to do with fusing the header object with the “body” object. By definition that requires a new object format, does it not? * In fact Spur inherits from the Squeak VM which already had a single memory chunk for the header and the body of objects. The problem for the previous Cog versions is that on large heaps the become primitive was too slow.
I really like your summary: *Don’t set the table for ten people. Wait to see how many show up.* It also fits very well the implementation of the Context to Stack mapping too.
Best,
Clement
2015-08-13 3:17 GMT+02:00 Chris Cunnington brasspen@gmail.com:
On 12/08/15 05:23, Chris Muller wrote:
- [1] -- A Partial Read Barrier for Efficient Support of Live
*>* Object-oriented Programming *>* http://conf.researchr.org/event/ismm-2015/ismm-2015-papers-a-partial-read-ba... http://conf.researchr.org/event/ismm-2015/ismm-2015-papers-a-partial-read-barrier-for-efficient-support-of-live-object-oriented-programming
For the paywall-free version: https://hal.inria.fr/hal-01152610
Stephan
I’m going to take a stab at explaining what I just read (as far as I read it).
You’re an instance of Rectangle. You have an ivar with a Point in it. The point has ivars x and y. This great because you can get the values of the instance of Point’s x and y when you need to. Funny thing, though, Point was just recompiled to add methods or change ivars. Now all the instances, including yours, are junk. Not to worry, the system has a plan and two tools to deal with it: two primitives fronted by #allInstances and #become:. The system will find all the instances of Point with #allInstances. It will then find each and apply #become: to switch the old version with the new.
In Rectangle we get a new number in our ivar slot for the Point instance. And things are caught up. But how does that actually work? The #become: part? I think that’s the story of three approaches to the problem with the last one being Spur.
The first way is the way used by Cincom’s VisualWorks now. It’s a two step process. To get from Rectangle to the value of x in an instance of Point we need to make two object pointer calls. The first goes to the head object of the class Point. A second goes from there to the “body” which is a basket of slots, which in our case includes x an y. The beauty of this is that it gives #become: a focal point. a become: b at the location of the header object and you’ve neatly swapped the address from Rectangle’s ivar to where the x and y values are.
There’s a problem. There’s trouble in paradise. We are not happy. It could be faster. We don’t want two steps. We don’t want a bridge between Rectangle and the “body” of values with the header object as the cornerstone. We want one step, not two. That’s faster. To do that, the first thing we do is fuse the header object with the “body”. They are no longer in separate places. One word for the header and the next word is slot 1, which is for us x. The next word will have y.
The system is faster, but we have a problem. Where are all those references we need to renumber? We no longer have a neat nexus in the header object that #become: can use. No problem, we’ll sweep all of memory (aka “the heap”) to find them again. We’re getting such a boost from one step instead of two that we can afford to brute force the problem with a sweep.
And we’re happy. For a while. And then we’re not. This does not scale. We find that the larger the memory gets, then the closer we get to where sweeping the heap becomes more expensive than the gains we’re getting. There’s a plateau point, a location on the graph beyond which the memory sweep is so costly it’s eating our gains.
What to do? We want the speed of the one-step process, but we want it to scale. We create a solution called Spur.
The salient passage here in the paper is:
"This paper describes the design and implementation of efficient schema migration using direct pointers [That’s the “one step” business I’ve been talking about above], which consists mainly in hiding the cost of checking for forwarding pointers behind other checking operations that the system performs as part of its normal processing.”
Did you get that part? Let’s repeat it:
"hiding the cost of checking for forwarding pointers behind other checking operations that the system performs as part of its normal processing.”
Normal processing. We want to be prepared. We want to do as much as we can in anticipation of the requirement that slows things down when the memory gets big. Anticipate. Do as much as you can beforehand.
A little vague? OK, I’ll try again. Read this:
"Become is therefore implemented lazily; copies of the pair of objects are created, and each original is forwarded to the matching copy; the forwarding pointer is followed when the object is encountered.”
I don’t understand all of that, but I did catch “lazily”. In the first of our three systems, the system is preparing all possible avenues. In Spur, I think, it is only opening avenues that need to be opened when they need to be opened. They are being opened “lazily.”
There seems to me a commonality to Spur, Cog and Sista. Don’t set the table for ten people. Wait to see how many show up. Don’t do unnecessary work. I think that’s what “lazily” means. These three also like to pay attention to what is happening over and over again and cache it for speed.
One last thing. It seems to me the reason Spur and 64-bit are related has to do with fusing the header object with the “body” object. By definition that requires a new object format, does it not?
That’s as far as I could make out. I’m sort of a big picture guy, so the details of “forwarding objects” and “partial read barriers” doesn’t interest me all that much. I like it more as a story of three versions with the last one being Spur.
FWIW, Chris
On Thu, Aug 13, 2015 at 10:19:35AM +0200, Cl??ment Bera wrote:
Hello,
I'm glad so many people read the paper and enjoyed it :-).
Firstly I'd like to say the implementation is mainly Eliot's work, I am a co-author because I was the guy telling Eliot every week 'Write something about Spur and the partial read barrier', and in the end, Eliot wrote a draft, I improved it so it looks like a paper, and Eliot made a few more reviews on top to fix the details.
I also enjoyed reading the paper, and I learned a lot from it. You and Eliot did a really good job explaining the design choices, as well as how the mechanism works in practice. I think that the Spur object model is a very nice design, and this is explained well in the paper also.
Thanks!
Dave
On 12/08/15 05:23, Chris Muller wrote:
- [1] -- A Partial Read Barrier for Efficient Support of Live
*>* Object-oriented Programming *>* http://conf.researchr.org/event/ismm-2015/ismm-2015-papers-a-partial-read-ba... http://conf.researchr.org/event/ismm-2015/ismm-2015-papers-a-partial-read-barrier-for-efficient-support-of-live-object-oriented-programming
For the paywall-free version: https://hal.inria.fr/hal-01152610
On Thu, Aug 13, 2015 at 1:19 AM, Clément Bera bera.clement@gmail.com wrote:
I heard recently that the implementation used by Cincom Smalltalk, splitting the object in 2 (header + fields), is also used in Pypy and the Dart VM as Python and Dart allow the user to add instance variables to objects at runtime which leads to the same problem.
Objects are not split in the Dart VM, and it does not support adding instance variables or otherwise changing classes at runtime. Objects have a single-word header with a class index, size information and GC bits. Identity hashes are not often used in Dart, so they are kept in a side table.
2015-08-14 4:29 GMT+02:00 Ryan Macnak rmacnak@gmail.com:
On Thu, Aug 13, 2015 at 1:19 AM, Clément Bera bera.clement@gmail.com wrote:
I heard recently that the implementation used by Cincom Smalltalk, splitting the object in 2 (header + fields), is also used in Pypy and the Dart VM as Python and Dart allow the user to add instance variables to objects at runtime which leads to the same problem.
Objects are not split in the Dart VM, and it does not support adding instance variables or otherwise changing classes at runtime. Objects have a single-word header with a class index, size information and GC bits. Identity hashes are not often used in Dart, so they are kept in a side table.
And I put "accept" on a paper that was claiming that... Damned. Any clue about Pypy ?
Greetings,
I would think that another option is to replace all the methods in the old class with "updater" methods and flush the method cache(s). [old selectors, fixup method(s)].
The new version of the class has a new class index.
At any send to an old instance, the updater has access to the calling context and can do the forward to the new intance and re-send the method.
Usual GC cleanup does the rest.
Why did you choose to avoid this strategy? (or am I just misunderstanding?)
Thanks much, -KenD
Hi Ken,
Sent from my iPhone
On Aug 13, 2015, at 4:56 PM, Ken.Dickey Ken.Dickey@whidbey.com wrote:
Greetings,
I would think that another option is to replace all the methods in the old class with "updater" methods and flush the method cache(s). [old selectors, fixup method(s)].
The new version of the class has a new class index.
At any send to an old instance, the updater has access to the calling context and can do the forward to the new intance and re-send the method.
Usual GC cleanup does the rest.
Why did you choose to avoid this strategy? (or am I just misunderstanding?)
Yes, this is a viable strategy (Am I right in thinking GemStone does this?) and a very good question. My reasons were two-fold. One, I started from the object representation, wanting the commonality of a single header format between 32- & 64-bits so I thought of the solution to become in that lower-level context. Two, I wanted as small a delta from the current system as possible to ease adoption and bootstrap. The approach above rally needs a completely different class builder, and that's a major rewrite of a lot of Smalltalk code.
Perhaps there's a third reason; lazy forwarding was a little crazy but I thought it could work and it had never been done. So I was curious.
But there's no reason why the class-level lazy update approach couldn't be explored. That's why I'm interested in a project to measure accurately the cost of object table indirection vs lazy forwarding vs no forwarding/slow become. If lazy forwarding's additional costs are not high (one benchmark slows down by ~ 10%) then re architecting the class builder perhaps isn't as compelling. But if they're really high then sure, try alternatives.
Thanks much, -KenD
Hi Clément:
On 14 Aug 2015, at 08:41, Clément Bera bera.clement@gmail.com wrote:
2015-08-14 4:29 GMT+02:00 Ryan Macnak rmacnak@gmail.com:
On Thu, Aug 13, 2015 at 1:19 AM, Clément Bera bera.clement@gmail.com wrote: I heard recently that the implementation used by Cincom Smalltalk, splitting the object in 2 (header + fields), is also used in Pypy and the Dart VM as Python and Dart allow the user to add instance variables to objects at runtime which leads to the same problem.
Objects are not split in the Dart VM, and it does not support adding instance variables or otherwise changing classes at runtime. Objects have a single-word header with a class index, size information and GC bits. Identity hashes are not often used in Dart, so they are kept in a side table.
And I put "accept" on a paper that was claiming that... Damned. Any clue about Pypy ?
PyPy uses maps ala Self, but objects are not ‘split’. It is more or less the same as with V8, which also uses maps aka hidden classes.
Best regards Stefan
Hello Stefan, Ryan and all,
I checked the paper where I read it (unfortunately it was rejected) and the exact sentence was:
*In some implementations (e.g. Dart [22] and PyPy [3]), object header and attribute storage can be separated, so the attribute storage can be relocated in order to grow. *
*[3]C. F. Bolz. Efficiently implementing objects with maps http://morepypy.blogspot.fr/2010/11/efficiently-implementing-python-objects.html, 2010. [22]F. Schneider. Compiling dart to efficient machine code https://www.dartlang.org/slides/2013/04/compiling-dart-to-efficient-machine-code.pdf, 2012.*
When I read F. Boltz. post, it looks like to me that in Pypy each instance of a class has a pointer to its map and its storage. The storage seems to be at a different location than the object's header and holds the instance variable values. To me it sounds very much like the object is 'split' to be able to grow the storage if a new instance variable is added for a specific instance. Accessing an object instance variable requires an extra indirection through the storage pointer. Is there something I miss there ? It looks like the paper we wrote with Eliot could definitely apply there in order to speed up instance variable access by removing the indirection to the storage.
In the talk compiling dart to efficient machine code, one section deals about Javascript and V8. Objects are described in V8 (slide 29) as having a pointer to their Map, their properties and their elements, which to me sounds similar to Cincom Smalltalk design (the object header is separated from the value of the instance variables). However the talk then discusses the Dart implementation and it's not the case there. I guess I got confused as the talk is about Dart but this part of the talk is about Javascript.
I am waiting for other people comments but to me it looks like the memory representation where the object's header is separated from the the object's fields is used in Javascript V8 and Pypy, as explained in the 2 references, and that they could benefit from our implementation.
2015-08-14 9:51 GMT+02:00 Stefan Marr smalltalk@stefan-marr.de:
Hi Clément:
On 14 Aug 2015, at 08:41, Clément Bera bera.clement@gmail.com wrote:
2015-08-14 4:29 GMT+02:00 Ryan Macnak rmacnak@gmail.com:
On Thu, Aug 13, 2015 at 1:19 AM, Clément Bera bera.clement@gmail.com
wrote:
I heard recently that the implementation used by Cincom Smalltalk,
splitting the object in 2 (header + fields), is also used in Pypy and the Dart VM as Python and Dart allow the user to add instance variables to objects at runtime which leads to the same problem.
Objects are not split in the Dart VM, and it does not support adding
instance variables or otherwise changing classes at runtime. Objects have a single-word header with a class index, size information and GC bits. Identity hashes are not often used in Dart, so they are kept in a side table.
And I put "accept" on a paper that was claiming that... Damned. Any clue
about Pypy ?
PyPy uses maps ala Self, but objects are not ‘split’. It is more or less the same as with V8, which also uses maps aka hidden classes.
Best regards Stefan
-- Stefan Marr Johannes Kepler Universität Linz http://stefan-marr.de/research/
Hi Clément:
On 14 Aug 2015, at 10:53, Clément Bera bera.clement@gmail.com wrote:
In some implementations (e.g. Dart [22] and PyPy [3]), object header and attribute storage can be separated, so the attribute storage can be relocated in order to grow. [3]C. F. Bolz. Efficiently implementing objects with maps, 2010. [22]F. Schneider. Compiling dart to efficient machine code, 2012.
After a brief discussion with Carl Friedrich, this blog post is slightly outdated. Each object is allocated with 5 fields. I think the last one can be used, if needed, to refer to an extra extension/storage array. So, objects are not split in the sense you got in mind. But they can have two parts. This is pretty common the Truffle Object Model uses the same strategy, as do I in my SOM implementations. [For Smalltalks, the strategy is also nice, because it gives you fast, object-table like become, without any need for barriers.]
Main drawback of the approach is that objects have a rather large size. But so far that was neither for PyPy nor Truffle a real issue.
For details, see https://bitbucket.org/pypy/pypy/src/7089cedc919340a0c07f78cc952d5760146f7d86... (_make_subclass_size_n (only ever used for n==5))
A little more tangible: https://github.com/smarr/RTruffleSOM/blob/master/src/som/vmobjects/object.py
When I read F. Boltz. post, it looks like to me that in Pypy each instance of a class has a pointer to its map and its storage. The storage seems to be at a different location than the object's header and holds the instance variable values. To me it sounds very much like the object is 'split' to be able to grow the storage if a new instance variable is added for a specific instance. Accessing an object instance variable requires an extra indirection through the storage pointer. Is there something I miss there ? It looks like the paper we wrote with Eliot could definitely apply there in order to speed up instance variable access by removing the indirection to the storage.
So, this is only true for fields that don’t fit into the slots that are directly following the ‘header’.
I am waiting for other people comments but to me it looks like the memory representation where the object’s header is separated from the the object's fields is used in Javascript V8 and Pypy, as explained in the 2 references, and that they could benefit from our implementation.
I don’t know about V8 for sure, but for PyPy (and Truffle, and SOM), I would not characterize it this way. The extension array is strictly optional for larger objects. From a conceptual point of view it is not designed as being split from the header. One could reduce the number of inlined fields to zero, and only keep the pointer to the storage array, but, this has a significant cost on my experience. (No, I don’t have numbers handy, but someone with an interest to easily do it by adjusting the min-max field number in PyPy).
Best regards Stefan
Ok I think I understand now. Thank you for the explanation. The approach is different. I believe V8 has the same design than you have based on the talk I referenced.
There are pros and cons for both techniques.
2015-08-14 14:59 GMT+02:00 Stefan Marr smalltalk@stefan-marr.de:
Hi Clément:
On 14 Aug 2015, at 10:53, Clément Bera bera.clement@gmail.com wrote:
In some implementations (e.g. Dart [22] and PyPy [3]), object header and
attribute storage can be separated, so the attribute storage can be relocated in order to grow.
[3]C. F. Bolz. Efficiently implementing objects with maps, 2010. [22]F. Schneider. Compiling dart to efficient machine code, 2012.
After a brief discussion with Carl Friedrich, this blog post is slightly outdated. Each object is allocated with 5 fields. I think the last one can be used, if needed, to refer to an extra extension/storage array. So, objects are not split in the sense you got in mind. But they can have two parts. This is pretty common the Truffle Object Model uses the same strategy, as do I in my SOM implementations. [For Smalltalks, the strategy is also nice, because it gives you fast, object-table like become, without any need for barriers.]
Main drawback of the approach is that objects have a rather large size. But so far that was neither for PyPy nor Truffle a real issue.
For details, see https://bitbucket.org/pypy/pypy/src/7089cedc919340a0c07f78cc952d5760146f7d86... (_make_subclass_size_n (only ever used for n==5))
A little more tangible:
https://github.com/smarr/RTruffleSOM/blob/master/src/som/vmobjects/object.py
When I read F. Boltz. post, it looks like to me that in Pypy each
instance of a class has a pointer to its map and its storage. The storage seems to be at a different location than the object's header and holds the instance variable values. To me it sounds very much like the object is 'split' to be able to grow the storage if a new instance variable is added for a specific instance. Accessing an object instance variable requires an extra indirection through the storage pointer. Is there something I miss there ? It looks like the paper we wrote with Eliot could definitely apply there in order to speed up instance variable access by removing the indirection to the storage.
So, this is only true for fields that don’t fit into the slots that are directly following the ‘header’.
I am waiting for other people comments but to me it looks like the
memory representation where the object’s header is separated from the the object's fields is used in Javascript V8 and Pypy, as explained in the 2 references, and that they could benefit from our implementation.
I don’t know about V8 for sure, but for PyPy (and Truffle, and SOM), I would not characterize it this way. The extension array is strictly optional for larger objects. From a conceptual point of view it is not designed as being split from the header. One could reduce the number of inlined fields to zero, and only keep the pointer to the storage array, but, this has a significant cost on my experience. (No, I don’t have numbers handy, but someone with an interest to easily do it by adjusting the min-max field number in PyPy).
Best regards Stefan
-- Stefan Marr Johannes Kepler Universität Linz http://stefan-marr.de/research/
On Fri, Aug 14, 2015 at 1:53 AM, Clément Bera bera.clement@gmail.com wrote:
Hello Stefan, Ryan and all,
I checked the paper where I read it (unfortunately it was rejected) and the exact sentence was:
*In some implementations (e.g. Dart [22] and PyPy [3]), object header and attribute storage can be separated, so the attribute storage can be relocated in order to grow. *
*[3]C. F. Bolz. Efficiently implementing objects with maps http://morepypy.blogspot.fr/2010/11/efficiently-implementing-python-objects.html, 2010. [22]F. Schneider. Compiling dart to efficient machine code https://www.dartlang.org/slides/2013/04/compiling-dart-to-efficient-machine-code.pdf, 2012.*
When I read F. Boltz. post, it looks like to me that in Pypy each instance of a class has a pointer to its map and its storage. The storage seems to be at a different location than the object's header and holds the instance variable values. To me it sounds very much like the object is 'split' to be able to grow the storage if a new instance variable is added for a specific instance. Accessing an object instance variable requires an extra indirection through the storage pointer. Is there something I miss there ? It looks like the paper we wrote with Eliot could definitely apply there in order to speed up instance variable access by removing the indirection to the storage.
In the talk compiling dart to efficient machine code, one section deals about Javascript and V8. Objects are described in V8 (slide 29) as having a pointer to their Map, their properties and their elements, which to me sounds similar to Cincom Smalltalk design (the object header is separated from the value of the instance variables). However the talk then discusses the Dart implementation and it's not the case there. I guess I got confused as the talk is about Dart but this part of the talk is about Javascript.
The split in V8 isn't between an object's header and its properties. It is between the header + the fast properties the hidden-class machinery could figure out ahead of allocation and the slow properties it could not. For instance, if I write well-behaved code like
function Point(x, y) { this.x = x; this.y = y; }
var p = new Point(3, 4);
p would in one block have a reference to its hidden-class, the properties 'x' and 'y', a bit of speculative space for properties that might be added later, and space to hang a properties overflow array. Access to x or y is a simple direct load and we're happy.
However, if I start treating objects like dictionaries as Javascript allows, and later I do,
p.someNewIdentifier = 5;
enough times or,
p["not an identifier"] = 6;
the new properties go into the overflow array, and they are more costly to access.
The actual mechanics are bit more complicated than this depending on the property name and value and the size of the object. Adding a function property may create a new hidden-class but leave the object's layout unchanged. Adding a property whose name isn't an identifier or too many properties may transition the object to dictionary-mode, where all the properties are indirect. Adding a property whose name is an identifier may try to use some of the left-over inline slots first and try give objects that add the same properties the same hidden class. So if something like
var p = new Point(3, 4); p.z = 6;
happens often, all these objects share a hidden-class and we reduce polymorphism.
If I do, 'delete p.x;' the slot where x was is filled in with a special value indicating the property no longer exists ('the hole').
The Spur model might be interesting in the Javascript context if it is used to avoid the memory overhead of allocating with extra space to deal with overflow.
Hi Ryan,
just one small thing to add to your description...
On Fri, Aug 14, 2015 at 6:43 PM, Ryan Macnak rmacnak@gmail.com wrote:
On Fri, Aug 14, 2015 at 1:53 AM, Clément Bera bera.clement@gmail.com wrote:
Hello Stefan, Ryan and all,
I checked the paper where I read it (unfortunately it was rejected) and the exact sentence was:
*In some implementations (e.g. Dart [22] and PyPy [3]), object header and attribute storage can be separated, so the attribute storage can be relocated in order to grow. *
*[3]C. F. Bolz. Efficiently implementing objects with maps http://morepypy.blogspot.fr/2010/11/efficiently-implementing-python-objects.html, 2010. [22]F. Schneider. Compiling dart to efficient machine code https://www.dartlang.org/slides/2013/04/compiling-dart-to-efficient-machine-code.pdf, 2012.*
When I read F. Boltz. post, it looks like to me that in Pypy each instance of a class has a pointer to its map and its storage. The storage seems to be at a different location than the object's header and holds the instance variable values. To me it sounds very much like the object is 'split' to be able to grow the storage if a new instance variable is added for a specific instance. Accessing an object instance variable requires an extra indirection through the storage pointer. Is there something I miss there ? It looks like the paper we wrote with Eliot could definitely apply there in order to speed up instance variable access by removing the indirection to the storage.
In the talk compiling dart to efficient machine code, one section deals about Javascript and V8. Objects are described in V8 (slide 29) as having a pointer to their Map, their properties and their elements, which to me sounds similar to Cincom Smalltalk design (the object header is separated from the value of the instance variables). However the talk then discusses the Dart implementation and it's not the case there. I guess I got confused as the talk is about Dart but this part of the talk is about Javascript.
The split in V8 isn't between an object's header and its properties. It is between the header + the fast properties the hidden-class machinery could figure out ahead of allocation and the slow properties it could not.
Talking with members of the V8 team at ISMM I was told that V8 also has a split between an array's header and its elements. So at least for arrays there is always an indirection.
For instance, if I write well-behaved code like
function Point(x, y) { this.x = x; this.y = y; }
var p = new Point(3, 4);
p would in one block have a reference to its hidden-class, the properties 'x' and 'y', a bit of speculative space for properties that might be added later, and space to hang a properties overflow array. Access to x or y is a simple direct load and we're happy.
However, if I start treating objects like dictionaries as Javascript allows, and later I do,
p.someNewIdentifier = 5;
enough times or,
p["not an identifier"] = 6;
the new properties go into the overflow array, and they are more costly to access.
The actual mechanics are bit more complicated than this depending on the property name and value and the size of the object. Adding a function property may create a new hidden-class but leave the object's layout unchanged. Adding a property whose name isn't an identifier or too many properties may transition the object to dictionary-mode, where all the properties are indirect. Adding a property whose name is an identifier may try to use some of the left-over inline slots first and try give objects that add the same properties the same hidden class. So if something like
var p = new Point(3, 4); p.z = 6;
happens often, all these objects share a hidden-class and we reduce polymorphism.
If I do, 'delete p.x;' the slot where x was is filled in with a special value indicating the property no longer exists ('the hole').
The Spur model might be interesting in the Javascript context if it is used to avoid the memory overhead of allocating with extra space to deal with overflow.
vm-dev@lists.squeakfoundation.org
-
Chris Cunnington -
Clément Bera -
David T. Lewis -
Eliot Miranda -
Ken.Dickey -
Ryan Macnak -
Stefan Marr