GC story for strings?

As of the MVP document, strings can be expressed as either an (array i8) or (array i16) per a language's string encoding, but with only one character at a time being accessible with array.get and no compatibility with JS strings I'd imagine that the MVP will not be very useful beyond pure experimentation if a language wants to target GC primarily. Think comparing, hashing, substrings, etc.

The Post-MVP document for instance mentions bulk-operations, in particular array.copy which is a start but won't help with strings, and to my surprise doesn't mention strings so far.

Hence I have questions:

Are there any plans yet to address strings in particular?
Is it reasonable to expect that Wasm strings and JS strings will be API-compatible eventually, so Web APIs can be called efficiently from Wasm and vice-versa?

Interface Types are supposed to handle the conversion from one string encoding to another

Yeah, this is somewhat a continuation of my infamous thread on UTF-16 over at interface types. Give it a read if you haven't yet, it's great. There is indeed some overlap between the two, and my impression is that interface types will be useful in the absence of GC, but we'll still need a better story in the presence of GC, most likely integrating with the parts of interface types that apply to both.

To give an example: A language may chose to not rely on linear memory at all, but use GC objects exclusively, including to represent strings, and there may be the expectation that these strings can be passed to or received from Web APIs, and that dealing with such strings internally to a module is reasonably efficient. Neither interface types nor GC, in its current forms, are very useful there, unfortunately.

The GC proposal is not responsible for this kind of interlanguage interop. Different languages represent the same high-level concepts differently in their low-level representations for a variety of reasons. For example, OO languages need strings to have a v-table with references to an i-table and to reflection information, and each of those would need to be organized according the specific OO language's APIs. Some languages/libraries represent strings as trees. Then of course there are the issues with encodings. Given the diversity, it seems difficult for there to be a concept like "wasm string" that different systems could reasonably use for interop without copying or wrapping. This is why the Requirements document explicitly lists this kind of interop as a non-requirement.

The requirements document also states the opposite in critical success factors, and I am very surprised to see this argument being made. If we don't have a good story for strings in Wasm GC, and given that strings are by far the most common higher data structure in most programming languages (and very common to be consumed and produced by Web APIs), I'd go as far as to say that we are about to make a critical mistake endangering the success of Wasm as part of the Web ecosystem. Not tackling this will significantly undermine the viability of AssemblyScript in favor of systems languages compiling to Wasm for example, and as such some might see this as an unexcusable standards body decision. That's exactly what I was concerned about in my comments on the requirements document.

There is a middle ground. WebAssembly (and specifically GC) can provide the infrastructure for interop without baking specific interop designs into its core design. So someone can design a specific way to represent strings using GC/wasm types, and then various languages can choose to use that particular representation to facilitate interop. This includes JS, though you'll have to get the browsers to agree to do so. Or someone can design a module interface (with an abstract exported type) for string values and operations that wasm modules can link to and which each browser can implement according to how it implements JS strings. (For this to be efficient, you'll want a better compilation model though, which would be useful for a variety of reasons.)

The high-level idea is that interlanguage interop is an ecosystem problem, not a low-level problem, and it is best served in WebAssembly by developing low-level mechanisms that can support various ecosystem solutions.

To me the middle ground is to ensure good interoperability with JavaScript as a critical success factor, not necessarily between arbitrary languages, and I was under the impression that this is what browser makers and the overwhelming majority of the group want as well. The arguments and suggestions you are bringing up might be worth to explore, of course, who knows what we'll be getting out of it, but so far I don't see a clear merit in making this any more complicated than it needs to be.

Concur with Ross here. The kind of interoperability you seem to be asking for is already impossible with JS. Most engines, including V8, use a multitude of internal representations for JS strings. The differences are 'papered over' at the source level.

I am completely stumped by the responses and will have to think about it for a bit. Might well be that betting on Wasm GC and trusting you with the changes made to the requirements document instead of following up on my points was a mistake.

@dcodeIO

@dcodeIO It would be helpful if you would more concretely illustrate the use cases you are concerned about. You mention wanting something like array.copy for strings and wanting to interop with JS strings, but these two desires seem to be contradictory given that JS strings are not represented in real engines as arrays. (Here is a summary I found of V8 string representation.) I feel like your needs might be met by having a host-implemented string library (as I suggested above) with a function for constructing a new string from the contents of a given mutable array (it has to be copied because JS strings must be immutable), and possibly another for constructing a new string from an immutable array. But without concrete illustrations of those needs, I can only guess.

