Binaryen: Explore Similar Function Elimination (SFE) optimization

[kripken]

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.

[jfbastien]

Isn't this a perfect place to use LLVM's merge-funcs?

[kripken]

merge-funcs merges identical functions, while the stuff here looks for similar-but-not-identical functions. Or did I misunderstand your question?

[jfbastien]

merge-funcs had some work-in-progress to also merge similar functions. It seems much more useful to continue that work rather than reimplement something that'll be WebAssembly-specific.

[achoudhury85]

Hello Alon

The 20% improvement was measured on a Tableau internal codebase that is very C++ template heavy. (the codebase after all optimizations and DFE was at around 4 Mb and with SFE, the size went down to 3.2Mb). I put together a simple template heavy example since we can't share the Tableau internal codebase to demonstrate SFE's effectiveness, although, we should note that we go from 620Kb to 505kb without DFE in that example (if we first apply DFE for the example, SFE's effectiveness drops to 5%).

Numbers for hello_libcxx.js:

Without DFE

achoudhury-lnx$~/code/emscripten/emscripten/tests>emcc -O3 hello_libcxx.cpp -o hello_libcxx.js
achoudhury-lnx$~/code/emscripten/emscripten/tests>ls -l hello_libcxx.js
-rw-r--r-- 1 achoudhury domain users 459432 Aug 21 10:48 hello_libcxx.js

achoudhury-lnx$~/code/emscripten/emscripten/tests>node ~/code/SimilarFunctionElimination/src/run_sfe.js --file ~/code/emscripten/emscripten/tests/hello_libcxx. > hello_libcxx_reduced.js
achoudhury-lnx$~/code/emscripten/emscripten/tests>ls -l hello_libcxx*.js
-rw-r--r-- 1 achoudhury domain users 459432 Aug 21 10:48 hello_libcxx.js
-rw-r--r-- 1 achoudhury domain users 436977 Aug 21 10:50 hello_libcxx_reduced.js

So without DFE turned on, SFE yields around a 5% reduction in size for hello_libcxx.js.

With DFE

achoudhury-lnx$~/code/emscripten/emscripten/tests>emcc -O3 -s ELIMINATE_DUPLICATE_FUNCTIONS=1 hello_libcxx.cpp -o hello_libcxx.js
achoudhury-lnx$~/code/emscripten/emscripten/tests>ls -l hello_libcxx*.js
-rw-r--r-- 1 achoudhury domain users 441718 Aug 21 10:54 hello_libcxx.js

achoudhury-lnx$~/code/emscripten/emscripten/tests>node ~/code/Similar-Function-Elimination/src/run_sfe.js --file ~/code/emscripten/e
mscripten/tests/hello_libcxx.js > hello_libcxx_reduced.js
achoudhury-lnx$~/code/emscripten/emscripten/tests>ls -l hello_libcxx*.js
-rw-r--r-- 1 achoudhury domain users 441718 Aug 21 10:54 hello_libcxx.js
-rw-r--r-- 1 achoudhury domain users 429709 Aug 21 10:55 hello_libcxx_reduced.js

So, with DFE turned on, SFE yields only an additional 3% reduction for hello_libcxx.cpp.

This size reduction seems expected as hello_libcxx doesn't really make use of any template code.

Hope this helps, and let me know if you have further questions.

Regards,
Arnab

[kripken]

@jfbastien: interesting, I don't see that in the main repo, I suppose this was an experiment somewhere else? Do you know where?

I agree it would be good to do this in LLVM if it's practical to do so.

@achoudhury85: thanks for the data. Makes sense, yeah, 20% does seem unlikely to happen on most codebases. But 3%-5% is still very useful :)

Would it be practical to measure how important the different pieces of SFE are? I mean, if at full power it's 20%, and you disable handling of different constants, how much worse does it become? And so forth for disabling handling of different functions. (Maybe this could be done with just commenting out a few lines, etc.? If it's very hard then probably not worth it.)

