Switch AssemblyScript to UTF-8 by default?

[dcodeIO]

Given the amount of foregoing heated discussions on the topic, especially in context of Interface Types and GC, I am not getting the impression that anything of relevance is going to change, and we should start planning for the worst case.

So I have been thinking about what would be the implications of switching AssemblyScript's string encoding to W/UTF-8 by default again, and that doesn't look too bad if all one really wants is to get rid of WTF-16, is willing to break certain string APIs, wants it to be efficient after the breakage and otherwise is not judging.

Implications:

• String#charCodeAt would be removed in favor of String#codePointAt
• String#charAt would be removed, or changed to retain codepoint boundaries if viable
• String#[] would be removed, or changed to retain codepoint boundaries if viable, or to return bytes numeric like C
• String#length would return the length of the string in bytes
• Sting.fromCharCode would be removed, or deprecated and polyfilled
• String#split with an empty string separator would split at codepoints
• Ill-formed Unicode would be rejected
  • if it can be done efficiently
  • if not, we'd have to think about WTF-8 instead
• Anything returning a character offset before would return a byte offset after:
  • Most String APIs would "just work" with byte offsets instead of character offsets as well
  • Mileage may vary if one uses string APIs with constant (incremented) offsets, as that would not map well anymore
    • Example: The compiler's tokenizer would need to skip codepoints instead of += 1

Means we'd essentially jump the UTF-8 train to have

• efficient calls to WASI APIs
• efficient calls to DOM APIs typically accessed with 7-bit ASCII strings (think .className = "abc)
• the same problem as everyone else where 7-bit ASCII is not enough

Note that the proposition of switching AS to UTF-8 is different from most of what has been discussed more recently, even though it has always been lingering in the background. Hasn't been a real topic so far due to the implied breakage with JS, but unlike the alternatives it can be made efficient when willing to break with JS. Certainly, the support-most-of-TypeScript folks may disagree as it picks a definite site.

If anything, however, we should switch the entire default and make a hard cut because

• maintaining two string implementations, and ensuring that all APIs work with both, is not exactly realistic
• maintaining a single string implementation understanding both encodings would yield the problem we are trying to avoid in Wasm, but in AS
• any of the above would often double code size of string operations

Thoughts?

[MaxGraey]

You know my opinion. I agree with everything except the point that it should be the default and suggest creating a new string class using UTF-8 and more stricter / limited API with a shorter name str. Also add conversions on language level for str <-> string

[dcodeIO]

The problem I see with maintaining two string classes is that we are essentially making WebAssembly's problems ours, as part of the language. Of course providing say a separate String8 class is not necessarily bad, just having it is fine, but any attempts to integrate it with the rest of the standard library are most likely doomed from the start. To make proper use of that second class with external APIs for instance, without inflicting the burden to re-encode before the final destination of the string, we would have to provide say two abstractions around WASI, or the DOM, or whatnot. Plus, everyone building a library for AS would have to do the same if they wanted to support both as input without re-encoding where possible. As far as I am concerned that's not feasible.

Apologies if anything I say is irrelevant to this, or if I've misunderstood anything.

WebAssembly/interface-types#13 (comment)
WebAssembly/interface-types#13 (comment)

According to the interface-types proposal itself, UTF-16 will not be at any performance disadvantage compared to UTF-8 or even ASCII.

Btw, WTF-8 shouldn't be a viable target, as out of range Unicode characters would trap, which UTF-8 does not enforce.

String#[] would be removed, or changed to retain codepoint boundaries if viable, or to return bytes numeric like C

This could simply be made an O(n) operation by iterating. Unfortunate, but it would keep TS/JS compatability. (also, unindexable strings lose a whole lot of value)

[dcodeIO]

The performance disadvantage I worry about is when chaining modules. Say for instance you have a webapp written in Rust, a form validator written in AssemblyScript, a RegEx engine written in C++ and a database written in Java. Then a user inputs "something".

webapp: utf8
  to validator: utf8->wtf16
    to regex engine: wtf16->utf8
      capture groups to validator: utf8->wtf16 (for each)
  to database: utf8->wtf16
    store to file: wtf16->utf8

Now that's kinda a constructed example, but it helps to illustrate the general problem we'll eventually be dealing with. At any point, in any module graph, there may be an AssemblyScript module in between two Rust modules or vice-versa, just passing a string forward while not even necessarily doing something with it, producing two unnecessary re-encodings on the string's way through. My expectation is that this will only become worse once Interface Types become available, as it makes small modules more viable while currently most binaries are monoliths because it isn't available.

To fully solve the problems of true polyglot WebAssembly, we'd either need

• caching along the lines of Universal Strings, perhaps rethinking Interface Types entirely - or -
• all languages deciding upon a common string encoding, which AS can kinda do while others can't

[Pauan]

@dcodeIO just passing a string forward while not even necessarily doing something with it, producing two unnecessary re-encodings on the string's way through.

That is not the case, because of laziness and adapter fusing it is possible to optimize away the encoding. This technique is already used extensively in Haskell and Rust, so it should be possible to apply it to Wasm engines as well.

Note that because interface adapters work lazily, that means they are basically like a JavaScript Iterator, so it does not require intermediate memory.

Encoding might still be necessary if the intermediate modules use different encodings and need to actually use the strings... but that is not a Wasm-specific problem... that is just unavoidable in general unless all the modules use the same encoding.

Interface types smooth things over by providing a universal encoding-agnostic exchange format (list char) which is lazily computed and fused (to avoid intermediate copies).

Note that the most recent interface types proposal is far more general than your Universal Strings proposal, since list char can handle any encoding efficiently without intermediate copies, there are no hardcoded encodings.

[dcodeIO]

I do agree that the current state of IT is based on a clever idea, I'd just not agree that it leads to significant improvements in practice. For instance, as soon as a string goes into a linear memory based language, the string goes into memory more often than not. So, unfortunately, whenever that happens, or the string is otherwise "used", there's re-encoding, leading us to

that is just unavoidable in general unless all the modules use the same encoding

as the common case (also in the future even more because the proposed canon encoding effectively biases towards linear memory languages), which is unfortunate for AssemblyScript, and this issue is about. Let me know if you'd agree, but I'd appreciate if we could discuss the more general challenges within the other issue.

[Pauan]

For instance, as soon as a string goes into a linear memory based language, the string goes into memory more often than not.

Yes, but unfortunately there's no way around that, I am unaware of any technical solution other than "languages must agree on the same representation format if they want to pass strings without any performance penalty". So there are only two solutions:

1. You force all languages to use a Wasm-specific GC string type (which means languages cannot use their own native string types, which means you can't use native string APIs or libraries, since they won't work with the Wasm-specific type).

2. Or you accept that converting to/from a language's native format incurs some minor cost (though that cost is mitigated and minimized in various ways).

This problem isn't just limited to strings, it also happens when passing records/tuples/lists between languages. It's unfeasible to require all languages to have the same string/list/tuple/record representation, since Wasm is not an abstract runtime like the JVM, and it does not try to be like the JVM.

Also don't forget that Wasm is intentionally designed around a shared-nothing model, where modules do not share their memory with each other, so each module has a separate linear memory. So a certain amount of copying is unavoidable with that model (even with lift_canon).

GC fixes that copying problem, but only for languages which choose to use GC (and which have the same GC representation). So non-GC languages will still need to use the adapter system forever.

And so interface types gives a solution which works for linear memory now, and which can be upgraded to GC later, and which supports interop between GC and non-GC languages.

the proposed canon encoding effectively biases towards linear memory languages

Why do you say that? Yes interface types are intentionally designed so they can be used without a GC (and thus work well for "linear memory languages"), but interface types also work with GC, and GC strings can be added in the future, they are orthogonal features.

If anything, it's biased in the opposite way: GC languages will be able to use GC strings (and thus can pass strings with no performance penalty, since they're just passing pointers), whereas "linear memory languages" are always forced to copy the full string into linear memory (even with lift_canon/lower_canon), and thus are at an inherent disadvantage.

