[ wxwindows-Bugs-1534704 ] wxASSERT / wxStackWalker O(n^2) and unusable on deep stacks

[SourceForge.net]

Bugs item #1534704, was opened at 2006-08-04 18:00
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=109863&aid=1534704&group_id=9863

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Unix specific
Group: Must fix
Status: Open
Resolution: None
Priority: 5
Submitted By: Alex Bligh (abligh)
Assigned to: Nobody/Anonymous (nobody)
Summary: wxASSERT / wxStackWalker O(n^2) and unusable on deep stacks

Initial Comment:
If you have a deep stack frame (say 50 or so levels),
wxStackWalker and thus wxASSERT become unusable due to
an O(n^2) problem. For instance, on a very fast
machine, it can take 40 seconds for the wxASSERT box to
appear.

This is in essence because wxStackWalker executes the
addr2line on each line individually. So for n stack
frames, there are n calls to addr2line. Each of these
has to load the binary, resolve all the symbol tables,
and find the appropriate stack frame. I believe this is
O(n) if not O(n log n). That means we have at least an
O(n^2) problem.

addr2line is capable of taking multiple addresses on
the command line, or reading them from standard input.
Thus it could be called far fewer times (optimally, it
could be called once). This would give a huge speed
improvement.

wxDebugReport also relies on wxStackWalker, and this
explains why debug dumps on Xara Xtreme take over 40
seconds to produce (longer on debug builds, because
wxDebugReport itself wxAsserts about a hole in
/proc/maps, leading to another complete stackwalk, and
another 40 seconds...)


----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=109863&aid=1534704&group_id=9863