Estimation of program run-time
Hi everyone,
I am trying to come up with a solution to a problem that seems simple to me, being a noob.
Lets assume that there is a file containing a random access machine program (or a program in similar, simple, assembly - like language). The task is to read the file - and to _estimate_ how long will it take to execute that program. For simplicity's sake lets assume that there won't be endless loops.
What'd be the best approach to this kind of problem? Any ideas?
Should we put symbols into hashtable - then read the file, check if a command is correct and ... then what? What is the best way to estimate the run-time? Is it actually possible, without actually running the program (emulating the machine on which the program executes). I know that its time complexity we're dealing here with... Any suggestions on how to approach that kind of problem?
Any help would be very much appreciated.
Re: Estimation of program run-time
What if I create a double - linked list (second pointer reserved for jump address) then go along the list while adding times required for each step execution - and whenever loop occures simply create expression ( a string ) saying something like that: "N * (sum of time required for steps within the loop)".
But it sounds kind-of lame even to me ... maybe there is other not-so-naive way of doing this?
Re: Estimation of program run-time
This is going to be a very difficult problem. The more general problem of whether or not a given program will ever terminate is actually undecidable (the Halting Problem).
A programmer can give you a big-O analysis of the running time, but I think it would be very hard to come up with such a thing automatically.
Re: Estimation of program run-time
Quote:
Originally Posted by
Lindley
This is going to be a very difficult problem. The more general problem of whether or not a given program will ever terminate is actually undecidable (the Halting Problem).
Well ... what if we narrow down the problem to the programs of whom we KNOW that they will terminate in a finite number of steps (really simple stuff)? I'm actually interested HOW to represent a "external program", so to say.
Quote:
Originally Posted by
Lindley
A programmer can give you a big-O analysis of the running time, but I think it would be very hard to come up with such a thing automatically.
Maybe I should try to write a Random Access Machine emulator (simulator) - how difficult would it be? Any suggestions on how to start with that kind of task?
Re: Estimation of program run-time
What you are trying to build is a computer program profiler
http://en.wikipedia.org/wiki/Profili...r_programming))
There should be open source versions around probably look at embedded computer program profilers because they will expect to have a completely different machine code set to the standard Intel 0x86 code set.
I should also say a good place to start with this sort of idea is with some of the game console machine emulators for PC like MESS (http://www.mess.org/download.php) and MAME (http://mamedev.org). They will show you how to simulate a microcontroller machine code on a PC.
Re: Estimation of program run-time
Re: Estimation of program run-time
Quote:
Originally Posted by
Uglybb
What you are trying to build is a computer program profiler
http://en.wikipedia.org/wiki/Profili...r_programming))
There should be open source versions around probably look at embedded computer program profilers because they will expect to have a completely different machine code set to the standard Intel 0x86 code set.
I should also say a good place to start with this sort of idea is with some of the game console machine emulators for PC like MESS (
http://www.mess.org/download.php) and MAME (
http://mamedev.org). They will show you how to simulate a microcontroller machine code on a PC.
a profiler measures how long a program actually takes to do something *whilst* it is doing it. I think the op wanted an estimate without having to run the program, correct?
Re: Estimation of program run-time
Computationally speaking, just emulating the program run and counting the number of steps is not so hard - but if a program with finite run-time may still run for a VERY long time depending on the input size, making this method not practical for deriving the run-time complexity.
Deriving a program run-time complexity automatically is a very complex(sometimes undecidable) problem which is highly dependent on the specific programing language being analyzed.
The first thing you would probably need to do is to create an abstract representation of the program - maybe in the form of a Control Flow Graph.
The abstract representation should help you reach some conclusions regarding the number of repetitions each loop will undergo. Since (non-endless)loops are bound by some variable - you need to statically analyze the way that your variables change during the program execution.
If you are interested, there are many theoretical researches on the subject.
Regards,
Zachm
