Data count section is insufficient for shared data segments

[tlively]

The point of the data count section is to pre-declare the number of data segments so that the code section can be parsed to refer to pre-allocated segments. The code should be able to be generated and then the segments should be filled in once the data section is parsed and everything should just work. But there's not currently any way to know in advance if a data segment will be shared, so if the code needs to be generated differently for shared segments, we're plumb out of luck.

It seems we need to be able to emit the data section before the code section or introduce a beefier version of the data count section that can declare data segment types.

[conrad-watt]

if the code needs to be generated differently for shared segments, we're plumb out of luck.

Is there also a more immediate problem with streaming validation? If we say that memory.fill can't reference a non-shared segment in a shared function, the type of the segment isn't available in time for the code section to be validated.

I vaguely remember we discussed whether data segments would actually need shared and nonshared variants. Collapsing the distinction might theoretically leave some performance on the table, but might also be the least disruptive solution. If shared data segments did need different compilation, there could at least be an engine optimisation where modules with no shared functions could compile their data segments the "old" way. IIRC data segments can't be imported or exported so "thread escape analysis" is easier?

[rossberg]

Good points. As far as I'm concerned, the data count section was a wild hack and is an evolutionary dead end. Piling new hacks on top will just dig a deeper hole. The clean solution again is repeated and relaxed sections.

[tlively]

I would be happy if we required the data section to be ordered before the code section to support using shared data segments in the code. I don’t think we should jump all the way to fully relaxed sections without more motivation, though.

I agree that the data count section in particular is not something we want to grow organically to solve isolated problems, but I think the idea of systematically being able to decouple type declarations from their corresponding contents is fine. It’s what we do with the function section, for instance.

Do engines currently parallelize code section validation/compilation with loading of the data section?

[jakobkummerow]

Is there also a more immediate problem with streaming validation?

Yes, good point! Our prototype implementation isn't quite far enough to expose this yet, but I'm pretty sure we will run into this in due course.

repeated and relaxed sections

Unless I'm missing something, that solution would regress on the current design's motivation: to allow engines to start validating and/or compiling before the (potentially very large) data section has been downloaded.

Do engines currently parallelize code section validation/compilation with loading of the data section?

Yes: V8 validates functions concurrently while the rest of the module is still downloading.
V8 in its current default configuration doesn't compile functions eagerly, but AFAIK other engines do that, and the Compilation Hints proposal will likely provide a way for modules to explicitly request that behavior, so I think we do need a way to support that.

---

Without reordering sections (and paying the resulting initialization latency price), other options would be:

(1) Introduce a "Shared Data Section", and corresponding "Shared Data Count" to precede the Code Section.
(2) Require shared data segments in the data section to be grouped together at the beginning of the section, and have a separate Count section for them so we could have e.g. (module ... (data-count: 3) (shared-data-count: 2) (code: ...) (data: [shared], [shared], [non-shared]) ... ). The superficial details could be decided differently without changing the fundamental idea: make shared segments go last instead of first; make "data-count" and "shared-data-count" additive instead of the former being the total number of segments.
(3) Allow arbitrary interleaving of shared and non-shared segments in the data section, and replace the "data count" section with (conceptually) a bit vector indicating the sharedness of each segment. Or perhaps we'd call that a "data type" section then, and it'd have a byte for each segment, of which seven bits are reserved for future kinds of segment type annotations. Obviously this would come at a module size cost.

---

Side note: I'd like to point out that terms like "wild hack" and "evolutionary dead end", while they might be appropriately dramatic for expressing a strong personal preference, are unlikely to help us find consensus on the technical merits of various ideas.

[rossberg]

@tlively, for a while I also thought that separating declarations from definitions may be a sufficient solution. However, it has at least two shortcomings: (1) it isn't general enough to solve all streaming issues (e.g., in some cases — like globals — you may actually need to know the definition in time, not just its type), and inversely, (2) it also is too general, as it would naively allow arbitrary recursion between all definitions, unless additional restrictions akin to ordered sections are imposed (globals are again an example, where we must prevent cyclic definitions, including with element segments).

So some form of sequential syntax & semantics for definitions appears to be needed either way (and is a natural fit for streaming). But that generally requires to be able to split up certain sections into multiple parts. And once we introduce that, it's not clear that we still gain a lot by also splitting declarations from definitions, other than more complexity.

@jakobkummerow, it helps to identify our mistakes instead of fooling ourselves and pretend it was a well-designed and scalable solution. This isn't about blame but about acknowledging the situation — I'm blaming myself for it as well. FWIW, we already have a similar issue with globals vs element sections, which prevented us from allowing array.new_elem as a constant expression. And pre-declaring alone won't solve that instance, for the reasons mentioned above. So yes, our current approach is a dead end.

[eqrion]

@tlively

Do engines currently parallelize code section validation/compilation with loading of the data section?

Yes, SpiderMonkey can start compiling functions in parallel and on background threads as soon as we download them off the network. Having to download the data section first before beginning compilation would regress the total time to compile a module.

@conrad-watt

I vaguely remember we discussed whether data segments would actually need shared and nonshared variants. Collapsing the distinction might theoretically leave some performance on the table, but might also be the least disruptive solution. If shared data segments did need different compilation, there could at least be an engine optimisation where modules with no shared functions could compile their data segments the "old" way. IIRC data segments can't be imported or exported so "thread escape analysis" is easier?

