* [Qemu-devel] Time complexity for self-modifying code
@ 2007-02-08 20:01 Michael Gagnon
2007-02-08 20:37 ` Paul Brook
0 siblings, 1 reply; 2+ messages in thread
From: Michael Gagnon @ 2007-02-08 20:01 UTC (permalink / raw)
To: qemu-devel
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
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [Qemu-devel] Time complexity for self-modifying code
2007-02-08 20:01 [Qemu-devel] Time complexity for self-modifying code Michael Gagnon
@ 2007-02-08 20:37 ` Paul Brook
0 siblings, 0 replies; 2+ messages in thread
From: Paul Brook @ 2007-02-08 20:37 UTC (permalink / raw)
To: qemu-devel; +Cc: Michael Gagnon
On Thursday 08 February 2007 20:01, Michael Gagnon wrote:
> 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!
Depends what your N is.
Worst case for SMC (Self Modifying Code) is modifying code in the same TB
(Translation Block) as the store instruction. This kind of fault requires
O(tb_size) time, so executing a TB (assuming every insn traps) takes
O(tb_size ^2) time. However the page boundaries impose a hard limit on the
size of a TB.
Thus for N < TARGET_PAGE_SIZE worst case total execution time is O(N^2), but
for N > TARGET_PAGE_SIZE total execution time is still O(N).
For SMC the constant factor may be orders of magnitude larger than for regular
code.
Paul
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2007-02-08 20:37 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-02-08 20:01 [Qemu-devel] Time complexity for self-modifying code Michael Gagnon
2007-02-08 20:37 ` Paul Brook
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.