Opportunity: Software Execution Time Determinism
Walter Bright via Digitalmars-d
digitalmars-d at puremagic.com
Wed Apr 13 18:47:32 PDT 2016
On 4/13/2016 6:13 PM, Andrei Alexandrescu wrote:
> 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.
This looks like it could be combined with Simen's @constanttime idea. After all,
a function would have to run in constant time in order for the credits to be
consistent.
Or maybe go one step further, and use @BigO(2) ? @BigO(2) would imply constant
time. This would fit in with your research on combining complexities.
More information about the Digitalmars-d
mailing list