I wasn't able to find any discussion of this, but I personally don't know of a reason to have the shared/nonshared distinction for data segments. SpiderMonkey already represents every data segment as an atomic refptr to an immutable vector of bytes. We do this because we hold on to the data segments from the module object, and modules are shared on the web (and probably everywhere?). So I don't think we'd ever really want to allocate these in some sort of local heap.

I also don't know of any code generation differences we'd do. Data segment payloads are immutable, so it's not like we'd need to emit any different kinds of loads/stores when reading from them from multiple threads.

[manoskouk]

I would like to revive this thread since the issue has come up multiple times in V8.
It seems to me the simplest solution is to drop the shared/nonshared data segment distinction. Is there an argument why we cannot do so?

[tlively]

So essentially we'd just say that all data segments are shared? That seems fine. We can revisit this if we ever find a reason why that wouldn't work.

edit: I added an agenda item to discuss this to the next threads subgroup meeting: WebAssembly/meetings#2022

[rossberg]

With the possibility of a concurrent data.drop, wouldn't that require synchronisation around every access to a data segment? Unless the engine can prove that drop can't occur concurrently? (FWIW, what actually is the semantics of a concurrent drop in the middle of a bulk read from the same segment?)

I'm a bit wary of making that the default. This would be another hack around the restrictive section structure. The Data Count section itself already was a hack, and it's biting back now. To me that suggests not continuing further down that road.

[jakobkummerow]

Allowing interleaving of partial sections may have its merits, but I don't think it's a satisfactory solution here. There's a good reason why the data section follows the code section; it's not great to say "yeah, well, with shared modules you just can't do that any more".

data.drop is a wrinkle indeed. Ideally, toolchains just never emit that instruction; it's a useless waste of CPU cycles anyway. But as long as the spec includes it, it must have defined behavior... I see a few possibly-viable options:

(1) New bulk ops on any thread cannot start after any thread did data.drop, but in-flight bulk ops will continue.
Pro: might be what you'd expect
Con: makes data segment accesses slower
TBD: is data.drop a synchronizing instruction, or do other threads only see its effect "eventually"?

(2) Access to data segments is effectively "thread-local": when one thread does data.drop, then only that thread cannot use that segment any more.
Pro: no perf cost, this behavior emerges naturally from the existing implementation (at least in V8, and I'd assume in other engines too)
Con: might be surprising (but again: ideally, just don't use data.drop at all, then you don't need to worry about any perceived weirdness of its behavior)

(3) Define data.drop to be equivalent to nop.
Pro: fast and simple
Con: technically a breaking change, might be too risky. Then again AFAICS it only turns traps into non-traps, so that might be okay?

[tlively]

At the threads subgroup meeting today, we considered that making data.drop a nop might be a nice solution. In V8, data.drop does not save any memory because the data segment is just a view into the module bytes. But @eqrion mentioned that data.drop is more useful in SM.

[eqrion]

In SpiderMonkey we only hold onto the code section bytes, not the full module. A data segment is an atomic reference counted pointer to a vector of bytes. Modules hold onto all data segments, while Instances hold onto just the passive ones. Dropping a data segment is implemented by nulling out the pointer from Instance to the data segment. If this was the last reference, it frees the bytes. I don't know how important this is in practice, but I could imagine cases where it's a nice property. This all also applies to element segments too.

This model works today because we don't have imports/exports of data segments (which I think we should have someday). If we did, we'd need to add an indirection so that dropping an imported data segment in one instance also drops it in all the other instances. IIUC, that's the problem we're facing with shared functions too.

Right now data.drop is specified to mutate to the data segment's length to 0. Could we alternatively model a data segment as a shared global that points at a nullable shared GC (array i8)? data.drop would be a write of null to the shared global. memory.init would be global.get and then an memory.copy_array. I'm pretty sure that'd have minimal synchronization costs. Engines could also avoid it in the case where none of the functions defined are shared.

[tlively]

Do you mean literally re-specifying data segments in terms of globals and arrays, or just specifying a concurrent semantics that behaves the same as an implementation in terms of globals and arrays would behave? The latter sounds reasonable to me.

[eqrion]

Just specifying equivalent concurrent semantics. Data segment + gc array unification could be cool (and I was tempted to suggest that) but I don't think we'd need to do that here.

[rossberg]

The data count section as we designed it obviously was too short-sighted. But hacking around the limitations of a bad hack with another bad hack and limitation doesn't strike me as long-sighted either. We should rather find a future-proof solution.

I suggest we fix the data count section by generalising it to a proper "data declaration section". That should be easy to implement, doesn't require changes to the semantics, and enables future extensions. Concretely:

• Similar to all other sections, it contains a list of entries; similar to the function section, these are data segment types that act as forward declarations.

• For the time being, there are only two types, unshared and shared, represented by a single byte; this provides an extension point to add more information in the future if necessary.

  datatype ::= 0x00 | 0x01
  

• To avoid adding a new section, we can extend the current: a data count of 0xffff_ffff is redefined(*) to be the marker for a "proper" data declaration section, and is followed by the list of types. The existing format remains as a shorthand for a list of default (i.e., unshared) data types.

  datadecsec ::= n:u32 list(datatype) (if n = 0xffff_ffff)
               | n:u32                (if n ≠ 0xffff_ffff)    (≡ 0xffff_ffff:u32 0x00^n)
  

  (Of course, adding a new section tag instead would also be fine, and perhaps is preferable.)

(*) A module with that many data segments, while theoretically valid a.t.m., would be at least 8 GiB in size if completely useless, a useful one more like 100s of GiB, so we can safely assume that doesn't break anybody in practice.