[dcodeIO]

GC has the same problem if languages use different encodings, or somehow different object layouts, or otherwise require side-effects when constructing a string, yeah. The story just continues forever, unless we start to at least think about alternatives. Universal Strings is my attempt to come up with an idea that minimizes the problem by introducing an encoding-agnostic universal string type. It has a graceful fallback for non-GC languages (plus a graceful outlook to define a wasm::string for example in Rust), and solves some problems IT does not. Of course it has its own problems, but that's the alternative we would have to at least talk about if converging all languages to UTF-8 isn't an option. I don't see anyone discussing that, so here we are.

Other than that, I cannot express how tired I am of repeating myself while achieving exactly nothing. Probably not an unexpected outcome.

[Pauan]

Universal Strings is my attempt to come up with an idea that minimizes the problem by introducing an encoding-agnostic universal string type.

That proposal is basically just GC strings, which are great, but that doesn't replace interface types, and GC strings can be layered on top of interface types.

Since AssemblyScript is supposed to mirror TypeScript, I think it makes sense for it to use GC strings (when they become available). And in the meantime I don't think it matters too much what encoding is used.

The only benefit of choosing UTF-8 is that it can be slightly more efficient (if lift_canon and lower_canon are standardized), but that advantage is temporary and will go away after GC strings exist.

