Deterministic Proposal

classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

Deterministic Proposal

Guy Ellis
I have an idea rattling around that allowing the developer to mark a function as deterministic would allow the compiler to determine if a speed/memory memoization trade-off will improve performance.

Possible syntax:

deterministic function sum(a, b) { return a + b; }

Use case:

I can only think of one right now: compiler memoization

Why not a memoization library?

I'm not a compiler expert. I've read that today's compilers are doing optimizations at runtime based on call frequency and other metrics that they collect. If a compiler knows that a function is deterministic it will be able to use call time metrics against the return value size to determine if memoization should be done on specific calls.

I think (I could be completely wrong here) that the compiler has access to memory metrics that a memoization library would not have access to in order to optimize this on-the-fly.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

kdex
Can already be solved using decorators. Thus, no need for new syntax.
If we get a standard library to import some common decorators from, one could
easily write:

```js
import { memoize } from "std::decorators";
@memoize
function sum(a, b) {
        return a + b;
}
```

On Wednesday, June 21, 2017 12:58:43 AM CEST Guy Ellis wrote:

> I have an idea rattling around that allowing the developer to mark a
> function as deterministic would allow the compiler to determine if a
> speed/memory memoization trade-off will improve performance.
>
> Possible syntax:
>
> deterministic function sum(a, b) { return a + b; }
>
> Use case:
>
> I can only think of one right now: compiler memoization
>
> Why not a memoization library?
>
> I'm not a compiler expert. I've read that today's compilers are doing
> optimizations at runtime based on call frequency and other metrics that
> they collect. If a compiler knows that a function is deterministic it will
> be able to use call time metrics against the return value size to determine
> if memoization should be done on specific calls.
>
> I think (I could be completely wrong here) that the compiler has access to
> memory metrics that a memoization library would not have access to in order
> to optimize this on-the-fly.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

kdex
Also, "compiler memoization" may not necessarily be as useful as one might
think. It's a good thing to keep memoization abstract/parameterized, so if
anything, it should be defined via a (standard) library as a function, not via
syntax.

Think of it like this: It might be enough for your application only to memoize
the last `n` results. If you don't, depending on your function, you might be
blowing up memory rather quickly.

On Wednesday, June 21, 2017 1:03:20 AM CEST kdex wrote:

> Can already be solved using decorators. Thus, no need for new syntax.
> If we get a standard library to import some common decorators from, one
> could easily write:
>
> ```js
> import { memoize } from "std::decorators";
> @memoize
> function sum(a, b) {
> return a + b;
> }
> ```
>
> On Wednesday, June 21, 2017 12:58:43 AM CEST Guy Ellis wrote:
> > I have an idea rattling around that allowing the developer to mark a
> > function as deterministic would allow the compiler to determine if a
> > speed/memory memoization trade-off will improve performance.
> >
> > Possible syntax:
> >
> > deterministic function sum(a, b) { return a + b; }
> >
> > Use case:
> >
> > I can only think of one right now: compiler memoization
> >
> > Why not a memoization library?
> >
> > I'm not a compiler expert. I've read that today's compilers are doing
> > optimizations at runtime based on call frequency and other metrics that
> > they collect. If a compiler knows that a function is deterministic it will
> > be able to use call time metrics against the return value size to
> > determine
> > if memoization should be done on specific calls.
> >
> > I think (I could be completely wrong here) that the compiler has access to
> > memory metrics that a memoization library would not have access to in
> > order
> > to optimize this on-the-fly.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Guy Ellis
In reply to this post by kdex
@kdex I initially thought of decorators but did not know that there were plans for a standard library that compilers would be "aware of" and would be able to draw this from. Thanks!

On Tue, Jun 20, 2017 at 4:03 PM kdex <[hidden email]> wrote:
Can already be solved using decorators. Thus, no need for new syntax.
If we get a standard library to import some common decorators from, one could
easily write:

```js
import { memoize } from "std::decorators";
@memoize
function sum(a, b) {
        return a + b;
}
```

On Wednesday, June 21, 2017 12:58:43 AM CEST Guy Ellis wrote:
> I have an idea rattling around that allowing the developer to mark a
> function as deterministic would allow the compiler to determine if a
> speed/memory memoization trade-off will improve performance.
>
> Possible syntax:
>
> deterministic function sum(a, b) { return a + b; }
>
> Use case:
>
> I can only think of one right now: compiler memoization
>
> Why not a memoization library?
>
> I'm not a compiler expert. I've read that today's compilers are doing
> optimizations at runtime based on call frequency and other metrics that
> they collect. If a compiler knows that a function is deterministic it will
> be able to use call time metrics against the return value size to determine
> if memoization should be done on specific calls.
>
> I think (I could be completely wrong here) that the compiler has access to
> memory metrics that a memoization library would not have access to in order
> to optimize this on-the-fly._______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Guy Ellis
What was drawing me to this idea is that the compiler is already doing performance optimization and a typical performance optimization is memoization. If the compiler were aware that it could memoize the results of a function it could determine this on-the-fly in a way that a library would not be able to. i.e. the compiler has access to metrics that the library does not have access to. I'm theorizing that the compiler could significantly outperform a library based solution here. Do you think that there might be any validity to that theory?

On Tue, Jun 20, 2017 at 4:11 PM Guy Ellis <[hidden email]> wrote:
@kdex I initially thought of decorators but did not know that there were plans for a standard library that compilers would be "aware of" and would be able to draw this from. Thanks!

On Tue, Jun 20, 2017 at 4:03 PM kdex <[hidden email]> wrote:
Can already be solved using decorators. Thus, no need for new syntax.
If we get a standard library to import some common decorators from, one could
easily write:

```js
import { memoize } from "std::decorators";
@memoize
function sum(a, b) {
        return a + b;
}
```

On Wednesday, June 21, 2017 12:58:43 AM CEST Guy Ellis wrote:
> I have an idea rattling around that allowing the developer to mark a
> function as deterministic would allow the compiler to determine if a
> speed/memory memoization trade-off will improve performance.
>
> Possible syntax:
>
> deterministic function sum(a, b) { return a + b; }
>
> Use case:
>
> I can only think of one right now: compiler memoization
>
> Why not a memoization library?
>
> I'm not a compiler expert. I've read that today's compilers are doing
> optimizations at runtime based on call frequency and other metrics that
> they collect. If a compiler knows that a function is deterministic it will
> be able to use call time metrics against the return value size to determine
> if memoization should be done on specific calls.
>
> I think (I could be completely wrong here) that the compiler has access to
> memory metrics that a memoization library would not have access to in order
> to optimize this on-the-fly._______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

peter miller
In reply to this post by kdex
Hi,

> Think of it like this: It might be enough for your application only to  
> memoize
> the last `n` results. If you don't, depending on your function, you  
> might be
> blowing up memory rather quickly.
>

But I don't know how much memory my data uses or how much memory is  
available. So I don't know how quickly I'm blowing up memory. We need help  
with the environment with caching.

Peter

--
"There were drawings, and sheets of paper with writing on them, and it  
seemed that they were the sustenance of life, that here were the warlocks,  
almost the vehicles of destruction of man's life, but at the same time the  
very reason for his living." --- Maeve Gilmore/Titus Awakes.
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Jussi Kalliokoski
In reply to this post by Guy Ellis

deterministic function sum(a, b) { return a + b; }

Ironically, having the engine decide when to memoize would make the "deterministic" functions non-deterministic:

deterministic function foo(a, b) { return { a, b }; }
foo(1, 2) === foo(1, 2) // may or may not be true 


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Isiah Meadows-2
I'd like to note that even Haskell compilers (which can check for this
trivially) never memoize implicitly. They only memoize infinite data
structures.

As for this proposal, I see exactly zero benefit whatsoever. Engines
already cover the relevant optimization opportunity without this
(through type ICs), and it's often faster in practice to recalculate
than memoize based on argument.

The only time I have found memoization to be very useful is in one
specific case: lazy evaluation (run once). But that is constrained to
just evaluating a thunk and storing the result.
-----

Isiah Meadows
[hidden email]

Looking for web consulting? Or a new website?
Send me an email and we can get started.
www.isiahmeadows.com


On Wed, Jun 21, 2017 at 6:01 AM, Jussi Kalliokoski
<[hidden email]> wrote:

>
>> deterministic function sum(a, b) { return a + b; }
>
>
> Ironically, having the engine decide when to memoize would make the
> "deterministic" functions non-deterministic:
>
> deterministic function foo(a, b) { return { a, b }; }
> foo(1, 2) === foo(1, 2) // may or may not be true
>
>
> _______________________________________________
> es-discuss mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/es-discuss
>
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Michał Wadas
To be honest it's probably solvable using decorators with memoization.

If we ever have a decorators (any updates on proposal BTW?) language can have decorators with implementation-specific behaviour (eg. "functions decorated with @pure builtin decorator can be assumed by engine to not produce side effects and became a subject of lazy evaluation" or "@memorySizeCache(size) builtin decorator has semantics almost identical to builtin @cache decotor, but engine can drop entries in cache if it exceeds given treshold "). Fallback for other implementations would be of course no-op.



On Wed, Jun 21, 2017 at 5:34 PM, Isiah Meadows <[hidden email]> wrote:
I'd like to note that even Haskell compilers (which can check for this
trivially) never memoize implicitly. They only memoize infinite data
structures.

As for this proposal, I see exactly zero benefit whatsoever. Engines
already cover the relevant optimization opportunity without this
(through type ICs), and it's often faster in practice to recalculate
than memoize based on argument.

The only time I have found memoization to be very useful is in one
specific case: lazy evaluation (run once). But that is constrained to
just evaluating a thunk and storing the result.
-----

Isiah Meadows
[hidden email]

Looking for web consulting? Or a new website?
Send me an email and we can get started.
www.isiahmeadows.com


On Wed, Jun 21, 2017 at 6:01 AM, Jussi Kalliokoski
<[hidden email]> wrote:
>
>> deterministic function sum(a, b) { return a + b; }
>
>
> Ironically, having the engine decide when to memoize would make the
> "deterministic" functions non-deterministic:
>
> deterministic function foo(a, b) { return { a, b }; }
> foo(1, 2) === foo(1, 2) // may or may not be true
>
>
> _______________________________________________
> es-discuss mailing list
> [hidden email]
> https://mail.mozilla.org/listinfo/es-discuss
>
_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss


_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Andreas Rossberg-4
In reply to this post by Guy Ellis
On 21 June 2017 at 00:58, Guy Ellis <[hidden email]> wrote:
I have an idea rattling around that allowing the developer to mark a function as deterministic would allow the compiler to determine if a speed/memory memoization trade-off will improve performance.

Possible syntax:

deterministic function sum(a, b) { return a + b; }

Use case:

I can only think of one right now: compiler memoization

You probably mean "pure", not "deterministic", which has nothing to do with this. However, JavaScript is far, far too impure for any such annotation to ever make sense or enable any sort of memoization. Consider

let i = 0
let o = {valueOf() {return i++}}
sum(o, 0)
sum(o, 0)

 On 21 June 2017 at 17:34, Isiah Meadows <[hidden email]> wrote:
I'd like to note that even Haskell compilers (which can check for this
trivially) never memoize implicitly. They only memoize infinite data
structures.

[...]

The only time I have found memoization to be very useful is in one
specific case: lazy evaluation (run once). But that is constrained to
just evaluating a thunk and storing the result.

I think you are confused. Laziness and memoization are different mechanisms. And neither takes the finiteness of a data structure into account.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Bradley Meck
You probably mean "pure", not "deterministic", which has nothing to do with this. However, JavaScript is far, far too impure for any such annotation to ever make sense or enable any sort of memoization. Consider
let i = 0
let o = {valueOf() {return i++}}
sum(o, 0)
sum(o, 0)

If type coercion was disabled within "pure" functions I am not sure this would be a problem.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Andreas Rossberg-4
On 21 June 2017 at 18:40, Bradley Meck <[hidden email]> wrote:
You probably mean "pure", not "deterministic", which has nothing to do with this. However, JavaScript is far, far too impure for any such annotation to ever make sense or enable any sort of memoization. Consider
let i = 0
let o = {valueOf() {return i++}}
sum(o, 0)
sum(o, 0)

If type coercion was disabled within "pure" functions I am not sure this would be a problem.

A new language mode with modified semantics is a whole new dimension that is far from simple to add to JS. And even then the pure subset of JS would remain tiny.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Guy Ellis
My thoughts are along the lines that the developer would decide what a deterministic function was and decorate/tag it as such. That's why I used the word deterministic and not pure. Basically the developer is signaling the compiler that given an identical parameter signature the result received back from the first call can be used for all subsequent results.

The developer implementing compiler optimization would then have a flag available against any method that would signal if it is deterministic or not and would decide to use that information or not.

The question is: Would that extra information provide the Compiler Optimizing Developer with information that they could use to improve performance or anything else? If you are/were such a Compiler-Optimizing-Developer how would you use this information?

On Wed, Jun 21, 2017 at 9:59 AM Andreas Rossberg <[hidden email]> wrote:
On 21 June 2017 at 18:40, Bradley Meck <[hidden email]> wrote:
You probably mean "pure", not "deterministic", which has nothing to do with this. However, JavaScript is far, far too impure for any such annotation to ever make sense or enable any sort of memoization. Consider
let i = 0
let o = {valueOf() {return i++}}
sum(o, 0)
sum(o, 0)

If type coercion was disabled within "pure" functions I am not sure this would be a problem.

A new language mode with modified semantics is a whole new dimension that is far from simple to add to JS. And even then the pure subset of JS would remain tiny.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Andreas Rossberg-4
On 22 June 2017 at 01:24, Guy Ellis <[hidden email]> wrote:
My thoughts are along the lines that the developer would decide what a deterministic function was and decorate/tag it as such. That's why I used the word deterministic and not pure. Basically the developer is signaling the compiler that given an identical parameter signature the result received back from the first call can be used for all subsequent results.

The developer implementing compiler optimization would then have a flag available against any method that would signal if it is deterministic or not and would decide to use that information or not.

Except in a very small set of uninteresting cases, such an optimisation is not allowed, because it changes the semantics of the function. A "tag" as a compiler hint would not change that. The semantics of every language construct has to be well-defined, and must not depend on whether or not a compiler chooses to apply certain optimisations.


 
The question is: Would that extra information provide the Compiler Optimizing Developer with information that they could use to improve performance or anything else? If you are/were such a Compiler-Optimizing-Developer how would you use this information?


On Wed, Jun 21, 2017 at 9:59 AM Andreas Rossberg <[hidden email]> wrote:
On 21 June 2017 at 18:40, Bradley Meck <[hidden email]> wrote:
You probably mean "pure", not "deterministic", which has nothing to do with this. However, JavaScript is far, far too impure for any such annotation to ever make sense or enable any sort of memoization. Consider
let i = 0
let o = {valueOf() {return i++}}
sum(o, 0)
sum(o, 0)

If type coercion was disabled within "pure" functions I am not sure this would be a problem.

A new language mode with modified semantics is a whole new dimension that is far from simple to add to JS. And even then the pure subset of JS would remain tiny.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Deterministic Proposal

Lars Hansen
On Thu, Jun 22, 2017 at 9:14 AM, Andreas Rossberg <[hidden email]> wrote:
On 22 June 2017 at 01:24, Guy Ellis <[hidden email]> wrote:
My thoughts are along the lines that the developer would decide what a deterministic function was and decorate/tag it as such. That's why I used the word deterministic and not pure. Basically the developer is signaling the compiler that given an identical parameter signature the result received back from the first call can be used for all subsequent results.

The developer implementing compiler optimization would then have a flag available against any method that would signal if it is deterministic or not and would decide to use that information or not.

Except in a very small set of uninteresting cases, such an optimisation is not allowed, because it changes the semantics of the function. A "tag" as a compiler hint would not change that. The semantics of every language construct has to be well-defined, and must not depend on whether or not a compiler chooses to apply certain optimisations.

​Well, the annotation could be a hint that the optimization is allowed, and if the implementation could check cheaply that the function is indeed pure it might still be a win.  Depending on details, of course.  Not that I'm advocating it :)

​I *think* that a purity annotation was at least proposed for early versions of the Parallel JS work (Intel's "RiverTrail", later Intel/Mozilla's "PJS") but I can't find any details anywhere.   If there were such annotations they were already gone by 2012 [1].  All PJS work I know about based itself on assuming a kind of observational purity of the kernel functions that were being run in parallel -- side effects were OK as long as you were only touching memory that was private to the invocation, in general this required a combination of compile-time and run-time checks -- with a fallback to sequential execution.  This turned out to be hard to spec and to implement [2].  A purity annotation would probably not move the needle on the difficulty; in effect, all kernel functions for PJS were implicitly annotated as pure (or really, observationally pure, which is more powerful).

--lars




 
The question is: Would that extra information provide the Compiler Optimizing Developer with information that they could use to improve performance or anything else? If you are/were such a Compiler-Optimizing-Developer how would you use this information?


On Wed, Jun 21, 2017 at 9:59 AM Andreas Rossberg <[hidden email]> wrote:
On 21 June 2017 at 18:40, Bradley Meck <[hidden email]> wrote:
You probably mean "pure", not "deterministic", which has nothing to do with this. However, JavaScript is far, far too impure for any such annotation to ever make sense or enable any sort of memoization. Consider
let i = 0
let o = {valueOf() {return i++}}
sum(o, 0)
sum(o, 0)

If type coercion was disabled within "pure" functions I am not sure this would be a problem.

A new language mode with modified semantics is a whole new dimension that is far from simple to add to JS. And even then the pure subset of JS would remain tiny.

_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss



_______________________________________________
es-discuss mailing list
[hidden email]
https://mail.mozilla.org/listinfo/es-discuss