From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KnIKG-0003OP-7i for qemu-devel@nongnu.org; Tue, 07 Oct 2008 15:34:32 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KnIKE-0003MP-M2 for qemu-devel@nongnu.org; Tue, 07 Oct 2008 15:34:31 -0400 Received: from [199.232.76.173] (port=32849 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KnIKE-0003MD-Fl for qemu-devel@nongnu.org; Tue, 07 Oct 2008 15:34:30 -0400 Received: from rv-out-0708.google.com ([209.85.198.241]:39934) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1KnIKE-0001Yn-2z for qemu-devel@nongnu.org; Tue, 07 Oct 2008 15:34:30 -0400 Received: by rv-out-0708.google.com with SMTP id f25so3218245rvb.22 for ; Tue, 07 Oct 2008 12:34:25 -0700 (PDT) Message-ID: <761ea48b0810071234v7fb5eaf4hc3a434cb6fd2602c@mail.gmail.com> Date: Tue, 7 Oct 2008 21:34:25 +0200 From: "Laurent Desnogues" Subject: Re: Hash table based symbol lookup (was: Re: [Qemu-devel] [PATCH] Fix symbol lookup for mips64* targets) In-Reply-To: MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline References: <761ea48b0810060329l5d05315euea009eb97d22799b@mail.gmail.com> <761ea48b0810060928p5f97e03cx7c43cbc1a75a0d6a@mail.gmail.com> <761ea48b0810062348m4a394195r1463952b0157e787@mail.gmail.com> Reply-To: qemu-devel@nongnu.org List-Id: qemu-devel.nongnu.org List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org On Tue, Oct 7, 2008 at 7:50 PM, Blue Swirl wrote: > On 10/7/08, Laurent Desnogues wrote: >> >> This could be made less memory hungry by using some >> binary tree data structure at the expense of code complexity. >> I won't go down that road as anyway this stuff is mainly used >> for debugging and tracing purposes. > > I agree that hash and binary tree would be too complex. > > But what if you dropped the hash table and used a binary tree instead? > A binary tree would be both memory efficient (you could keep the > regions, maybe just use a pointer to the original symbol table) and > it's relatively fast. Maybe the original symbols could be sorted so > that the binary search could use the original table directly? I was indeed talking about replacing the whole hash table by a binary tree (it has been proven that mixing both is not the way to go; cf Knuth). The problem we have here is that we are doing an interval search: we are looking if an address belongs to a function. I will give that some thought, but don't hold your breath :-) Laurent