Why did tree shaking as a phrase come to exist when “dead code elimination” had been around forever?
it's an evocative phrase, and sounds more colloquial than "dead code elimination". not hard to see why it caught on.
Tree-shaking, the horticulturally misguided algorithm (2023)
61–70 of 151 posts
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#62Earlier quoted context omitted.
Dead branches and loose leaves are still connected to a real tree, that's why it's a misnomer. "Raking" would be a better name if you want to keep to the metaphor. Dead code elimination is the most precise term, and is already well established.
Tree shaking is also well established in the JavaScript world, more so than DCE, so it's pretty natural for it to be used in a wasm context.
DCE is a standard compiler optimization that's been been around since at least the 80s. It's done in multiple different ways, and "tree shaking" is just one more way. Whether the term DCE is known doesn't seem relevant to what is the most descriptive and meaningful term for this optimization.
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#63Earlier quoted context omitted.
Dead branches and loose leaves are still connected to a real tree, that's why it's a misnomer. "Raking" would be a better name if you want to keep to the metaphor. Dead code elimination is the most precise term, and is already well established.
dead branches and loose leaves are connected to a real tree in the same way that dead code is connected to the program in a file. if you break off the dead branch, nothing happens to the tree, just like when you remove unused code, nothing happens to the program.
> if you break of the dead branch, nothing happens to the tree, just like when you remove unused code, nothing happens to the program.
Indeed, and this has been known since the 80s as dead code elimination. So why are we using a new, less descriptive, more confusing term again?
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#64Earlier quoted context omitted.
Dead branches and loose leaves are still connected to a real tree, that's why it's a misnomer. "Raking" would be a better name if you want to keep to the metaphor. Dead code elimination is the most precise term, and is already well established.
Have you... Ever seen a tree? And what happens when the wind blows? Shaking and raking are hardly different in kind.
> And what happens when the wind blows?
And wind blowing has what to do with compiler optimizations again?
> Shaking and raking are hardly different in kind.
The only way they're similar is that they're both kinda dumb names for this optimization that has had a standard name for 40 years.
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#65Tree-shaking is such a bad misnomer. Virgil's compiler calls this "reachability analysis" and it's built into the compilation model. The compiler will parse and typecheck a program's (and libraries' code), and run initializers, but after that the compilation proceeds by exploring from the main entrypoint(s) and only reachable code is analyzed and ends in the final binary. It will happily generate a program (without r…
The correct general term is “dead-code elimination” [0]. Reachability analysis is commonly used do determine what code can be removed, but other methods are possible, and the analysis by itself doesn’t remove any code, that’s a subsequent step.
“Tree-shaking” as commonly used implies that the granularity of the removal is functions, whereas dead-code elimination can generally be at arbitrarily fine levels, for example eliminating branches of conditional expressions, and can be based on all kinds of static program analyses.
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#66My philosophy is to work hard at optimizing my javascript with algorithms and design simplifications for size/performance to make room (in bundle size and CPU) for parts of my code that require brute force compute to solve. In my ClubCompy project, I use WASM to implement a FAT filesystem atop local storage, which has proven to be very computationally expensive. And, I plan to use WASM for pixel-perfect sprite collis…
1fps is the kind of frame rate you should be getting with 20000 collisions, not 256. Your algorithm is the bottleneck, here, not the programming language.
You say "pixel-perfect". If you have enough spare memory, one simple algorithm would be: render an offscreen canvas of the whole arena, draw each sprite as a stencil in a different colour, and test against that. Linear time, and no need to segment anything. (You might need to use the high bits of the canvas, though: I don't know how anti-fingerprinting measures work, but I expect they replace the low bits of a canvas' data with noise.)
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#67Earlier quoted context omitted.
avoid floats (fixed point arithmetic saved quite a bit of space) Can someone help me understand how this works? I thought JavaScript uses doubles for everything. Is WASM completely different in this regard?
Yes. WASM has proper integer and floating-point types.
And even JavaScript only conceptually uses doubles everywhere, JavaScript engines do use integers where they get away with it. Your loop counter is almost certainly an int. You can use this to your advantage for optimization purposes if you carefully craft your statements to probably fit in integers (e.g. by adding bitwise operations)
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#68Earlier quoted context omitted.
> browsers have various popular language runtimes (and perhaps even popular libraries) preloaded, so that all web pages requiring that runtime can share the same (read-only) copy of that code. That sounds a lot like the idea from some years past that commonly used JavaScript frameworks would be served from a few common CDNs and would be widely enough used to be almost always in cache in the browser, and therefore won…
These are good questions and I think there's more than one answer that's worth exploring. I think that the privacy problems caused by shared caches could be solved, without simply prohibiting them altogether. Like, what if you only use the shared cache after N different web sites have requested the same module? But if we really can't get around that problem, then I think another approach worth exploring is for there…
I think a better model would be for the site itself to provide the modules, but the browser will hash and cache them for the next site that may want to use the same module.
This way, there's no central authority that determines what is common enough.
This model does not allow for versioning. For this model, it would be risky to allow it (one website could provide a malicious model that infects the next site you visit).
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#69Tree-shaking is such a bad misnomer. Virgil's compiler calls this "reachability analysis" and it's built into the compilation model. The compiler will parse and typecheck a program's (and libraries' code), and run initializers, but after that the compilation proceeds by exploring from the main entrypoint(s) and only reachable code is analyzed and ends in the final binary. It will happily generate a program (without r…
Proving yet again that there aren’t enough gardeners in computer science. The metaphor we use for optimization is “low hanging fruit” which no orchard owner would ever do. It’s massively wasteful, be you a programmer or a farmer. It’s what amateurs do. I do tree shaking. Pick a tree (subject matter in the code) and get all of the fruit that’s willing to fall off before moving to the next. It’s more efficient, more ef…
I believe low hanging fruit is not specific to CS.
Regardless, it is a perfect metaphor. You want to eat an apple: which one do you pick? Taking the low-hanging fruit is less work right now and gets you to your immediate goal, but disregards general efficiency. Sure, picking a whole tree is more efficient. But if you want a single apple, taking the low hanging fruit is the fastest approach. The metaphor works because it actually implies that it's not the most efficient approach, just the easiest
Re: Tree-shaking, the horticulturally misguided algorithm (2023)
#70I've kept openEtG's wasm blob (card game engine) 1. avoid floats (fixed point arithmetic saved quite a bit of space) 2. avoid hashmaps (originally used hashmaps since it was easy to port JS maps to, have since ported everything to vecs) 3. avoid strings (for awhile there were no strings, but eventually brought it in for display logic) 4. use a small allocator, like talc 5. avoid dependencies. I only use rand & fxhash…
I've been working on a C++ deep RL library (RLtools) and also created some WASM examples (https://rl.tools). I didn't pay any attention to the binary size at all but it turns out it is also just around 200-300kb (including everything, deep learning forward/backward, RL algo and dynamics simulation).
Even though it's not prohibitive rn, I'm curious how small it could be and hopefully find some time soon to squeeze it down