On 11/17/2013 02:55 AM, Jonathan M Davis wrote:

> And since additional calls to strongly pure functions are only optimized out
> within a single expression (or maybe statement - I'm not sure which - but
> certainly not across multiple statements), it's not like calls to strongly
> pure functions can be optimized out very often anyway.

I don't see why not.

    if (pure_func(a)) {
        // ...
    }

    // assume 'a' is not mutated here

    if (pure_func(a)) {
        // ...
    }

There is no reason why pure_func(a) cannot be executed only once, right?

Ali

On Sunday, November 17, 2013 08:46:49 Ali Çehreli wrote:
> On 11/17/2013 02:55 AM, Jonathan M Davis wrote:
>  > And since additional calls to strongly pure functions are only
> 
> optimized out
> 
>  > within a single expression (or maybe statement - I'm not sure which - but
>  > certainly not across multiple statements), it's not like calls to
> 
> strongly
> 
>  > pure functions can be optimized out very often anyway.
> 
> I don't see why not.
> 
>      if (pure_func(a)) {
>          // ...
>      }
> 
>      // assume 'a' is not mutated here
> 
>      if (pure_func(a)) {
>          // ...
>      }
> 
> There is no reason why pure_func(a) cannot be executed only once, right?

The reason would be that the compiler doesn't do flow analysis and as I understand it, it makes zero attempt to optimize calls to pure functions outside of an expression. So,

auto foo = pure_func(a) * pure_func(a);

should result in only one call to pure_func, but something like

auto foo = pure_func(a);
auto bar = pure_func(a);

will definitely result in multiple calls to pure_func. It's not that it's impossible for the compiler to do it - it's perfectly possible. But doing so would require at least basic code flow analysis, and dmd almost never does any kind of code flow analysis.

So, a smarter compiler could optimize calls to strongly pure functions more than dmd does, but even then, I question that you'd get much optimized outside of example code, because I don't think that it's all that common for the same function to be called multiple times with the same arguments within a function - and you certainly can't save the result for use outside of a function, because that would mean compiler-generated memoization, which would would require storing the results of all of those function calls somewhere.

- Jonathan M Davis

On 11/17/2013 12:59 PM, Jonathan M Davis wrote:

> On Sunday, November 17, 2013 08:46:49 Ali Çehreli wrote:

>> There is no reason why pure_func(a) cannot be executed only once, right?
>
> The reason would be that the compiler doesn't do flow analysis

Cool. I thought that you meant a technical impossibility. :)

Ali

On Sunday, 17 November 2013 at 21:00:16 UTC, Jonathan M Davis wrote:
> will definitely result in multiple calls to pure_func. It's not that it's
> impossible for the compiler to do it - it's perfectly possible. But doing so
> would require at least basic code flow analysis, and dmd almost never does any
> kind of code flow analysis.

I remember Walter being against flow analysis in the frontend. This is middleend optimization stuff, though. Does dmd really use no data flow analysis anywhere?

On Monday, November 18, 2013 08:22:37 qznc wrote:
> On Sunday, 17 November 2013 at 21:00:16 UTC, Jonathan M Davis
> 
> wrote:
> > will definitely result in multiple calls to pure_func. It's not
> > that it's
> > impossible for the compiler to do it - it's perfectly possible.
> > But doing so
> > would require at least basic code flow analysis, and dmd almost
> > never does any
> > kind of code flow analysis.
> 
> I remember Walter being against flow analysis in the frontend. This is middleend optimization stuff, though. Does dmd really use no data flow analysis anywhere?

