From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1KnKCt-0001si-0l for qemu-devel@nongnu.org; Tue, 07 Oct 2008 17:35:03 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1KnKCr-0001rr-Cv for qemu-devel@nongnu.org; Tue, 07 Oct 2008 17:35:02 -0400 Received: from [199.232.76.173] (port=42757 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1KnKCr-0001ro-6y for qemu-devel@nongnu.org; Tue, 07 Oct 2008 17:35:01 -0400 Received: from rv-out-0708.google.com ([209.85.198.251]:57705) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1KnKCq-0003jJ-Nr for qemu-devel@nongnu.org; Tue, 07 Oct 2008 17:35:01 -0400 Received: by rv-out-0708.google.com with SMTP id f25so3265413rvb.22 for ; Tue, 07 Oct 2008 14:34:59 -0700 (PDT) Message-ID: <761ea48b0810071434y7dd3fc01n8a40174a78e1fe61@mail.gmail.com> Date: Tue, 7 Oct 2008 23:34:59 +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: <761ea48b0810071234v7fb5eaf4hc3a434cb6fd2602c@mail.gmail.com> 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> <761ea48b0810071234v7fb5eaf4hc3a434cb6fd2602c@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 9:34 PM, Laurent Desnogues wrote: > 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 :-) It suddenly occurred to me a simple binary search could be a good solution and should be easy to implement. The resulting complexity and memory usage should be acceptable. I will give that a try with some huge executable. Laurent