search

WebAssembly / spec

WebAssembly specification, reference interpreter, and test suite.
https://webassembly.github.io/spec/
Other
3.11k stars 439 forks source link

Is "large" test required for compliance? #1619

Closed SoniEx2 closed 1 year ago

SoniEx2 commented 1 year ago

Is the br_table "large" test required? Some platforms (e.g. JVM bytecode) simply do not support jump tables that large.

sunfishcode commented 1 year ago

I would propose considering it required. It appears to contain 25340 entries, which is large, but not unreasonably large in contexts like binary decoding or lookup tables. Large jump tables can be split up into small jump tables by using eg. binary search with comparisons and branches to split the range into ranges small enough to be encoded.

SoniEx2 commented 1 year ago

25340 entries requires 101360 bytes in JVM bytecode.

we only have 65535 bytes to work with.

rossberg commented 1 year ago

What would be the max number of entries that you can handle without splitting up the function?

SoniEx2 commented 1 year ago

less than 16380 (tho at 16380 there wouldn't be space for anything else)

rossberg commented 1 year ago

Personally, I'd be fine reducing the example to a number like that, if there is a concrete implementation to justify it with and test against. Does that actually exist or is the question just hypothetical?

SoniEx2 commented 1 year ago

wasm2kotlin (targets JVM) exists, yes. tho we're unsure what exact size it needs to be in order to fit.

rossberg commented 1 year ago

Well, thus my question earlier. Can you find out?

SoniEx2 commented 1 year ago

looks like we need to optimize wasm2kotlin codegen. it's currently having an overhead of 4 extra bytes per branch - so it only fits about 8190 entries instead of the theoretical 16380. it should be able to do at least 16370 (there's still gonna be a bit of overhead) once we fix this.

will check back in once we have that done.

ericprud commented 1 year ago

At some point, we discussed a base conformance plus a small number of features, e.g. "2.0 + FwSimd + TailCall". Would it be useful to consumers to have a sense of the size of the jump table they could expect an implementation to handle? (Also, would it be nice to have a tool that read a .wasm and estimate the features required to execute it?

SoniEx2 commented 1 year ago

we have managed to compile it with 16149 cases

(kotlinc 1.8 appears to have a bug, where it unnecessarily generates some extra branches, so it does eat at the max a little. kotlin 2.0 (experimental) gets us to at least 16353.)

(yes, these are in 34-case chunks.)