On 8 April 2013 21:46, Iain Buclaw <ibuclaw@ubuntu.com> wrote:

> On 8 April 2013 11:59, Manu <turkeyman@gmail.com> wrote:
>
>> On 8 April 2013 19:41, Iain Buclaw <ibuclaw@ubuntu.com> wrote:
>>
>>> On 8 April 2013 10:06, Timon Gehr <timon.gehr@gmx.ch> wrote:
>>>
>>>> On 04/08/2013 10:29 AM, Iain Buclaw wrote:
>>>>
>>>>> On 6 April 2013 12:09, bearophile <bearophileHUGS@lycos.com <mailto:bearophileHUGS@lycos.**com <bearophileHUGS@lycos.com>>> wrote:
>>>>>
>>>>>     I remember Walter saying two or more times that the semantics of D
>>>>>     offers some optimization opportunities that probably are not yet
>>>>>     used to try to reduce the run-time of D programs. Is Walter willing
>>>>>     to write down a list of such opportunities? (Ideas from other
>>>>>     persons are welcome). Maybe some LDC/GDC developer will make the
>>>>>     GCC/LLVM back-ends use them. The implementation of those ideas will
>>>>>     require some time, so later it's better to put the list in the D
>>>>> wiki.
>>>>>
>>>>>     Bye,
>>>>>     bearophile
>>>>>
>>>>>
>>>>>
>>>>> This information could possibly be helpful.  Though given that most of (gdc) codegen is on par with g++, there's probably not much on the list that isn't already detected by the backend optimisation passes.
>>>>>
>>>>>
>>>>> --
>>>>> Iain Buclaw
>>>>>
>>>>> *(p < e ? p++ : p) = (c & 0x0f) + '0';
>>>>>
>>>>
>>>> Does GDC use the additional type information for optimization? Eg. if something is immutable, then aliasing issues do not have to be considered for it when reading and writing through multiple pointers repeatedly.
>>>>
>>>
>>> It uses some type information, eg:
>>>
>>> const/immutable/wild  -> qualified const.
>>> shared -> qualified volatile.
>>> shared + const/wild -> qualified const/volatile.
>>>
>>>
>>> Done nothing in regards to C 'restrict' optimisations.  However the D array .ptr type could also be considered 'restrict' also.
>>>
>>
>> Yes, I was just about to bring up __restrict, there is probably good
>> opportunity for that.
>> Why do you suppose .ptr is restrict? One problem with D's slicing is it's
>> very hard to assume __restrict on basically any arrays.
>> I feel like 'scope' might imply a __restrict input... although the
>> relationship is kinda backwards, so maybe not...
>>
>>
> At least, many array operations, eg:  a[] += b[].  Require the arrays not to be overlapping, so could do some optimisations based around that knowledge.
>

What reason is there that these may not be overlapping?



> How about pure? Is GDC able to factor pure function calls with the same
>> arguments outside of loops, or eliminate consecutive calls? It's really tedious to do this by hand, and breaks code continuity. Particularly important in a language that supports properties, since they'll be accessed consecutively all the time.
>>
>>
> Only builtins are pure in the sense of 'C'.  Even functions considered PUREstrong by the frontend may update an internal state, so the rules just don't apply.  Except for maybe global functions...   In any case, the only benefit you can reap from 'D pure' functions are that they are more likely to be const-folded / inlined.
>

Oh my god... ..... this is the most upsetting thing I've heard all day! :(
No really, I have been SOOOO excited for so long about this optimisation
potential in D!
There's gotta be something that can be done! >_<

Does the front end know if the function actually DOES assign to any state? The compiler could easily work that out, and in the event it doesn't actually perform any such assignment, it could be marked pure for reals...


What about immutable? You said it qualifies const, which in C++ is
>> absolutely meaningless in terms of optimisation potential; just because something is const, the source of the pointer can certainly be non-const somewhere else, which means C++ can't possibly factor const loads outside of loops, and must respect consecutive dereferences of the same pointer. immutable in D should certainly be able to be factored outside loops, so it is more meaningful than const, and actually has real optimisation potential. Can GCC actually express an immutable value?
>>
>
> Other than saying that the type is const-qualified, the decl is set read-only, which only means to the backend that 'this decl may not be the lhs of an assignment.'
>

