Re: RFC: The Constructor Breakpoint Issue

[Jim Blandy <jimb at redhat dot com>]

Daniel Jacobowitz <drow@false.org> writes:

> On Wed, Oct 20, 2004 at 11:00:25AM -0500, Jim Blandy wrote:
> > The line number lookup code actually looks for "best" matches, not
> > just exact matches; see symtab.c:find_line_common.  Preserving that
> > behavior will require a bit of care.
> > 
> > The downside that comes to mind is that this approach requires GDB to
> > always traverse the full linetable, instead of stopping as soon as it
> > finds an exact match, as it does now.
> 
> I think the data structures involved will have to change to do this, or
> it will just be too painful.

Will it be such a big change?  It seems reasonable to assume that line
number queries are evenly distributed across the line tables.  So on
average, every query traverses half the line table now.  This change
would double the number of entries we examine for a single query.  So
you've doubled your search time, and doubled your working set for the
query.

Unlike queries by address, I can't think offhand of a situation where
queries by line occur that are not in response to user input.  This
doesn't seem like a show-stopper to me.


If the data structures do need to change, let me throw an idea out
there:

Our current structures are ordered by address, not by source location.
But adding a new structure indexed by source location could be a big
memory hit.

One way to reduce the size of that structure is to record the
information inexactly.  That is, instead of a table mapping line
numbers to lists of address ranges, we could have a table mapping
*ranges* of line numbers to lists of address ranges.  Or, ranges of
line numbers to lists of blocks, since blocks have start and end
addresses.  Then we could then use this information to narrow down the
range of PC values we need to search; since the line table is already
sorted by PC (I don't know why we don't use a binary search there),
that would cut down the amount of linear searching needed to something
acceptable.