On 10/25/10 8:44 CDT, Bruno Medeiros wrote:
> I think we need to be more realistic with what kinds of optimizations
> we could expect from a D compiler and pure functions.
> Caching might be done, but only a temporary sense (caching under a
> limited execution scope). I doubt we would ever have something like
> memoization, which would incur memory costs (potentially quite big
> ones), and so the compiler almost certainly would not be able to know
> (without additional metadata/anotations or compile options) if that
> trade-off is acceptable.

Speaking of which - memoization should be implementable safely and efficiently in a library. I'm thinking of something like this:

alias memoize!sin msin;
...
double x = msin(angle);

It does get tricky though. For example, for doubles you'd need to do some interpolation and there are several ways of interpolating. For other types you need to make sure there's no undue aliasing, etc.


Andrei

On 25/10/2010 13:46, Bruno Medeiros wrote:
>
> I'm confused: Isn't this essentially the same as the "partially pure"
> functions idea that was discussed as far back as 2008? And wasn't it
> agreed already that this would be the way things would work?
>
>

I've only now seen this additional post (that shows up out of it's thread in my ThunderBird) :

On 25/09/2010 03:53, Jason House wrote:
> It looks like your proposal was accepted. Walter just checked in changes to make this a reality. http://www.dsource.org/projects/dmd/changeset/687


I was getting worried otherwise

-- 
Bruno Medeiros - Software Engineer

Bruno Medeiros:

> Robert Jacques:
>> Weakly-pure functions, don't provide either of
> > these guarantees, but allow a much larger number of functions to be strongly-pure.
>> ...
> I think we need to be more realistic with what kinds of optimizations we could expect from a D compiler and pure functions.


Partally unrelated: in DMD 2.050 I think it's possible to have both std.algorithm.swap and std.algorithm.sort weakly pure. So I am able to sort data even in a strongly pure function :-) This is an important change.

Bye,
bearophile

Andrei:

> Speaking of which - memoization should be implementable safely and efficiently in a library. I'm thinking of something like this:
> 
> alias memoize!sin msin;
> ...
> double x = msin(angle);

Good.


> It does get tricky though. For example, for doubles you'd need to do some interpolation and there are several ways of interpolating. For other types you need to make sure there's no undue aliasing, etc.

Not good. Please keep things simple. If the programmer wants to use floats, then it's not the job of the memoizing function to define tolerances, etc.

If you want to add other features to a memoizing function, here are two useful features:
- An optional max number of items stored in the cache, using a LRU strategy (Python 3.2 standard library has this).
- An optional max number of bytes used by the cache (this is not present in Python std lib, but I have found this useful).

The first feature (max number of items using LRU) may be done wrapping the associative array keys inside a linked list.

Bye,
bearophile

Bruno Medeiros wrote:
> On 23/09/2010 23:39, Robert Jacques wrote:
>> On Thu, 23 Sep 2010 16:35:23 -0400, Tomek Sowiński <just@ask.me> wrote:
>>>
>>> On topic: this means a pure function can take a reference to data that
>>> can be mutated by
>>> someone else. So we're giving up on the "can parallelize with no
>>> dataraces" guarantee on
>>> pure functions?
>>>
>>
>> In short, No. In long; the proposal is for pure functions become broken
>> up into two groups (weak and strong) based on their function signatures.
>> This division is internal to the compiler, and isn't expressed in the
>> language in any way. Strongly-pure functions provide all the guarantees
>> that pure does today and can be automatically parallelized or cached
>> without consequence. Weakly-pure functions, don't provide either of
>> these guarantees, but allow a much larger number of functions to be
>> strongly-pure. In order to guarantee a function is strongly pure, one
>> would have to declare all its inputs immutable or use an appropriate
>> template constraint.
> 
> I think we need to be more realistic with what kinds of optimizations
> we could expect from a D compiler and pure functions.
> Caching might be done, but only a temporary sense (caching under a limited execution scope). I doubt we would ever have something like memoization, which would incur memory costs (potentially quite big ones), and so the compiler almost certainly would not be able to know (without additional metadata/anotations or compile options) if that trade-off is acceptable.
> 
> Similarly for parallelism, how would the compiler know that it's ok to spawn 10 or 100 new threads to parallelize the execution of some loop?
> The consequences for program and whole-machine scheduling would not be trivial and easy to understand. For this to happen, amongst other things the compiler and OS would need to ensure that the spawned threads would not starve the rest of the threads of that program.
> I suspect all these considerations might be very difficult to guarantee on a non-VM environment.

I agree with this, especially with regard to memoization.
However, several other very interesting optimisations are
possible with pure, especially with regard to memory allocation.

At exit from an immutably pure function, all memory allocated by that function and its subfunctions can be collected, except for anything which is reachable through the function return value.
Even for a weakly-pure function, the set of roots for gc is limited to
the mutable function parameters and the return value.
And for all pure functions with no mutable reference parameters, it is guaranteed that no other thread has access to them.

The implications for gc are very interesting.

On Mon, 25 Oct 2010 09:44:14 -0400, Bruno Medeiros <brunodomedeiros+spam@com.gmail> wrote:

> On 23/09/2010 23:39, Robert Jacques wrote:
>> On Thu, 23 Sep 2010 16:35:23 -0400, Tomek Sowiński <just@ask.me> wrote:
>>>
>>> On topic: this means a pure function can take a reference to data that
>>> can be mutated by
>>> someone else. So we're giving up on the "can parallelize with no
>>> dataraces" guarantee on
>>> pure functions?
>>>
>>
>> In short, No. In long; the proposal is for pure functions become broken
>> up into two groups (weak and strong) based on their function signatures.
>> This division is internal to the compiler, and isn't expressed in the
>> language in any way. Strongly-pure functions provide all the guarantees
>> that pure does today and can be automatically parallelized or cached
>> without consequence. Weakly-pure functions, don't provide either of
>> these guarantees, but allow a much larger number of functions to be
>> strongly-pure. In order to guarantee a function is strongly pure, one
>> would have to declare all its inputs immutable or use an appropriate
>> template constraint.
>
> I think we need to be more realistic with what kinds of optimizations
> we could expect from a D compiler and pure functions.
> Caching might be done, but only a temporary sense (caching under a limited execution scope). I doubt we would ever have something like memoization, which would incur memory costs (potentially quite big ones), and so the compiler almost certainly would not be able to know (without additional metadata/anotations or compile options) if that trade-off is acceptable.
>
> Similarly for parallelism, how would the compiler know that it's ok to spawn 10 or 100 new threads to parallelize the execution of some loop?
> The consequences for program and whole-machine scheduling would not be trivial and easy to understand. For this to happen, amongst other things the compiler and OS would need to ensure that the spawned threads would not starve the rest of the threads of that program.
> I suspect all these considerations might be very difficult to guarantee on a non-VM environment.
>

Ahem, it's trivial for the compiler to know if it's okay to spawn 10 or 100 _tasks_. Tasks, as opposed to threads or even thread pools, are extremely cheap (think on the order of function call overhead).

