Wasm: Make itables immutable struct #5038
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
sjrd
requested changes
Sep 17, 2024
Comment on lines
138
to
139
| /** Generate common taible global for all array classes | ||
| */ |
There was a problem hiding this comment.
Typo + formatting:
Suggested change
| /** Generate common taible global for all array classes | |
| */ | |
| /** Generate common itable global for all array classes. */ |
linker/shared/src/main/scala/org/scalajs/linker/backend/wasmemitter/VarGen.scala
Show resolved
Hide resolved
| if interfaceInfo.isInterface | ||
| } { | ||
| val init = interfaceInfo.tableEntries.map { method => | ||
| ctx.refFuncWithDeclaration(resolvedMethodInfos(method).tableEntryID) |
There was a problem hiding this comment.
Since this is now in a global section, we don't need separate declarations anymore:
Suggested change
| ctx.refFuncWithDeclaration(resolvedMethodInfos(method).tableEntryID) | |
| wa.RefFunc(resolvedMethodInfos(method).tableEntryID) |
|
|
||
| val global = wamod.Global( | ||
| classITableGlobalID, | ||
| makeDebugName(ns.ITable, classInfoForResolving.name), |
There was a problem hiding this comment.
This is going to be confusing for the itables array of array classes. Previously we had
OriginalName(genGlobalID.arrayClassITable.toString())for that one. Pass it as an additional parameter to genGlobalClassItable?
There was a problem hiding this comment.
Oh yeah thanks, I added an originalName parameter to genGlobalClassItable
Previously, we used mutable array-based interface tables (itables) without a specific reason. However, accessing mutable arrays can lead to missed optimization opportunities. For instance, loop-invariant code motion (LICM) won't be able to move certain parts of interface dispatching operations out of loops: When we invoke a method using interface table dispatching, it requires retrieving an itable from the class's itable array, which is considered non-pure. In fact, reading from an array is marked as unsafe to move in wasm-opt's LICM implementation: https://github.com/WebAssembly/binaryen/blob/34ad6a7598e662e9ff357987f2c81fde1e05c522/src/ir/effects.h#L207-L210 https://github.com/WebAssembly/binaryen/blob/34ad6a7598e662e9ff357987f2c81fde1e05c522/src/passes/LoopInvariantCodeMotion.cpp#L125-L128 (Note: We may not run wasm-opt's LICM in favor of the VM's LICM, as discussed in WebAssembly/binaryen#6924) This commit changes itables to be immutable structs, making itable retrieval a pure operation. Here's a comparison of benchmark results between commit 4c9494e and this change: | | array itables | struct itables | | ----------- | ------------- | -------------- | | sha512 | 12128.73213 | 12107.94142 | | queens | 3.632068223 | 3.655815179 | | list | 84.61223471 | 65.69730564 | | richards | 92.12833022 | 91.19028905 | | cd | 46267.10318 | 46574.81215 | | gcbench | 116540.568 | 112594.324 | | tracerFloat | 2569.675034 | 2551.227714 | | tracer | 1725.591249 | 1697.907466 | | sudoku | 14863.33909 | 12066.23882 | | nbody | 366388.3292 | 199625.971 | | permute | 1006.215249 | 983.9858283 | | deltaBlue | 2205.002528 | 2320.038418 | | kmeans | 1752457.829 | 1754425.973 | | brainfuck | 36983.97583 | 36093.7837 | | json | 1205.92764 | 1191.768986 | | bounce | 21.14001572 | 20.8851082 | While most benchmark results remain same, some tests such as `list`, `sudoku`, and `nbody` show improved performance compared to the array-based itables (may be thanks to the VM's optimization capabilities). **immutable array?** In this change, we implement itables using immutable structs However, we can use immutable arrays as an alternative. We implemented and benchmarked itables using immutable arrays, and the results show nearly same performance as the immutable struct-based implementation. WebAssembly/gc#250 v8/v8@6e36e3e Let's proceed with the immutable struct-based implementation for now because - While V8 seems to optimize immutable array-related operations, other VMs may not offer similar optimizations (?) - Currently, wasm-opt doesn't take into account the mutability of arrays in its optimization process.
4fbda49 to
614e228
Compare
sjrd
approved these changes
Sep 17, 2024
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Previously, we used mutable array-based interface tables (itables) without a specific reason. However, accessing mutable arrays can lead to missed optimization opportunities. For instance, loop-invariant code motion (LICM) won't be able to move certain parts of interface dispatching operations out of loops: When we invoke a method using interface table dispatching, it requires retrieving an itable from the class's itable array, which is considered non-pure.
In fact, reading from an array is marked as unsafe to move in wasm-opt's LICM implementation:
https://github.com/WebAssembly/binaryen/blob/34ad6a7598e662e9ff357987f2c81fde1e05c522/src/ir/effects.h#L207-L210 https://github.com/WebAssembly/binaryen/blob/34ad6a7598e662e9ff357987f2c81fde1e05c522/src/passes/LoopInvariantCodeMotion.cpp#L125-L128
(Note: We may not run wasm-opt's LICM in favor of the VM's LICM, as discussed in WebAssembly/binaryen#6924)
This commit changes itables to be immutable structs, making itable retrieval a pure operation. Here's a comparison of benchmark results between commit 4c9494e and this change:
While most benchmark results remain same, some tests such as
list,sudoku, andnbodyshow improved performance compared to the array-based itables (may be thanks to the VM's optimization capabilities).immutable array?
In this change, we implement itables using immutable structs However, we can use immutable arrays as an alternative. We implemented and benchmarked itables using immutable arrays, and the results show nearly same performance as the immutable struct-based implementation.
WebAssembly/gc#250
v8/v8@6e36e3e
Let's proceed with the immutable struct-based implementation for now because