Proposal: Relax rules for 'pure'

[Robert Jacques]

On Mon, 25 Oct 2010 09:44:14 -0400, Bruno Medeiros  
<brunodomedeiros+spam at 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 at 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).