A stab at explaining Spur

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

>For the paywall-free version:
>https://hal.inria.fr/hal-01152610

>Stephan

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