@RossTate

There seem to be two needs at play here: 1) String manipulation in the GC proposal needs to be competitive with string manipulation in linear memory and 2) JS interop is generally important, and interop with JS strings is particularly important.

On the first point, I agree that the current MVP seems to leave a lot on the table since it can only access one array element at a time. It seems that the best solution would be to have instructions akin to the variety of MVP load and store instructions that operate on i8 arrays (or arbitrary integer/number arrays?) rather than linear memories.

On the second point, the complexity and diversity of string representations in JS engines make it infeasible and undesireable to expose the underlying structure directly to WebAssembly, as @RossTate pointed out. That leaves two possible paths for first-class JS string interop: A) a "wasm string" type is introduced with instructions corresponding to all the common string operations that can be an abstraction directly on top of an engine's native JS string representation, or B) the JS API defines a coercion from JS strings to GC types and vice versa to make passing strings into and out of WebAssembly simpler.

Both of these solutions are problematic. (A) does not fit in with the goal of having the GC proposal represent only low-level representation types and as Ross mentioned, most languages would not be able to use a native "wasm string" as their string type anyway. There's also practically very little difference between (A) and just importing a string type and functions on it from the environment, which will be possible with type imports. (B) is problematic because there is no good way to choose which representation of strings as a GC type to choose. Choosing any particular "blessed" representation would inherently favor some source languages over others, so it would be better to produce a more general solution like interface types, that can work for all languages.

most languages would not be able to use a native "wasm string" as their string type anyway

Actually, I think a first-class immutable string primitive that "papers over" the underlying byte encoding could still help a lot, even for languages that have a different native string representation.

For example, while C# might not be able to adopt "wasm string" as the underlying representation of System.String, C# could expose this new type as 'System.Interop.WebAssembly.WasmString' and let C# developers choose if they want to use the new zero-copy WasmString or pay the cost of transcoding to get a classic C# string.

I think option (A) is worth pursuing further.

@tlively

One specific point: We are discussing strings here on the GC proposal, but the issues are separable. It's very possible strings do not fit in with the goals of the GC proposal (as @tlively just mentioned), but also that @dcodeIO 's requests are valid and should be addressed by adding a string type to wasm in another proposal.

My perspective is that we should add a string type to wasm, perhaps doing that in a separate proposal all by itself. The benefit of a string type would be similar to string types in other multi-language VMs (CLR, JVM, and for that matter JS) - they allow quick and easy passing of string data between languages. C won't use it (just like it won't on the CLR), but I understand @dcodeIO to be asking for AssemblyScript to be able to interop with JavaScript the way that TypeScript and many other languages that compile to JS can. That's a good goal!

@tlively

Great points above. And I'm realizing (thanks to @tlively's post) that I overlooked a concern raised in the OP about arrays. Sorry @dcodeIO!

On arrays, one thought that's come up a few times is having linear memories within GC objects. This came up in at least #94 / #109, and in WebAssembly/interface-types#68 there is some discussion of slices, where I think it would be nice from an interop perspective for a slice to be either a view into a linear memory or a view into non-referential data within a GC object.

I like the idea of a separate proposal for strings. In Java or equals languages you can hold the "native" string inside the language string like the native array inside an array object.

Currently a string from JavaScript can only hold as a erxternref. I can not check an equals, etc. It is like a black box.

That with Interfaces types a string must convert on every call. This will never effective.

I expect even a separate "add a string" proposal is fraught with peril because there are so many fundamentally-incompatible low-level design choices with strings that will ultimately force the proposal to bias towards one subset of languages at the expense of others.

One alternative route for JS that I've been imagining is:

