Squawks of the Parrot

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

and

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.