WebAssembly / WebAssembly/binaryen
Explore Similar Function Elimination (SFE) optimization
Nobody has claimed this yet.
- Dominant language
- WebAssembly
- Stars
- 8.6k
- Forks
- 885
- Avg merge
- 1d 19h
- Merged PRs (30d)
- 69
Description
See https://groups.google.com/d/msg/emscripten-discuss/XJr7jiXDuy8/G2eAHdmSAgAJ , it looks like we could reduce binary size quite a bit using that technique. Opening this issue to discuss implementation here in Binaryen.
To get started, some questions (cc @achoudhury85 ) and notes on the implementation written in that link:
-
On what codebase was the 20% improvement measured? If we don't already, it would be good to measure on things like tests/hello_libcxx.cpp (which is a simple hello world using libc++). The goal with measurements is to see if the 20% is a special thing on specific codebases, or if this is more general.
-
It looks like a key trick (from the document in that link) is to compare functions with the same signature (# of params, types, and return type). I wonder if we should also explore looking at more things, but that does seem quite powerful already in terms of handling c++ templates.
-
When comparing functions to look for optimization opportunities, we can basically build an AST of the match between two methods, noting where they differ. Then the optimization is to write code that in those differing places handles the different cases, doing an if-else on the parameter.
-
The optimization seems like it needs to carefully measure when it makes sense to do. The amount of shared code vs non-shared code, plus the overhead (extra param, if-elses, etc.).
-
A difference with the asm.js implementation is that a table is used for calling different functions. Wasm only has a single table for now, and it's not easy to add to it, since it would be an observable difference (the outside can look at the table size, append to it, etc.). Instead, maybe we can just do an if-else, which is what we might do anyhow for other cases, conceptually
function merged(param1, param2, which) {
..
if (which == 1) {
func1(..);
} else {
func2(..);
}
..
}
A downside there is we need to repeat the arguments.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Read the linked SFE implementation notes and use tests/hello_libcxx.cpp as the initial measurement case. Investigate whether same-signature function matching and merged control flow are viable in Binaryen, including code-size tradeoffs and WebAssembly table constraints. Done means a concrete implementation plan backed by measurements, or a clearly scoped optimization change.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, wasm
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100