Opportunity: Software Execution Time Determinism

[Simen Kjaeraas via Digitalmars-d]

On Wednesday, 13 April 2016 at 22:58:26 UTC, Walter Bright wrote:
> The compiler could be fairly easily compute cyclomatic 
> complexity, but how that would be used to determine max time 
> escapes me.
>
> For example, how many times would a particular loop be 
> executed? Isn't this the halting problem, i.e. not computable?

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.

> Andrei has done some great work on determining big O complexity,
> but that's only a small part of this problem.

I have a friend who works on timing attacks in cryptography. 
Knowing
the implementation and measuring the time it takes to multiply two
bigints can help you guess what the numbers are, so in his case
@constanttime would be exactly what he wants, while big-O would be
useless. Not knowing Nordlöw's use case I can't say for sure what 
he
actually needs.

--
   Simen