Another thought is I wonder if it's important to handle extra code, i.e.
function foo(x, y) { x += y; return x; } function bar(x, y) { x += y; work(); // an extra line return x; }
It would be easy to handle that (an if instead of an if-else) but it does seem like it would be harder to find such opportunities.

[jfbastien]

I can't find the reference right now, somewhere on LLVM. Regardless, the code probably would need an update. The basic idea is simple: MergeFunctions knows everything about each IR construct, and can be taught about what's a "fuzzy" comparator as well as the current exact comparators. Differing by e.g. one function call can be a thing that gets merged.

IIRC with precise function merging the pass was a 7% size with on Chrome, back in summer 2015.

[dschuff]

The pass is in https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/IPO/MergeFunctions.cpp and yeah it would be great to do this in LLVM. Also IIRC JF is on the hook to find a reviewer for your MergeFuncs changes :)

[jfbastien]

I'm happy to help review it.

[kripken]

Doing some searching, I found Swift has a similar-functions-merging pass,

https://github.com/apple/swift/blob/master/lib/LLVMPasses/LLVMMergeFunctions.cpp

@jfbastien, maybe that's what you meant?

Looks like it handles different constants, but otherwise is a copy-paste of the LLVM one. Apparently in Swift it's common to template on metadata which ends up being pointer constants.

Overall, I suspect we will want duplicate and similar function elimination in both LLVM and Binaryen because each location is useful in a different way. So the question might be which to improve first. For LLVM,

• We can build on the existing MergeFuncs pass.
• Improving LLVM would help everything using LLVM, not just wasm. For example, it would help native compilation to x86, ARM, etc. (But MergeFuncs appears to be turned off by default in LLVM, so I suspect very few people would benefit? Looks like only Swift has it on.)
• MergeFuncs can be run on LLVM IR, so it can be done when doing LTO.

For Binaryen,

• We can build on the existing DuplicateFunctionElimination pass.
• Improving Binaryen would help everything using Binaryen, not just LLVM output. For example, it could help gcc, WasmScript, etc.
• DFE can be run on arbitrary wasm, so it can be done after linking wasm once we get that (i.e. when not doing LTO).

I'd say those are mostly even. However, some additional reasons for focusing on Binaryen first are

• Faster to run, since it can be parallel like DFE is, which can matter a lot in whole-program passes like this.
• Faster to write, since I'm volunteering to do it, and I know Binaryen a lot better than I know LLVM.
• Also some concern on Swift having an improved fork of LLVM's MergeFuncs, might need to coordinate with more than one upstream.

[jfbastien]

Yes, it's a copy / paste, and that's what I was talking about.

We should work towards enabling it by default for LLVM. It's not just a size win, it's also a compile-time win because fewer functions are optimized. You can run exact match early for that. Partial match should run late, won't be a compile-time win, but will win on size.

Re-importing Swift's improvements to LLVM is easy.

[kripken]

I think partial match could also be a compile time win, it also causes fewer functions to be optimized. (But of course it does do more work and the functions left are slightly bigger, so it's not obvious either way.)

[jfbastien]

You don't want to do partial merge early because it can defeat other things such as inlining. First you do exact, and then after doing some passes you'd do partial.

[kripken]

Yeah, I agree inlining probably makes more sense first.

[hackcasual]

I'm on the same team as @achoudhury85. SFE is likely to be a bit better in the WASM world, as it can more efficiently represent the hoisted variants, which means there is less overhead with helper functions. SFE commonly hoists things like vtable pointers (~4 bytes in textual notation, ~2 bytes with LEB128 encoded integers) and structure memory layout, ~2-3bytes - 1 byte.

This is perhaps another argument for having binaryen support some level of this, as some of the cost computation will be unique to the WASM binary encoding.

[dcodeIO]

Might also be useful for things that use Binaryen, but not LLVM.

[kripken]

@achoudhury85, @hackcasual: does your current implementation handle just pairs of functions, or also three or more? For three or more this seems less efficient (can't use a simple if-else, and harder to find matches), I'm wondering if it's worth handling that.

[achoudhury85]

@kripken - Our current implementation handles as many functions as possible that are deemed to be "similar in nature". Thus if we have N functions that all have literals and identifiers in the same places in the AST, we will parametrize the literals and identifiers accordingly and invoke a single helper function from each one of the N functions. The helper function would have parameters corresponding to the number of locations all N functions differ in.

I'm not sure I follow why this is inefficient - can you expand a bit on that :)? Thanks!

[jfbastien]

With 100000 functions it'll be inefficient if you compare all of them to each other. LLVM migrated to a hashing-based approach to do this, and then does a strict comparison of what hashes the same. For "fuzzy" matching we just implemented two hashes: one for precise match, and one of fuzzy where we'd take into account e.g. opcode type like "invoke" but not say invoke target. As I said above this fuzzy matching never made it into the tree (my intern's term finished) but it's easy to add.

[achoudhury85]

Thanks for the update @jfbastien. In SFE, we solve this problem by hashing the canonicalized ASTs of all N functions, and we bucket on the hashes. Functions that are similar will hash to the same bucket (since their canonicalized ASTs - i.e., AST with consistent placeholders for literals and identifiers, are the same and will hash to the same value).

So, we don't actually compare all N functions, we make one pass through all the functions where we hash and bucket them. Hope this helps.

[kripken]

Yeah, definitely hashing is crucial here.

The inefficiency I meant is that switches are less compact (need more blocks + branches in wasm). And if-else gets slow with a long chain.

The complexity I meant is what if A is similar to B but also similar to C in another way, you need to pick one. If you consider triple+ matches, this is less simple (decision depends on later funcs).

[achoudhury85]

Thanks @kripken.

Regarding complexity, we pondered the exact question you posed quite a bit when designing SFE. We realized that for this case where A is similar to B, and B is similar to C, given that A and B are differing only by identifiers and literals, and so are B and C, we can posit that A, B, and C are all structurally similar, i.e., their AST's tree structure is the same, except for differences in leaf nodes that can be either identifiers or literals. Once we get to this realization, we then further realize that their canonicalized ASTs will be the same (since we replace literals and identifiers with placeholders), and thus, A, B, and C will hash to the same bucket and we will generate a single helper function that all 3 call out to. In terms of space overhead, this is great. The generated function will have more extra parameters however, and we will incur the penalty of an extra function call at runtime.

I still don't follow completely about the efficiency part, but this is probably more due to the fact that I need to read up a bit on WASM optimization :).

Let me know if you have more questions.

[kripken]

I see. So if A and B differ just in one location, and A and C also differ just in one, while B and C differ in 2, then you still optimize them all into one function? Make sense for code size, and I guess this pass is focused on that anyhow. (It's not obvious to me that this won't miss some things. The overhead from handling 3 functions in one might be larger than the win - but it does seem like those would be odd corner cases.)

About code size, in wasm an if-else is 4 bytes. If there are no side effects - likely - then we can use a select, just 1 byte. But a switch requires a block and a break for each condition, 5 bytes :( That's already bigger than a constant or a local...

[hackcasual]

We use a purely greedy approach, which may in some cases mean we would do better by evicting a function from a similarity set.

Looking at a simple example:

function z1(a, b)
{
  var $1 = 5 | 0 * b;
  return R[Q[a << 4 + 12] - $1];
}

function z2(a, b)
{
  var $1 = 6 | 0 * b;
  return R[Q[a << 4 + 12] - $1];
}

function z3(a, b)
{
  var $1 = 5 | 0 * b;
  return R[Q[a << 4 + 16] - $1];
}

The algorithm roughly follows this process:

1. Replace every hoistable value (constants, function references) with a place holder
2. Hash the replaced AST
3. Functions that hash to the same value are part of the same similarity set
4. Functions in the same similarity set are compared with each other and any differeing locations in the AST are marked
5. A new function is generated that takes in the parameters the original function did, plus all parameters that represent the variation in the AST

From our example the functions will get converted to this:

function (a, b)
{
  var $1 = ϕ | ϕ * b;
  return R[Q[a << ϕ + ϕ] - $1];
}

After comparing them, we'll get the merged function like this:

function zPrime(a, b, $$1, $$2)
{
  var $1 = $$1 | 0 * b;
  return R[Q[a << 4 + $$2] - $1];
}

function z1(a, b)
{
  return zPrime(a, b, 5, 12);
}

function z2(a, b)
{
  return zPrime(a, b, 6, 12);
}

function z3(a, b)
{
  return zPrime(a, b, 5, 16);
}

Hopefully that helps clarify things

[kripken]

I see, thanks. One thing I didn't fully appreciate til now is that when handling constants, you can avoid ifs - instead of a parameter saying which control flow path to take, the parameter can be the value itself. Also hashing is easy that way, as you said.

Do you handle arbitrary expressions? Say if two functions differ only in one part where one has a + b and the other has a * b, would you do an if there,
function helper(.., which) { .. .. (which ? a + b : a * b) .. .. }
Or do you not handle that case?

Same question for extra code, where two functions differ by one having a few extra statements in the middle, optimizable to
function helper(.., which) { .. if (which) { extra(); code(); } .. }
?

I am leaning towards trying to support those as well, but it does make things more complex and longer to run.

[hackcasual]

Yep, we brought that up as a possible improvement. I believe in our code base we have quite a few cases with smart pointer logic where the functions have a lot of similarity at the beginning, but one is a shorter version of the other. For obvious reasons, finding those cases are a lot harder. It's possible you could do something by hashing subtrees, but you'll also need to normalize identifier names.

[kripken]

Got it. And what about a + b vs a * b, did you consider optimizing functions differing only in that?

[hackcasual]

Yeah, you can arbitrarily handle any AST difference as long as scope is preserved. I'd say in that case you're not likely to find a function that just differs by an operation like that though, so we haven't collected what it would actually help with.

[kripken]

How do you handle hashing in that case? Do you ignore the operation, so it's a ? b? In that case, I guess you wouldn't match ~a (a unary) with a + b (a binary)?

[hackcasual]

So our current code doesn't handle that, but you could do it through replacing the AST node with a place holder.

[kripken]

Got it, thanks, I was just wondering if there was a clever hashing trick I was missing here.

[hackcasual]

At a certain point you'll end up with all the complexity in resolving the similarity sets.

[jfbastien]

If you start doing fairly complex things like this it would be great to do good perf measurements on all available browser implementations. Merging things like + and * would save size, but VMs might want to start doing very different codegen and optimizations to "undo" some of the hurt this can cause.

It's a moving target, though: don't take current VM performance as a thing that won't change. All I mean is, please don't just measure on one engine and call it a day.

[kripken]

Another thing to consider here is the effect on gzipped size. Has that been measured on the asm.js implementation?

I would guess this reduces the benefits of gzip but probably doesn't have a negative effect, but would be good to confirm. However, we should probably remeasure on wasm as function order matters. We currently order functions by number of uses, so the index of popular functions is small, but we should also order by similarity for gzip purposes as in that link, and so any measurement would be incomplete before we do that.

[hackcasual]

In theory it's better than DFE when it comes to GZIP, as its context aware. While DFE is picking up stuff that is basically free for LZW type compressors, SFE is being a little bit smarter. In any case, even if gzip brings the results down a bit, there is something to be said for less stuff to parse.

[jfbastien]

I don't think parse-time matters here. Download does, but parsing is nothing compared to work that the optimizer needs to do. Therefore, any compression which forces the optimizer to perform more work has to yield valuable download savings.

[hackcasual]

That's a good point, I'd say for measuring likely impact, using DFE would be a good first approximation for the gains here.

[kripken]

Ok, then as a first step here I think we should get the compression-friendly reordering in place. That will allow later SFE measurements to be more valid. I can get to this soon unless someone else wants to.

[achoudhury85]

Hey folks - I'll have some numbers out on compression with and without SFE by EOD today. Alon, I'll also take a look at what the percentages are for literals vs identifiers. Thanks!

[achoudhury85]

Hey folks, here are some numbers for a number of codebases with uncompressed and gzip9 sizes (all in bytes) listed with and without SFE. As can be seen, gzip savings varies, in the case of ammo.js for example, gzip performed quite poorly with SFE turned on, but in other cases like BananaBread - SFE+gzip results in big savings.

| JS File | Uncompressed | With Gzip9 |
|---------------------------------|--------------|-------------|
| Roll-A-Ball With SFE | 17,828,112 | 4,343,711 |
| Roll-A-Ball Without SFE | 19,349,834 | 4,433,581 |
| Tableau Internal JS With SFE | 3,198,386 | 696,932 |
| Tableau Internal JS Without SFE | 3,964,275 | 715,952 |
| ammo.js With SFE | 1,880,651 | 387,550 |
| ammo.js Without SFE | 1,888,389 | 386,182 |

EDIT - looks like the previous BananaBread numbers were off as the BananaBread JS was unoptimized. So, the best case savings seems to be for Roll-A-Ball - around 100Kb

[achoudhury85]

Here is another analysis of SFE (I have excluded BananaBread as I don't have it optimized) where we run variants of SFE that canonicalize only on literals or only on identifiers. We compare the resultant sizes vs vanilla SFE (where we canonicalize ASTs on both literals and identifiers), and also the size without SFE.

Ammo.js was a bit surprising - running SFE where we canonicalize only on identifiers actually enlarged the size of the file - since we're not optimizing too much with ammo.js, the additional parameter and return type annotations seem to be bumping up the size of the file. Probably worth a future fix where we measure in bytes the size with and without SFE when reducing.

| JS File | SFE With Identifiers | SFE With Literals | Vanilla SFE | Without SFE |
|---------------------|----------------------|-------------------|--------------|--------------|
| Roll-A-Ball | 19,117,209 | 18,375,377 | 17,828,112 | 19,349,834 |
| Tableau Internal JS | 3,422,383 | 3,844,775 | 3,198,386 | 3,964,275 |
| Ammo.js | 1,891,843 | 1,877,376 | 1,880,651 | 1,888,389 |

[kripken]

Very interesting data, thanks @achoudhury85!

Looks like we'll need to be careful here because of those cases where code size is actually increased or gzip size is.

My plan is still to get the gzip-optimized reordering in first. I hope this will give us most of the benefits of SFE on gzip size, in which case maybe it's actually not worth doing SFE (given the complexity and risk). More likely there will still be a benefit, and then we can use the gzip-optimization code to help avoid the bad cases where we increase gzip size.

[kripken]

Sorry I haven't had enough time to really focus on this. I did find out a few things in experimentation, writing it out since maybe someone else can get to it before me:

• We should sort by LEB size (how many bytes in the call instruction) and afterwards similarity.
• Similarity sorting can probably be greedy - pick the most similar for the last function emitted so far.
• Similarity can take into account only the last 32K of the last function and first 32K of the next function, as that is the gzip window size. Much less would work too, probably. This avoids scanning very large functions.
• The new tableOfContents attribute in the binary writer makes it easy to look at the byte output of all the functions.
• Similarity should be done in O(N) time, without comparing every pair of functions, as in big files it's just too slow. One option is to generate a "fingerprint" of a sequence of bytes (say, hash each byte, pair, and so forth, and note how many of those hash values we see), and then comparing two fingerprints is pretty efficient.

[kripken]

• Similarity ordering is probably a blocker for enabling function reordering, as reordering by itself improves binary size but often regresses gzip size.

[kripken]

Some more experimentation in https://github.com/WebAssembly/binaryen/commits/func-order