Re: [Qemu-devel] PowerPC64 and more

[Joe Batt <Joe@soliddesign.net>]

On Fri, 2005-07-22 at 00:37 +0200, J. Mayer wrote:
> We agreed with Fabrice that there should be at least one more
> indirection in page mapping, because it would cost too much memory to
> try to map the whole needed memory space in one table, even if we can
> "forget" some of the middle bits in most cases.

I haven't had time to even look at the qemu code, but in my last
emulator, we found it was fastest to keep a sorted array of chunks of
memory instead of some sort of tree.

To fetch a chunk of memory, you would scan through the device list for a
chunk that covered that range and swap it with the previous chunk in the
list.  System RAM bubbled to the top and the control structures of a
particular timer that our real code used bubbled to the top.  Most
access is to system RAM, so there is only one indirection most of the
time.  We had a 15% speed improvement over using a hash table.
(disclaimer, we were implementing in Java, so array access is a bit slow
due to bounds checking.)

Knuth has a name for the data structure, but I don't remember what it
is.

-- 
Joe Batt <Joe@soliddesign.net>