* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
@ 2013-02-26 14:43 ` cr at progress dot com
2013-02-26 18:27 ` steven at gcc dot gnu.org
` (6 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: cr at progress dot com @ 2013-02-26 14:43 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
2013-02-26 14:43 ` [Bug libgcc/56460] " cr at progress dot com
@ 2013-02-26 18:27 ` steven at gcc dot gnu.org
2013-02-26 22:57 ` steven at gcc dot gnu.org
` (5 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu.org @ 2013-02-26 18:27 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
2013-02-26 14:43 ` [Bug libgcc/56460] " cr at progress dot com
2013-02-26 18:27 ` steven at gcc dot gnu.org
@ 2013-02-26 22:57 ` steven at gcc dot gnu.org
2013-02-27 12:16 ` cr at progress dot com
` (4 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu.org @ 2013-02-26 22:57 UTC (permalink / raw)
To: gcc-bugs
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...).
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
` (2 preceding siblings ...)
2013-02-26 22:57 ` steven at gcc dot gnu.org
@ 2013-02-27 12:16 ` cr at progress dot com
2013-02-27 21:10 ` stevenb.gcc at gmail dot com
` (3 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: cr at progress dot com @ 2013-02-27 12:16 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
` (3 preceding siblings ...)
2013-02-27 12:16 ` cr at progress dot com
@ 2013-02-27 21:10 ` stevenb.gcc at gmail dot com
2013-02-27 21:15 ` steven at gcc dot gnu.org
` (2 subsequent siblings)
7 siblings, 0 replies; 9+ messages in thread
From: stevenb.gcc at gmail dot com @ 2013-02-27 21:10 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
` (4 preceding siblings ...)
2013-02-27 21:10 ` stevenb.gcc at gmail dot com
@ 2013-02-27 21:15 ` steven at gcc dot gnu.org
2013-02-27 21:17 ` steven at gcc dot gnu.org
2015-04-14 22:30 ` daekharel at gmail dot com
7 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu.org @ 2013-02-27 21:15 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
` (5 preceding siblings ...)
2013-02-27 21:15 ` steven at gcc dot gnu.org
@ 2013-02-27 21:17 ` steven at gcc dot gnu.org
2015-04-14 22:30 ` daekharel at gmail dot com
7 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu.org @ 2013-02-27 21:17 UTC (permalink / raw)
To: gcc-bugs
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
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug libgcc/56460] _Unwind_Find_FDE is O(n) in the number of frame infos, (and LLVM's JIT will generate many of them)
2013-02-26 14:42 [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
` (6 preceding siblings ...)
2013-02-27 21:17 ` steven at gcc dot gnu.org
@ 2015-04-14 22:30 ` daekharel at gmail dot com
7 siblings, 0 replies; 9+ messages in thread
From: daekharel at gmail dot com @ 2015-04-14 22:30 UTC (permalink / raw)
To: gcc-bugs
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.
^ permalink raw reply [flat|nested] 9+ messages in thread