Open Bug 1561576 Opened 7 years ago Updated 9 months ago

Avoid inflating to UTF-16 when decoding Latin1-range UTF-8 via TextDecoder

Categories

(Core :: Internationalization, enhancement, P3)

Product:
Core
Component:
Internationalization
Type:
enhancement

Tracking

()

Status:
ASSIGNED

People

(Reporter: hsivonen, Assigned: hsivonen)

References

(Blocks 1 open bug)

Details

Attachments

(2 files, 1 obsolete file)

Bug 1561576 - Avoid inflating to UTF-16 when decoding Latin1-range UTF-8 via TextDecoder.
47 bytes, text/x-phabricator-request
Details | Review
Benchmark comparison, v2
124.89 KB, text/html
Details

To optimize Wasm to JS string passing:

When the encoding is UTF-8, check the input for Latin1 range using encoding_rs::mem and convert directly from UTF-8 to Latin1 if in range and pass the result to SpiderMonkey without inflating.

Bonus for avoiding a copy, too, when passing the Latin1 data to SpiderMonkey.

Bonus for avoiding a copy, too, when passing the Latin1 data to SpiderMonkey.

Looks like bug 1534437 enabled copy avoidance here.

Is it appropriate to change the return value to any and just always set the return to a manually-constructed JSString*, or do we need a return-position specialization for JSString (like bug 1561564 is an argument-position specialization) to convey the information that we're always returning a JSString* specifically?

Flags: needinfo?(bzbarsky)

You can certainly do the any thing. It will mean that the jitinfo doesn't claim a known return type and so the JIT will have a bit more barrier/typecheck stuff for type inference purposes (i.e. verifying that a string was in fact returned), but on the scale of the work TextDecoder does that barrier is not a huge deal.

Flags: needinfo?(bzbarsky)
Priority: -- → P3
Assignee: nobody → hsivonen
Status: NEW → ASSIGNED

Performance-wise this patch is very mixed. I see execution time shortening by 35% for ASCII inputs. This is also (obviously) a win for short strings that can become inline strings in SpiderMonkey.

However, I see double-digit percentage regressions for strings that start with an ASCII prefix but then eventually aren't deflatable. This applies both to UTF-8 that's checked for Latin1ness before conversion in TextDecoder and for other encodings that are checked afterwards by SpiderMonkey.

When filing this bug my premise was that we'd try to deflate all output from TextDecoder. While working on this, I learned that when our DOM bindings output UTF-16, we only deflate short strings and leave long ones as UTF-16 regardless of content. Maybe this patch should change not to try to deflate long strings. jandem, based on your previous work in the area, do you have an opinion on this?

In any case, when we do deflate, we should do it using the facilities from bug 1490601. Maybe this patch should go on hold until SpiderMonkey-side deflation uses the SIMD acceleration from bug 1490601.

Flags: needinfo?(jdemooij)

