Re: Ada.Execution_Time

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

Randy Brukardt wrote:
> I think we're actually in agreement on most points.

Good, and I agree. Nevertheless I again make a lot of comments, below, 
because I think your view, if true, means that Ada.Execution_Time is 
useless for real-time systems.

> The main difference is 
> that I contend that the theoretical "execution time" is, in actual practice, 
> unmeasurable. ("Unmeasurable" is a bit strong, but I mean that you can only 
> get a gross estimation of it.)

You are right, we disagree on this.

> You have argued that there exist cases where it is possible to do better (a 
> hardware clock, a single processor, a kernel that doesn't get in the way of 
> using the hardware clock,

Yes.

> no contention with other devices on the bus, etc.),

I may have been fuzzy on that. Such real but variable or unpredictable 
delays or speed-ups are, in my view, just normal parts of the execution 
time of the affected task, and do not harm the ideal concept of "the 
execution time of a task" nor the usefulness of Ada.Execution_Time and 
its child packages. They only mean that the measured execution time of 
one particular execution of a task is less predictive of the execution 
times of future executions of that task. More on this below.

> and I wouldn't disagree. The problem is that those cases aren't 
> realistic, particularly if you are talking about a language-defined package. 

I am not proposing new general requirements on timing accuracy for the RM.

> (Even if there is a hardware clock available on a particular target, an 
> off-the-shelf compiler isn't going to be able to use it. It can only use the 
> facilities of the kernel or OS.)

For critical, embedded, hard-real-time systems I think it is not 
uncommon to use dedicated real-time computers with kernels such as 
VxWorks or RTEMS or bare-board Ada run-time systems. I have worked on 
such computers in the past, and I see such computers being advertised 
and used today.

In such systems, the kernel or Ada RTS is usually customised by a "board 
support package" (BSP) that, among other things, handles the interfaces 
to clocks and timers on the target computer (the "board"). Such systems 
can provide high-accuracy timers and mechanisms for execution-time 
monitoring without having to change the compiler; it should be enough to 
change the implementation of Ada.Execution_Time. In effect, 
Ada.Execution_Time would be a part of the BSP, or depend on types and 
services defined in the BSP.

The question is then if the compiler/system vendors will take the 
trouble and cost to customise Ada.Execution_Time for a particular 
board/computer, or if they will just use the general, lowest-denominator 
but portable service provided by the kernel. Dmitry indicates that GNAT 
on VxWorks takes the latter, easy way out. That's a matter of cost vs 
demand; if the users want it, the vendors can provide it.

For example, the "CPU Usage Statistics" section of the "RTEMS C User's 
Guide" says: "RTEMS versions newer than the 4.7 release series, support 
the ability to obtain timestamps with nanosecond granularity if the BSP 
provides support. It is a desirable enhancement to change the way the 
usage data is gathered to take advantage of this recently added 
capability. Please consider sponsoring the core RTEMS development team 
to add this capability." Thus, in March 2010 the RTEMS developers wanted 
and could implement accurate execution-time measurement, but no customer 
had yet paid for its implementation.

> This shows up when you talk about the inability to reproduce the results. In 
> practice, I think you'll find that the values vary a lot from run to run; 
> the net effect is that the error is a large percentage of the results for 
> many values.

Again, I may have not have been clear on my view of the reproducibility 
and variability of execution-time measurements. The variability in the 
measured execution time of a task has three components or sources:

1. Variable execution paths due to data-dependent conditional 
control-flow (if-then-else, case, loop). In other words, on different 
executions of the task, different sequences of instructions are 
executed, leading to different execution times.

2. Variable execution times of indivual instructions, for example due to 
variable cache contents and variable bus contention.

3. Variable measurement errors, for example truncations or roundings in 
the count of CPU_Time clock cycles, variable amount of interrupt 
handling included in the task execution time, etc.

Components 1 and 2 are big problems for worst-case analysis but in my 
view are not problems for Ada.Execution_Time. In fact, I think that one 
of the intended uses of Ada.Execution_Time is to help systems make good 
use of this execution-time variability by letting the system do other 
useful things when some task happens to execute quicker than its 
worst-case execution time and leaves some slack in the schedule.

Only component 3 is an "error" in the measured value. This component, 
and also constant measurement errors if any, are problems for users of 
Ada.Execution_Time.

> Your discussion of real-time scheduling using this still seems to me to be 
> more in the realm of academic exercise than something practical. I'm sure 
> that it works in very limited circumstances,

I think these circumstances have some correlation with the domain for 
which Ada is or was intended: reliable, embedded, possibly real-time 
systems. Well, this is a limited niche.

> but those circumstances are 
> getting less and less likely by the year. Techniques that assume a strong 
> correspondence between these values and real-time are simply fantasy -- I 
> would hope no one depend on these for anything of importance.

If this is true, Ada.Execution_Time is useless for real-time systems. 
Since it was added to the RM for 2005, and is still in the draft for RM 
2012, I suppose the ARG majority does not share your view.

Thanks for a frank discussion, and best wishes for 2011!

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .