What are the benefits over having a particular "WTF-16 string reference" type?

[skuzmich]

This would allow working with JS strings without copy or validation in any language. This will be especially beneficial to many languages that use WTF-16 natively.

We could have instruction to encode such string using popular encodings (one-byte, UTF-8, UTF-16, WTF-16) from linear memory, data sections and GC arrays.
Iteration over unicode scalar value can be implemented in user-space without VM and spec support.

[wingo]

Heya @skuzmich :) Thanks for the question, it is a good one.

I think I should start by agreeing with you that it would be good if we can come up with a stringref that suits Kotlin's needs and which would be an obviously compelling replacement for the array(u16) that you currently use. See below.

I think the main reason is that as an encoding scheme, UTF-16 is already not optimal. Nobody designing a programming language would choose it, unless targetting a platform that is already bought in to it. As an indication, some implementations that target platforms with heavy UTF-16 investment are even switching or considering switching to UTF-8 (e.g. Swift). Baking a deep UTF-16 assumption into a new platform would be an error. I am not aware of anyone seriously arguing this point but would be happy to be corrected.

WTF-16 inherits the memory/performance problem of UTF-16 and adds the WTF-16-specific concern of isolated surrogates: something that's simply not a thing in any system you would design today. So in a way it's strictly worse, from a platform point of view.

That said... the principal motivation here is zero-copy sharing strings with JavaScript, and JavaScript must always have high-performance support for UTF-16 code unit indexing, and even support for isolated surrogates, even if an implementation eventually switched to UTF-8 internally. I think the challenge is to define stringref in a way that is abstract enough to not lock us in to always thinking of strings in terms of 16-bit code units -- meaning, probably we shouldn't start by saying "strings are essentially sequences of 16-bit WTF-16 code units".

But -- and here's the diff relative to the current proposal -- we should provide for efficient ways to advance string cursors in terms of UTF-16 code units, regardless of the representation used by the implementation. It may be though that the cursor is still opaque, and that there is no valid cursor position corresponding to the low surrogate of a surrogate pair; I think this could be a reasonable price to pay to get WTF-16 access without baking WTF-16 representation into the platform.

And, probably, given that on the web the door is open to isolated surrogates, we should probably go ahead and say "stringref is composed of USV's and isolated surrogates", add WTF-8/WTF-16 encodings (for string.new and string.encode), and in practice require implementations to carry a bit around indicating whether strings are proper USV sequences or not. This will complicate the acceptance criteria of stringref on non-web platforms but maybe it is the right choice.

As long as we're doing that though we should provide some more value in the stringref type and support ropes and slices -- though there, if we keep the "one cursor position per codepoint" point of view, we will have to be careful about splitting and joining surrogate pairs.

So, some things to work on. I feel like there's something valuable here and we should orient the proposal in that direction.

[skuzmich]

Thanks for detailed reply!

I think the main reason is that as an encoding scheme, UTF-16 is already not optimal.

For JavaScript and other WTF-16 languages like Kotlin, WTF-16 is an optimal string interface because this is the most-performant interface that language provides. Developers rely on it being fast. Iteration over USV is considered as something "extra" on top of that.

Baking a deep UTF-16 assumption into a new platform would be an error.

It is already baked into Web via JavaScript and DOM. It would be great if we could introduce support for superior encoding for new languages without hurting existing ones.

WTF-16 inherits the memory/performance problem of UTF-16 and adds the WTF-16-specific concern of isolated surrogates: something that's simply not a thing in any system you would design today. So in a way it's strictly worse, from a platform point of view.

This statement feels biased towards "system you would design today" as opposed to systems that we already have.
If you are an WTF-16 languages, you would have performance overhead when accessing UTF-8 encoded strings via WTF-16 interface with breadcrumbs. Wouldn't it be beneficial give to implementation a choice of which encoding to use? Perhaps, multiple stringref types with concrete encodings?

And, probably, given that on the web the door is open to isolated surrogates, we should probably go ahead and say "stringref is composed of USV's and isolated surrogates",