On 26/10/2010 03:07, Don wrote:
> Bruno Medeiros wrote:
>> On 23/09/2010 23:39, Robert Jacques wrote:
>>> On Thu, 23 Sep 2010 16:35:23 -0400, Tomek Sowiński <just@ask.me> wrote:
>>>>
>>>> On topic: this means a pure function can take a reference to data that
>>>> can be mutated by
>>>> someone else. So we're giving up on the "can parallelize with no
>>>> dataraces" guarantee on
>>>> pure functions?
>>>>
>>>
>>> In short, No. In long; the proposal is for pure functions become broken
>>> up into two groups (weak and strong) based on their function signatures.
>>> This division is internal to the compiler, and isn't expressed in the
>>> language in any way. Strongly-pure functions provide all the guarantees
>>> that pure does today and can be automatically parallelized or cached
>>> without consequence. Weakly-pure functions, don't provide either of
>>> these guarantees, but allow a much larger number of functions to be
>>> strongly-pure. In order to guarantee a function is strongly pure, one
>>> would have to declare all its inputs immutable or use an appropriate
>>> template constraint.
>>
>> I think we need to be more realistic with what kinds of optimizations
>> we could expect from a D compiler and pure functions.
>> Caching might be done, but only a temporary sense (caching under a
>> limited execution scope). I doubt we would ever have something like
>> memoization, which would incur memory costs (potentially quite big
>> ones), and so the compiler almost certainly would not be able to know
>> (without additional metadata/anotations or compile options) if that
>> trade-off is acceptable.
>>
>> Similarly for parallelism, how would the compiler know that it's ok to
>> spawn 10 or 100 new threads to parallelize the execution of some loop?
>> The consequences for program and whole-machine scheduling would not be
>> trivial and easy to understand. For this to happen, amongst other
>> things the compiler and OS would need to ensure that the spawned
>> threads would not starve the rest of the threads of that program.
>> I suspect all these considerations might be very difficult to
>> guarantee on a non-VM environment.
>
> I agree with this, especially with regard to memoization.
> However, several other very interesting optimisations are
> possible with pure, especially with regard to memory allocation.
>
> At exit from an immutably pure function, all memory allocated by that
> function and its subfunctions can be collected, except for anything
> which is reachable through the function return value.
> Even for a weakly-pure function, the set of roots for gc is limited to
> the mutable function parameters and the return value.
> And for all pure functions with no mutable reference parameters, it is
> guaranteed that no other thread has access to them.
>
> The implications for gc are very interesting.