Well tell the backend that it's restrict aswell, that will give the backend more opportunities where aliasing is a potential problem.



> I remember there was a problem a while back that I brought to you about
>> GDC generating stack frames unnecessarily for leaf functions, is that resolved? I haven't checked in a while.
>>
>>
> It probably is if you re referring to the thread I'm thinking of.
>
> Does GDC have access to a GDC-specific __restrict attribute to tag stuff
>> manually? I'm struggling to think where it can be automated...
>>
>
> Nope, but that can be added in using our new attribute syntax. :~)
>

So, the sad truth is, with all of D's numerous keywords and explicit
qualifications, there are actually NO potential optimisations available
that C could not equally make use of.
I can't believe that pure thing, that's seriously depressing! I forgot you
could assign to state within pure functions. Why is that? It's not actually
pure at all!

I guess there's a little bonus if you tag immutable as restrict, but that's a disappointing sum total...

On 8 April 2013 21:53, Iain Buclaw <ibuclaw@ubuntu.com> wrote:

> On 8 April 2013 12:41, deadalnix <deadalnix@gmail.com> wrote:
>
>> On Monday, 8 April 2013 at 09:41:52 UTC, Iain Buclaw wrote:
>>
>>> It uses some type information, eg:
>>>
>>> const/immutable/wild  -> qualified const.
>>> shared -> qualified volatile.
>>> shared + const/wild -> qualified const/volatile.
>>>
>>>
>> const/wild can be muted via aliasing. I'm not sure how GCC's backend understand const, but this seems unclear to me if this is correct.
>>
>>
> GCC's backend is pretty much C/C++ semantics.  So the const qualifier is shallow, and does not guarantee that no mutations will occur.
>

But D makes no further guarantee. I don't see how const in D is any different than const in C++ in that sense? That's basically the concept of const, it's not a useful concept for optimisation, only immutable is.

On 8 April 2013 22:25, Jacob Carlborg <doob@me.com> wrote:

> On 2013-04-08 10:29, Iain Buclaw wrote:
>
>  This information could possibly be helpful.  Though given that most of
>> (gdc) codegen is on par with g++, there's probably not much on the list that isn't already detected by the backend optimisation passes.
>>
>
> Multiple calls to pure functions could be cached.