Wouldn't it make isolated surrogates a "thing in a system you would design today"? :)

It feels like this proposal aims to create a single universal string reference type while compromising on important concrete use-cases, like WTF-16 <-> WTF-16 interoperation. Have you considered having multiple, more focused stringref types?

[wingo]

Hi :)

If you are a WTF-16 language, you would have performance overhead when accessing UTF-8 encoded strings via WTF-16 interface with breadcrumbs.

If you think of whole-system performance, I think there are reasons to believe that WTF-8 might be the right string representation even for Kotlin: less memory, less polymorphism, less overhead when exchanging strings with the world. Swift made that choice and I am aware of a number of other language implementations whose strings are sequences of 16-bit code units that are considering switching too. Because whole-system performance is a function of a number of different subcomponents, I think focusing simply on this one piece may miss the big picture.

Besides that, languages do evolve over time. The arrow of time in strings points towards iteration rather than random access, and I think this proposal should probably make iteration the primary interface and lazily layer random access on top when needed, as Swift does.

And, probably, given that on the web the door is open to isolated surrogates, we should probably go ahead and say "stringref is composed of USV's and isolated surrogates",

Wouldn't it make isolated surrogates a "thing in a system you would design today"? :)

Touché :)

It feels like this proposal aims to create a single universal string reference type while compromising on important concrete use-cases, like WTF-16 <-> WTF-16 interoperation. Have you considered having multiple, more focused stringref types?

How would this work? Keeping in mind that the goals of "zero-copy" and "no new string implementations on the web". I don't see it clearly but perhaps I am missing something.

[skuzmich]

If you think of whole-system performance, I think there are reasons to believe that WTF-8 might be the right string representation even for Kotlin: less memory, less polymorphism, less overhead when exchanging strings with the world. Swift made that choice and I am aware of a number of other language implementations whose strings are sequences of 16-bit code units that are considering switching too. Because whole-system performance is a function of a number of different subcomponents, I think focusing simply on this one piece may miss the big picture.

Good point! Modules with heavy internal string processing would favour internal encodings (WTF-16 in case of Kotlin) and those that exchange strings with "incompatible" host would want to eat costs of Char access and adapt to host's representation to avoid copies. It seems like there are use-cases of choosing string representation even within a single host (via compiler option, for example).

Besides that, languages do evolve over time. The arrow of time in strings points towards iteration rather than random access, and I think this proposal should probably make iteration the primary interface and lazily layer random access on top when needed, as Swift does.

Would providing low-level random access hurt iteration in any way?

How would this work? Keeping in mind that the goals of "zero-copy" and "no new string implementations on the web". I don't see it clearly but perhaps I am missing something.

"WTF-16 string reference" is certainly "zero-copy", and "zero-access-overhead" on top of that.

Goal "no new string implementations on the web" can be achieved using type imports. For example, if browsers would not want to implement UTF-8 - you could provide it via Wasm module. Similarly, in UTF-8-only embedding, Kotlin can bring its WTF-16.wasm to fill the gap.
This goal seems to only aim at reducing complexity, while hurting performance of important use-cases. Also, you'll get some complexity discount by not implementing cursors, surrogate replacing, etc.

Are there UTF-8 language toolchains that want to share strings with UTF-8 host via this special string type? If not, we could postpone adding non-WTF-16 strings until there is a demand for them.

[skuzmich]

Also, providing low-level API for JavaScript string could help many languages that compile to Wasm to improve string processing performance in cases when they don't care about surrogates. For example, in cases like "count the number of lines" or "parse CSV" we don't have to match surrogates and combine them into USVs, this would be a wasteful operation.
I'm no string processing expert, but my intuition is that current proposal would put all Wasm languages, including C++, at disadvantage when processing JS strings compared to JavaScript itself. I would like to know what you think.

[skuzmich]

Idea of a proposal focused on JS string interop:

• Scope the proposal to achieve Goal (1.) only: "Enable WebAssembly programs to efficiently create and consume JavaScript strings".
• Put this under WebAssembly JavaScript Interface spec. Core Wasm spec might be more reluctant to add such a high-level host-specific concept.
• Initially provide the minimal viable set of methods:
  • charCodeAt
  • length
