Opportunity: Software Execution Time Determinism

qznc via Digitalmars-d digitalmars-d at puremagic.com
Thu Apr 14 08:40:21 PDT 2016


On Thursday, 14 April 2016 at 01:35:34 UTC, Walter Bright wrote:
> On 4/13/2016 5:31 PM, Simen Kjaeraas wrote:
>> 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.
>
> Very interesting. Recursion would have to be disallowed as well.
>
>
>> The part about conditionals seems a bit harsh, but it's got to
>> be there for determinism.
>
> Understood.

A limited version is allowed. For example, on x86 the CMOV 
instruction. The basic idea: You have to do all branches and 
select the result.

This is about code generation and cannot be checked via 
annotation.



More information about the Digitalmars-d mailing list