It has very, very limited flow analysis that it uses in constructors to avoid multiple calls to super as well as guaranteeing that nothing gets initialized multiple times in a const or immutable constructor. It may also does some very minimal flow analysis when dealing with value range propagation ( http://www.drdobbs.com/tools/value-range-propagation/229300211 ). It may also do some minimal checks for missing return statements. But it general, no, it doesn't do flow analysis, and when it does, it's very minimal. Walter does not consider it to be worth the complexity that it requires.

And while in this particular case, it would certainly be much nicer for repeated calls to a pure function to be optimized within an entire function instead of just within an expression, I don't think that it actually ends up mattering much in practice, simply because it's generally rare to make the exact same call multiple times within a function. And if you do, it's trivial to save the result in a variable to be reused.

> This is middleend optimization stuff, though.

I'm not quite sure what you mean by this. There is no middle-end. We have the front-end, which is shared by dmd, gdc, and ldc, and then each compiler has its own backend. Anything D-specific is done in the front-end. So, if there are any D-specific optimizations (such as optimizations related to pure), they need to be in the front-end.

- Jonathan M Davis

18-Nov-2013 11:37, Jonathan M Davis пишет:
> On Monday, November 18, 2013 08:22:37 qznc wrote:
>> On Sunday, 17 November 2013 at 21:00:16 UTC, Jonathan M Davis
>>
>> wrote:
>>> will definitely result in multiple calls to pure_func. It's not
>>> that it's
>>> impossible for the compiler to do it - it's perfectly possible.
>>> But doing so
>>> would require at least basic code flow analysis, and dmd almost
>>> never does any
>>> kind of code flow analysis.
>>
>> I remember Walter being against flow analysis in the frontend.
>> This is middleend optimization stuff, though. Does dmd really use
>> no data flow analysis anywhere?
>

The backend, of course:

https://github.com/D-Programming-Language/dmd/blob/master/src/backend/gflow.c

> It has very, very limited flow analysis that it uses in constructors to avoid
> multiple calls to super as well as guaranteeing that nothing gets initialized
> multiple times in a const or immutable constructor. It may also does some very
> minimal flow analysis when dealing with value range propagation (
> http://www.drdobbs.com/tools/value-range-propagation/229300211 ). It may also
> do some minimal checks for missing return statements. But it general, no, it
> doesn't do flow analysis, and when it does, it's very minimal. Walter does not
> consider it to be worth the complexity that it requires.

I think it was about doing it in the frontend.

> And while in this particular case, it would certainly be much nicer for
> repeated calls to a pure function to be optimized within an entire function
> instead of just within an expression, I don't think that it actually ends up
> mattering much in practice, simply because it's generally rare to make the
> exact same call multiple times within a function. And if you do, it's trivial
> to save the result in a variable to be reused.


-- 
Dmitry Olshansky

On Monday, 18 November 2013 at 07:37:27 UTC, Jonathan M Davis wrote:
>> This is middleend optimization stuff, though.
>
> I'm not quite sure what you mean by this. There is no middle-end. We have the
> front-end, which is shared by dmd, gdc, and ldc, and then each compiler has
> its own backend. Anything D-specific is done in the front-end. So, if there are
> any D-specific optimizations (such as optimizations related to pure), they need
> to be in the front-end.

For me, middle-end is stuff, which is neither specific to input language nor to output OS/architecture/runtime. Effectively, all compiler optimizations which are useful everywhere. Maybe this view is a little outdated, since most people consider LLVM has simply a backend, while I would consider it middle- and backend of a compiler.

On Sunday, 17 November 2013 at 10:56:16 UTC, Jonathan M Davis wrote:
>
> I think that the typical approach at this point is to just drop purity for the
> moment, but if you want you really want it, you are indeed going to have to
> implement it yourself. But we'll get there with Phobos eventually. The primary
> holdup is some compiler improvements, and we'll get them. It's just a question
> of when.
>
> - Jonathan M Davis

Why is it that compiler improvements are the holdup? Honest question. Is it more that the approach taken for the specific implementation went beyond the capabilities of the compiler at the time (like its inferencing capabilities)? Maybe purity was not a focus at the time of writing a lot of phobos and there are not loads of testing on it where purity was a factor. If so, isn't an alternative implementation now an improvement over waiting for the compiler updates. A corollary question would be are the benefits of Voldermort types in phobos worth the purity issues they cause?

From this article (http://www.drdobbs.com/cpp/voldemort-types-in-d/232901591) Walter says, regarding the pre-Voldermort version of RandomNumberGenerator:

"I could mark it with the private attribute and modules other than rnd won't be able to access it. But it's still there, outside the scope of where it belongs, and other module members can still access it, private or not (in D, private declarations are not hidden from other declarations within the same module). Besides, I want it to be so clean it squeaks."

Noble goal - maybe. But maybe not as noble as users' efforts to realize benefits of purity now. Purity/const/immutable when broken spread virally.

Thanks
Dan

On Monday, November 18, 2013 19:16:11 Daniel Davidson wrote:
> On Sunday, 17 November 2013 at 10:56:16 UTC, Jonathan M Davis
> 
> wrote:
> > I think that the typical approach at this point is to just drop
> > purity for the
> > moment, but if you want you really want it, you are indeed
> > going to have to
> > implement it yourself. But we'll get there with Phobos
> > eventually. The primary
> > holdup is some compiler improvements, and we'll get them. It's
> > just a question
> > of when.
> > 
> > - Jonathan M Davis
> 
> Why is it that compiler improvements are the holdup? Honest question. Is it more that the approach taken for the specific implementation went beyond the capabilities of the compiler at the time (like its inferencing capabilities)? Maybe purity was not a focus at the time of writing a lot of phobos and there are not loads of testing on it where purity was a factor.

Attribute inferrence was added to the language specifically in order to make it possible for pure, nothrow, and @safe to work with templates and therefore make it possible to use them with Phobos. Without it, they don't, because you're stuck either requiring a specific set of attributes (limiting what the templates work with) or duplicating the templates with different combinations of attributes. We got enough attribute inferrence to reduce the problem, but the feature has yet to be implemented enough to fully fix the problem. It's compiler improvements which made using pure with std.algorithm possible at all.

> If so,
> isn't an alternative implementation now an improvement over
> waiting for the compiler updates. A corollary question would be
> are the benefits of Voldermort types in phobos worth the purity
> issues they cause?

Voldemort types are just part of the problem. Attribute inferrence is just plain too primitive right now, and really needs to be improved. The problem is reduced if you don't used Voldemort types, but it's not fixed.

> Noble goal - maybe. But maybe not as noble as users' efforts to realize benefits of purity now. Purity/const/immutable when broken spread virally.

It's also the case that none of that has ever worked with pure, so we haven't lost anything. We just haven't yet gained what we should have gained. But the push really needs to be to improve the compiler IMHO, because without that, attribute inferrence in general just isn't going to be good enough, and if Phobos' current situation highlights how poor the attribute inferrence is, all the better, because that puts more pressure on getting it fixed.

Some of the newer functions have not used Voldemort types in order to fix similar problems, but I don't think that it's worth going and changing them all just to work around a problem with the compiler. The compiler needs to be fixed. At best, what you're talking about doing is contorting Phobos' implementation in order to make it work better with the half-implemented feature of attribute inferrence, but since it's that feature that makes it possible at all, and it really needs to be fully implemented regardless, it makes by far the most sense IMHO to just finish implementing it. But when that happens is up to the compiler devs, and at this point, I'm a library dev, not a compiler dev.

- Jonathan M Davis

On Monday, 18 November 2013 at 19:52:42 UTC, Jonathan M Davis wrote:
> On Monday, November 18, 2013 19:16:11 Daniel Davidson wrote:
>> On Sunday, 17 November 2013 at 10:56:16 UTC, Jonathan M Davis
>> 
>> wrote:
>> > I think that the typical approach at this point is to just drop
>> > purity for the
>> > moment, but if you want you really want it, you are indeed
>> > going to have to
>> > implement it yourself. But we'll get there with Phobos
>> > eventually. The primary
>> > holdup is some compiler improvements, and we'll get them. It's
>> > just a question
>> > of when.
>> > 
>> > - Jonathan M Davis
>> 
>> Why is it that compiler improvements are the holdup? Honest
>> question. Is it more that the approach taken for the specific
>> implementation went beyond the capabilities of the compiler at
>> the time (like its inferencing capabilities)? Maybe purity was
>> not a focus at the time of writing a lot of phobos and there are
>> not loads of testing on it where purity was a factor.
>
> Attribute inferrence was added to the language specifically in order to make it
> possible for pure, nothrow, and @safe to work with templates and therefore
> make it possible to use them with Phobos. Without it, they don't, because
> you're stuck either requiring a specific set of attributes (limiting what the
> templates work with) or duplicating the templates with different combinations
> of attributes. We got enough attribute inferrence to reduce the problem, but
> the feature has yet to be implemented enough to fully fix the problem. It's
> compiler improvements which made using pure with std.algorithm possible at
> all.
>
>> If so,
>> isn't an alternative implementation now an improvement over
>> waiting for the compiler updates. A corollary question would be
>> are the benefits of Voldermort types in phobos worth the purity
>> issues they cause?
>
> Voldemort types are just part of the problem. Attribute inferrence is just
> plain too primitive right now, and really needs to be improved. The problem is
> reduced if you don't used Voldemort types, but it's not fixed.
>
>> Noble goal - maybe. But maybe not as noble as users' efforts to
>> realize benefits of purity now. Purity/const/immutable when
>> broken spread virally.
>
> It's also the case that none of that has ever worked with pure, so we haven't
> lost anything. We just haven't yet gained what we should have gained. But the
> push really needs to be to improve the compiler IMHO, because without that,
> attribute inferrence in general just isn't going to be good enough, and if
> Phobos' current situation highlights how poor the attribute inferrence is, all
> the better, because that puts more pressure on getting it fixed.
>
> Some of the newer functions have not used Voldemort types in order to fix
> similar problems, but I don't think that it's worth going and changing them
> all just to work around a problem with the compiler. The compiler needs to be
> fixed. At best, what you're talking about doing is contorting Phobos'
> implementation in order to make it work better with the half-implemented
> feature of attribute inferrence, but since it's that feature that makes it
> possible at all, and it really needs to be fully implemented regardless, it
> makes by far the most sense IMHO to just finish implementing it. But when that
> happens is up to the compiler devs, and at this point, I'm a library dev, not
> a compiler dev.
>
> - Jonathan M Davis


I opened a new pull request to fix the compiler issue.

https://github.com/D-Programming-Language/dmd/pull/2832

Kenji Hara