Not if it can still make external assignments though. pure in D is basically a lie! :,(

On Monday, 8 April 2013 at 12:25:01 UTC, Jacob Carlborg wrote:
> On 2013-04-08 10:29, Iain Buclaw wrote:
>
>> This information could possibly be helpful.  Though given that most of
>> (gdc) codegen is on par with g++, there's probably not much on the list
>> that isn't already detected by the backend optimisation passes.
>
> Multiple calls to pure functions could be cached.

As D have identity semantic, this isn't that simple.

On 8 April 2013 13:25, Jacob Carlborg <doob@me.com> wrote:

> On 2013-04-08 10:29, Iain Buclaw wrote:
>
>  This information could possibly be helpful.  Though given that most of
>> (gdc) codegen is on par with g++, there's probably not much on the list that isn't already detected by the backend optimisation passes.
>>
>
> Multiple calls to pure functions could be cached.
>
> --
> /Jacob Carlborg
>

Not always, but in some circumstances, yes.

---
struct Foo
{
  int a = 0;
  pure int bar (immutable int x)
  {
    ++a;
    return x * 2;
  }
}


void main()
{
  Foo f;
  int i = f.bar(2) + f.bar(2);

  assert (i == 8);
  assert (f.a == 2);
}
---


Again, the characteristics of D pure functions mean that the backend can const-fold away the function entirely under normal optimisations.

---
D main ()
{
  <bb 2>:
  # DEBUG f.a => 0
  # DEBUG f.a => 1
  # DEBUG f.a => 2
  # DEBUG i => 8
  return 0;
}
---


Possibly strongly-pure functions could be marked as pure in the 'C' sense, but only if they are also nothrow, eg to add to the above example:

---
pure nothrow int baz (Foo f)
{
  return f.bar(2) + f.bar(2);
}
---


Regards
-- 
Iain Buclaw

*(p < e ? p++ : p) = (c & 0x0f) + '0';

On Monday, 8 April 2013 at 12:39:58 UTC, Manu wrote:
> On 8 April 2013 21:53, Iain Buclaw <ibuclaw@ubuntu.com> wrote:
>
>> On 8 April 2013 12:41, deadalnix <deadalnix@gmail.com> wrote:
>>
>>> On Monday, 8 April 2013 at 09:41:52 UTC, Iain Buclaw wrote:
>>>
>>>> It uses some type information, eg:
>>>>
>>>> const/immutable/wild  -> qualified const.
>>>> shared -> qualified volatile.
>>>> shared + const/wild -> qualified const/volatile.
>>>>
>>>>
>>> const/wild can be muted via aliasing. I'm not sure how GCC's backend
>>> understand const, but this seems unclear to me if this is correct.
>>>
>>>
>> GCC's backend is pretty much C/C++ semantics.  So the const qualifier is
>> shallow, and does not guarantee that no mutations will occur.
>>
>
> But D makes no further guarantee. I don't see how const in D is any
> different than const in C++ in that sense? That's basically the concept of
> const, it's not a useful concept for optimisation, only immutable is.

D const is transitive, surely that makes a difference/presents an opportunity?

>
> Possibly strongly-pure functions could be marked as pure in the 'C' sense, but only if they are also nothrow, eg to add to the above example:
>
> ---
> pure nothrow int baz (Foo f)
> {
>   return f.bar(2) + f.bar(2);
> }
> ---
>
>
Or a better example that could also be pure in the 'C' sense.

int baz (Foo f) pure nothrow
{
  return f.bar(f.a) + f.bar(f.a);
}


-- 
Iain Buclaw

*(p < e ? p++ : p) = (c & 0x0f) + '0';

On 8 April 2013 23:01, John Colvin <john.loughran.colvin@gmail.com> wrote:

> On Monday, 8 April 2013 at 12:39:58 UTC, Manu wrote:
>
>> On 8 April 2013 21:53, Iain Buclaw <ibuclaw@ubuntu.com> wrote:
>>
>>  On 8 April 2013 12:41, deadalnix <deadalnix@gmail.com> wrote:
>>>
>>>  On Monday, 8 April 2013 at 09:41:52 UTC, Iain Buclaw wrote:
>>>>
>>>>  It uses some type information, eg:
>>>>>
>>>>> const/immutable/wild  -> qualified const.
>>>>> shared -> qualified volatile.
>>>>> shared + const/wild -> qualified const/volatile.
>>>>>
>>>>>
>>>>>  const/wild can be muted via aliasing. I'm not sure how GCC's backend
>>>> understand const, but this seems unclear to me if this is correct.
>>>>
>>>>
>>>>  GCC's backend is pretty much C/C++ semantics.  So the const qualifier
>>> is
>>> shallow, and does not guarantee that no mutations will occur.
>>>
>>>
>> But D makes no further guarantee. I don't see how const in D is any different than const in C++ in that sense? That's basically the concept of const, it's not a useful concept for optimisation, only immutable is.
>>
>
> D const is transitive, surely that makes a difference/presents an opportunity?
>

No, I think that just makes it 'safer', or as many might say, "more annoying" ;)

Casting away D const is undefined behavior. It is still not for single-threaded C++11 code AFAIK. That may make an important difference for optimization opportunities.

On Monday, 8 April 2013 at 13:13:22 UTC, Dicebot wrote:
> Casting away D const is undefined behavior. It is still not for single-threaded C++11 code AFAIK. That may make an important difference for optimization opportunities.

Minor fix: It is undefined in C++11 to cast away const from pointer to data immutable by definition (like string literals), but that can't be known from function that accepts const argument.