[Bug libgcc/56460] New: _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)

[cr at progress dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56460



 Bug #: 56460

   Summary: _Unwind_Find_FDE is O(n) in the number of frame infos,

(and LLVM's JIT will generate many of them)

Classification: Unclassified

   Product: gcc

   Version: 4.7.2

Status: UNCONFIRMED

  Severity: normal

  Priority: P3

 Component: libgcc

AssignedTo: unassig...@gcc.gnu.org

ReportedBy: c...@progress.com





Using LLVM with stack unwinding code calls __register_frame_info for every

function it JITs.  After generating a large number of functions, any occurrence

of throwing an exception (even in G++ compiled code) takes a very long time

(10's of milliseconds if 50,000 functions are generated) between  the throw and

catch, even if the catch is in the same function.  



Profiling and code inspection shows that the time is spent in _Unwind_Find_FDE

where it linearly walks the seen_objects linked list, looking for an object to

map the PC's on the stack up to.  Typically, there is at most one frame_info

registered per shared object, so typically a low number.  But if we want to

dynamically add a large number (as LLVM's JIT does; one per function), we could

maintain an ordered array of objects and perform a binary search of that array.



A proposed diff is attached.  We're seeing significant performance improvements

with this patch.

[Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)

[cr at progress dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56460



--- Comment #1 from Chris Reed  2013-02-26 14:43:15 UTC 
---

Created attachment 29540

  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29540

Proposed fix - maintain array, binary search it

[Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)

[cr at progress dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56460



--- Comment #4 from Chris Reed  2013-02-27 12:15:52 UTC 
---

Yes, I'm happy to address the copyright issue - the copyright disclaimer route

seems simpler.



qsort'ing the entire array was more for simplicity - I was more concerned by

the performance of throwing a lot of exceptions than the one time cost of

sorting the array (and I expect an ever changing number of registrations would

be unusual).  The sort order was changed simply because it matched the bsearch

algorithm used elsewhere and seemed more intuitive. I considered a binary tree;

a sorted array was just simpler to implement.