Why function template 'among' is of complexity O(1) and not O(n)?

[anonymous]

On Thursday, 20 February 2014 at 01:41:25 UTC, Chris Williams
wrote:
> On Thursday, 20 February 2014 at 00:36:38 UTC, anonymous wrote:
>> On Wednesday, 19 February 2014 at 22:46:45 UTC, Chris Williams
>> wrote:
>>> When the template writes out the definition of the function, 
>>> if the parameters can be interpreted during compile-time, 
>>> then the foreach ( O(n) ) will be run by the compiler to 
>>> detect the correct parameter and the function will be written 
>>> out as just as a return statement in the body, without the 
>>> loop. So during runtime, the function would have an O(1) 
>>> runtime.
>>
>> That's an optimization the compiler may do, but it's not
>> guaranteed. And `among` is not special in this regard.
>
> I think "expected to do" is probably the better phrasing at the 
> moment. Traits/annotations would be largely unusable unless 
> foreach was able to behave as a static construct. And since 
> there is no way for one to declare "static foreach", the only 
> way foreach can be used for running over traits, is for the 
> compiler to detect constant values in the parameters to the 
> statement.

The foreach is definitely always evaluated at compile time.
That's independent of the values being known statically. It
generates a couple of if statements. But optimizing those if
statements away for static values is not guaranteed or expected.

In other words, with code, this:
---
uint among(Value, Values...) (Value value, Values values)
{
        foreach (i, v; values) if (value == v) return i + 1;
        return 0;
}
auto foo = among("a", "b", "c");
---

definitely boils down to something like this:
---
uint among_string_string_string(string value, string v0, string
v2)
{
        if(value == v0) return 1;
        if(value == v1) return 2;
        return 0;
}
auto foo = among_string_string_string("a", "b", "c");
---

But it's a mere optimization to get to this:
---
auto foo = 0;
---