From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 3230 invoked by alias); 20 Oct 2004 18:24:09 -0000 Mailing-List: contact gdb-patches-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-patches-owner@sources.redhat.com Received: (qmail 3223 invoked from network); 20 Oct 2004 18:24:08 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org with SMTP; 20 Oct 2004 18:24:08 -0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.12.11/8.12.10) with ESMTP id i9KIO3IQ017572 for ; Wed, 20 Oct 2004 14:24:08 -0400 Received: from zenia.home.redhat.com (sebastian-int.corp.redhat.com [172.16.52.221]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id i9KIO2r16215; Wed, 20 Oct 2004 14:24:02 -0400 To: Daniel Jacobowitz Cc: David Lecomber , patches Subject: Re: RFC: The Constructor Breakpoint Issue References: <1097714229.11117.99.camel@localhost.localdomain> <1097847699.1773.81.camel@localhost.localdomain> <20041015145144.GB25188@nevyn.them.org> <1098277715.628.20.camel@delmo.priv.wark.uk.streamline-computing.com> <20041020160416.GA7279@nevyn.them.org> From: Jim Blandy Date: Wed, 20 Oct 2004 18:24:00 -0000 In-Reply-To: <20041020160416.GA7279@nevyn.them.org> Message-ID: User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-SW-Source: 2004-10/txt/msg00347.txt.bz2 Daniel Jacobowitz 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.