Possible simplification: drop all indexed/position-based access for MVP

[jakobkummerow]

Continuing #26 (comment):

This is just an idea that came to my mind, I'm not sure it's feasible. That said, on a high level it would turn this proposal into a strict subset of its former self, and the removed parts could always be added back (post-MVP) if desired.

In short, the idea would be to only have two encoding-specific kinds operations: creating strings from linear memory (and WasmGC arrays), and writing them back to such. On strings themselves, only encoding-independent operations (concatenation, equality checking) would remain.

For source languages that need indexed operations, the source-to-Wasm compiler would have to emit conversions. There are at least three strategies how this could be done:

• always two copies: a source string could be represented as a pair of an (i8/i16) array and a stringref. Depending on the operation, one or the other is used.
• lazy copy: same as above, but one entry of the pair is created lazily by the first operation that needs it.
• temporary conversion: array copies are created on demand and discarded afterwards. Assuming that indexed operations typically happen in loops, the algorithmic complexity (though not necessarily the constant-factor overhead) of such loops would remain the same. For example, a UTF-8 source language's for (int i = 0; i < string.length; i++) foo(string.usvAt(i)) would compile to something like:

  bytes = (string.measure_wtf8 string)
  temp = (array.new ($i8-array-type) bytes 0 /* default */)
  (string.encode_wtf8 string temp)
  for (i = 0; i < bytes; i++) {
    byte = (array.get temp i)
    if (byte > 0x7F) { /* decode more utf-8 bytes */ }
  }
  

  So the whole task of dealing with utf-8 falls to the module itself. Considering that this source language is used to representing UTF-8 strings in memory, it must already have the required logic for that task.

Benefits:

• gives maximum flexibility to source languages
• gives maximum opportunity to Wasm engines to choose their preferred internal encoding for stringrefs; as long as modules consistently use one encoding, the amount of re-encoding (though not copying; see below) is minimal: engines can go as far as supporting several internal encodings, turning a matching string.new_wtf8/string.encode_wtf8 pair into a pair of memcpy calls
• in case of mixed-encoding usage patterns (not sure how frequent those are?), e.g. creating a string with string.new_wtf8 and then using string.get_wtf16 on it a lot, avoids Wasm engine implementation complexity and corresponding highly-unpredictable performance by instead letting the module control (and minimize) the conversions that have to happen. To clarify, when I say "engine complexity" I'm not "selfishly" talking about V8 here, as I believe this could be built on top of our existing string system with relative ease and relatively good performance; I'm more worried about Wasm engines that use utf8/wtf8 strings internally, and trying to run an e.g. Java-produced module on them.

Drawbacks:

• limits the feature set offered by Wasm itself, requires source language compilers to do more work
• the first point might well imply module binary size increases
• increases the amount of copying of character data that needs to be done, which might make the resulting overall performance unacceptable
• support for string slices would have to be dropped, as they aren't expressible without start/length information.

One potential strategy to resolve this question could be to build a prototype for the reduced feature set first, and gather some experimental data. The benefit of offering built-in indexed operations could then be measured as a delta to that. Since the feature set is a subset, this wouldn't create any extra work for the engine prototype; however it would create extra work for the module producer prototype.

[wingo]

Very interesting thoughts. I certainly hate the notion of using WTF-8 offsets for operations that don't require WTF-8, like string.eq.

Just while it is in my mind, another couple drawbacks for this proposal:

• Related to the string slice question, there are some operations whose cost from the source language point of view is constant -- e.g. str.startsWith("hello, "), or str.charCodeAt(42) -- but if you copied out the whole string for the operation, the cost would depend on the length of the string. I feel like the "predictable performance" principle should translate into something a source-language author can reason about.
• You can't stream over the contents of a string using a fixed working buffer without persistently keeping around an encoded buffer. E.g. imagine you have a FILE* with a 1024-byte ring buffer, you can't feed that buffer with UTF-8 slices of a long string; you need to first encode the whole string then copy. Maybe OK, but it is a drawback.

[wingo]

Is string.get_wtf16 a required feature of an MVP? For Java and friends I think it probably is. If I were writing a compiler from Java I wouldn't trust the compiler to be able to always turn a loop over str[n] to only encode the WTF-16 once, and I would worry about the O(n) cost for str[n] outside a loop. I think I would prefer in that case to either generate calls out to JS, which is something of an admission of failure, or prefer GC arrays of u16 for my strings.

But, WTF-8 positions aren't really a required feature, I don't think. Low-level languages like Rust or C++ will likely prefer to encode to memory.

Then there are languages like OCaml whose strings are really arbitrary byte arrays; they will probably continue to use (array u8) and not stringref.

