From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 21811 invoked by alias); 24 Sep 2002 10:51:47 -0000 Mailing-List: contact gdb-help@sources.redhat.com; run by ezmlm Precedence: bulk List-Subscribe: List-Archive: List-Post: List-Help: , Sender: gdb-owner@sources.redhat.com Received: (qmail 21787 invoked from network); 24 Sep 2002 10:51:45 -0000 Received: from unknown (HELO otisco.McKusick.COM) (209.31.233.190) by sources.redhat.com with SMTP; 24 Sep 2002 10:51:45 -0000 Received: (from hilfingr@localhost) by otisco.McKusick.COM (8.9.3/8.9.3) id DAA10302; Tue, 24 Sep 2002 03:52:34 -0700 Date: Tue, 24 Sep 2002 03:51:00 -0000 Message-Id: <200209241052.DAA10302@otisco.McKusick.COM> X-Authentication-Warning: localhost.localdomain: hilfingr set sender to hilfingr@otisco.mckusick.com using -f From: "Paul N. Hilfinger" To: carlton@math.stanford.edu CC: drow@mvista.com, jimb@redhat.com, gdb@sources.redhat.com In-reply-to: (message from David Carlton on 23 Sep 2002 10:38:54 -0700) Subject: Re: suggestion for dictionary representation Reply-to: Hilfinger@otisco.mckusick.com References: <200209230244.g8N2ieo21741@zenia.red-bean.com> <20020923031056.GA26307@nevyn.them.org> X-SW-Source: 2002-09/txt/msg00368.txt.bz2 A random piece of empirical data, for what it's worth: Out of curiosity, I slapped together a little skip-list implementation and ran all the stabs symbols in a large (67MByte) executable through it---adding all of them. There were a total of about 670000 adds, of which about 150000 were distinct. This required about 3 seconds (including the time to allocate new list nodes, allocate copies of the keys, and insert the new items) running on an 800MHz Athlon processor. For comparison, the time to first prompt for a version of GDB (version 5.1.1 or so) on this same file was 4 seconds, or 47 seconds if started with -r. Interpretation, I admit, is difficult, but I think this establishes some sort of rough bound on possible performance hits from this representation (the skip-list implementation, being hasty, was not particularly optimized). Paul Hilfinger