Iterator protocols

This is related to the general question of efficiency of unwinds. I'm mulling over whether to use the Java-style or Python-style iterator protocol for my language. The Python style is to have a special exception (StopIteration) that is thrown when the end of the sequence is reached. The Java style is to have a separate "hasNext" method on the iterator object that says whether or not the sequence is finished.

So the question is, what's the trade-off. In most languages that support exceptions, you tend to think of exceptions as expensive operations that should only be thrown if something truly "exceptional" happens. OTOH, the Java case is also made worse by the fact that a large part of the time you'll be using the more expensive interface dispatching, rather than simple vtable dispatching.

I would imagine that for smaller sequences the Java protocol wins (because of the expense of unwinding), whereas for longer sequences the per-item overhead dominates. The question is, what's the cutoff point likely to be - how expensive is an unwind compared to, say, a regular function call. (I haven't tried to measure it because I'm not yet sure what I am measuring.) I'm just curious if anyone has an opinion on this.

-- Talin

I would imagine that for smaller sequences the Java protocol wins
(because of the expense of unwinding), whereas for longer sequences the
per-item overhead dominates. The question is, what's the cutoff point
likely to be - how expensive is an unwind compared to, say, a regular
function call. (I haven't tried to measure it because I'm not yet sure
what I am measuring.) I'm just curious if anyone has an opinion on this.

I expect unwinding to be much more expensive than an ordinary function call.

Ciao,

Duncan.

How dynamic is your language? Is it possible that the resolution of
the hasNext method could change as the loop executes? If not, it
would be neat to find a way to resolve the hasNext callee once,
before the loop, and then just make a simple call on each iteration.

Dan

I wonder if it would be worthwhile to have a flag on loads to mark them as immutable. A flag from the source language stating "this load never aliases any subsequent store." A majority of loads in functional languages are of this nature. I could see a number of benefits:

• Duplicate loads could be RAUW'd based solely on SSA properties.
• load / store alias analysis could be short-circuited for such loads.
• Codegen could remat such loads under register pressure.
• Vtable lookups through loop-invariant SSA vars could trivially be shown to be themselves loop-invariant.

C++'s predilection for swizzling vtable pointers in constructors and destructors probably prevents it from being a useful facility for vtable lookups though. Short of a necessarily whole-program source-language interprocedural analysis proving safety. Sigh.

— Gordon

Dan Gohman wrote:

  

So the question is, what's the trade-off. In most languages that support
exceptions, you tend to think of exceptions as expensive operations that
should only be thrown if something truly "exceptional" happens. OTOH,
the Java case is also made worse by the fact that a large part of the
time you'll be using the more expensive interface dispatching, rather
than simple vtable dispatching.
    
How dynamic is your language? Is it possible that the resolution of
the hasNext method could change as the loop executes? If not, it
would be neat to find a way to resolve the hasNext callee once,
before the loop, and then just make a simple call on each iteration.
  

That's a good idea, actually - all my vtables are LLVM constants.

Actually, what I am hoping for is a little better than that: In the cases where the compiler can "see" the concrete class of the iterator, and the "hasNext" method is declared final (which it should be), it ought to be able to inline the "hasNext" method directly into the loop code.

However, such cases may end up being rare, so I need to consider the less optimal case.

I really like the idea of the (apparently possible, if uncommon)
implementation of (C++) exceptions that means no overhead at all in
the normal path, but with a somewhat expensive throw.

There's something quite satisfying about exceptions being able to
actually make code faster (since it can get rid of the checks on
return values).

But even with that an expensive throw, exceptions can still be the
fastest way to exit a deep (non-tail) recursion (with no non-trivial
local scope destructors).

And yes, reaching the end of an iterator range does not seem to me
like a good use for exceptions.

YMMV, of course.

So the question is, what's the trade-off. In most languages that support
exceptions, you tend to think of exceptions as expensive operations that
should only be thrown if something truly "exceptional" happens.

