From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21406 invoked by alias); 5 Oct 2004 05:07:50 -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 21052 invoked from network); 5 Oct 2004 05:07:48 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org with SMTP; 5 Oct 2004 05:07:48 -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 i9557mao014625 for ; Tue, 5 Oct 2004 01:07:48 -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 i9557lr22140; Tue, 5 Oct 2004 01:07:47 -0400 To: Daniel Jacobowitz Cc: gdb-patches@sources.redhat.com Subject: Re: [rfa/dwarf] Support for attributes pointing to a different CU References: <20040923045723.GA11871@nevyn.them.org> <20040924003412.GB10500@nevyn.them.org> <20041003161221.GA3234@nevyn.them.org> <20041004212201.GA21064@nevyn.them.org> From: Jim Blandy Date: Tue, 05 Oct 2004 05:07:00 -0000 In-Reply-To: <20041004212201.GA21064@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/msg00076.txt.bz2 Daniel Jacobowitz writes: > On Mon, Oct 04, 2004 at 04:14:24PM -0500, Jim Blandy wrote: > > > > Daniel Jacobowitz writes: > > > On Wed, Sep 29, 2004 at 12:49:35PM -0500, Jim Blandy wrote: > > > > Since we never toss types anyway, would it make sense to move > > > > type_hash to dwarf2_per_objfile? > > > > > > I don't think so. type_hash is used in two ways: individual items are > > > set, when we know which CU we ought to have, and a whole CU is > > > restored, when we know which CU we're restoring. It's always more > > > efficient to have a lot of small hash tables if you know precisely > > > which one you'll need; fewer collisions. > > > > Really? libiberty/hashtab.c is a resizing hash table; I thought hash > > table resizing was supposed to keep the collision rate roughly > > constant (modulo hysteresis) regardless of the number of elements. If > > that's not so, doesn't that mean your hash function isn't doing its > > job spreading the elements across the (adequately sized) table? > > Poor job of thinking on my part, there. The rest of the paragraph > still makes sense to me, though. For instance, in a resizing hash > table, I suspect that there is more copying to have one large > expandable hash table than several small ones. > > I haven't done the math for that, of course. Maybe I've got it > backwards. Do you think there would be any advantage to doing it the > other way round? The only advantage I had in mind was simplicity, and it didn't seem like it'd be a performance hit. The libiberty hash table expands by a given ratio each time, which means that, overall, the number of rehashings per element is constant no matter how large the table gets. It's similar to the analysis that shows that ye olde buffer doubling trick ends up being linear time. (I'm thinking on my own here, not quoting anyone, so be critical...) There could be a locality disadvantage to doing it all in one big hash table. When the time comes to restore a given CU's types, their table entries will be sharing cache blocks with those of other, irrelevant CU's. That doesn't happen if we use for per-CU hash tables: table entries will never share cache blocks with table entries for other CU's (assuming the tail of one table doesn't share a block with the head of another, blah blah blah...). I'm concerned about the legacy of complexity we'll leave. Wrinkles should prove they can pay their own way. :)