Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tree-shaking, the horticulturally misguided algorithm (2023)

wingolog.org

Post reply on HN
Print view View original

121–130 of 151 posts

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#121

Post by josephg »

azakai wrote: post #25

> If your language’s compiler toolchain can manage to produce useful Wasm in a file that is less than a handful of over-the-wire kilobytes, you can win. I agree that tiny binaries will open up new use cases for wasm! And WasmGC definitely helps. As more context, Java and Kotlin can do fairly well there today, around 2-3 K: https://developer.chrome.com/blog/wasmgc https://twitter.com/bashorov/status/166137726027472077…

I'm curious if wasmgc will help with rust as well. I can imagine it helping when handling javascript objects. And I think it could be used as an alternative, less efficient memory allocator.

But even so, the default rust allocator in wasm is probably fine in most cases. Once you start compiling for size, using wasm-opt and brotli compressing your wasm code, you can fit a massive amount of code in less than 100kb of downloaded content. And its a mistake to directly compare the cost of 100kb of wasm with 100kb of bundled javascript. Javascript is many times slower to parse and initialize. The download time is real, but actual time-to-first-paint is much better using 100kb of wasm vs 100kb of javascript.

But smaller is better. I'm quite excited for Java, Kotlin, C#, Python, Go and friends to all become viable languages for web applications. I'm curious what the resulting size of real applications will end up being. I suspect one of the biggest differences will be in how the frameworks are made. Virtual DOM diffing will always be more complex and slow than reactive component libraries like Svelte, Solidjs, Leptos (rust) and so on. Once wasmgc lands everywhere, I think which web framework you use will have a much bigger impact on performance than language.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#122

Post by josephg »

rowanG077 wrote: post #114
__s wrote: post #3

I'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…

Why do floats and strings have such a high cost?

Strings seem to have a high cost because there's a lot of complexity in rust's format! macros. And the generated code seems to end up with a lot of obscure ways it can panic.

I've found just having one stray dbg!() in my rust code can add ~20kb to my wasm bundle size. Look at what a single dbg!(some_u32) generates: https://rust.godbolt.org/z/bex9z8vx7 . Its also calling into a bunch of garbled functions in the standard library - which will bring in a lot more code.

I suspect zig's comptime approach might work much better for for this sort of thing, if we want smaller binary sizes.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#123

Post by 38 »

__s wrote: post #3

I'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…

jesus christ, just do a desktop app. by your own admission you only saved 300k with all that. a desktop app at 700k is nothing, which means you could ignore all these optimizations and focus on improving speed or adding features

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#124

Post by Dylan16807 »

naasking wrote: post #95
HumanOstrich wrote: post #79

Earlier quoted context omitted.

Language and terminology evolve over time. It can be uncomfortable and challenging to adapt. Some new developers might be introduced to the concept initially as "tree-shaking". It's not wrong; it just differs from your preference.

I learned of tree shaking first, and DCE is clearly superior as a term: 1) it's actually descriptive, 2) there's a large literature using this term to look for further information, and 3) as the original poster noted, it's not actually a misnomer. There is literally no advantage to the new term that I can think of.

DCE is too general.

Tree-shaking is specifically the form of DCE where you remove unreferenced functions/modules.

Especially important is that you can do tree-shaking without analyzing control flow, while by default "DCE" implies you're analyzing control flow.

And I don't think tree-shaking is a misnomer. Depending on how you visualize the metaphor, unreferenced functions are either barely attached or not attached. Shaking them off is simple and sufficiently realistic.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#125

Post by crabmusket »

__s wrote: post #3

I'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…

> 1. avoid floats (fixed point arithmetic saved quite a bit of space)

This is really interesting, since WASM has built in float types of course - is there any more detail you can go into / examples you can show us?

I have a problem at work where I was thinking fixed point arithmetic might help, because I know my maximum resolution needs (e.g. I know the problem will never care about sub-millimetre positioning). I'd be interested to hear more about related issues.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#126

Post by wruza »

munificent wrote: post #113
sroussey wrote: post #31

Why did tree shaking as a phrase come to exist when “dead code elimination” had been around forever?

"Dead code elimination" usually refers to smaller-scale compiler optimizations where within a function, you're discarding pieces of code that will never be reached. "Tree-shaking" refers to a whole-program analysis where you discard entire modules and functions if they are never invoked. They are conceptually the same, but a compiler author will likely have to implement them separately, so having two names helps.

Feels like it became “usually” only recently, cause before “web2.0” DCE always meant eliminating both codepaths and unreachable symbols.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#127

Post by rurban »

naasking wrote: post #24
paulddraper wrote: post #20

Earlier quoted context omitted.

