Re: Ada.Execution_Time

["Randy Brukardt" <randy@rrsoftware.com>]

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:8o0p0lF94rU1@mid.individual.net...
> Randy, I'm glad that you are participating in this thread. My duologue 
> with Dmitry is becoming repetitive and our views entrenched.
>
> We have been discussing several things, although the focus is on the 
> intended meaning and properties of Ada.Execution_Time. As I am not an ARG 
> member I have based my understanding on the (A)RM text. If the text does 
> not reflect the intent of the ARG, I will be glad to know it, but perhaps 
> the ARG should then consider resolving the conflict by confirming or 
> changing the text.

Perhaps, but that presumes there is something wrong with the text. A lot is 
purposely left unspecified in the ARM; what causes problems is when people 
start reading stuff that is not there.

...

>> My understanding was that it was intended to provide a window into 
>> whatever facilities the underlying system had for execution "time" 
>> counting.
>
> Of course, as long as those facilities are good enough for the RM 
> requirements and for the users; otherwise, the implementor might improve 
> on the underlying system as required. The same holds for Ada.Real_Time. If 
> the underlying system is a bare-board Ada RTS, the Ada 95 form of the RTS 
> probably had to be extended to support Ada.Execution_Time.
>
> I'm sure that the proposers of the package Ada.Execution_Time expected the 
> implementation to use the facilities of the underlying system. But I am 
> also confident that they had in mind some specific uses of the package and 
> that these uses require that the values provided by Ada.Execution_Time 
> have certain properties that can reasonably be expected of "execution 
> time", whether or not these properties are expressly written as 
> requirements in the RM.

Probably, but quality of implementation is rarely specified in the Ada 
Standard. When it is, it generally is in the form of Implementation Advice 
(as opposed to hard requirements). The expectation is that implementers are 
going to provide the best implementation that they can -- implementers don't 
purposely build crippled or useless implementations. Moreover, that is 
*more* likely when the Standard is overspecified, simply because of the need 
to provide something that meets the standard.

> Examples of these uses are given in the paper by A. Burns and A.J. 
> Wellings, "Programming Execution-Time Servers in Ada 2005," pp.47-56, 27th 
> IEEE International Real-Time Systems Symposium (RTSS'06), 2006. 
> http://doi.ieeecomputersociety.org/10.1109/RTSS.2006.39.
>
> You put "time" in quotes, Randy. Don't you agree that there *is* a valid, 
> physical concept of "the execution time of a task" that can be measured in 
> units of physical time, seconds say? At least for processors that only 
> execute one task at a time, and whether or not the system provides 
> facilities for measuring this time?

I'm honestly not sure. The problem is that while such a concept might 
logicially exist, as a practical matter it cannot be measured outside of the 
most controlled circumstances. Thus, that might make sense in a bare-board 
Ada implementation, but not in any implementation running on top of any OS 
or kernel. As such, whether the concept exists is more of an "angels on the 
head of a pin" question than anything of practical importance.

> I think that the concept exists and that it matches the description in RM 
> D.14 (11/2), using the background from D.2.1, whether or not the ARG 
> intended this match.
>
> If you agree that such "execution time" values are conceptually well 
> defined, do you not think that the "execution time counting facilities" of 
> real-time OSes are meant to measure these values, to some practical level 
> of accuracy?
>
> If so, then even if Ada.Execution_Time is intended as only a window into 
> these facilities, it is still intended to provide measures of the physical 
> execution time of tasks, to some practical level of accuracy.

The problem is that that "practical level of accuracy" isn't realistic. 
Moreover, I've always viewed such facilities as "profiling" ones -- it's the 
relative magnitudes of the values that matter, not the absolute values. In 
that case, the scale of the values is not particularly relevant.

Specifically, I mean that what is important is which task is taking a lot of 
CPU. In that case, it simply is the task that has a large "execution time" 
(whatever that means) compared to the others. Typically, that's more than 
100 times the usage of the other tasks, so the units involved are hardly 
relevant.

>> That had no defined relationship with what Ada calls "time".
>> As usch, I think the name "execution time" is misleading, (and I recall 
>> some discussions about that in the ARG), but no one had a better name 
>> that made any sense at all.
>
> Do you remember if these discussions concerned the name of the package, 
> the name of the type CPU_Time, or the very concept "execution time"? If 
> the question was of the terms "time" versus "duration", I think "duration" 
> would have been more consistent with earlier Ada usage, but "execution 
> time" is more common outside Ada, for example in the acronym WCET for 
> Worst-Case Execution Time.
>
> The fact that Ada.Execution_Time provides a subtraction operator for 
> CPU_Time that yields Time_Span, which can be further converted to 
> Duration, leads the RM reader to assume some relationship, at least that 
> spans of real time and spans of execution time can be measured in the same 
> physical units (seconds).
>
> It has already been said, and not only by me, that Ada.Execution_Time is 
> intended (among other things, perhaps) to be used for implementing task 
> scheduling algorithms that depend on the accumulated execution time of the 
> tasks. This is supported by the Burns and Wellings paper referenced above. 
> In such algorithms I believe it is essential that the execution times are 
> physical times because they are used in formulae that relate (sums of) 
> execution-time spans to spans of real time.

That would be a wrong interpretation of a algorithms, I think. (Either that, 
or the algorithms themselves are heavily flawed!). The important property is 
that all of the execution times have a reasonably proportional relationship 
to the actual time spent executing each task (that hypothetical concept); 
the absolute values shouldn't matter much (just as the exact priority values 
are mostly irrelevant to scheduling decisions). Moreover, when the values 
are close, one would hope that the algorithms don't change behavior much.

The values would be trouble if they bore no relationship at all to the 
"actual time spent executing the task", but it's hard to imagine any 
real-world facility in which that was the case.

...
...
>> In particular, there is no requirement in the RM or anywhere else that 
>> these "times" sum to any particular answer.
>
> I agree that the RM has no such explicit requirement. I made this claim to 
> counter Dmitry's assertion that CPU_Time has no physical meaning, and of 
> course I accept that the sum will usually be less than real elapsed time 
> because the processor spends some time on non-task activities.
>
> The last sentence of RM D.14 (11/2) says "It is implementation defined 
> which task, if any, is charged the execution time that is consumed by 
> interrupt handlers and run-time services on behalf of the system". This 
> sentence strongly suggests to me that the author of this paragraph had in 
> mind that the total available execution time (span) equals the real time 
> (span), that some of this total is charged to the tasks, but that some of 
> the time spent in interrupt handlers etc. need not be charged to tasks.
>
> The question is how much meaning should be read into ordinary words like 
> "time" when used in the RM without a formal definition.
>
> If the RM were to say that L is the length of a piece of string S, 
> measured in meters, and that some parts of S are colored red, some blue, 
> and some parts may not be colored at all, surely we could conclude that 
> the sum of the lengths in meters of the red, blue, and uncolored parts 
> equals L? And that the sum of the lengths of the red and blue parts is at 
> most L? And that, since we like colorful things, we hope that the length 
> of the uncolored part is small?
>
> I think the case of summing task execution time spans is analogous.

I think you are inventing things. There is no such requirement in the 
standard, and that's good: I've never seen a real system in which this has 
been true.

Even the various profilers I wrote for MS-DOS (the closest system to a bare 
machine that will ever be in wide use) never had this property. I used to 
think that it was some sort of bug in my methods, but even using completely 
different ways of measuring time (counting ticks at subprogram heads vs. 
statistical probes -- I tried both) the effects still showed up. I've pretty 
much concluded that is is simply part of the nature of computer time -- much 
like floating point, it is an incomplete abstraction of the "real" time, and 
expecting too much out of it is going to lead immediately to disappointment.

>> I don't quite see how there could be, unless you were going to require a 
>> tailored Ada target system (which is definitely not going to be a 
>> requirement).
>
> I don't want such a requirement. The acceptable overhead (fraction of 
> execution time not charged to tasks) depends on the application.
>
> Moreover, on a multi-process systems (an Ada program running under Windows 
> or Linux, for example) some of the CPU time is spent on other processes, 
> all of which would be "overhead" from the point of view of the Ada 
> program. I don't think that the authors of D.14 had such systems in mind.

I disagree, in the sense that the ARG as a whole certainly considered the 
use of this facility in all environments. (I find that it would be very 
valuable for profiling on Windows, for instance, even if the results only 
have a weak relationship to reality).

It's possible that the people who proposed it originally were thinking as 
you are, but the ARG modified those proposals quite a bit; the result is 
definitely a team effort and not the work on any particular individual.

                               Randy.