Certainly the vast majority of cases, but is it also reasonable to write a
method that will likely or always throw an exception, but cheaper to setup,
unwind and tear-down the exception than to litter a computational expensive
routine with explicit end-condition testing.

OTOH, the Java case is also made worse by the fact that a large part of
the time you'll be using the more expensive interface dispatching,
rather than simple vtable dispatching.

What I've seen is that when runtime compiling: most 'invokeinterface' calls
can
be converted into direct vtable dispatches, specifically when the type of
the
object in question is a class (as opposed to an interface). And in the
remaining
cases, when the type is an interface, the methods tend to be short and
suitable
for inlining. (mileage may vary)

So the question is, what's the trade-off. In most languages that
support exceptions, you tend to think of exceptions as expensive
operations that should only be thrown if something truly
"exceptional" happens. OTOH, the Java case is also made worse by
the fact that a large part of the time you'll be using the more
expensive interface dispatching, rather than simple vtable
dispatching.

How dynamic is your language? Is it possible that the resolution of
the hasNext method could change as the loop executes? If not, it
would be neat to find a way to resolve the hasNext callee once,
before the loop, and then just make a simple call on each iteration.

I wonder if it would be worthwhile to have a flag on loads to mark
them as immutable. A flag from the source language stating "this load
never aliases any subsequent store." A majority of loads in functional
languages are of this nature. I could see a number of benefits:

• Duplicate loads could be RAUW'd based solely on SSA properties.
• load / store alias analysis could be short-circuited for such loads.
• Codegen could remat such loads under register pressure.
• Vtable lookups through loop-invariant SSA vars could trivially be
shown to be themselves loop-invariant.

This is very interesting. If there is a use-case that this sort of thing would strongly benefit, then we could add it. We would want very strongly defined properties though. Saying that no subsequent store aliases the load is probably sufficient.

C++'s predilection for swizzling vtable pointers in constructors and
destructors probably prevents it from being a useful facility for
vtable lookups though. Short of a necessarily whole-program source-
language interprocedural analysis proving safety. Sigh.

Right :frowning: :frowning:

-Chris

Any tight loop that uses a virtual function.
That's interesting for languages where functions are virtual by default.
(I think OO language designers tend to avoid nonvirtual functions in
general.)

Note that functional language tend to have the moral equivalent of
virtual functions, too, but I don't know how strong the effect would be.

Regards,
Jo

This isn't safe in C++ for example.

Also, the proposed definition wouldn't permit hoisting one of these loads out of a loop.

-Chris

Right, so that's not really ideal. The reason for the semantic I described is to avoid doing something obviously stupid like promoting the load above the store here:

     word *foo = gcalloc(1);
     foo[0] = f();
     // foo.bar is now initialized and will never be changed.
     word x = __immutable_load(foo[0]);

Which is approximately the obvious translation of x = { foo_bar = f () }.foo_bar in Ocaml, for instance. If instead foo got a new SSA name after it was initialized, then the ordering restriction could be eliminated:

     word *tmp = gcalloc(1);
     tmp[0] = f();
     word *foo = initialized(tmp);
     word x = __immutable_load(foo[0]);

A crude sledgehammer to accomplish that would be to provide a "Foo constructor" function (word *foo = make_block(f()):wink: and not provide the body until link time in order to prevent inlining. Maybe if it proves useful an ‘SSA rename’ intrinsic (slotted in at 'initialized' above) could be added.

I expect this would generate recursive simplifications where the language permits such (as C++ doesn't). But Java/.NET string and array lengths are candidates, and it might also apply to final or readonly fields in Java or C#; I don't remember whether those suffer from the same problems as C++ initializers.

But I think I'd have to rearchitect my ocaml compiler to handle an earlier IR in order to take advantage of this property, and PR1917 would have to be fixed as well, so I probably won't contribute here any time soon. :frowning:

Now that I think about it, there's a related problem when the object is disposed:

     word x = __immutable_load(foo[0]);
     free(foo);

Can't sink the load below the free. So I think the semantics required would probably cripple this for any language without GC.

— Gordon