July 14, 2005

WWIT: Making the destination exist

Here's one that caused much consternation at times. I ruled that the destination of an assignment must always exist. That is, code that looks like:

add Pdest, Pleft, Pright

needs to have a real Pdest -- that is, it's an in parameter, not an out parameter.

Some people hate this. "Why can't my add function create the destination?" they cry.

Well, because in many cases the destination already exists. Creating a new PMC unconditionally means generating a lot of temporary garbage. More temps means more garbage for the garbage collector, more temps needed from the allocator, and more time spent in bookkeeping with these temps.

Consider, if you will, these two scenarios:

a = b + c


d = e + f + g

where we're only interested in the "e + f" part.

In the first case, the destination already exists. (We can't just arbitrarily whack destination name/variable bindings, because the destination might be active data. That warrants a What The Heck Is post of its own. Active data has been the bane of many optimization strategies, but it's also phenomenally useful, and more importantly an integral part of Perl so there's no ignoring it) There's no need to create a temp for the "b + c" addition, as we already have a spot to stick the result -- the PMC for a. There's a possibility in the first case that the destination PMC is of an inappropriate type, in which case a temp PMC needs to be created and handed to the destination PMC for ultimate assignment/value snagging.

In the second case, a destination doesn't exist. Since this is known at compile time, though, the compiler can just emit code to create a temp of the appropriate type and we're fine there, or emit a generic Undef if the compiler doesn't know. (Depending on the language it usually will know the appropriate type to emit)

So we've got three possibilities -- destination exists and is OK, destination exists and isn't OK, and destination doesn't exist. In the second and third cases we have to create an intermediate PMC, and in the first case we don't. If, on the other hand, we had the add op unconditionally create PMCs, then the first case creates a temp PMC which is then discarded. More garbage than we need.

Things get more interesting with extended expressions, like:

a = b + c + d + e + f

If add creates a temp, then we have created 4 temp PMCs. (for the b+c, that result + d, that result + e, and that result + f) On the other hand, if we make the destination exist, we need exactly two temporary PMCs. In fact, we need only two temp PMCs no matter how complex the expression is, as long as there are no function or method calls in it. That's a lot less garbage, especially if you're in a loop.

You may be thinking "two temp PMCs? How, exactly?" That's easy. There's a temp needed for the b+c part, and a second for the result + d. The first temp can be reused again to add e in, then the destination to add in f.

"What about continuations" I hear you cry. (Though, I suppose, not necessarily about this specifically) "They could happen anywhere!" No, they can't. They can only happen explicitly, or inside functions or method calls. Parrot specifically forbids continuations to escape from within vtable functions so there's no way our expression there can be resumed in the middle, which means that the compiler's free to reuse its temps. Consider, for example, the following:

foreach a (@foo) {

b = b + c * a


Where we're iterating through the @foo array. No function or method calls, which means there's no way that continuations could be taken. If there are a thousand elements in @foo, if we have our math ops create temps, we've created two thousand temps. If we have the destination exist, we have to create... two. Even if we're Really Clever and explicitly free up the created temps, that's still two thousand calls to the allocator and two thousand calls to the free routine, instead of two to each.

So there you go. If the destination has to exist it means that, worst case, performance is no worse than if binary ops create their own PMCs, and in some case significantly (orders of magnitude) better.

Posted by Dan at July 14, 2005 05:24 PM | TrackBack (0)

I'm pretty sure there's a typo in the "You may be thinking" paragraph: "There's a temp needed for the a+b part, and a second for the result + c." should read "b+c" and "+ d", no?

Even with that, I don't understand, though. Why is a second temp needed for the + d part?

Posted by: Todd Larason at July 15, 2005 11:25 PM

D'oh! Yeah, you're right. Fixed.

Posted by: Dan at July 16, 2005 11:56 AM

As for the "why the second temp" question, consider the equation:

a = b + c + d

that breaks down into:

add temp1, b, c
add temp2, temp1, d
assign a, temp2

if add creates temps.

Posted by: Dan at July 16, 2005 12:09 PM

Is there any merit for static analysis on behalf of parrot (as opposed to the language compiler) to make

a = b + c + d + e


a = b
a += c
a += d
a += e

or equiv, for known PMCs where it's safe?

Posted by: Yuval Kogman at August 23, 2005 05:48 PM

Sure, you could do that. You could even cut out the first assignment and make it a=b+c. That'd be somewhat more efficient, as you'd skip the temp creation, which is a good thing. Less pressure on the resource allocation system and less garbage for the garbage collector to deal with.

Posted by: Dan at August 23, 2005 08:45 PM