(In reply to Henri Sivonen (:hsivonen) from comment #8)

When filing this bug my premise was that we'd try to deflate all output from TextDecoder. While working on this, I learned that when our DOM bindings output UTF-16, we only deflate short strings and leave long ones as UTF-16 regardless of content.

Do you mean this check in NewMaybeExternalString?

Maybe this patch should change not to try to deflate long strings. jandem, based on your previous work in the area, do you have an opinion on this?

For longer strings the memory usage win from deflating is nice, but if deflating is too expensive in that case that's probably reasonable.

So the equivalent of this loop is a slowdown? If we could speed that up using SIMD that would be nice...

Flags: needinfo?(jdemooij)

(In reply to Jan de Mooij [:jandem] from comment #9)

So the equivalent of this loop is a slowdown? If we could speed that up using SIMD that would be nice...

Or is the utf8-is-ASCII check fast but the utf8-is-Latin1 part is slow?

(In reply to Jan de Mooij [:jandem] from comment #9)

(In reply to Henri Sivonen (:hsivonen) from comment #8)

When filing this bug my premise was that we'd try to deflate all output from TextDecoder. While working on this, I learned that when our DOM bindings output UTF-16, we only deflate short strings and leave long ones as UTF-16 regardless of content.

Do you mean this check in NewMaybeExternalString?

Yes.

Maybe this patch should change not to try to deflate long strings. jandem, based on your previous work in the area, do you have an opinion on this?

For longer strings the memory usage win from deflating is nice, but if deflating is too expensive in that case that's probably reasonable.

I don't know what's too expensive. We could decide that we care more about saving memory than about maximal speed for the problematic inputs. However, to the extent that TextDecoder is used for Wasm-to-JS glue code and the output of TextDecoder enters some DOM API immediately, it would be sad to burn cycles to deflate the string only to have our DOM bindings inflate it immediately after.

So the equivalent of this loop is a slowdown? If we could speed that up using SIMD that would be nice...

I have a patch that SIMD-accelerates that loop in bug 1578339.

Or is the utf8-is-ASCII check fast but the utf8-is-Latin1 part is slow?

Yes. The ASCII check is SIMD. If we knew UTF-8 to be valid, the "UTF-8 is Latin1" check could be SIMD, but we don't know whether UTF-8 is valid, so the "UTF-8 is valid and Latin1" check falls off the SIMD path for each non-ASCII character. (In contrast, the "UTF-16 is Latin1" obviously stays on the SIMD path.)

Maybe the problem is that I'm worrying about particular kinds of synthetic inputs and maybe the real world is OK.

Specifically: Maybe real-world non-Latin1 inputs don't have a long ASCII prefix. Also, real-world Latin1 input should have relatively few non-ASCII characters.

Flags: needinfo?(jdemooij)

(In reply to Henri Sivonen (:hsivonen) from comment #11)

Maybe the problem is that I'm worrying about particular kinds of synthetic inputs and maybe the real world is OK.

Specifically: Maybe real-world non-Latin1 inputs don't have a long ASCII prefix. Also, real-world Latin1 input should have relatively few non-ASCII characters.

Could we instrument the browser and browse the web a bit to get some data on this? It's not representative for all users but might be a good indication.

If the is-ASCII check is fast and ASCII is most common, one option is to just leave it at that and not worry about the (less common) non-ASCII-but-Latin1 case? That still lets us optimize the common ASCII case without the non-ASCII-but-Latin1 complexity and potential performance issues.

Flags: needinfo?(jdemooij)

(In reply to Jan de Mooij [:jandem] from comment #12)

If the is-ASCII check is fast and ASCII is most common, one option is to just leave it at that and not worry about the (less common) non-ASCII-but-Latin1 case?

I'm going to proceed along these lines. However, upon thinking about this more carefully, I'm going to add a bit of abstraction-piercing API surface to encoding_rs and rewrite the patch here.

The patch has now been rewritten. (Since it has alternative code paths that WPTs don't assume to exist, I should probably write more tests.)

Latin1ness of single-byte encodings is determined pre-decode.

Legacy CJK encodings are checked for ASCII pre-decode, and there's no post-decode deflation. (I.e. the edge case of non-ASCII Latin1 in legacy CJK encodings is left undeflated.)

UTF-16LE and UTF-16BE are post-decode deflated.

Latin1ness of non-streaming UTF-8 is determined pre-decode.

For streaming UTF-8, post-decode deflation is used if decoder has seen a partial byte sequence at the end of the previous stream segment. Otherwise, including the case of a partial sequence at the end of the current segment, Latin1ness of streaming UTF-8 is determined pre-decode.

https://treeherder.mozilla.org/#/jobs?repo=try&revision=db91eae9e4d7cfa30d7978a9568934d67d5a5a54

Attached file Benchmark comparison (obsolete) —

These benchmark results for Russian and Thai make no sense to me. I don't understand what JS_NewUCStringDontDeflate would do that'd be this much slower than adopting an nsStringBuffer. All the other code should get out of the way so quickly that one mispredicted branch can't explain the difference for long strings.

I expect there's a super-embarrassing bug somewhere in here, but I don't know what it is, yet.

The slow-down is either in function calls that return right away for zero-length inputs than in the hashing of new JSStrings. I'll try adding checks for zero to skip calling the functions that do nothing if the length is zero to get rid of the function call overhead.

Benchmarking build that explicitly checks for zero length cases and avoids calling functions that do nothing with zero-length inputs:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=f6cc7c9e3047fb406d9392dfbc637fda3ff54296

(In reply to Henri Sivonen (:hsivonen) from comment #21)

in the hashing of new JSStrings.

Did I read my debugger stepping right that creating an external string doesn't read the contents of the string to unify duplicates and only compares the memory location of the buffer with buffer memory locations seen since the last GC while creating a non-external JSString hashes on content? If so, this is another way (the other being not trying to deflate long strings) how creating an external string does less work than an non-external string, which makes it really hard to compete with external string creation using non-external string creation.

Flags: needinfo?(jdemooij)

Benchmarking build with the non-BOM-handling, non-streaming UTF-8 code path extracted from the generic path and cleaned up to be less branchy:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=9efbd5476afec972f5cddd6e90812f6dcca8494d

Creating an external string via NewMaybeExternalString does the following things:

  1. Check for empty or static strings, if match use that.
  2. Check for the ability to inline the string, if we can use that.
  3. Look up in the external string cache. This does a pointer compare on everything in the external string cache (max 4 entries) and if the length is <= 100 also compares string chars to see whether we get a hit.
  4. If all that fails, allocates new external string.

So one obvious question is: given the structure of your performance testcase, is the string cache getting hit in step 3?

Creating a non-external string via JS_NewUCStringDontDeflate does the empty-or-static string check, then the inline check. The inline check is a bit different: the external string case does the inline thing only if it can deflate to Latin1 and therefore for all lengths that can fit in a Latin1 thin inline. The JS_NewUCStringDontDeflate case does the length check for 16-bit chars but allows non-thin inlines. I don't know whether these length differences matter for purposes of the performance testcase.

Then if all that fails and we get to JSFlatString::new_, we allocate the string, if it's not tenured put the pointer to the chars into the malloced buffer hash set (this just hashes the pointer itself, not the chars), and that's it. There is no deduplication going on here that I can see, and no examination of the string chars...

(In reply to Boris Zbarsky [:bzbarsky, bz on IRC] from comment #26)

So one obvious question is: given the structure of your performance testcase, is the string cache getting hit in step 3?

The work to fill a new nsStringBuffer has been performed, and it's a newly-filled nsStringBuffer so I'd expect it to be a cache miss and not to save work.

if it's not tenured put the pointer to the chars into the malloced buffer hash set (this just hashes the pointer itself, not the chars), and that's it. There is no deduplication going on here that I can see, and no examination of the string chars...

OK. I guess it was hashing just the pointer and not the content, then.

Flags: needinfo?(jdemooij)

(In reply to Henri Sivonen (:hsivonen) from comment #27)

(In reply to Boris Zbarsky [:bzbarsky, bz on IRC] from comment #26)

So one obvious question is: given the structure of your performance testcase, is the string cache getting hit in step 3?

The work to fill a new nsStringBuffer has been performed, and it's a newly-filled nsStringBuffer so I'd expect it to be a cache miss and not to save work.

Oh, for length < 100, it's a cache hit, if it looks at content, but I still don't see how it would save work, since the nsStringBuffer has already been filled.

Hmm. Unless the outgoing string is nsAutoString-like there's no nsStringBuffer at all. Could that be it?

Or maybe I'm accidentally measuring GC and the cache eliminates three quarters of garbage?

Or maybe I'm accidentally measuring GC and the cache eliminates three quarters of garbage?

Right, that is the main benefit of the cache: avoids allocation of new JS strings and GC pressure.

(In reply to Boris Zbarsky [:bzbarsky, bz on IRC] from comment #31)

Or maybe I'm accidentally measuring GC and the cache eliminates three quarters of garbage?

Right, that is the main benefit of the cache: avoids allocation of new JS strings and GC pressure.

OK. Let's assume that's the explanation and wrap this up without investigating endlessly. Thanks.

Attaching the spreadsheet for the latest patch

Attachment #9093841 - Attachment is obsolete: true

Looks like I used AsciiValidUpTo from the patch for bug 1578339, so marking dependency.

Depends on: 1578339
Severity: normal → S3

(In reply to Henri Sivonen (:hsivonen) from comment #28)

Oh, for length < 100, it's a cache hit

I've been told that the cache went away in bug 1903037, so it would be worthwhile to re-evaluate this patch, since there should no longer be the downside of failing to use the cache on microbenchmarks.

You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: