Hi Duncan, Hi Bjarke, Duncan Sands wrote:> Take a look at libunwind (http://www.hpl.hp.com/research/linux/libunwind/). > Another possibility, very close you yours and currently used by the vmkit > project, is to modify all functions so they return two values, the usual > return value and an additional boolean value indicating whether an exception > was thrown during the call or not. Callers then branch to an appropriate > place based on this value. Thus there is no special stack unwinding, it > is just functions returning. This adds some distributed overhead, but > unwinding is fast. You can always return something more complicated than > a boolean of course. >That's correct. Although, to make things clear, I'm not using the multiple return value features of LLVM. The signature of functions only return one value. If an exception happens, the boolean value is stored in a thread local specific variable. But conceptually, this pretty much is the same than returning two values.> The vmkit experience is that unwinding using their method is a lot faster > than using the dwarf unwinder. I don't know if the distributed overhead > is noticeable or not. >It's *hardly* noticeable. If your language/runtime throws a lot of exceptions, that's the way to go currently (there are other sophisticated techniques, but much more complex). Dwarf is great if your language/runtime basically never throws exceptions. I can't give you an accurate measure of the real cost of Dwarf on Java applications because, unfortunately, libgcc did not optimize its dwarf info lookup on dynamically registered frames. It's doing a linear search of the info, and that takes *a lot* of time. Nicolas
Nicolas Geoffray wrote:> It's *hardly* noticeable. If your language/runtime throws a lot of > exceptions, that's the way to go currently (there are other > sophisticated techniques, but much more complex). Dwarf is great if your > language/runtime basically never throws exceptions. I can't give you an > accurate measure of the real cost of Dwarf on Java applications because, > unfortunately, libgcc did not optimize its dwarf info lookup on > dynamically registered frames. It's doing a linear search of the info, > and that takes *a lot* of time.gcj uses DWARF unwinder data, and the overhead is quite significant; The unwinder code is fairly high in the list when profiling, mostly because of the very unfortunate way that ClassLoader.loadClass throws exceptions when a class could not be found. It should be easy enough to fix libgcc to do something more efficient with dynamically registered frames. Andrew.
Hi Nicolas, On Tue, Mar 3, 2009 at 11:38 AM, Nicolas Geoffray <nicolas.geoffray at lip6.fr> wrote:> > Duncan Sands wrote: >> >> Another possibility, very close you yours and currently used by the vmkit >> project, is to modify all functions so they return two values, the usual >> return value and an additional boolean value indicating whether an >> exception >> was thrown during the call or not. Callers then branch to an appropriate >> place based on this value. Thus there is no special stack unwinding, it >> is just functions returning. This adds some distributed overhead, but >> unwinding is fast. You can always return something more complicated than >> a boolean of course. > > > That's correct. Although, to make things clear, I'm not using the multiple > return value features of LLVM. The signature of functions only return one > value. If an exception happens, the boolean value is stored in a thread > local specific variable. But conceptually, this pretty much is the same than > returning two values.I see. So you check this value stored in a thread-local variable after each call? And you lower invoke to a call and branch with regard to this value?> It's *hardly* noticeable. If your language/runtime throws a lot of > exceptions, that's the way to go currently (there are other sophisticated > techniques, but much more complex). Dwarf is great if your language/runtime > basically never throws exceptions. I can't give you an accurate measure of > the real cost of Dwarf on Java applications because, unfortunately, libgcc > did not optimize its dwarf info lookup on dynamically registered frames. > It's doing a linear search of the info, and that takes *a lot* of time.In my view I would use exceptions a lot more if they were very efficient. Exceptions are nice, because they break the current code flow and send a signal/message in the dynamic call stack. What are these sophisticated techniques you are talking about? My time frame for implementing this is, not unlimited, but fairly long. Less than a year (of spare time) would be ok. I still need to feel progress. Another option I'm thinking about is creating a runtime that, when initialized, compiles the DWARF information to native code. It could create an Instruction Pointer lookup hash table associated with unwind actions. Maybe libgcc/libunwind does this already? Starting your executable would have a small overhead, but unwinding would be efficient. I didn't start implementing this, mainly because I'm not sure it's already implemented and also because I think exceptions, like many other programming concepts, should be placed as a responsibility of the compiler, not the executable. If I could place as much overhead for the unwinding proces as possible in the compiler instead of the runtime it would be great. I thought that instead of the runtime created lookup table you could encode it as jmp instructions after each call. It is like the optimisation of malloc/free where you write a size value just before the allocated memory block. The memory is in itself a hash table if the hashes are memory locations. Bjarke Walling
Bjarke Walling wrote:> Another option I'm thinking about is creating a runtime that, when > initialized, compiles the DWARF information to native code. It could > create an Instruction Pointer lookup hash table associated with unwind > actions.JIT-compiling the unwinder data, yes. Given that the unwinder data is, basically, the source for a specialized bytecode interpreter I can't see any reason this wouldn't work.> Maybe libgcc/libunwind does this already?It doesn't. Andrew.
Hi Bjarke, Bjarke Walling wrote:> I see. So you check this value stored in a thread-local variable after > each call? And you lower invoke to a call and branch with regard to > this value? >Yes, that's correct.> What are these sophisticated techniques you are talking about? My time > frame for implementing this is, not unlimited, but fairly long. Less > than a year (of spare time) would be ok. I still need to feel > progress. > >I'm talking about this: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.9083 I don't know how difficult it would be to implement it in LLVM's codegen. Nicolas
Nicolas Geoffray wrote:> It's *hardly* noticeable. If your language/runtime throws a lot of > exceptions, that's the way to go currently (there are other > sophisticated techniques, but much more complex). Dwarf is great if your > language/runtime basically never throws exceptions. I can't give you an > accurate measure of the real cost of Dwarf on Java applications because, > unfortunately, libgcc did not optimize its dwarf info lookup on > dynamically registered frames. It's doing a linear search of the info, > and that takes *a lot* of time.Plus, for those of us who care, the linear search is protected by a single mutex because there appears to be the potential that dynamically registered frames can be removed from the list (in addition to being inserted) and a mutex is the easiest way to protect against inconsistency. Unfortunately, this means that threads that throw a lot will end up serializing here, plus there's a decent amount of cache-line pinging for read-only use of the list. There are other ways to deal with the potential concurrent removal from the list that force the remover to do much more overhead (rcu, node pools rather than deallocation, etc), but I've never gotten around to actually doing it. Luke> > Nicolas > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev