Tree shaking
In computing, tree shaking is a dead code elimination technique that is applied when bundling code with its dependencies. It is most commonly applied to dynamic languages, in practice most commonly JavaScript/ECMAScript.[1] Often contrasted with traditional single-library dead code elimination techniques common to minifiers, tree shaking eliminates unused functions from across the bundle by starting at the entry point and only including functions that may be executed.[2][3] It is succinctly described as "live code inclusion".
In less-dynamic languages such as C, ordinary dead-code elimination becomes equivalent to tree-shaking with whole program optimization, which also uses knowledge of entry points.
History
[edit]Dead code elimination in dynamic languages is a much harder problem than in static languages. The idea of a "treeshaker" originated in LISP[4] in the 1990s. The idea is that all possible execution flows of a program can be represented as a tree of function calls, so that functions that are never called can be eliminated.
The algorithm was applied to JavaScript in Google Closure Tools and then to Dart in the dart2js compiler also written by Google, presented by Bob Nystrom in 2012[5][3] and described by the book Dart in Action by author Chris Buckett in 2013:
When code is converted from Dart to JavaScript the compiler does 'tree shaking'. In JavaScript you have to add an entire library even if you only need it for one function, but thanks to tree shaking the Dart-derived JavaScript only includes the individual functions that you need from a library
— Chris Buckett
The next wave of popularity of the term is attributed to Rich Harris's Rollup project[6] developed in 2015.
Relation to ECMAScript 6 modules
[edit]The popularity of tree shaking in JavaScript is based on the fact that in contrast to CommonJS modules, ECMAScript 6 module-loading is static and thus the whole dependency tree can be deduced by statically parsing the syntax tree. Furthermore, ES6 imports can be done to the granularity of single named values (functions are values) instead of whole files. Thus tree shaking becomes an easy problem.[citation needed]
However, tree shaking does not only apply at the file or value levels: it can also work at the statement level, depending on the implementation.[citation needed]
Comparison to DCE techniques in compiled languages
[edit]Tree-shaking at the source file level is analogous to the standard (C/C++/...) linker's handling of static libraries, which only links in the required object files.
Tree-shaking at the function/variable level is analogous to creating individual sections for functions and/or values (-ffunction-sections -fdata-sections) and having the linker remove unused sections (--gc-sections).
Tree-shaking at the statement level is analogous to compiler DCE under whole program optimization.
In all three cases, a concept of entry points exists to determine what is reachable and what is not.
References
[edit]- ↑ "Reduce JavaScript Payloads with Tree Shaking".
- ↑ Harris, Rich (15 January 2019). "Tree-shaking versus dead code elimination". Retrieved 16 September 2020.
- 1 2 Ladd, Seth (29 January 2013). "Minification is not enough, you need tree shaking". Seth Ladd's Blog.
- ↑ comp.lang.lisp What's a treeshaker?
- ↑ Can Google Dart Solve JavaScript's Speed and Scale Problems?
- ↑ How To Clean Up Your JavaScript Build With Tree Shaking