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.
