From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 4907 invoked by alias); 19 Feb 2007 11:57:55 -0000 Received: (qmail 4856 invoked by uid 22791); 19 Feb 2007 11:57:54 -0000 X-Spam-Check-By: sourceware.org Received: from nevyn.them.org (HELO nevyn.them.org) (66.93.172.17) by sourceware.org (qpsmtpd/0.31.1) with ESMTP; Mon, 19 Feb 2007 11:57:49 +0000 Received: from dsl093-172-095.pit1.dsl.speakeasy.net ([66.93.172.95] helo=caradoc.them.org) by nevyn.them.org with esmtp (Exim 4.63) (envelope-from ) id 1HJ79O-0004yx-H2; Mon, 19 Feb 2007 06:57:46 -0500 Received: from drow by caradoc.them.org with local (Exim 4.63) (envelope-from ) id 1HJ79N-0001w8-TR; Mon, 19 Feb 2007 06:57:46 -0500 Date: Mon, 19 Feb 2007 12:54:00 -0000 From: Daniel Jacobowitz To: Thomas Neumann Cc: gdb@sourceware.org Subject: Re: Organization of breakpoint locations Message-ID: <20070219115744.GC6815@caradoc.them.org> Mail-Followup-To: Thomas Neumann , gdb@sourceware.org References: <45D97E30.2060008@users.sourceforge.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <45D97E30.2060008@users.sourceforge.net> User-Agent: Mutt/1.5.13 (2006-08-11) X-IsSubscribed: yes Mailing-List: contact gdb-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sourceware.org X-SW-Source: 2007-02/txt/msg00197.txt.bz2 On Mon, Feb 19, 2007 at 11:38:40AM +0100, Thomas Neumann wrote: > Hi, > > I would like some suggestions on the organization of breakpoint > locations in breakpoint.c. Currently, all breakpoint locations are > stored in a linear list. This does not scale if the number of > breakpoints is large, see PR 2230 for an example. Instead the > breakpoints should be stored in a suitable search structure (e.g. a > balanced tree). > > I have a patch that converts the list into a splay. Works fine, and the > bottleneck indeed goes away, but I am not satisfied with the approach > itself. Have you tested this in any real world use yet? This is only the first limitation you'll encounter, I think. For instance, every time you step and then stop the program, GDB is going to remove every breakpoint. That's going to be just as slow. > It would be nicer to reuse existing data structures instead of > implementing a new one. I thought about using splay-tree in libiberty, > but the breakpoint locations have some unique characteristics: 1. the > locations have to be organized by address, but the address is not > necessarily unique. So the search structure must handle duplicates. 2. > the test suite (and perhaps other code) expect that a breakpoint is > added "last" in the list, i.e. duplicate handling must keep an order > within the duplicates. 3. it must be possible to iterate over search > structure (directly, without callbacks), as otherwise a lot of code has > to be changed. > > The splay implementation from libiberty satisfies none of these > constraints. Why do you think that the splay tree in libiberty can't handle any of these? Your key would not be the address, but the address plus the breakpoint sequence number. That handles one and two. Then you can iterate over items using splay_tree_successor. The key could be the same pointer as the value, by the way - it just takes a clever splay_tree_compare_fn. Another way is to use the address as a key, but store a VEC of breakpoints as the values, sorted by number. That's messier though. > Is there perhaps something else in the gdb sources that I > can reuse? Or should I submit my (admittedly quite large) patch? But > this would probably no longer count as a "small changes" that according > to CONTRIBUTE do not require a copyright assignment. To be honest, I don't think this will be a small change either way. -- Daniel Jacobowitz CodeSourcery