Opportunity: Software Execution Time Determinism

[Tamas via Digitalmars-d]

I think the problem can be separated into two:
1. Guarantee a given Big O complexity of a function, (that's what 
matters for most cases),
2. Guarantee / tell the worst case execution time / CPU cycles of 
a given @constanttime function.
Combining these two, we can calculate the worst case execition 
time for the full program.

@constanttime can have branches, each branch with different worst 
case execution time, it won't change the @constanttime nature of 
the funcion. (But makes it harder to calculate the worst case 
execution time, and the average case and the worst case won't be 
the same.)

@constanttime could also have loops / recursion, if the number of 
iterations / recursion is limited. I.e. sorting 5 numbers during 
the median of 5 algorithm is @constanttime, even if it calls a 
sort function which is O(N log N).  I.e. this is valid:

@constanttime auto sort5(Range)(Range values)
{
   assert(values.length <= 5);
   return values.bubblesort();
}

/* inferred: @quadratic */ int[] bubblesort(int[] values) {
   for (int i=0; i<values.length; i++)
     for (int j=i+1; j<values.length; j++)
       if (values[j] < values[i])
         swap(values[i], values[j]);
}

If the number of iteration in a function is proportional to the 
input's length, then it's @linear or @BigO_N. If there are two 
such iterations nested, then it's @quadratic or @BigO_N2, and so 
on.
These could be very well inferred and guaranteed by the compiler. 
But the Compiler might not realize that the amortized time is 
less than what it looks like from the first glance. So the user 
could annotate a function inferred as @quadratic as @linear. Then 
the linearity of the function could be validated / guaranteed 
during runtime using the amortization credit system: the function 
should allocate credits based on the input size and its promise, 
then use this credit to call @constattime functions, while not 
running out of credits. These credits could be passed-on to 
@linear functions as well, those will use more credits, according 
their input sizes. If the promise is broken and the program runs 
out of credit, it should break immediately. This validation could 
be turned off, similar to assert calls.