Julia is the only language I know of that tries to treat strings as USV sequences but exposes UTF-8 offsets, complete with invalid position errors: https://docs.julialang.org/en/v1/manual/strings/#Unicode-and-UTF-8. This is closest to what the proposed WTF-8 indexing offers.

Finally you have languages like Python, Scheme, Ruby (to an extent) and so on, that are really thinking about codepoints or even USVs. There, having the only way to iterate a string be via WTF-8 offsets is a bit weird? The only reason you would do that is that you expect all implementations to represent data as WTF-8, and that would be a nice performance hack. See https://hsivonen.fi/string-length/#:~:text=Which%20Unicode%20Encoding%20Form%20Should%20a%20Programming%20Language%20Choose%3F.

In summary I think that we probably do need WTF-16 offsets (though let's keep talking) but I wonder if there is another solution that can avoid the concept of a WTF-8 offset, for example a codepoint offset, or (gasp) an opaque cursor again.

[wingo]

Aaaaaaaaah I just had a brain wave --- apologies for going back and forth so many times on this.

(local $str stringref)
(local $wtf8 stringview-wtf8)             ;; new type
(local $wtf16 stringview-wtf16)           ;; new type
(local $codepoints stringview-codepoints) ;; new type
(local.set $str (string.const "a string, a string, hear ye, hear ye"))
(local.set $wtf8 (string.as_wtf8 (local.get $str)))
(local.set $wtf16 (string.as_wtf16 (local.get $str)))
(local.set $codepoints (string.as_codepoints (local.get $str)))
(string.get (local.get $wtf8) (i32.const 0)) ;; -> 1st WTF-8 byte
(string.get (local.get $wtf16) (i32.const 2)) ;; -> 3rd WTF-16 codeunit
(string.get (local.get $codepoints) (i32.const 9)) ;; -> 10th codepoint

The idea being, if you want an interpretation of the string's contents, you have to ask for a view on the string. That gives you a cost model, to a degree -- getting a view may have a cost. For the implementation's native string encoding this cost will always be O(1), maybe even not implying an allocation, whereas for "foreign" encodings that's where you would allocate the breadcrumbs or what have you. String views are reference types (opaque, can't be written to memory) and hold on to their underlying strings. Given a view, accessing bytes/shorts/codepoints is constant-time. Positions in strings are only associated with stringviews, and therefore you can only slice a string via stringview. If we have slices, we can check equality just against whole strings (take a slice beforehand if you want to check a substring). string.measure and string.encode work only on wtf-8 and wtf-16 views.

Layering-wise, string views can come after a MVP stringref, though I would want to line up a bit of buy-in beforehand.

Somewhat inspired by Swift, which also adds on a "extended grapheme cluster" layer that would be more appropriate for the application to do, if it wanted to :)

WDYT @jkummerow @lars-t-hansen ?

[lars-t-hansen]

They are reference types with unobservable (modulo performance) mutable state to hold the breadcrumbs etc? This seems like an improvement on the previous immutable-cursor-reftypes idea, which I thought would be hard to make fast reliably. Here we just copy pointers.

I agree exposing the cost is meaningful. There may be a tie-in with the feature detection proposal if the internal string type can be exposed as a feature.

(I wonder whether, in that case, stringview-wtf8 is not just a new heap type and we're better off dealing with (ref stringview-wtf8) and with a set of these under a generic stringview type, but I think that's just a detail for now.)

[jakobkummerow]

@wingo Yeah, that could work. Compared to the approach I sketched at the beginning of this thread, it has the big benefit that it avoids unnecessary copies.

I suppose the three stringview-* types could also be subtypes of stringref, if we wanted them to be. Not sure there are strong reasons either way. A minor advantages of subtyping would be that it would allow many (I think?) modules to work (almost?) entirely on one of the stringview types (depending on which one fits their source language), and string.eq and other encoding-independent instructions could just accept those. A possible drawback could be that it makes it less convenient for engines to represent the views as "stringref pointer + metadata (e.g. breadcrumbs)", as opposed to a full re-encoded string. (Which technique is better likely depends a lot on the expected frequency of encoding changes.)

An open detail is whether/how to specify performance guarantees. It might be fine not to specify anything, and just rely on engines' desire to be as fast as possible.
The other end of the scale would be to say "string.as_* is O(string length), string.get is O(1)".
A possible middle ground would be to standardize "string.as_* is at most O(string length), string.get is amortized O(1)". While this would take some "predictability" away from module producers, it would enable potentially interesting engine-side optimizations: it would allow engines to perform the conversion lazily, e.g. an engine could decide to make string.as_* always an O(1) "pointer copy", and perform actual re-encoding only after N string.get accesses (or at the first string.get N with N greater than some threshold). I'm not sure engines would go that far, but it might be good to have the freedom: e.g. this would work well for the use case of long_string.startsWith("hello"), because computing the positions of the first five codepoints without breadcrumbs in O(5) each is faster than scanning or re-encoding the entire hundreds-of-kilobytes string just to do five O(1) accesses. An engine betting on re-encoding might not want to do this (because handling the memory requirements of lazy re-encoding is difficult); for an engine using breadcrumbs this could make a lot of sense.

Taking a step back: how different would this be from having two or three separate string types (stringref_wtf8, stringref_wtf16, and maybe stringref_codepoint), along with explicit conversion functions between them? One difference I can see is that a generic stringref base type causes automatic conversions when different modules using different views want to exchange strings. Put differently, if we encourage (or enforce?) that only stringref is used on public module interfaces, then that avoids incompatibilities between one module exporting (func $foo (param $stringref_wtf8)) and another module importing (func $foo (param $stringref_wtf16)).

One issue this doesn't address is that all variants of string.get would have to perform bounds checks (unless a "sufficiently smart compiler" manages to optimize them away, which I wouldn't bet on). That's probably okay.

I'm guessing that a fairly common situation will be that an engine represents strings as u/wtf8 internally (e.g. for reasons laid out in the article you linked), and a module wants to iterate over code points (so it doesn't have to deal with decoding). So you'd have (wasm-ish pseudocode):

local $codepoints = string.as_codepoints(local.get $string);
for (local $i = 0; $i < string.length($codepoints); $i++) {
  $cp = string.get($codepoints, $i);
  // Do something with $cp
}

IIUC, this would be slower than the positions-based alternative:

for (local $position = 0, $delta = 1;
     $delta != 0;  // Needs another check for zero-length strings!
     $position, $delta = string.advance_wtf8($string, $position, 1)) {
  $cp = string.get_wtf8($string, $position)
  // Do something with $cp
}

because at least one of string.as_codepoints and string.length before the first iteration is O(n) regardless of implementation technique (breadcrumbs or re-encoding), so overall this will do (at least) two passes over the string. Is that acceptable? (The string.get in the loop can be made fast with any of breadcrumbs, re-encoding, or a one-element cache.)

[wingo]

Thanks Lars & Jakob. (& thanks for your patience too :)

As regards typing, good thoughts. To summarize we could have a base stringview type with wtf8, wtf16, and codepoints subtypes, or have the views be subtypes of stringref, or have two or three string types.

1. If stringviews and stringref are unrelated types, having a supertype does seem tidy. However, consider you have a wtf8 stringview, what good does it do to you to treat it as a generic stringview? What operations would be common to all? Logically get and length are common but unless you know what kind of stringview you are working with, it's hard to interpret their meaning. You also probably wouldn't want stringview.length to take the base type; it's a needless source of (potentially) dynamic dispatch. But, I see the attraction and we can be on the lookout for an annealing/simplification opportunity like this.

2. If stringviews are a subtype of stringref somehow, they can essentially substitute for stringref in most places. A Java compiler could just eagerly acquire a wtf16 stringview for all its strings, and anything that needs a stringref (JS, other components, any instruction taking stringref) could just take the stringview and rely on implicit upcasting. Otherwise we'd have to provide a stringview.get_string instruction. This has a natural implementation for stringview on a web browser -- all JS strings are actually stringview_wtf16, a subtype of stringref. But, usually with subtyping we want the values to share representation in all cases, and you wouldn't necessarily want to WTF-8 stringviews to share the same representation as a JS string, with the same initial fields and all. Similar concerns for the non-web wasm implementations in the other direction.

3. Or we could have lots of string types! I am assuming the idea would be to still additionally have a base stringref type. Jakob rightly points out that we would need to avoid a world in which two modules can't talk because they are using different string types. But, in a Java compiler that emits fine-grained modules that later get linked together, I could imagine you wanting to just send around stringref_wtf16 or stringview_wtf16. Certainly stringref should be the only thing on a component boundary, but I am unsure how to proceed here. At the very least surely we should prevent stringview_wtf8/stringref_wtf8 from going to JavaScript, but that is a JS API concern.

Considering has-a vs is-a from point (2) -- I think we should go has-a. The casting to stringref advantages of is-a are relatively small I would say from an author's perspective and the implementation is gnarly for foreign encodings. The efficiency you would gain in e.g. a web browser that a JS string is already not only a stringref but a stringview_wtf16 is minimal -- most string access will be function-local, and in that case we can expect the allocation cost of has-a stringviews via stringref.as_wtf16 to be removed by SROA in almost all cases. Acquiring the stringview is side-effect-free and dominates its uses. No compiler heroism required, just standard optimizations. Even Java might just want to pass around stringref instead of stringview_wtf16, given that it's free on web browsers, and that on non-web you might want to only pay the memory cost of breadcrumbs/copies for the strings you are working with right now rather than all strings.

