[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Hash table based symbol lookup (was: Re: [Qemu-devel] [PATCH] Fix sy

From: Laurent Desnogues
Subject: Re: Hash table based symbol lookup (was: Re: [Qemu-devel] [PATCH] Fix symbol lookup for mips64* targets)
Date: Tue, 7 Oct 2008 23:34:59 +0200

On Tue, Oct 7, 2008 at 9:34 PM, Laurent Desnogues
<address@hidden> wrote:
> On Tue, Oct 7, 2008 at 7:50 PM, Blue Swirl <address@hidden> wrote:
>> On 10/7/08, Laurent Desnogues <address@hidden> 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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]