Given a specific computer system, is it possible to estimate the actual precise run time of a piece of Assembly codeX F e d L
this is a piece of Assembly code
section .text
global _start ;must be declared for using gcc
_start: ;tell linker entry point
mov edx, len ;message length
mov ecx, msg ;message to write
mov ebx, 1 ;file descriptor (stdout)
mov eax, 4 ;system call number (sys_write)
int 0x80 ;call kernel
mov eax, 1 ;system call number (sys_exit)
int 0x80 ;call kernel
section .data
msg db 'Hello, world!',0xa ;our dear string
len equ $ - msg ;length of our dear string
Given a specific computer system, is it possible to predict precisely the actual run time of a piece of Assembly code.
-
4$\\begingroup$ Is "run the code on that computer and use a stopwatch" a valid answer? $\\endgroup$ – Draconis yesterday
-
1$\\begingroup$ I suspect the majority of time spent on executing this piece of code is waiting for I/O. The time it takes to execute the individual instructions is somewhat predictable if you knew the memory location of the code and all the details about the processor (which are extremely complex nowadays), but the speed is also affected by the memory and disk so you'd have to know a very large amount of details about them as well. So unless you consider physical phenomena (which affect the time as well), you could say it is predictable, but unimaginably hard to do so. $\\endgroup$ – IllidanS4 15 hours ago
2 Answers
I can only quote from the manual of a rather primitive CPU, a 68020 processor from around 1986: "Calculating the exact runtime of a sequence of instructions is difficult, even if you have precise knowledge of the processor implementation". Which we don't have. And compared to a modern processor, that CPU was primitive.
I can't predict the runtime of that code, and neither can you. But you can't even define what "runtime" of a piece of code is, when a processor has massive caches, and massive out-of-order capabilities. A typical modern processor can have 200 instructions "in flight", that is in various stages of execution. So the time from trying to read the first instruction byte, to retiring the last instruction, can be quite long. But the actual delay to all other work that the processor needs doing may be (and typically is) a lot less.
Of course doing two calls to the operating system makes this completely unpredictable. You don't know what "writing to stdout" actually does, so you can't predict the time.
And you can't know the clock speed of the computer at the precise moment you run the code. It may be in some power saving mode, the computer may have reduced clock speed because it got hot, so even the same number of clock cycles can take different amounts of time.
All in all: Totally unpredictable.
-
$\\begingroup$ That said, it's impossible for cryptography based on constant-time operations to ever have any variance that might create a vulnerability to timing attacks. $\\endgroup$ – Nat 13 hours ago
-
$\\begingroup$ I think your conclusions are too strong. Latency and throughput are common metrics to measure the "runtime" of a program. Also you can simply settle on a suitable definition of "runtime". Moreover, if you have a complete snapshot of the system state, hw and sw, and a perfect knowledge of the CPU internals you can predict the runtime. At Intel they can probably estimate the runtime, even here on SO we can predict latencies and tputs with cycle accuracy. In this case, besides the syscalls, it is not even that hard. $\\endgroup$ – Margaret Bloom 8 hours ago
-
1$\\begingroup$ @MargaretBloom not even then. I place my phone too close to the oven, the CPU underclocks to manage the temperature, your runtime estimate is suddenly too low. And even if you count in cycles and don't do syscalls, other threads and CPUs may play nicely with the RAM contents, or they may dump your memory to the hard drive while you are swapped out, based on unpredictable circumstances, ranging from power surges slowing down the hard drive just enough that a competing thread gets enough memory in time to wreck yours, all the way to threads straight up rolling dice to see how much time to waste. $\\endgroup$ – John Dvorak 8 hours ago
-
$\\begingroup$ Besides that, "complete knowledge of the system state, hw and sw" is a pretty tall order, methinks. Add "10 ms in advance", and you're already asking for the impossible. And if your CPU's implementation of hardware random number generation uses quantum phenomena (it probably does), and some thread on the CPU calls it, then not even knowing the complete state of the universe 3000 km around the computer will save you. And in MWI, you can't even guess right. $\\endgroup$ – John Dvorak 8 hours ago
There are two aspects at play here
As @gnasher729 points out, if we know the exact instructions to execute, it's still difficult to estimate the exact runtime because of things like caching, branch prediction, scaling, etc.
However, the situation is even worse. Given a chunk of assembly, it's impossible to know which instructions will run, or even to know how many instructions will run. This is because of Rice's theorem: if we could determine that precisely, then we could use that information to solve the Halting Problem, which is impossible.
Assembly code can contain jumps and branches, which are enough to make the full trace of a program possibly infinite. There has been work on conservative approximations of execution time, that gives upper bounds on execution, through things like cost semantics or annotated type systems. I'm not familiar with anything for assembly specifically but I wouldn't be surprised if something like that existed.
-
1$\\begingroup$ I mean, the Halting Problem applies directly here, since if we knew the run time we'd know if it halts. Also the fact that there are no conditionals doesn't even help here, since in x86,
movis Turing-Complete $\\endgroup$ – BlueRaja - Danny Pflughoeft 14 hours ago -
$\\begingroup$ Rice and the Halting Problem are statements about arbitrary (any) programs -- but the OP here has specified one specific piece of code in the question. You can determine semantic and halting properties about individual or limited categories of programs, right? It's just that there's no general procedure that covers all programs. $\\endgroup$ – Daniel R. Collins 11 hours ago
-
1$\\begingroup$ We can definitively know which instruction will run next, what we cannot tell is if we ever hit a
sys_exitand thus stop the stopwatch. If we restrict to terminating programs, which is reasonable for such a practical question, then then answer is actually yes (granted you have a perfect snapshot of the state, hw and sw, of the system just before starting the program). $\\endgroup$ – Margaret Bloom 8 hours ago
