On 07.12.2013 00:58, H. S. Teoh wrote:
> On Sat, Dec 07, 2013 at 12:40:35AM +0100, bearophile wrote:
> [...]
>> Regarding Java performance matters, from my experience another
>> significant source of optimization in the JavaVM that is often
>> overlooked is that the JavaVM is able to partially unroll even loops
>> with a statically-unknown number of cycles. Currently I think
>> GCC/DMD/LDC2 are not able or willing to do this.
> [...]
>
> Really? I've seen gcc/gdc unroll loops with unknown number of
> iterations, esp. when you're using -O3. It just unrolls into something
> like:
>
> 	loop_start:
> 		if (!loopCondition) goto end;
> 		loopBody();
> 		if (!loopCondition) goto end;
> 		loopBody();
> 		if (!loopCondition) goto end;
> 		loopBody();
> 		if (!loopCondition) goto end;
> 		loopBody();
> 		goto loop_start;
> 	end:	...
>
> I'm pretty sure I've seen gcc/gdc do this before.

The classic way of doing this (I have no idea if it's actually done by any compilers) is Duff's Device[1], which turns this code:

    do {
        *to++ = *from++;
    } while(--count > 0);}

into this:

    int n = (count + 7) / 8;
    switch(count % 8) {
    case 0: do {    *to++ = *from++;
    case 7:         *to++ = *from++;
    case 6:         *to++ = *from++;
    case 5:         *to++ = *from++;
    case 4:         *to++ = *from++;
    case 3:         *to++ = *from++;
    case 2:         *to++ = *from++;
    case 1:         *to++ = *from++;
            } while(--n > 0);

[1]: http://en.wikipedia.org/wiki/Duff's_device
-- 
  Simen

On 07.12.2013 08:38, Maxim Fomin wrote:
> On Friday, 6 December 2013 at 23:30:45 UTC, Walter Bright wrote:
>> On 12/6/2013 3:06 PM, Maxim Fomin wrote:
>>> and what about holes in immutable, pure and rest type system?
>>
>> If there are bugs in the type system, then that optimization breaks.
>
> Bad news: there are many bugs in type system.
>
>>
>>> C doesn't have virtual functions.
>>
>> Right, but you can (and people do) fake virtual functions with tables
>> of function pointers. No, C doesn't devirtualize those.
>>
>
> Neither does D.
>
>>> By the way, does D devirtualize them?
>>
>> It does for classes/methods marked 'final'
>
> this is essentially telling nothing, because these functions are not
> virtual. In your speaking, C 'devirtualizes' all direct calling.

They're both virtual and not (sorta). Consider this case:

class A {
    int foo() { return 3; }
}

class B : A {
    final int foo() { return 4; }
}

int bar(A a) {
    return a.foo();
}

void baz(B b) {
    int n = bar(b);
}

If the compiler does not inline the call to bar in baz, a virtual call is performed. If it does inline it, then it knows that the function called will always be B.foo, even if the received value may be a subclass of B.

-- 
  Simen

On 12/08/2013 07:53 PM, Walter Bright wrote:
> On 12/8/2013 2:13 AM, Araq wrote:
>> From this list only (7) is a valid point. All the others can be
>> trivially dealt
>> with whole program optimization (1,2,3)
>
> If it's trivial, it's not happening. (1) would require solving the
> halting problem.  ...

No it would not. If all you need to do is catching up with D, just infer where immutability qualifiers should go. This is decidable (the search space is finite). Of course, an analysis of this style could infer more fine-grained global aliasing information anyway.

On 12/8/2013 12:06 PM, Timon Gehr wrote:
> On 12/08/2013 07:53 PM, Walter Bright wrote:
>> On 12/8/2013 2:13 AM, Araq wrote:
>>> From this list only (7) is a valid point. All the others can be
>>> trivially dealt
>>> with whole program optimization (1,2,3)
>>
>> If it's trivial, it's not happening. (1) would require solving the
>> halting problem.  ...
>
> No it would not. If all you need to do is catching up with D, just infer where
> immutability qualifiers should go. This is decidable (the search space is
> finite). Of course, an analysis of this style could infer more fine-grained
> global aliasing information anyway.

I don't believe it is remotely correct that any amount of static analysis will determine where a pointer points to, just as it won't tell you what value the variable 'i' has in it.

On 12/08/2013 09:42 PM, Walter Bright wrote:
> On 12/8/2013 12:06 PM, Timon Gehr wrote:
>> On 12/08/2013 07:53 PM, Walter Bright wrote:
>>> On 12/8/2013 2:13 AM, Araq wrote:
>>>> From this list only (7) is a valid point. All the others can be
>>>> trivially dealt
>>>> with whole program optimization (1,2,3)
>>>
>>> If it's trivial, it's not happening. (1) would require solving the
>>> halting problem.  ...
>>
>> No it would not. If all you need to do is catching up with D, just
>> infer where
>> immutability qualifiers should go. This is decidable (the search space is
>> finite). Of course, an analysis of this style could infer more
>> fine-grained
>> global aliasing information anyway.
>
> I don't believe it is remotely correct that any amount of static
> analysis will determine where a pointer points to,
> just as it won't tell you what value the variable 'i' has in it.

?

Static analysis will tell you where a pointer might point to (more importantly, it may exclude aliasing) and what values the variable 'i' might have in it. How precise this information is hinges on the details of the analysis and the program it is applied on. I'm just saying that this may be more precise than what 'immutable' qualifiers give you (since those are quite easy to infer, given the program, and alias analysis may be non-trivial.)

Walter Bright:

> You can do these in D with a library type.

We'll discuss much better about similar topics in another specific thread.

Bye,
bearophile

On 12/8/2013 4:47 PM, Timon Gehr wrote:
> Static analysis will tell you where a pointer might point to (more importantly,
> it may exclude aliasing) and what values the variable 'i' might have in it. How
> precise this information is hinges on the details of the analysis and the
> program it is applied on. I'm just saying that this may be more precise than
> what 'immutable' qualifiers give you (since those are quite easy to infer, given
> the program, and alias analysis may be non-trivial.)

There has been a lot of work trying to eliminate array bounds checking by figuring out the limits of i. This has met with only limited success.

I know of no C compiler that even attempts such things, and it certainly would be done if it was trivial.

"Proper" D code makes routine use of const and immutable, and so that information is effortlessly available to even simple optimizers.

On 2013-12-07 00:56, Walter Bright wrote:

>>> 2. D knows when functions are pure. C has to make worst case
>>> assumptions.
>>
>> Does the compiler currently take advantage of this?
>
> dmd does.

Compiling the following code:

pure int foo (immutable int a, immutable int b)
{
    return a + b;
}

void main ()
{
    auto a = foo(1, 2);
    auto b = foo(1, 2);
    auto c = a + b;
}

With DMD 2.064.2 produce the exact same assembly code for "foo" and "main" with our without "pure". I compiled with "dmd -O -release foo.d", am I doing something wrong?

> This is about inherent language opportunities, not whether current
> implementations fall short or not.

I think most people will care about what's working right now. Not what could possibly work sometime in the future.

-- 
/Jacob Carlborg

On 2013-12-08 19:44, Walter Bright wrote:

> To be fairer (!), all of these (except restrict) are non-Standard
> extensions for C. "restrict" is an extension for C++.

It doesn't matter they're not standard, as long as people are using them.

-- 
/Jacob Carlborg

On 9 December 2013 08:05, Jacob Carlborg <doob@me.com> wrote:
> On 2013-12-07 00:56, Walter Bright wrote:
>
>>>> 2. D knows when functions are pure. C has to make worst case assumptions.
>>>
>>>
>>> Does the compiler currently take advantage of this?
>>
>>
>> dmd does.
>
>
> Compiling the following code:
>
> pure int foo (immutable int a, immutable int b)
> {
>     return a + b;
> }
>
> void main ()
> {
>     auto a = foo(1, 2);
>     auto b = foo(1, 2);
>     auto c = a + b;
> }
>
> With DMD 2.064.2 produce the exact same assembly code for "foo" and "main" with our without "pure". I compiled with "dmd -O -release foo.d", am I doing something wrong?
>

Of course, it will not work unless you also pass the following options: -version=Enterprise -noboundscheck -inline -property -transition=11629

I thought everyone knew that??!?? :o)