[Vm-dev] A stab at explaining Spur

[Clément Bera]

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 at 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-barrier-for-efficient-support-of-live-object-oriented-programming <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
>
>
>
>
>
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20150813/b5243700/attachment-0001.htm