How so? There is lots of code (tree). Some of the code is not connected to the entry point (trunk). Tree shaking removes the disconnected parts (loose leaves, dead branches).

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 the established lisp term, but not used for compilers, but packagers, to shrink images. Dead branches are NOT stored in the pruned image.

Dead code elimination came 20 years later with C compilers.

The problem with treeshaking - I wrote my first for my lisp 30 years ago, it was trivial - is the lack of compile-time evaluation. The more the compiler knows, the more it can prune. Every run-time branch, late binding and esp. dynamic call by string kills it. With simple tricks you can eliminate 90% of your code. IO, error handling, the number tree, lots of slack in the stdlib's. With GUI even more. I heard from CL images shrinked from 2GB down to a floppy disk.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#128

Post by tapirl »

> If your language’s compiler toolchain can manage to produce useful Wasm in a file that is less than a handful of over-the-wire kilobytes, you can win.

Zig is perfect for this.

Personally, I don't think this is an important factor if Wasm file size is less than 100K. It does matter if the file size is over MB.

Builtin GC is only important for some apps, not all. It is best to make your web app GC-free.

The most important factor for apps using Wasm to succeed is still performance benefit.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#129

Post by fenomas »

naasking wrote: post #62
lolinder wrote: post #43

Earlier quoted context omitted.

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.

I can't speak to origins, but currently in the JS world DCE and tree-shaking refer to different things. "Tree-shaking" normally refers to when the bundler omits unreachable code, that a more naive bundler would have included. It's an oft-discussed topic because it wasn't possible to do in some earlier module formats, and some bundlers do it better than others. In this context the "tree" mostly refers to the dependency tree.

In contrast DCE usually refers what the JS engine does at runtime, via whatever means. But DCE isn't much discussed, unless one talking about v8 internals or the like.

Re: Tree-shaking, the horticulturally misguided algorithm (2023)

#130

Post by lispm »

lispm wrote: post #47
titzer wrote: post #2

Tree-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 name "treeshaker" for an application delivery tool possibly originated in Lisp. The first time I've found it was in Lucid Common Lisp, a (no longer available) commercial implementation of Common Lisp for UNIX. Lucid CL 4.1 in 1992 included a tool called Treeshaker. Lucid CL was one of those Lisps which have the idea of an image (see for example the "image" feature of Lisp 1 in 1960), a saved memory dump of the cu…

References:

Lucid Inc. used the word internally at least since 1987, mentioning a treeshaker for Lucid CL 3.0 on the VAX.

"Lisp Systems in the 1990s", Layer/Richardson, 1991 https://dl.acm.org/doi/10.1145/114669.114674

From above: "In contrast, tree shaking uses the approach of eliminating --shaking out-- what is not needed in a static fashion. Programmers specify the requirements of their application and the unneeded parts of the Lisp system are removed using their detailed knowledge of the application. The disadvantages of tree shaking are that it requires programmer intervention and that a function which is shaken out cannot be easily restored."

"Building Common Lisp Applications with Reasonable Performance", Boreczky/Rowe, 1993, https://dl.acm.org/doi/10.1145/1040032.174174

"Lisp: Good News, Bad News, How to Win Big", Gabriel, (not sure from when this version is, the original article is from 1989) https://www.dreamsongs.com/Files/LispGoodNewsBadNews.pdf

From Gabriel's essay:

> "1.6.3 The Treeshaker

> Most Lisp development systems, including Lucid’s, provide all the resources of the Lisp system by default, and this in turn leads to a style of development in which the programmer makes use of whatever tool happens to be most convenient. Because much of the basic Lisp system (or any development system built on top of the basic Lisp system) will generally be unused by a given application, it is very worthwhile to have a tool for excising these unused parts. This tool is called the Treeshaker.

> Treeshaker execution occurs in three phases: walking, testing and writing. In the walking phase, the Treeshaker accumulates a set of objects that need to be included in the saved image. After making this set, the treeshaker runs a test of the application to check that all objects which are used in a typical run have been included. The writing phase then generates an executable image which will run the application.

> To a first approximation, the walk phase is just a matter of computing the connected component of the Lisp image (treated as a directed graph in the obvious way) generated by the application’s toplevel function. However, because of the way that Lisp objects are generally connected this usually includes almost the entire Lisp image including the unused subsystems. Therefore the treeshaker uses several techniques to find connections between objects that do not actually need to be followed in the walk."

> "The name Treeshaker is meant to be evocative of the idea of actually shaking a tree to dislodge dead branches or other trash."

On the more funny side, LispWorks has a keyword to the DELIVER function :shake-shake-shake , which invokes the treeshaker during application delivery.

https://www.lispworks.com/documentation/lw80/deliv/deliv-key...

Post reply on HN