WebAssembly / WebAssembly/binaryen

Explore Similar Function Elimination (SFE) optimization

Open
#1,142 44 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

help wanted
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:

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

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

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

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

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.