From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43)
	id 1KnGhX-0006Y3-NN
	for qemu-devel@nongnu.org; Tue, 07 Oct 2008 13:50:27 -0400
Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43)
	id 1KnGhW-0006Wv-7n
	for qemu-devel@nongnu.org; Tue, 07 Oct 2008 13:50:27 -0400
Received: from [199.232.76.173] (port=40774 helo=monty-python.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.43) id 1KnGhW-0006Wr-32
	for qemu-devel@nongnu.org; Tue, 07 Oct 2008 13:50:26 -0400
Received: from wx-out-0506.google.com ([66.249.82.236]:5900)
	by monty-python.gnu.org with esmtp (Exim 4.60)
	(envelope-from <blauwirbel@gmail.com>) id 1KnGhV-0008Cj-Nm
	for qemu-devel@nongnu.org; Tue, 07 Oct 2008 13:50:25 -0400
Received: by wx-out-0506.google.com with SMTP id h27so778105wxd.4
	for <qemu-devel@nongnu.org>; Tue, 07 Oct 2008 10:50:23 -0700 (PDT)
Message-ID: <f43fc5580810071050ge827d36vdbf618dd941f8d1d@mail.gmail.com>
Date: Tue, 7 Oct 2008 20:50:23 +0300
From: "Blue Swirl" <blauwirbel@gmail.com>
Subject: Re: Hash table based symbol lookup (was: Re: [Qemu-devel] [PATCH] Fix
	symbol lookup for mips64* targets)
In-Reply-To: <761ea48b0810062348m4a394195r1463952b0157e787@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <761ea48b0810060329l5d05315euea009eb97d22799b@mail.gmail.com>
	<f43fc5580810060911m5d5bafchec77cfcb56ad824d@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: <http://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.gnu.org/pipermail/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <http://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: qemu-devel@nongnu.org

On 10/7/08, Laurent Desnogues <laurent.desnogues@gmail.com> wrote:
> Here is a revised version that uses less memory while keeping
>  the same complexity.
>
>  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?