[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)

[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: unassigned@gcc.gnu.org
        ReportedBy: cr@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 <cr at progress dot com> 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)

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2013-02-26
                 CC|                            |steven at gcc dot gnu.org
     Ever Confirmed|0                           |1

--- Comment #2 from Steven Bosscher <steven at gcc dot gnu.org> 2013-02-26 18:26:40 UTC ---
Re. patch:
- Why change the sort order?
- Why qsort the whole array, instead of e.g. memmove'ing the bits
that have to be moved? Those are still sorted, after all.

Note, if you have no copyright assignment on file, we cannot do
anything with the 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)

[steven at gcc dot gnu.org]

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

--- Comment #3 from Steven Bosscher <steven at gcc dot gnu.org> 2013-02-26 22:57:02 UTC ---
(In reply to comment #2)

> - Why qsort the whole array, instead of e.g. memmove'ing the bits

Ah, oops. qsort can't be used in libgcc, the target may not provide
a qsort implementation (e.g. a free-standing target).

Talking this over on IRC, the best solution probably is to make
seen_objects some kind of balanced tree. Alternatively, another
custom sort function could be added (unwind-dw2-fde.c already has
frame_heapsort...).

[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 <cr at progress dot com> 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.

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

[stevenb.gcc at gmail dot com]

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

--- Comment #5 from stevenb.gcc at gmail dot com <stevenb.gcc at gmail dot com> 2013-02-27 21:09:55 UTC ---
> --- Comment #4 from Chris Reed <cr at progress dot com> 2013-02-27 12:15:52 UTC ---
> Yes, I'm happy to address the copyright issue - the copyright disclaimer route
> seems simpler.

I can take care of a patch along the lines of your idea. Working on it
already. It's too late now for GCC 4.8 but I will attach the patch to
this bug report when it's ready.

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

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|steven at gcc dot gnu.org   |
         AssignedTo|unassigned at gcc dot       |steven at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #6 from Steven Bosscher <steven at gcc dot gnu.org> 2013-02-27 21:14:17 UTC ---
Mine now.

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

[steven at gcc dot gnu.org]

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

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED

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

[daekharel at gmail dot com]

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

Michael Arntzenius <daekharel at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |daekharel at gmail dot com

--- Comment #7 from Michael Arntzenius <daekharel at gmail dot com> ---
Hi, I work on the Pyston project (http://blog.pyston.org/) and we've been
having this issue precisely: we JIT a lot of functions, this makes throwing
exceptions really slow, and _Unwind_Find_FDE seems to be the culprit. Does it
seem likely this issue will be fixed anytime soon? Looks like the last activity
was in 2013.