March 05, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Regan Heath | Regan Heath wrote:
> If the input to the function is not known till runtime, how is this possible?
> Example:
>
> void uppercase(char[] line) {}
Uppercase is not a pure function if it modifies its argument, so this optimization is not applicable to it.
But if you have such a function return a new string, then you could prove it would return a string with the same contents and reuse the previously returned string instead of another function call.
-eye
|
March 05, 2005 Pure functions (Re: Stable functions) | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ilya Minkov | Ilya Minkov schrieb:
> Another question is whether they belong in the declaration. One can argue, that, given the source, the compiler can detect these automatically during whole-program compilation.
Still, the code would be somewhat cleaner if it had to be specified explicitely. You immediately see that a function is intended to be pure and the compiler can check this a the time of definition of the function.
Basically, it is the same for all interface declarations: The compiler could very often determine the interface from reading the definition, but it cleans up the design phase a lot and improves the quality of the code if the interface gives all the crucial information and the compiler can then check whether the implementation actually does what the interface promises.
|
March 05, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick Sabalausky | Nick Sabalausky schrieb:
> Isn't this more of a compiler optimization than a language feature though?
Not really: the question is, whether you can use pure functions in places where a constant is expected:
const double pi = asin(1)*2;
const int DIM = myfunc(17);
MyArrayClass!(DIM,float) someobject;
|
March 07, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ilya Minkov | On Sat, 05 Mar 2005 19:09:49 +0100, Ilya Minkov <minkov@cs.tum.edu> wrote:
> Regan Heath wrote:
>
>> If the input to the function is not known till runtime, how is this possible?
>> Example:
>> void uppercase(char[] line) {}
>
> Uppercase is not a pure function if it modifies its argument, so this optimization is not applicable to it.
>
> But if you have such a function return a new string, then you could prove it would return a string with the same contents and reuse the previously returned string instead of another function call.
How can you do that at compile time, without the input to test it with?
Regan
|
March 07, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Regan Heath | Regan Heath schrieb:
> On Sat, 05 Mar 2005 19:09:49 +0100, Ilya Minkov <minkov@cs.tum.edu> wrote:
>
>> Regan Heath wrote:
>> Uppercase is not a pure function if it modifies its argument, so this
>> optimization is not applicable to it.
>>
>> But if you have such a function return a new string, then you could prove it would return a string with the same contents and reuse the previously returned string instead of another function call.
>
>
> How can you do that at compile time, without the input to test it with?
There are two possibilities for optimization here:
1. Uppercase is called on constants in the code. In that case, the result can be evaluated at compile time.
2. Uppercase is called multiple times on the same input. In that case, the result can be cached.
Example:
char[] printUpper(char[] str)
{
writef("%s", uppercase(str));
return uppercase(str); // This result could be cached!
}
-Sebastian
|
March 07, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sebastian Beschke | On Mon, 07 Mar 2005 10:12:29 +0100, Sebastian Beschke <s.beschke@gmx.de> wrote:
> Regan Heath schrieb:
>> On Sat, 05 Mar 2005 19:09:49 +0100, Ilya Minkov <minkov@cs.tum.edu> wrote:
>>
>>> Regan Heath wrote:
>>> Uppercase is not a pure function if it modifies its argument, so this
>>> optimization is not applicable to it.
>>>
>>> But if you have such a function return a new string, then you could
>>> prove it would return a string with the same contents and reuse the
>>> previously returned string instead of another function call.
>>
>>
>> How can you do that at compile time, without the input to test it with?
>
> There are two possibilities for optimization here:
>
> 1. Uppercase is called on constants in the code. In that case, the
> result can be evaluated at compile time.
>
> 2. Uppercase is called multiple times on the same input. In that case,
> the result can be cached.
What input!?! It's unknown until runtime. The OP's suggestion was for a compile time feature, and by compile time he did not mean JIT compile. Am I not making myself clear somehow??
Regan
|
March 07, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Regan Heath | Regan Heath schrieb:
> On Mon, 07 Mar 2005 10:12:29 +0100, Sebastian Beschke <s.beschke@gmx.de> wrote:
>
>> There are two possibilities for optimization here:
>>
>> 1. Uppercase is called on constants in the code. In that case, the result can be evaluated at compile time.
>>
>> 2. Uppercase is called multiple times on the same input. In that case, the result can be cached.
>
>
> What input!?! It's unknown until runtime. The OP's suggestion was for a compile time feature, and by compile time he did not mean JIT compile. Am I not making myself clear somehow??
Well, optimization 2 could also be performed at compile time. For example, the code I mentioned:
char[] printUpper(char[] str)
{
writef("%s", uppercase(str));
return uppercase(str); // This result could be cached!
}
could be optimized at compile time to:
char[] printUpper(char[] str)
{
char[] temp = uppercase(str);
writef("%s", temp);
return temp; // This result could be cached!
}
Of course, you can't eliminate the first call to the function, except maybe in the case where the printUpper() function is called with a constant argument - dunno how hard this is to do.
-Sebastian
|
March 07, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Sebastian Beschke | On Mon, 07 Mar 2005 13:10:17 +0100, Sebastian Beschke <s.beschke@gmx.de> wrote:
> Regan Heath schrieb:
>> On Mon, 07 Mar 2005 10:12:29 +0100, Sebastian Beschke
>> <s.beschke@gmx.de> wrote:
>>
>>> There are two possibilities for optimization here:
>>>
>>> 1. Uppercase is called on constants in the code. In that case, the
>>> result can be evaluated at compile time.
>>>
>>> 2. Uppercase is called multiple times on the same input. In that case,
>>> the result can be cached.
>>
>>
>> What input!?! It's unknown until runtime. The OP's suggestion was for a
>> compile time feature, and by compile time he did not mean JIT compile.
>> Am I not making myself clear somehow??
>
> Well, optimization 2 could also be performed at compile time. For
> example, the code I mentioned:
>
> char[] printUpper(char[] str)
> {
> writef("%s", uppercase(str));
> return uppercase(str); // This result could be cached!
> }
>
> could be optimized at compile time to:
>
> char[] printUpper(char[] str)
> {
> char[] temp = uppercase(str);
> writef("%s", temp);
> return temp; // This result could be cached!
> }
>
> Of course, you can't eliminate the first call to the function, except
> maybe in the case where the printUpper() function is called with a
> constant argument - dunno how hard this is to do.
So, what you're suggesting is that the program keeps a list of all arguments to every function, and records the result, then, if it gets the same argument to a function it simply returns the result it got last time.
So, if you're processing a 1,000,000 line file, with printUpper it will have 2,000,000 lines stored in memory somewhere?
Regan
|
March 08, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Martin M. Pedersen | Martin M. Pedersen wrote:
> "Andy Friesen" <andy@ikagames.com> skrev i en meddelelse news:d0969a$i1b$1@digitaldaemon.com...
>
>>Martin M. Pedersen wrote:
>>.NET's new generic facilities are another example: instead of emitting a container class that works on a specific element type, emit the generic skeleton, and recompile that (at runtime!) for specific types.
>
>
> Interesting. Does that mean that you can have run-time compilation errors?
No, the language restricts things in such a way that it can't happen. A side effect of this is that .NET generics aren't as flexible as C++ or D templates, as you have to explicitly constrain a generic type to an interface. (of course, they still kick the crap out of Java 5.0's pathetic generics)
-- andy
|
March 08, 2005 Re: Stable functions | ||||
---|---|---|---|---|
| ||||
Posted in reply to Regan Heath | Regan Heath wrote: > On Sat, 05 Mar 2005 19:09:49 +0100, Ilya Minkov <minkov@cs.tum.edu> wrote: > >> Regan Heath wrote: >> >>> If the input to the function is not known till runtime, how is this possible? >>> Example: >>> void uppercase(char[] line) {} >> >> >> Uppercase is not a pure function if it modifies its argument, so this optimization is not applicable to it. >> >> But if you have such a function return a new string, then you could prove it would return a string with the same contents and reuse the previously returned string instead of another function call. > > > How can you do that at compile time, without the input to test it with? There are a number of things the compiler could hypothetically do. // suppose uppercase is a pure function char[] uppercase(char[] str) { ... } // uppercase() call is interpreted at compile-time // same as "const char[] blah = "FOOBAR"; const char[] blah = uppercase("foobar"); void foo(char[] input) { char[] a = uppercase(input); // optimize to "char[] b = a.dup;" char[] b = uppercase(input); } int fibo(int i) { if (i < 2) return 1; else return fibo(i-1) + fibo(i-2); } // simpler than the template metaprogramming approach... const int f9 = fibo(9); The big question is how large the performance gains could be. Clean and O'Caml manage to beat out C frequently enough* that I can't help but think it may be worthwhile. :) * see <http://shootout.alioth.debian.org> -- andy |
Copyright © 1999-2021 by the D Language Foundation