Opportunity: Software Execution Time Determinism
Andrei Alexandrescu via Digitalmars-d
digitalmars-d at puremagic.com
Wed Apr 13 18:13:06 PDT 2016
On 4/13/16 6:58 PM, 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?
>
> Andrei has done some great work on determining big O complexity, but
> that's only a small part of this problem.
>
> I don't know about any work in this area, but I can see it would be
> valuable.
Tarjan was among the first to study the problem:
http://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/Amortized.pdf.
He assigned "computational credits" to functions and designed a type
system in which functions cannot consume more credits than assigned.
One simpler thing we can do is add an attribute:
void fun() @credits(2);
meaning fun() consumes two computational credits. Then a function that
calls fun() n times consumes n*2 credits etc. Generally we wouldn't aim
for automatically determining credits consumed, but we can define a
library that allows the user to declare credits appropriately.
Andrei
More information about the Digitalmars-d
mailing list