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

131–140 of 151 posts

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

#131

Post by dartos »

crabmusket wrote: post #125
__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 b…

They said why right there. Floating point numbers take up more space in memory and can only store smaller values than internet.

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

#132

Post by naasking »

paulddraper wrote: post #100
naasking wrote: post #64

Earlier quoted context omitted.

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

> And wind blowing has what to do with compiler optimizations again? The wind blowing shakes the tree. When the tree shakes, the dead branches and loose leaves are removed. --- This is similar to when a bundler will traverse the connected code graph and remove the things that are not attached.

So in your mind, a compiler pass is somehow supposed to be similar to the wind blowing, and despite the fact that "tree shaking" makes no reference to the wind or dead branches or leaves, you think anyone seeing this term will immediately make this "completely obvious" connection, and to you, this makes more sense than simply calling an optimization a straightforward, self-explanatory name like "reachability analysis" or "dead code elimination".

It's no wonder naming things is considered one of the hardest things in computer science if this kind of convoluted argument makes sense to people.

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

#133

Post by [deleted] »

chongli wrote: post #50
__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…

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?

[deleted]

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

#134

Post by flohofwoe »

chongli wrote: post #50
__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…

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?

WASM has 32-bit and 64-bit integer and float types:

https://webassembly.github.io/spec/core/syntax/types.html

(...and additionally can load/store 8- and 16-bit integers).

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

#135

Post by flohofwoe »

38 wrote: post #123
__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

Arguably, on the web a difference between 300 KB and 700 KB doesn't matter either, many web pages have a single hero image bigger than that.

But for a long time one main critique point was that WASM apps are "bloated", so its good to see counter examples, and that devs start caring about trimming fat in general (this would also be a good thing for many desktop applications tbh).

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

#136

Post by flohofwoe »

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…

Is there a conceptual difference to the traditional term "dead code elimination" that's been used for an eternity in C/C++ compilers and linkers?

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

#137

Post by flohofwoe »

GrumpySloth wrote: post #116
layer8 wrote: post #65

Earlier quoted context omitted.

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 exampl…

Although true, in most cases when people talk about dead code elimination, they refer to eliminating code inside a function, whereas tree-shaking unambiguously refers to inter-procedural dead code elimination.

Probably because traditionally, unused 'objects' in static link libraries were ignored in the first place by linkers. But with LTO the term dead-code-elimination makes sense IMHO (since the LTO pass will drop any code and data that ends up being unused).

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

#138

Post by flohofwoe »

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.

FWIW I never encountered 'tree shaking' in the C/C++ world (only in the Javascript world). Commonly in the C/C++ world, dead-code-elimination is used for anything that removes (or ignores in the first place) unused code and data.

And I think with LTO it's all the same anyway (in the past there were a lot of gnarly details how the compiler/librarian actually created a static link library to avoid linking code that's not actually used, but that all doesn't matter anymore with LTO).

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

#139

Post by xyzzy_plugh »

GrumpySloth wrote: post #116
layer8 wrote: post #65

Earlier quoted context omitted.

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 exampl…

Although true, in most cases when people talk about dead code elimination, they refer to eliminating code inside a function, whereas tree-shaking unambiguously refers to inter-procedural dead code elimination.

I've been around the block and I've never seen it referred to in this way. Dead code is dead code.

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

#140

Post by dwoldrich »

mrob wrote: post #98
dwoldrich wrote: post #58

My 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…

>pixel-perfect sprite collision detection This is something that sounds like a good idea when you first hear it, but feels unpleasant when you actually play it. Most 2D games use rectangular collision hitboxes for good reason: it's easier for the player to predict if sprites will collide or not. With pixel-perfect collisions, the same movement will collide or not depending on the phase of the animation cycles. It fee…

Agreed, pixel perfect sprite collision detection has limited applicability in games, like missiles vs ship in shmups. And even then, one would probably want to implement a hitbox system smaller than the sprite images for fairness reasons.

My pixel perfect collision detection is not just sprite-to-sprite, but also sprite-to-playfield. I also signal on overlapping sprite-to-sprite rectangles.

Users can "turn off" the pixel-perfect collision detection to save on compute by resizing the sprite to anything other than 24x24 (even 24.1x24, which rounds down to 24x24 on the displayed sprite image.)

I want pixel perfect collision-detection for authenticity and to provide an eclectic programming tool that creators may find clever uses for.

Post reply on HN