Indeed, this opens up several possibilities, it will be interesting to see what else pure can give us in terms of optimization. (I'm not a compiler or low level optimization expert, so my imagination here is somewhat limited :P )

Even for the optimizations that should not be applied completely automatically (the aforementioned parallelization, memoization) it is nice to have a language mechanism to verify their safety.

-- 
Bruno Medeiros - Software Engineer

On 26/10/2010 04:47, Robert Jacques wrote:
> On Mon, 25 Oct 2010 09:44:14 -0400, Bruno Medeiros
> <brunodomedeiros+spam@com.gmail> wrote:
>
>> On 23/09/2010 23:39, Robert Jacques wrote:
>>> On Thu, 23 Sep 2010 16:35:23 -0400, Tomek Sowiński <just@ask.me> wrote:
>>>>
>>>> On topic: this means a pure function can take a reference to data that
>>>> can be mutated by
>>>> someone else. So we're giving up on the "can parallelize with no
>>>> dataraces" guarantee on
>>>> pure functions?
>>>>
>>>
>>> In short, No. In long; the proposal is for pure functions become broken
>>> up into two groups (weak and strong) based on their function signatures.
>>> This division is internal to the compiler, and isn't expressed in the
>>> language in any way. Strongly-pure functions provide all the guarantees
>>> that pure does today and can be automatically parallelized or cached
>>> without consequence. Weakly-pure functions, don't provide either of
>>> these guarantees, but allow a much larger number of functions to be
>>> strongly-pure. In order to guarantee a function is strongly pure, one
>>> would have to declare all its inputs immutable or use an appropriate
>>> template constraint.
>>
>> I think we need to be more realistic with what kinds of optimizations
>> we could expect from a D compiler and pure functions.
>> Caching might be done, but only a temporary sense (caching under a
>> limited execution scope). I doubt we would ever have something like
>> memoization, which would incur memory costs (potentially quite big
>> ones), and so the compiler almost certainly would not be able to know
>> (without additional metadata/anotations or compile options) if that
>> trade-off is acceptable.
>>
>> Similarly for parallelism, how would the compiler know that it's ok to
>> spawn 10 or 100 new threads to parallelize the execution of some loop?
>> The consequences for program and whole-machine scheduling would not be
>> trivial and easy to understand. For this to happen, amongst other
>> things the compiler and OS would need to ensure that the spawned
>> threads would not starve the rest of the threads of that program.
>> I suspect all these considerations might be very difficult to
>> guarantee on a non-VM environment.
>>
>
> Ahem, it's trivial for the compiler to know if it's okay to spawn 10 or
> 100 _tasks_. Tasks, as opposed to threads or even thread pools, are
> extremely cheap (think on the order of function call overhead).

What are these tasks you mention? I've never heard of them.

-- 
Bruno Medeiros - Software Engineer

On Thu, 28 Oct 2010 10:48:34 -0400, Bruno Medeiros <brunodomedeiros+spam@com.gmail> wrote:
> On 26/10/2010 04:47, Robert Jacques wrote:
>> On Mon, 25 Oct 2010 09:44:14 -0400, Bruno Medeiros
>> <brunodomedeiros+spam@com.gmail> wrote:
>>
>>> On 23/09/2010 23:39, Robert Jacques wrote:
>>>> On Thu, 23 Sep 2010 16:35:23 -0400, Tomek Sowiński <just@ask.me> wrote:
>>>>>
>>>>> On topic: this means a pure function can take a reference to data that
>>>>> can be mutated by
>>>>> someone else. So we're giving up on the "can parallelize with no
>>>>> dataraces" guarantee on
>>>>> pure functions?
>>>>>
>>>>
>>>> In short, No. In long; the proposal is for pure functions become broken
>>>> up into two groups (weak and strong) based on their function signatures.
>>>> This division is internal to the compiler, and isn't expressed in the
>>>> language in any way. Strongly-pure functions provide all the guarantees
>>>> that pure does today and can be automatically parallelized or cached
>>>> without consequence. Weakly-pure functions, don't provide either of
>>>> these guarantees, but allow a much larger number of functions to be
>>>> strongly-pure. In order to guarantee a function is strongly pure, one
>>>> would have to declare all its inputs immutable or use an appropriate
>>>> template constraint.
>>>
>>> I think we need to be more realistic with what kinds of optimizations
>>> we could expect from a D compiler and pure functions.
>>> Caching might be done, but only a temporary sense (caching under a
>>> limited execution scope). I doubt we would ever have something like
>>> memoization, which would incur memory costs (potentially quite big
>>> ones), and so the compiler almost certainly would not be able to know
>>> (without additional metadata/anotations or compile options) if that
>>> trade-off is acceptable.
>>>
>>> Similarly for parallelism, how would the compiler know that it's ok to
>>> spawn 10 or 100 new threads to parallelize the execution of some loop?
>>> The consequences for program and whole-machine scheduling would not be
>>> trivial and easy to understand. For this to happen, amongst other
>>> things the compiler and OS would need to ensure that the spawned
>>> threads would not starve the rest of the threads of that program.
>>> I suspect all these considerations might be very difficult to
>>> guarantee on a non-VM environment.
>>>
>>
>> Ahem, it's trivial for the compiler to know if it's okay to spawn 10 or
>> 100 _tasks_. Tasks, as opposed to threads or even thread pools, are
>> extremely cheap (think on the order of function call overhead).
>
> What are these tasks you mention? I've never heard of them.
>

The programming language Cilk popularized the concept of parallelization through many small tasks combined with a work stealing runtime. Futures are essentially the same concept, but because futures were generally implemented with OS-threads, a thread pool or fibers/coroutines, that term is generally avoided. Like message passing, tasks are often implemented in libraries with Intel's threading building blocks probably being the most famous, though both Microsoft's Task Parallel Library and Apple's Grand Central are gaining mind-share. David Simcha currently has a task library in review for inclusion to phobos. Basically, the point of tasks is to provide parallelization with extremely low overhead (on average a Cilk spawn is less than 4 function calls). That way, instead of having a few coarse grain threads which neither scale nor load balance well, you're encouraged to use tasks everywhere and therefore reap the benefits of a balanced N-way scalable system. Getting back to pure, one of the "big" advantages of functional languages are their ability to automatically parallelize themselves; and they use a work stealing runtime (aka tasks) to do this.

Robert Jacques Wrote:

> Getting back to pure, one of the "big" advantages of functional languages are their ability to automatically parallelize themselves; and they use a work stealing runtime (aka tasks) to do this.

What functional has task? I switch in Meantime when D2 not staple to study this.