Closed Bug 551625 Opened 12 years ago Closed 1 year ago

Investigate the time spent in PushBackTrackState on Dromaeo regexps

Categories

(Core :: JavaScript Engine, defect)

x86
macOS
defect
Not set
normal

Tracking

()

RESOLVED WORKSFORME

People

(Reporter: bzbarsky, Unassigned)

References

Details

Attachments

(1 file)

Some of the Dromaeo regexp tests use the regexp /a.*a/ which is then applied to a 65KB string.  Our implementation seems to end up with 64% of its time spent in PushBackTrackState (which is presumably just called a bunch of times); the profile claims that 50% of the time (so 32% of total time) there is on the call instruction for the memcpy.  Maybe it's lying to me....

The other 35% or so is spent in js_ExecuteRegExp.

I'll attach a shell testcase equivalent of this.
Attached file Testcase
This takes about 7ms on my machine for that single match() call.
I just checked, and there are about 65k calls to PushBackTrackState on that testcase (which is the expected number; I'd been afraid it would end up quadratic in length of string or something).  So each one is taking about 100ns.  That's about 250 cycles on my hardware.  Doesn't seem all that unreasonable, even.
A bit more data: gData->stateStackTop is 1 on entry into this function in this testcase.  So the memcpy calls are copying a single REProgState (looks like 6 words)....
One more data point.  jsc does 6000 calls to match() per second for that testcase.  Given my 2.5GHz processor, that's about 6.5 cycles per character of the string.  V8 is closer to 8000 calls, or 4.8 cycles per character.

There's no way we can possibly hit 4.8 cycles given the need to PushBackTrackState on effectively every character after the first 'a'...
Assignee: general → nobody
Changing 'i' in the seconds loop to 1000 I get 63 on Nightly and Firefox 57, 62 on Chrome 62 and 211 on Edge.

Testcase fixed.

Resolving as WFM per comment #5.

Status: NEW → RESOLVED
Closed: 1 year ago
Resolution: --- → WORKSFORME
You need to log in before you can comment on or make changes to this bug.