For the same has-a/is-a shared-representation reasons I think probably having multiple stringref subtypes (point 3) is not the right thing. Could be wrong here though!

This leaves us with unrelated stringview and stringref types, possibly with a base stringview type. I'll see about adapting the text!

[wingo]

Regarding performance:

An open detail is whether/how to specify performance guarantees. It might be fine not to specify anything, and just rely on engines' desire to be as fast as possible. The other end of the scale would be to say "string.as_* is O(string length), string.get is O(1)". A possible middle ground would be to standardize "string.as_* is at most O(string length), string.get is amortized O(1)".

Good thoughts here. I think specifying upper bounds can be reasonable, though as @sunfishcode notes the spec currently doesn't include complexity/performance guarantees, so we may need to communicate/encourage/specify these in other ways.

...

local $codepoints = string.as_codepoints(local.get $string);
for (local $i = 0; $i < string.length($codepoints); $i++) {
  $cp = string.get($codepoints, $i);
  // Do something with $cp
}

IIUC, this would be slower than the positions-based alternative:

for (local $position = 0, $delta = 1;
     $delta != 0;  // Needs another check for zero-length strings!
     $position, $delta = string.advance_wtf8($string, $position, 1)) {
  $cp = string.get_wtf8($string, $position)
  // Do something with $cp
}

because at least one of string.as_codepoints and string.length before the first iteration is O(n) regardless of implementation
technique (breadcrumbs or re-encoding), so overall this will do (at least) two passes over the string.

I agree with this analysis.

Is that acceptable?

The problem I ran into was that for source languages that really want to access string contents by index rather than by iterator, it's less straightforward to a compiler to produce code that uses positions/cursors. Source languages that tend to use iterators are a bit easier to deal with for a cursor-based API, as it makes it more of a target-specific library concern than a compiler concern, but not all languages are like that.

To support more efficient iteration for source languages with iterators we could consider incorporating a cursor into stringviews, with seek and get_next_and_advance methods or so. I think though that this could be more appropriate as a post-MVP feature.

[jakobkummerow]

what good does it do to you to treat it as a generic stringview? What operations would be common to all?

I agree that having both a generic stringref and a generic stringview doesn't seem very useful, because there's not enough semantic distinction between the two.
Encoding-independent operations that come to mind are equality checking and concatenation. There may be others if the feature set increases over time (post-MVP).
I do still think it makes sense to have some generic type. Likely that would be stringref then.

I'm still undecided whether I'd prefer views to be subtypes or independent types (which means I'm fine with either). I'm not convinced by the argument that subtypes would want longer common prefixes in their internal representation: they do want a common representation, sure, but the prefix can be arbitrarily short (e.g. just having a shape descriptor as their first field). I also wouldn't mind a string_view.get_stringref instruction, seeing that implementations can just implement that as a no-op if they choose to have inheritance of their internal representations of stringview and stringref. (If such an instruction is even needed -- as you wrote, creating short-lived views might be cheap enough.)

the spec currently doesn't include complexity/performance guarantees

Yeah, and it's one of the things that a spec test suite can't really cover. Verifying compliance would require either inspecting the implementation, or executing long-running performance tests (with all the annoyances that benchmarking usually entails, such as dealing with flakiness, having to intentionally torpedo unrelated-but-interfering optimizations such as dead-code elimination, etc).
I'm totally fine with skipping any formal specification of performance guarantees, and at best having some non-normative prose along the lines of "it's expected that mature implementations make this operation's cost at most O(X)" or "be aware that this operation's cost is likely to be at least O(Y) in many implementations". What matters is that the design is chosen such that we see a realistic option for implementations to reach certain efficiency goals.

for source languages that really want to access string contents by index rather than by iterator, it's less straightforward to a compiler to produce code that uses positions/cursors.

Ah, yes, if you have found such examples then that's hard to argue with. I didn't think of it because I figured that iterating over codepoints in a UTF-8 encoded string lends itself so well to a cursor-based approach that it's a bit surprising to see anyone doing it differently.

This does mean that for that particular scenario (=iterating codepoints with underlying wtf8 representation), the views approach is no more efficient than the very simple "just decode it to linear memory" idea in the OP. Adding an optional cursor-based mechanism later sounds like a good ace up our sleeves, if the need arises.

[wingo]

The subtyping question is still open. The stringview idea evolved a bit before it landed in #36, with the interfaces being not entirely consistent, as the different view types have different use cases.

[wingo]

Subtyping discussion moved to WebAssembly/stringref#3