You could also choose to make AssemblyScript encoding-agnostic (like Python), so the encoding would be an internal implementation detail which is hidden from the user. The idea is that (from the user's perspective) strings would just be arrays of code points.

if converging all languages to UTF-8 isn't an option.

Converging to a single GC string type (e.g. Universal Strings) is also not an option. You're never going to convince all languages to converge toward a single string representation. Languages will have different string representations, that's just a fact we have to accept, a JVM-style universal representation is not feasible.

This isn't about Rust, or C++, it's about all languages. There are dozens of ways of handling strings, and each language makes a different choice:

• Python cannot use your universal strings, because it represents strings as first-class Python sequences of code points (which don't have an encoding). Internally it uses different encodings and automatically re-encodes based on the situation, similar to JS.
• Haskell cannot use your universal strings, because it uses lazy lists.
• Various Lisps cannot use your universal strings, because they use cons cells or ropes to represent strings.

This problem is a lot trickier than choosing between UTF-8 and UTF-16 (or choosing between linear memory and GC). Which is why interface types are designed to be shared-nothing, to support all encodings, and to support different representations. This has some performance costs, but it's the only feasible way to support different languages.

[dcodeIO]

Perhaps we can agree on the observation that Interface Types is a beautiful solution to a subset of the problem, while Universal Strings could or could not be the basis of yours truely messy compromise. On that premise, we are all right, and can use this issue to discuss about AS switching to UTF-8 by default again. What do you think? Is AS considering to join the UTF-8 bandwagon, for example for efficient interop with Rust, something you'd welcome?

[Pauan]

@dcodeIO What do you think? Is AS considering to join the UTF-8 bandwagon, for example for efficient interop with Rust, something you'd welcome?

Like I said, I don't think it matters too much. I think the performance gain from lift_canon/lower_canon are minimal, and any gains will go away after GC strings exist.

So I think the choice should be primarily determined by what makes the most sense in terms of functionality / user API. So I see three choices:

• List-of-codepoints (e.g. Python) is good because the user doesn't need to worry about encodings, instead the language will automatically choose UTF-8, UTF-16, or UTF-32 depending on the situation. And the user also doesn't need to worry about codepoint boundaries, and lookup is O(1).

  The downside of list-of-codepoints is that the language must automatically re-encode the string when adding non-ASCII characters. And it must use 2 bits to keep track of which encoding each string is using, so there's a minor performance cost on every string access.

• UTF-8 is good if you want to have a single explicit encoding. The benefit is that UTF-8 is very efficient in space and time, it is the optimal encoding, and you will always be able to use lift_canon/lower_canon. The downside is that now the user must think about codepoint boundaries, so lookup is no longer O(1).

• WTF-16 is good if you want to maintain strict compatibility with JS, but WTF-16 is less efficient than UTF-8 and it doesn't have O(1) lookup.

  However, it is possible to use lift_canon/lower_canon with WTF-16, as long as the string is ASCII-only. This can be done as an optimization which is not noticeable to the user.

For AssemblyScript I would personally choose list-of-codepoints, since it is the nicest user API, it has O(1) lookup, and it can still use lift_canon/lower_canon for ASCII strings. I think if JavaScript was designed today it would use list-of-codepoints instead of WTF-16.

[Pauan]

Note that the authors of UTF-8 everywhere disagree with me, they believe that UTF-8 is superior to list-of-codepoints.

They make some good points, and I agree with them that grapheme clusters is really what most people should be using, and so I think Rust's approach (UTF-8 + iterator of grapheme clusters) is ideal.

The difference is whether you care a lot about O(1) indexing/length. If you're willing to give up O(1) indexing then UTF-8 is indeed faster (especially for web servers).

However, JavaScript programmers expect O(1) indexing of code points, which is why I suggested list-of-codepoints as a compromise.

[Pauan]

Here are some anecdotes about UTF-8 usage:

• HTML and XML default to UTF-8.
• JSON mandates UTF-8.
• PyPy exclusively uses UTF-8.
• Go, D, and Rust use UTF-8 for all strings.
• Wasm itself uses UTF-8 for import paths.
• There are some plans for including UTF-8 validation in WASI.
• WASI uses UTF-8 for various things.
• HTTP servers almost exclusively use UTF-8.
• Linux and Mac almost exclusively use UTF-8 as the default encoding.
• Microsoft officially recommends UTF-8 for all UWP applications.

So there could be advantages to UTF-8 if you want to create an HTTP server or UWP application with AssemblyScript. And there could be performance gains to using UTF-8 when using WASI.

This is largely a choice between "good user API" (list-of-codepoints), "maximum performance" (UTF-8), and "strict compatibility and familiarity" (WTF-16).

All three options have merits, so it's up to the AssemblyScript community to decide which of the three options it wants.

[dcodeIO]

Perhaps a couple additional observations, given AssemblyScript's goals:

Performance: With multiple string representations, and abstracting over them, we may end up in a situation where re-encoding happens implicitly within the language's standard library. Depending on the use case that may be more or less often. More complex solutions may also be slower in general due to doing more work. As such, picking the most reasonable default and sticking with it has certain advantages.

Binary size: One difference to non-Wasm Java, Python and JS is for example that AS typically ships its string functions (and related standard library) with a Wasm binary, while in traditional VMs these functions are installed on the machine. This may relativize when binaries become bigger, but it doesn't necessarily make the "just a simple and small Wasm module" use case less important. The more complex our string handling becomes, the more these small modules will tank.

The list of codepoints idea may be related to both, as if I understood correctly it for example requires to maintain a separate lookup structure of "breadcrumbs" (once read something over at Swift about it, essentially caching the stride one knows already) to minimize the impact of random access. Of course I agree that this would be nice API-wise, as it would kinda just "fix" WTF-16 by eliminating surrogate pairs (incl. making underlying encoding irrelevant), but then there remains the question of how far we can or want to go for a nice API without re-targeting to a different audience. Given that, Rust's approach may be a more reasonable choice. As would be staying with WTF-16 for JS compat.

That's the unfortunate reality we are looking at. AS is essentially torn towards either of the approaches for one or another reason, and much of the heated discussion so far originated in Wasm not (yet) helping. Some sort of universal strings, not necessarily mine, could for example move all the heavy machinery to the VM instead of shipping it with every binary, to give just one example. I still hope we can get something like that eventually (for all languages), it's just that GC strings aren't moving into that direction as well currently, equally motivating this issue.