Hacker News Reader

Comment by fulafel | Hacker News Reader

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

View on HN

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.

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.

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.

Can you link to learning resources?

"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.

Why is this special? Doesn't that mean GHC is beta optimal since afaik it stores thunks to computations.

GHC is not beta optimal, due to some complications around what happens when a closures are created. (This is `HOW.md` claims)

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.

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".

"Beta Optimial" != Fastest Execution strategy for all kinds of code. Just defining the term, not arguing about it's engineering application.

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.

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.

Reply on news.ycombinator.com