From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43)
	id 1HFFaD-0007Fk-79
	for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:09:29 -0500
Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43)
	id 1HFFaA-0007FX-NF
	for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:09:27 -0500
Received: from [199.232.76.173] (helo=monty-python.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.43) id 1HFFaA-0007FU-Gz
	for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:09:26 -0500
Received: from caduceus2.gmu.edu ([129.174.0.41])
	by monty-python.gnu.org with esmtp (Exim 4.52) id 1HFFaA-0008QT-6Y
	for qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:09:26 -0500
Received: from [42.33.25.54] ([129.174.78.5])
	by caduceus2.gmu.edu (Sun Java System Messaging Server 6.2-2.05 (built
	Apr 28 2005)) with ESMTPA id <0JD500HLIUBIES50@caduceus2.gmu.edu> for
	qemu-devel@nongnu.org; Thu, 08 Feb 2007 15:02:06 -0500 (EST)
Date: Thu, 08 Feb 2007 15:01:57 -0500
From: Michael Gagnon <mgagnon1@gmu.edu>
Message-id: <45CB81B5.9080405@gmu.edu>
MIME-version: 1.0
Content-type: text/plain; charset=ISO-8859-1; format=flowed
Content-transfer-encoding: 7BIT
Subject: [Qemu-devel] Time complexity for self-modifying code
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

Hello.  I'm a student at George Mason University and I had a question 
regarding the time complexity of QEMU's algorithm for dealing with 
self-modifying code. 

 From looking at the QEMU Internals documentation 
(http://fabrice.bellard.free.fr/qemu/qemu-tech.html), it seems that 
QEMU's method for handling self-modifying code might have different 
algorithmic efficiency classes for it's average case and worst case.  As 
in, on average I assume that QEMU emulates instructions at O(n) 
efficiency.  In the worst-case, might self-modifying code change the 
efficiency of QEMU to another order of efficiency, such as O(n^2)?  Any 
thoughts would be greatly appreciated.  Thanks!

Mike Gagnon
http://www.mikegagnon.com