On Thursday, 14 April 2016 at 00:31:34 UTC, Simen Kjaeraas wrote:
The first step is simple - we care only about functions being
constant-time. Let's invent a @keyword for that: @constanttime.
@constanttime functions can only call other functions marked
@constanttime, and may not contain conditionals, gotos or
while-loops.
@constanttime functions may contain for and foreach-loops, iff
the number of iterations are known at compile-time, and 'break'
is never used.
The part about conditionals seems a bit harsh, but it's got to
be there for determinism.
Constant time is easy, and may or may not be enough to cover
Nordlöw's needs. Anything beyond it is very likely to be halting
problem stuff.
Yest, that's what I had in mind. Those mentioned are the
low-hanging fruits.
The situation is as follows:
A set of processes are tightly scheduled to run after one another
within a 1/N frame, where N is typically either 60 Hz. Each of
these processes run on a single CPU. The scheduler defines a
specific order for the execution of the different processes.
After each process has completed its execution within a frame it
copies its out-values to the in-values of other processes that
uses its results which are then executed.
Each process is assigned a time- and space-budget collectively
called WCRU (worst-case-resource-usage). Execution space can be
restricted by forbidding any kind of dynamic memory
(de)allocations. This is often straightforward but could be
useful to have restriction qualifer for aswell, for instance
`@noheap`.
Then a set of tedious manual code reviews are performed on the
executable code to assert that it doesn't contain any
non-deterministic constructs.
After that the main function of each process is run 100-1000
times and the WCET (worst-case-execution-time) paired with WCSU
(worst-case-stack-usage) is calculated through the maximum of a
set of executions typically a thousand with the correct "stimuli"
as input. Figuring out this stimuli is also cumbersome manual
work.
To conclude, the manual code review could be greatly simplified
or perhaps completely removed if a, say @constanttime as
mentioned above, function attribute was available in the language
and respected by the compiler.
