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.
On May 12, 2008, at 6:49 PM, Talin 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. Dan
On May 13, 2008, at 18:28, Dan Gohman wrote:> On May 12, 2008, at 6:49 PM, Talin 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.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:> On May 12, 2008, at 6:49 PM, Talin 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.> Dan > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >
On Mon, May 12, 2008 at 9:49 PM, Talin <viridia at gmail.com> 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. >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)