• Other JS string methods could be imported from JS without special optimisations. Overhead of import calls and JS glue for many such functions may end up being insignificant compared to cost of their useful action.
• Use type imports for String reference type and function imports for charCodeAt and length. This would enable polyfills for non-JS hosts.

Benefits over proposed stringref:

• We can access JS strings efficiently without compromises.
• Languages that use WTF-16 string could use such string as their default string.
• We don't have to argue which string encoding/interface is better. We provide what we already have in JS.
• We don't have to specify lone surrogate handling. We provide JS strings to Wasm as-is. Languages and libraries can efficiently do whatever they want: replace, trap, throw an exception, ignore, etc.
• We don't have to specify anything for non-JS runtimes.
• We don't add non-portable instructions. Imports can always be polyfilled in a portable way.
• Cursors are just i32s: simple, portable, serialisable, storable in linear memory.

Missing instructions:

• string.new is currently not representable as an import due to a lack of first-class memory references. Call to JS in MVP.
• string.const can be implemented as JS string literals imported to Wasm.
• string.advance and string.rewind are not needed. Use i32.add or i32.sub instead.
• string.measure and string.encode would be useful in JS too, wouldn't they? If so, they could be added to JS and then imported to Wasm.
• string.eq is covered by endsWith.

---

Good universal zero-copy string type could be implemented separately in user-space Wasm. In addition to host strings, it would probably make sense to abstract linear memory and GC strings, all under a single USV iteration interface. This could become a zero-copy alternative to interface types strings. There can be other variants of such optioned string types, unlike in core Wasm, which tries to be language-neutral.

[wingo]

Benefits over proposed stringref:
* We can access JS strings efficiently without compromises.

I don't know if you have ever worked on a JavaScript implementation but FWIW this is not necessarily the case:

• Rope strings make charCodeAt less efficient than you might think.
• Polymorphism will essentially ensure these are always callouts, not inline code.
  • Tight loops operating on string content will always spill
• You only get to access one code unit at a time, precluding simd algorithms
• I think it's likely that some JS implementations will in the future actually represent their strings internally using UTF-8, making this api suboptimal

* Languages that use WTF-16 string could use such string as their default string.

This goal is also achievable with this proposal.

I think that if you focus on just JS, removing other WebAssembly implementations and removing other languages, then I think there is little reason to do this over externref + imports (#1). What if you just import charCodeAt and length, does that solve your use case?

[skuzmich]

I don't know if you have ever worked on a JavaScript implementation

I have not. I really appreciate the opinions of the experts! :)

Rope strings make charCodeAt less efficient than you might think.

How string.cur that uses same indices be any better?

Polymorphism will essentially ensure these are always callouts, not inline code. Tight loops operating on string content will always spill

I'm afraid I fail to see how stringref helps with this.

You only get to access one code unit at a time, precluding simd algorithms

How would SIMD help stringref? Even if we somehow will deal with polymorphism, SIMD version of charCodeAt would be more efficient than string.cur because code units are stored continuously in memory, wouldn't it?

I think it's likely that some JS implementations will in the future actually represent their strings internally using UTF-8, ...

This is very interesting! Could you provide more information, which VMs are planning to move to UTF-8 and when?

... making this api suboptimal

Would this hit JS in the same way? Would JS mitigations be applicable to Wasm too?
This would make current string.cur suboptimal as well.

What if you just import charCodeAt and length, does that solve your use case?

Yes, if we can do it without performance issues described in #1

[wingo]

Thanks @skuzmich for your feedback -- it was really useful. In the end we decided to explicitly support WTF-16 access via stringview_wtf16. Kotlin should be able to use this interfaces with as few compromises as possible -- for free on WebAssembly implementations in browsers and in JS, and close to free on WebAssembly implementations that prefer to store strings as WTF-8. Your thoughts are very welcome. Closing this issue for now, and please do open more issues as you find them!

[wingo]

(Most of the concerns addressed in #36)