Deterministic Proposal
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:
import { memoize } from "std::decorators";
@memoize
function sum(a, b) {
return a + b;
}
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.
@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.
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?
Think of it like this: It might be enough for your application only to
memoize the lastnresults. 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
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
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 me at isiahmeadows.com
Looking for web consulting? Or a new website? Send me an email and we can get started. www.isiahmeadows.com
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 21 June 2017 at 00:58, Guy Ellis <wildfiction at gmail.com> 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 <isiahmeadows at gmail.com> 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.
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.
On 21 June 2017 at 18:40, Bradley Meck <bradley.meck at gmail.com> 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.
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 22 June 2017 at 01:24, Guy Ellis <wildfiction at gmail.com> 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.
On Thu, Jun 22, 2017 at 9:14 AM, Andreas Rossberg <rossberg at google.com>
wrote:
On 22 June 2017 at 01:24, Guy Ellis <wildfiction at gmail.com> 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
[1] smallcultfollowing.com/babysteps/blog/2012/10/10/rivertrail [2] groups.google.com/forum/#!msg/mozilla.dev.tech.js-engine/H-YEsejE6DA/BLERtTTm8GYJ, groups.google.com/forum/#!msg/mozilla.dev.tech.js-engine/H-YEsejE6DA/BLERtTTm8GYJ;context-place=forum/mozilla.dev.tech.js-engine
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.
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. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20170620/ba2c10e1/attachment.html>