From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1DvmCI-0001Yo-SP for qemu-devel@nongnu.org; Thu, 21 Jul 2005 21:19:32 -0400 Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1DvmC7-0001Sn-I3 for qemu-devel@nongnu.org; Thu, 21 Jul 2005 21:19:20 -0400 Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DvmC7-0001MG-Ax for qemu-devel@nongnu.org; Thu, 21 Jul 2005 21:19:19 -0400 Received: from [12.124.108.50] (helo=dash.soliddesign.net) by monty-python.gnu.org with esmtp (Exim 4.34) id 1Dvm8w-00026f-1y for qemu-devel@nongnu.org; Thu, 21 Jul 2005 21:16:02 -0400 Received: from fred.ofc.soliddesign.net (fred.ofc.soliddesign.net [10.2.3.225]) by dash.soliddesign.net (Postfix) with ESMTP id 32FEB20B090 for ; Thu, 21 Jul 2005 20:05:22 -0500 (EST) Subject: Re: [Qemu-devel] PowerPC64 and more From: Joe Batt In-Reply-To: <1121985441.9483.97.camel@rapid> References: <1121944537.9483.74.camel@rapid> <42E01D41.8020108@reactos.com> <1121985441.9483.97.camel@rapid> Content-Type: text/plain Date: Thu, 21 Jul 2005 20:05:40 -0500 Message-Id: <1121994340.30306.54.camel@fred.ofc.soliddesign.net> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit 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 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