the wasm module preimports a type that it uses as the host's string type, as well as function preimports for each string operation which use the imported string type in their signatures
the wasm module gets preinstantiated with some WebAssembly.StringType singleton (defined by the JS API to mean "the JS string type") and JS built-ins for each string operation (adding new ones for operations that don't already exist)
because preimports are used, the wasm engine is encouraged to statically specialize the machine code to the specific imported values, achieving essentially the same performance as core wasm types/instructions (to a knowing engine)

The advantage of this approach is that, when targeting a Web embedding, a wasm module can use operations that precisely match JS strings while a module targeting, say, a future Go embedding could import a completely different set of Go-string-appropriate operations.

Ultimately, if your aim is to write a single module that can be used across many different hosts, I think you're going to end up with an impedance mismatch unless you make a copy at the wasm/host boundary into and out of the wasm module's own private string representation. But if you're targeting only a single host and the source language is intentionally embracing the host's string type, then the preimport approach seems pretty good.

Gone through it now and made notes:

One (more generally) interesting aspect is that GGC assumes that copying is possible (it typically is if everything is JS with no external references), which might not be the case everywhere, especially off the web. Wondering if my observation has impact in practice, though, because copying may be hidden behind the ref types iff native code must unwrap the string first, i.e. likely copy so no references can break. If it wouldn't unwrap and copy, but reference, objects in the nursery that are live cannot be moved (technically can still be copied if the object is immutable like strings, not sure if there are other implications) without breaking the reference for instance. Thought I mention, because there might be other implications for GC algorithms off the web with this that might be interesting to talk about in other discussions.

we refer to Nursery collections as minor GC

and it also incurs some overhead during normal operation

Then, this summarizes my first impression above quite well: One reduces the amounts of major GCs to do, but still has the cost of minor GC including whatever a minor GC implies, like promoting objects or more work to do overall simply because the concept is there. Might be small, though, but it's not free.

Then there are also situations like

Consider the question of how to figure out whether some Nursery object is live. It might be pointed to by a live Tenured object — for example, if you create an object and store it into a property of a live Tenured object.

So we only care about the Tenured objects that have been modified since the last minor (or major) GC [...] In technical terms, this is known as a write barrier.

With a store buffer, the time for a minor GC is dependent on the number of newly-created edges from the Tenured area to the Nursery, not just the number of live objects in the Nursery.

indicating not immediately obvious overhead in minor GCs that are more complex than bump allocating, leading to

Also, keeping track of the store buffer records (or even just the checks to see whether a store buffer record needs to be created) does slow down normal heap access a little, so some code patterns may actually run slower with GGC.

indicating additional work to be necessary to enable the concept. and that there are other implied drawbacks again.

You are still right that

On the flip side, GGC can speed up object allocation.

but then the conclusion of the ideal-case (only) micro-benchmark still correctly (and I value that!) states

Note that this benchmark is intended to highlight the improvements possible with GGC. The actual benefit depends heavily on the details of a given script. In some scripts, the time to initialize an object is significant and may exceed the time required to allocate the memory. A higher percentage of Nursery objects may get tenured. When running inside the browser, we force enough major GCs (eg, after a redraw) that the benefits of GGC are less noticeable.

Hope this writeup, which is really just my impression from reading the pieces (and I only have good enough experience, I'm not an expert), is useful :)

On another note on WTF, I found this document on unicode.org, and under 2.7 Unicode Strings it says:

Depending on the programming environment, a Unicode string may or may not be required to be in the corresponding Unicode encoding form. For example, strings in Java, C#, or ECMAScript are Unicode 16-bit strings, but are not necessarily well-formed UTF-16 sequences. In normal processing, it can be far more efficient to allow such strings to contain code unit sequences that are not well-formed UTF-16—that is, isolated surrogates. Because strings are such a fundamental component of every program, checking for isolated surrogates in every operation that modifies strings can create significant overhead, especially because supplementary characters are extremely rare as a percentage of overall text in programs worldwide.

So seems Java and C# don't strictly need well-formedness just as JS. Perhaps it's even fair to conclude that this is rather the norm than the exception, so the WTF family of encodings makes perfect sense. Also mentions other benefits I haven't brought up yet.

Why should there be different encoded strings? There can be different factory instructions for an abstract string type. The internal representation of the string should be a job of the host. Java use internally also different encodings for strings.

A string.len should return the length without the knowing of the encoding that was used for creating.

The idea behind both 8 bit and 16 bit encodings (these are the two used in practice) is a use case like this: If we specify only an 8-bit encoding, and a module using a 16-bit encoding in its language passes a string to another module using a 16-bit encoding in its language, and now the second module wants to know the length of the string in its 16-bit encoding again for instance, then we end up in a situation where the first module has to (implicitly) re-encode, and the second module has to implicitly re-encode again. That's essentially the double re-encoding problem motivating WebAssembly/interface-types#13 years ago, and it also applies if no encoding is specced but the engine picks one.

The JavaScript language has also different implementations of a string. And there is no re-encode needed to return the length. You think too much in low level programming language. A sting is a high level object on the . It can be a list of 8 bit and 16 bit chunks and more more. A length is only an attribute of it.

Important is that a string reference is immutable.

A string reference from u8 and from u16 can be equals that a ref.eq must work between both. Also a concat must be possible.

If I need to know the encoding from the creating module then every module must re-encode it to its own encoding. Then there are exists more as one string reference type. But last not least. If I pass such string to JavaScript then the call to length() must also work without knowing of the crating encoding.

Noticed that you are working on JWebAssembly, which I think will have to solve very much the same challenges AssemblyScript has. If you want, I can offer to meet up with you on say Discord so we can discuss this in more detail? Curious to see how your adventure is going, and to have your ideas. (btw, seems we are both from .de)

@dcodeIO

@dcodeIO We can discuss this on https://discordapp.com/channels/453584038356058112/731539251698729030/765641907065192460 or any other location.

@dcodeIO

Agree with @dcodeIO and @Horcrux7 on a lot of points here. Wasm needs efficient immutable UTF-16-ish strings which are fully compatible with JS/DOM string in both directions. It doesn't make sense to copy strings on Wasm boundary, for languages, like AssemblyScript, Java and Kotlin, which are fine with using JS string encoding.

@jakobkummerow I wondering, is some form of this implementable in engines?

@skuzmich

@skuzmich : Sure, we obviously have support for JavaScript strings, and exposing those to Wasm would be easy. We don't have UTF-8/WTF-8 support yet, and adding that likely wouldn't be pleasant in terms of implementation complexity, but it's certainly doable. I think it mostly boils down to a spec question: what kinds of strings and string operations do we want to have in Wasm?

I agree that for JS<->Wasm interop in particular, having compatible strings would likely be very handy. I have no particular opinion on what Wasm strings should look like. Following the discussion here with interest. Given the complexities around strings, I'm inclined to think that while they feel related to the GC proposal, they probably deserve to be split out into their own proposal, just to let us focus on one thing at a time.

As an example: JavaScript, by spec, requires UCS2/WTF-16, so JS engines support that. It turns out that lots of memory is occupied by strings in many web apps, and many of those strings are one-byte strings, so V8 actually uses a one-byte ("latin1") encoding internally when possible. That makes everything much more complex, and requires copying conversions every now and then, but the memory savings are considered worth it. I see this as one data point illustrating how tough the tradeoff space is, and what kinds of ugly compromises Wasm strings may have to make in order to satisfy a number of competing goals.

My understanding is that 1-byte strings in JS engines are a 1-byte subset of Unicode (eg, ISO 8859-1) which maintains the core invariants:

length is fixed and known
reading a character code by index is possible O(1)
the character codes are the same
the contents and length are immutable

Copying from a 1-byte to a 2-byte string would only be required if you were already copying it for some reason, such as a concatenation.

None of these conditions would be true of UTF-8/WTF-8 strings which seem to be proposed as the alternative to UCS-2/WTF-16.

@jakobkummerow

@jakobkummerow thanks! People had concern that multiple internal representation of JS strings could prevent Wasm from efficiently using them. It is reassuring to hear that it is doable.

JS String operations that Kotlin's String class would care about are:

Construction from an array of 16-bit units.
Getting length.
Getting i-th 16-bit Char.
Checking content equality of two strings.
String concatenation.

Last two are easily implemented using others, but if they are optimized for some variants of internal representation, it would be nice to have them in Wasm.

Btw this issue may relate to discussion about UTF16 vs UTF8 interop here:
WebAssembly/interface-types#38

@dcodeIO

I think the interface types question about UTF-16 vs WTF-16 is quite separate from the question about whether, within a component, we want to allow passing strings across certain language boundaries. Here's my mental model of the situation, but I may be misunderstanding the point of components, so please correct me if this doesn't match others' intentions.

At big component boundaries, surrogate-checked UTF-16 makes sense to me, maybe with an opt-in for WTF-16 omitting surrogate checks. Coming from JS, this regularity will cost a linear-time scan, in addition to probably flattening (of the internal rope data structure) and maybe copying the string (depending what it ends up linking to). I'd be fine with including an unchecked WTF-16 domstring type initially, but I have no strong opinions, but I don't really see the rush.

Within a component, it will often be important to mix multiple programming languages, but it is even more important to avoid linear-time copies, checks, conversions between 8-bit and 16-bit string representations, and flattening of ropes. The importance is greater because there is more frequent expected back-and-forth within small modules of a component. This back-and-forth is amplified by how there can be reference circularities within a component, whereas there is a hierarchical relationship between components.

One example of such tight back-and-forth interaction which @dcodeIO provides is interaction is between AssemblyScript and JavaScript. In Igalia, we're interested in providing good cross-language support between C/C++ and JavaScript. In both cases, copying, flattening, converting between 8-bit and 16-bit, or doing a linear-time check over the string to detect missing surrogate pairs would add significant cost, due to the intention to enable lots and lots of strings crossing the boundary.

For the within-component case, the ideal solution would allow not just malformed surrogate sequences and 8-bit strings as V8 has, but also would allow JS Strings implemented as ropes (e.g., as the result of concatenation) to be passed to Wasm, possibly manipulated, and passed back, without verifying paired surrogates or even flattening the string.

To add a new type: my own personal aesthetics would be to start simpler, with a single built-in type and instructions to manipulate it, rather than the more complex pre-import strategy, but either option could be OK. (I'm OK with a built-in type being a little opinionated; I'm not sure if true neutrality is ever possible.)

I agree with others on this thread that a solution in this space is related to the Wasm GC proposal, but probably makes sense to pursue separately from this repository. In principle, such a separate proposal wouldn't actually depend on the GC proposal, since it could be refcounted, but I think we'd want to make it a subtype of externref (so, overall, it's very similar to typed function references). This new string type (or pre-import scheme) could provide a lot of value for both @dcodeIO 's and Igalia's use cases.

I suggest that we continue with the current MVP approach, to start out both Wasm GC and interface types without a solution for zero-copy, fully expressive string sharing across languages and components, while working in parallel on further proposals in this area such as the domstring interface type and a built-in Wasm string type (or pre-import scheme).

Now that we have https://github.com/WebAssembly/stringref, I'll go ahead and close this issue. Without that additional proposal, the options for strings include importing them as anyrefs or using byte arrays.

Navigation Menu

Repository navigation

GC story for strings? #145

61 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

GC story for strings? #145

Description

Activity

KronicDeth commented on Sep 30, 2020

dcodeIO commented on Sep 30, 2020

RossTate commented on Sep 30, 2020

dcodeIO commented on Sep 30, 2020

RossTate commented on Sep 30, 2020

dcodeIO commented on Sep 30, 2020

fgmccabe commented on Sep 30, 2020

dcodeIO commented on Sep 30, 2020

RossTate commented on Sep 30, 2020

tlively commented on Sep 30, 2020

DLehenbauer commented on Sep 30, 2020

kripken commented on Sep 30, 2020

RossTate commented on Sep 30, 2020

Horcrux7 commented on Sep 30, 2020

lukewagner commented on Sep 30, 2020

61 remaining items

dcodeIO commented on Oct 11, 2020

dcodeIO commented on Oct 11, 2020

Horcrux7 commented on Oct 12, 2020

dcodeIO commented on Oct 12, 2020

Horcrux7 commented on Oct 12, 2020

dcodeIO commented on Oct 12, 2020

Horcrux7 commented on Oct 13, 2020

skuzmich commented on Oct 14, 2020

jakobkummerow commented on Oct 20, 2020

bvibber commented on Oct 20, 2020

skuzmich commented on Oct 20, 2020

MaxGraey commented on Oct 30, 2020

littledan commented on Aug 3, 2021

tlively commented on Apr 29, 2022

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions