See the attached testcase. Apart from the fact that the indexOf tests are a lot slower than the lastIndexOf ones for some reason (and have been going back to Fx 3.5 at least), there's been a recent 3.5x regression on the indexOf tests. The m-c checkin range for that regression (using nightlies) is http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=def6be3d8b6b&tochange=149c3820e8a8 and there's a nice 100-changeset tracemonkey merge in there. indexOf got rewritten in bug 511777, which I'm fingering as the most likely culprit here. Shark just shows all the time spent in str_indexOf (yay inlining) and doesn't give me reasonable line listings for some reason (boo!).

And I bet the relevant change was this: - if (textlen - i >= 512 && (jsuint)(patlen - 2) <= BMH_PATLEN_MAX - 2) { + if (textlen >= 512 && patlen <= sBMHPatLenMax) { In particular this changed from doing the simple walk along the string for patlen == 1 to using BMH. This is an obvious loss, since BMH does more work and can't possibly win on patlen == 1. If I change the condition to also test patlen > 1, things get much faster, though still about 10-20% slower than Fx 3.5.

Ok, indexOf being a lot slower than lastIndexOf was somewhat due to pilot error. With that fixed, indexOf is only about 50% slower than lastIndexOf, not many times slower.... Still might be worth a separate bug on that. It looks like our indexOf has about the performance of Safari's lastIndexOf, while their indexOf is about 3x faster.

(In reply to comment #3) First of all, many thanks for finding the weakened BMH condition! I don't know what I was thinking when I left that out. On that line of though, it is also worth some quick measurements to see if there is a higher k where we don't do BMH for patlen < k. > Ok, indexOf being a lot slower than lastIndexOf was somewhat due to pilot > error. With that fixed, indexOf is only about 50% slower than lastIndexOf, not > many times slower.... Hmm, I ran your tests in a tracemonkey tip js shell (with the BMH thinko fixed) and here's what I see: (in ms) testIndexOfx: 63 testLastIndexOfx: 50 testIndexOfDash: 874 testLastIndexOfDash: 1587 Now, if I read the construction of testStrGiant, the '-' is equidistant from the beginning and end of the string, hence |testStrGiant.indexOf("-")| should be the same speed as |testStrGiant.lastIndexOf("-")|. However, indexOf is faster; I suspect because of the changes in bug 511777. Finding 'x' from the beginning and end, on the other hand, is not a symmetric task because 'x' is 24 characters from the beginning and 9 characters from the end. That indexOf is only 26% slower is, I believe, also a positive result of bug 511777. > It looks like our indexOf has > about the performance of Safari's lastIndexOf, while their indexOf is about 3x > faster. Wow. Hmm, and we are tracing those loops too. Are you quite sure of these results?

Someone confirm the head-to-head with Safari and dig into the generated machine code. It's time to get down and dirty. /be

> worth some quick measurements to see if there is a higher k Yep. ;) > Hmm, I ran your tests in a tracemonkey tip js shell (with the BMH thinko > fixed) Interesting. I was running in tracemonkey tip opt browser. I just tried this again (with the patlen > 1 added, and in shell I see: testIndexOfDash: 874 testLastIndexOfDash: 1587 In browser I see: testIndexOfDash: 2594 testLastIndexOfDash: 1720 In Safari (browser) I see: testIndexOfDash: 906 testLastIndexOfDash: 2219 This is very consistent. Without the BMH fix, browser is at about 6000 for testIndexOfDash, while shell is at 8600 or so. Sounds like we have a separate bug here... Can you try browser on your end to confirm? > the '-' is equidistant from the beginning and end of the string +-1, yes. That was the goal, at least. > Finding 'x' from the beginning and end, on the other hand, is not a symmetric > task Right. I was mostly looking at the '-' case. > Are you quite sure of these results? See above.

Hmm. I just did more testing, and now shell is consistently coming up with 1500ms or so for testIndexOfDash (???)

(In reply to comment #4) > (In reply to comment #3) > On that line of though, it is also > worth some quick measurements to see if there is a higher k where we don't do > BMH for patlen < k. I ran a matrix of pattern lengths and BMH threshold values. Each row runs with a different value of k in the abovementioned |(patlen - k) < sBMHPatLenMax|, starting at 0. Each column uses a different length pattern, starting at 1. You can see a diagonal starting at k = 2, patlen = 1 and fading away around patlen = 11. Hopefully this remains formatted: 267 134 91 68 56 47 42 35 34 30 28 26 24 24 23 20 22 268 134 91 69 55 47 41 36 33 30 28 26 23 24 24 20 22 29 134 90 69 56 47 41 36 33 30 28 26 24 24 23 20 21 30 28 91 69 55 48 41 35 33 31 28 26 23 24 23 20 21 29 29 28 69 56 47 41 35 33 31 28 26 24 24 23 19 22 29 29 28 29 56 47 41 35 34 30 28 26 23 24 24 19 22 29 29 28 29 28 47 41 36 33 30 28 26 23 24 23 20 22 29 29 29 28 29 29 41 35 33 31 28 26 23 24 23 20 21 28 29 29 28 29 29 28 36 33 30 28 26 24 24 23 19 22 29 29 29 28 30 28 29 29 33 30 29 25 24 24 23 19 22 29 28 30 28 29 29 28 29 28 31 28 26 23 24 23 19 22 29 29 29 29 29 29 28 29 29 28 28 26 23 24 23 20 22 29 28 29 28 29 29 28 29 29 29 28 26 23 24 24 19 22 29 29 29 28 29 28 29 29 28 29 29 29 23 24 23 20 21 30 29 28 29 29 28 29 29 30 28 29 29 29 24 23 20 21 29 28 29 29 28 29 29 29 28 29 29 29 29 29 23 19 22 30 28 29 29 29 28 29 29 29 29 29 29 29 29 29 19 22 28 29 28 29 28 29 29 28 29 29 28 29 29 29 28 29 22 Clearly the numbers are machine specific (Ubuntu w/ Core 2 Duo @ 2.67Ghz, btw), but it does clearly suggest a k higher than 2. Now back to the "why is the browser slower" hunt.

Confound it! One column too many.

(In reply to comment #6) > Sounds like we have a separate bug here... Can you try browser on your end to > confirm? I get pretty much the same relative performance as the js shell in a browser build: testIndexOfDash: 871 testLastIndexOfDash: 1582

Interesting. I wonder what the difference is... I'm just using --enable-optimize --disable-debug; pretty basic Firefox opt build.

Well, fix the glaring problem for now.

Explicit cast to jsuint might be nice there. And maybe a comment.

tests added to sunspider harness: http://hg.mozilla.org/users/rsayre_mozilla.com/benchmarker/file/d31b875708c1/SunSpider/tests/LIST-MICROSTRING

Comment on attachment 410041 [details] [diff] [review] with comments and cast We try not to overparenthesize subtraction against <= and so on (gal's Pascal or Oberon mistrained fingers excluded :-P). /be

(In reply to comment #8) Split off to bug 526348.

I ran a try-server-built version of your benchmark and indeed there is a horrendous regression from testIndexOfDash being 2x faster to < 2x slower! I will shark this.

So looking at the disassembly with Shark data, it seems Mac gcc doesn't think that 't' and 'p0', the hottest variables of the unrolled loop in StringMatch, deserve registers. Slowness ensues.

Hmm. I just tried making those |register| with no effect, but it could well just be ignoring me....

Yeehaa! register int test_integer asm ("EBX"); Puts performance back to Linux-level for both shell and browser!

We used to have to do this kind of shit in the '80s (with the Portable C Compiler). To quote from the Wicked Witch of the West: "What a world!" /be

I tried to make the register/asm hack apply as narrowly as possible (__APPLE__ && __GNUC__ && __i386__); anyone with portability experience, please let me know if I could do better. With this, OS X 32-bit browser and shell have much better indexOf performance than 3.5 and are on par with Ubuntu.

So WebKit has a hard-coded loop for length-one patterns. This should be slower than an unrolled loop (extra comparison and branch) and on 64-bit OS X, the unrolled loop wins. However, register pressure on 32-bit x86 (both OS X and Linux, no idea for Windows) slows down the unrolled loop due to spilling. testIndexOfDash spends enough time in the loop body for this to make a difference (~60ms). Comparing the result against 1.9.1, I also noticed that testLastIndexOfDash, which is syntactically identical, has dropped from 1141ms to 1511ms on tip. Looking at it under shark, all the time is spent in the 1 loop at the end. I played to forcing things into registers, but to no avail. Tweaking the logic to use pointers and a cached pat[0] recovers old performance almost exactly, so that is also in the patch. End result for 32-bit OS X browser: FF3.5.4 WebKit nightly tip patch textIndexOfx 80 74 263 63 testLastIndexOfx 45 86 43 45 testIndexOfDash 1876 803 5288 787 testLastIndexOfDash 1141 1916 1510 1143

These bugs landed after b4 was cut. Moving flag out.