我们可以预测方法的执行时间吗？ [英] Can we predict the execution time for method ?

问题描述

是否可以预测方法或代码块的执行时间？

Is it possible to predict the execution time for a method or block of code ?

推荐答案

在Windows上，没有。 Windows不是一个实时操作系统，而是一个执行抢占式多任务处理的共享系统。在Windows将您的线程重新执行并且您无法知道线程将被允许执行多长时间之前，您无法知道它将持续多长时间。这使得无法提前知道任何代码执行需要多长时间。



你为什么要这样做？

On Windows, no. Windows is not a real-time operating system and is a shared system that does preemptive multitasking. You have no way of knowing how long it's going to be before Windows puts your thread back into execution and you have no way of knowing how long the thread is going to be allowed to execute. This makes it impossible to know ahead of time how long any piece of code is going to take to execute.

Why would you want to?

除了解决方案1.



一般情况下，这种预测理论上不可能。我的意思是，即使对于每个逻辑确定性样本的定时完全确定的系统也是不可能的，例如在具有每个CPU指令的已知定时（在CPU周期中）和CPU周期的单线程单进程系统的情况下频率。



因此，在这样的系统中，您可以完美地预测特殊（简单）情况下的时间。但一般情况下为什么不呢？由于条件运算符，通常是指令流控制语句，例如if。嗯，有了这样的陈述，在特殊（简单）情况下也可以进行时序预测。但是，为什么不是一般情况下呢？



因为即使是逻辑行为也无法预测一般情况。基于另一个经过数学验证的陈述，我可以用数学方法证明 暂停问题无法解决 。广义陈述被称为赖斯定理。请参阅：

https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof [ ^ ]，

https://en.wikipedia.org/wiki/Rice%27s_theorem [ ^ ]。



I可以证明我对赖斯定理的看法，但为了简单起见，它足以使用它的特殊情况，停止问题的事实是不可解决的。在一般情况下，你甚至无法预测一些不那么微不足道的算法是否会停止执行。这意味着，您可以预期程序将执行一段时间，通常很长时间，最终停止，或永远不会停止。



显然，如果你不这样做甚至从算法中知道时间是无限的有限，这意味着你无法预测时间。 :-)







我们可以面对或构建一个总是暂停的算法，但是时机有限，但理论上仍然不可预测？是的，有赖斯的定理。如果你的一些属性值不确定，你可以写一些类似 if（myProperty）LongMethod（）else QuickMethod（）。



一个简单的实际案例是使用伪随机数生成器。是的，它的算法本身是确定性的，但是如果你种子算法，那么这些值将不是确定性的，例如，使用从实时时钟设备获得的值。



另一个微不足道的案例是一个互动程序。 :-)



现在，即使使用多线程系统，在特殊情况下你仍然可以预测时间，但它将是曲棍球时间，而不是足球时间。也许你知道，在曲棍球比赛中，时钟在所有休息时间停止，只计算游戏的纯粹时间。您可以精确地评估单个线程的时序，而不是计算所有中断和线程切换的时间。对于实时（足球时间），它将为您提供可能真实的 infinum - 持续时间。



但是这个估计仅对固定CPU型号和固定CPU时钟频率有效。滴答时间可从CPU规格中获得，因此您可以总结所有指令的所有滴答计数。但请记住，您的代码可以与类似的CPU兼容，后者可能有不同的时序。一般来说，这一切都归结为代码和预测所理解的内容。如果这是高级编程语言中的代码，则不同的编译器可能会生成不同的CPU指令。



预测也不是明确定义的类别。假设您正在使用 recurrent 算法计算广义 Fibonacci序列。该算法是完全确定的，但预测是什么，特别是如果初始数据集和所需的序列长度取自输入数据？每次，您都可以完美地预测算法的行为，但这种预测的方法只有一个：使用完全相同的数据集从头到尾执行所有计算。是预测与否？ :-)

只是一些值得思考的东西...

-SA

In addition to Solution 1.

In general case, such prediction is theoretically impossible. I mean, it is impossible even for the systems where the timing of every logically deterministic sample is totally deterministic, such as in the case of single-thread single-process system with known timing of each CPU instruction (in CPU cycles) and CPU cycle frequency.

So, in such systems, you can perfectly predict timing in special (simple) cases. But why not in general case? Because of conditional operators and, generally, instruction-flow control statements, such as "if". Well, with such statements, timing prediction can also be possible in special (simple) cases. But, again, why not in general case?

Because even the logical behavior cannot be predicted in general case. I can proof it mathematically, based on another mathematically proven statement, that the halting problem is unsolvable. The generalized statement is known as Rice's theorem. Please see:
https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof[^],
https://en.wikipedia.org/wiki/Rice%27s_theorem[^].

I could prove my point on the Rice's theorem, but for simplicity, it's enough to use its special case, the fact that halting problem is not solvable. In general case, you cannot even predict if some not so trivial algorithm will ever halt the execution. That means, you can expect that the program will execute for some, usually long, time, and eventually halt, or will never stop.

Apparently, if you don't even know from the algorithm that the time is infinite of finite, it means you cannot predict the time. :-)



Can we face or build an algorithm which always halts, but timing is finite but still theoretically unpredictable? Yes, with Rice's theorem. If some your property value is not deterministic, you can write something like if (myProperty) LongMethod() else QuickMethod().

One simple practical case is the use of pseudo-random number generator. Yes, its algorithm itself is deterministic, but the values won't be deterministic if you seed the algorithm, for example, with the value taken from the real-time clock device.

Another trivial cases is an interactive program. :-)

Now, even with multi-threaded systems, in special cases you can still predict timing, but it will be "hockey time", not "football time". Perhaps you know that in hockey, the clock is stopped on all breaks, to count only the "pure" time of the game. You can precisely evaluate the timing for a single thread, not counting the time for all interrupts and thread switching. For real time ("football time") it will give you the infinum of the possible real-time durations.

But this estimate will be valid only on the fixed CPU model and fixed CPU clock frequency. The tick times are available from the CPU specs, so you can sum up all the tick counts for all instructions. But remember that your code can be compatible with the similar CPU, which may have different timing. Generally, it all boils down to what you understand by "code" and "prediction". If this is the code in high-level programming language, different compilers may generate different CPU instructions.

"Prediction" is also not a well-defined category. Let's say, you are calculating generalized Fibonacci sequence using the recurrent algorithm. The algorithm is perfectly deterministic, but what would be the prediction, especially if the initial data set and required length of sequence is taken from input data? Each time, you can predict the behavior of the algorithm perfectly, but the method of such prediction is only one: to perform all the calculations from the beginning to the end with the exact same data set. Is it prediction or not? :-)
Just some food for thought…

—SA

在有限的意义上，你可以使用一个高分辨率的.NET计时器来计算方法/代码，在你通过执行它至少一次预先编写代码之后，在计时之前......一个合格的是。 '



我建议你查看这篇文章的优秀链接和信息：[ ^ ]熟悉.NET计时器及其怪癖，以及使用它们的最佳实践。





但是，请记住：



你怎么知道你已经使用输入数据运用了代码它运行最慢？你怎么知道你有时间可能的许多模态用例？



戴夫和谢尔盖在这里做了一个很好的工作来定义Windows固有的因素使计时结果近似，并且超出一定的阈值是不可靠的。



但是，相对时间数据仍然很有价值！有昂贵的第三。用于.NET的派对工具（来自PostShap，RedGate，Telerik等），以及一些来自Microsoft和各种开源项目的免费工具，试图分析应用程序性能：[ ^ ]。



在CodeProject上搜索Profiler。



在实际水平上，最佳使用时间可能是A / B测试：比较两种不同实现技术，或两种不同的类设计。而且，在实际层面上，经常分析内存消耗与执行时间一样重要。

In the limited sense that you can use a high-resolution .NET timer to time the method/code, after you pre-jit the code by executing it at least once, before timing it ... a qualified 'yes.'

I suggest you review the excellent links and information on this post: [^] to familiarize yourself with .NET timers and their quirks, and best practices in using them.


But, keep in mind:

How do you know you have "exercised the code" with the input data that would make it run the slowest ? How do you know you have timed the possible many modal use-cases ?

Dave and Sergey do a good job in their answers here of defining the factors inherent in Windows that make results of timing "approximate," and unreliable beyond a certain threshold.

However, relative timing data can still be valuable ! There are expensive 3rd. party tools for .NET (from PostShap, RedGate, Telerik, etc.), and some free ones from Microsoft and various open-source projects, that attempt to "profile" application performance: [^].

Search here on CodeProject on "Profiler."

On a practical level, the best use of timing may be A/B Testing: to compare two different implementation techniques, or two different Class designs. And, also on the practical level, often analyzing memory consumption is as, or more, important than execution time.

这篇关于我们可以预测方法的执行时间吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！