3 ms·

The submission title says "optimal", the README says "beta-optimal", what do they mean in this context and are they true?

opnitro 5y ago
"Optimal" in this context means it never repeats the work of beta reduction when it doesn't have to. Ie, evaluating `(\x -> x + x) (2 * 2)` only evaluates `2 * 2` once.
- rowanG077 5y ago
  Why is this special? Doesn't that mean GHC is beta optimal since afaik it stores thunks to computations.
  - opnitro 5y ago
    GHC is not beta optimal, due to some complications around what happens when a closures are created. (This is `HOW.md` claims)
- astrange 5y ago
  That's not optimal on real machines; it's often faster to recalculate x*y than to cache it. In general this "optimal" strategy seems to assume infinite memory that's all accessible at the same speed.
  - opnitro 5y ago
    "Beta Optimial" != Fastest Execution strategy for all kinds of code. Just defining the term, not arguing about it's engineering application.
    - astrange 5y ago
      The project certainly says it has "drastically improved efficiency" and "uncharted levels of performance". I don't think "massively parallel" is all that good for performance either, because battery life is part of that.
      - opnitro 5y ago
        Ok well _I_ was just defining the term. I didn't write the project. You will note they provide benchmarks with data showing the efficiency gain. What's left (as a reader) is evaluate the quality of those benchmarks.
  - HelloNurse 5y ago
    The compiler could have heuristics and profiling data to replace optimal but "small" reductions with cheap recomputation with even less locking where it seems like a good idea; it's an additional level of improvement rather than a competing choice. As the Python documentation says, "practicality beats purity", particularly when the sacrificed purity is only the pride of using an universal solution. In a similar vein, if typical strategies for unstable sorting of arrays in place use quicksort splitting for long spans and insertion sort for short spans it doesn' mean that either algorithm is "better".
voxl 5y ago
Optimal beta reduction is a very technical term. In effect it means any "family" of lambda terms will all be reduced "at once." What is a family? Go take two semesters in rewriting theory and then perhaps our two heads together can pin it down exactly. In laymen's terms, it means that you're doing a variant of call-by-need, except you can be absolutely sure you don't copy applications without need. I am personally skeptical it's a useful idea at all. Machine computation is what we really care about (how fast can you push instructions through the pipeline) and graph reduction systems were already all the rage in the 80s. We gave up on them because they didn't interact with the cache well. So, this is the "motherload" of all graph reduction strategies, yet it will get absolutely trounced in settings like numerical computation.
- Azsy 5y ago
  As a counter argument ( and i'm not 100% sure it holds up ). The cache failures was because the cache was to small. Whereas now we care about CPU OP data dependencies.
- txdv 5y ago
  Can you link to learning resources?
- JonChesterfield 5y ago
  There's an interesting interaction with implicit parallelism. For a given reduction to occur at most once you need communication across threads so that two don't do the same reduction at once. I suspect at most once per hardware thread is a faster choice - repeating some calculation for decreased communication. Or you need a static assignment of reduction to threads which means predicting how long each reduction will take.

opnitro 5y ago

"Optimal" in this context means it never repeats the work of beta reduction when it doesn't have to. Ie, evaluating `(\x -> x + x) (2 * 2)` only evaluates `2 * 2` once.

rowanG077 5y ago
Why is this special? Doesn't that mean GHC is beta optimal since afaik it stores thunks to computations.
- opnitro 5y ago
  GHC is not beta optimal, due to some complications around what happens when a closures are created. (This is `HOW.md` claims)
astrange 5y ago
That's not optimal on real machines; it's often faster to recalculate x*y than to cache it. In general this "optimal" strategy seems to assume infinite memory that's all accessible at the same speed.
- opnitro 5y ago
  "Beta Optimial" != Fastest Execution strategy for all kinds of code. Just defining the term, not arguing about it's engineering application.
  - astrange 5y ago
    The project certainly says it has "drastically improved efficiency" and "uncharted levels of performance". I don't think "massively parallel" is all that good for performance either, because battery life is part of that.
    - opnitro 5y ago
      Ok well _I_ was just defining the term. I didn't write the project. You will note they provide benchmarks with data showing the efficiency gain. What's left (as a reader) is evaluate the quality of those benchmarks.
- HelloNurse 5y ago
  The compiler could have heuristics and profiling data to replace optimal but "small" reductions with cheap recomputation with even less locking where it seems like a good idea; it's an additional level of improvement rather than a competing choice. As the Python documentation says, "practicality beats purity", particularly when the sacrificed purity is only the pride of using an universal solution. In a similar vein, if typical strategies for unstable sorting of arrays in place use quicksort splitting for long spans and insertion sort for short spans it doesn' mean that either algorithm is "better".

voxl 5y ago

Optimal beta reduction is a very technical term. In effect it means any "family" of lambda terms will all be reduced "at once." What is a family? Go take two semesters in rewriting theory and then perhaps our two heads together can pin it down exactly. In laymen's terms, it means that you're doing a variant of call-by-need, except you can be absolutely sure you don't copy applications without need. I am personally skeptical it's a useful idea at all. Machine computation is what we really care about (how fast can you push instructions through the pipeline) and graph reduction systems were already all the rage in the 80s. We gave up on them because they didn't interact with the cache well. So, this is the "motherload" of all graph reduction strategies, yet it will get absolutely trounced in settings like numerical computation.

Azsy 5y ago
As a counter argument ( and i'm not 100% sure it holds up ). The cache failures was because the cache was to small. Whereas now we care about CPU OP data dependencies.
txdv 5y ago
Can you link to learning resources?
JonChesterfield 5y ago
There's an interesting interaction with implicit parallelism. For a given reduction to occur at most once you need communication across threads so that two don't do the same reduction at once. I suspect at most once per hardware thread is a faster choice - repeating some calculation for decreased communication. Or you need a static assignment of reduction to threads which means predicting how long each reduction will take.