Mitigating No Ropes

[swankjesse]

I love QuickJS. The latest releases even have ropes, which means that code like this is faster than O(N*N):

var result = ""
for (i in 0 until 1000000) {
  result += "x"
}

Unfortunately, the release we’ve shipped to millions of our customers doesn’t have ropes, and that’s both caused real performance problems, and risks future performance problems.

We’ve worked around this problem elsewhere by avoiding StringBuilder. For example Json.encodeToStringFast uses JSON.stringify() to create its strings.

But there’s some places where it’s super awkward to work around this. For example, Wire’s ByteArrayProtoReader32 calls the stdlib’s ByteArray.decodeToString() function, and that thing uses a StringBuilder that runs super slowly on our QuickJS. Wire’s calling the right API here, and even the stdlib is also not unreasonable by assuming strings’ performance characteristics.

[swankjesse]

I’d like to swap the stdlib’s implementation of ByteArray.decodeToString() with a different implementation that runs okay on QuickJS. I expect we might have 3 or 4 other functions that we want to swap.

Swap Option: Custom kotlin-stdlib-js

This is straightforward enough, though I expect it’ll be a bit of a drag to keep up-to-date, and to get our build tools to use it.

[swankjesse]

Swap Option: Patch it in JavaScript

I think this is difficult ’cause we’d need to patch both debug JavaScript and also minified/obfuscated JS.

[swankjesse]

Swap Option: Patch it in Bytecode

We’ve already got a QuickJS bytecode transformer for line number mapping. We could swap functions by creating a transformer that finds the declaration of a from function and updates it with data from a to function. This would need a way to identify from and to, and that mechanism would need to survive minifying.

Here’s one possibility:

@JsName("quickjs_bytecode_swap_decodeToString_from")
fun quickjs_bytecode_swap_decodeToString_from(
  byteArray: ByteArray,
  startIndex: Int,
  endIndex: Int,
  throwOnInvalidSequence: Boolean,
): String {
  return byteArray.decodeToString(startIndex, oldIndex, throwOnInvalidSequence)
}

@JsName("quickjs_bytecode_swap_decodeToString_to")
fun quickjs_bytecode_swap_decodeToString_to(
  startIndex: Int,
  endIndex: Int,
  throwOnInvalidSequence: Boolean,
): String {
  return byteArray.quickJsOptimizedDecodeToString(startIndex, oldIndex, throwOnInvalidSequence)
}

1. The transformer finds all functions prefixed quickjs_bytecode_swap_.
2. It organizes such functions into (from, to) pairs
3. It takes the single function called by each
4. It copies the bytecode from one to the other

[JakeWharton]

Can we patch what is now our effective fork? It'll be conflicted as hell, but the work of applying the patch is one time and solves the problem for everyone rather than as a one-off.

[dellisd]

For posterity: the new QuickJs implementation of string concatenation does not seem to meaningfully improve performance in cases like ByteArray.decodeToString() because rope usage in QuickJs is limited to certain string lengths to avoid the associated memory overhead of using and rebalancing ropes.

By default QuickJs will only use ropes if:

1. The string being appended is >512 bytes in length
2. The string being appended to is >8192 bytes in length

In practice for our applications, these conditions are rarely met. For ByteArray.decodeToString() specifically, we are always appending to the string one character at a time meaning we never hit the first threshold. Plus, the strings we are decoding are rarely long enough to hit the second threshold.