Closed Bug 1462486 Opened 6 years ago Closed 6 years ago

copyChars for ropes is optimized for uncommon case

Categories

(Core :: JavaScript Engine, enhancement, P2)

enhancement

Tracking

()

RESOLVED FIXED
mozilla62
Performance Impact ?
Tracking Status
firefox62 --- fixed

People

(Reporter: sfink, Assigned: sfink)

Details

(Keywords: perf)

Attachments

(1 file)

It appears much more common to have left-leaning ropes, as you would get from eg

  s = ""
  for (i = 0; i < 1000; i++)
      s += "a";

I guess you could get a right-leaning rope from

  s = ""
  for (i = 0; i < 1000; i++)
      s = "a" + s;

but that seems far less likely. jesup is seeing a bunch of 25-35k character long strings, one character per rope node, coming from a facebook zone. So it seems worth optimizing for these left-leaning ropes.
The change is to do a depth first traversal right node first, building the string up backwards. With a left-leaning rope, that means you'll never have more than 1 element on the stack. With a right-leaning rope, you'll fill the stack with a number of nodes equal to the depth of the tree, but that should be less common.
Attachment #8976726 - Flags: review?(jcoppeard)
Comment on attachment 8976726 [details] [diff] [review]
Optimize copyCharsInternal for left-leaning ropes

Review of attachment 8976726 [details] [diff] [review]:
-----------------------------------------------------------------

Nice.
Attachment #8976726 - Flags: review?(jcoppeard) → review+
Gah! I was assuming that copyCharsInternal was used by other parts of SpiderMonkey. It seems it is not, it is only used for the MemoryMetrics. And the other changes in bug 1441876 should have a vastly larger effect on that.

A microbenchmark emulating a simple form of the situation in bug 1441876 shows a good improvement -- going from 36 to 23 seconds, shaving off a third of the time. (This is on a set of 3 strings, each of them maximal left-leaning ropes containing 32k "1"s.)

I think that whenever the engine needs the string data, it flattens them using flattenInternal, which does its own crazy stuff that already avoids the need for a separate stack (it stores the stack in the rope nodes themselves, temporarily overwriting the flags/length word.)

Maybe I should make JS_CopyStringChars use this instead of flattening.
(In reply to Steve Fink [:sfink] [:s:] (PTO June 31) from comment #3)
> Gah! I was assuming that copyCharsInternal was used by other parts of
> SpiderMonkey. It seems it is not, it is only used for the MemoryMetrics.

It seems to be called when wrapping strings, doesn't it?

JSRope::copyCharsInternal(JSContext *, ScopedJSFreePtr<CharT> &, bool) : bool
	JSRope::copyLatin1Chars(JSContext *, ScopedJSFreePtr<Latin1Char> &) : bool
	JSRope::copyLatin1CharsZ(JSContext *, ScopedJSFreePtr<Latin1Char> &) : bool
		CopyStringPure(JSContext *, JSString *) : JSString *
			JSCompartment::wrap(JSContext *, MutableHandleString) : bool
	JSRope::copyTwoByteChars(JSContext *, ScopedJSFreePtr<char16_t> &) : bool
	JSRope::copyTwoByteCharsZ(JSContext *, ScopedJSFreePtr<char16_t> &) : bool
		CopyStringPure(JSContext *, JSString *) : JSString *
			JSCompartment::wrap(JSContext *, MutableHandleString) : bool
You are totally right, and when I look at the callgraph now I see it clear as day.

Then again, my callgraph is missing the edge from JSRope::copyChars to anything at all, which makes me rather suspicious of its correctness.
Keywords: perf
Priority: -- → P2
Whiteboard: [qf]
Pushed by sfink@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/da8925b18399
Optimize copyCharsInternal for left-leaning ropes, r=jonco
https://hg.mozilla.org/mozilla-central/rev/da8925b18399
Status: ASSIGNED → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla62
Performance Impact: --- → ?
Whiteboard: [qf]
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: