Wednesday, October 8, 2008

In Firefox, String and RegExp performance is not a bottleneck for real-world pages
And, SunSpider might weigh String and Regexp too high

(Thanks to collaborators Joel Galenson, David Mandelin, and Ras Bodik.)

We are investigating how and whether to build a parallel web browser. The SunSpider benchmark suggests that 30-50% of time taken by JavaScipts is in String and RegExp (hereafter stregexp) methods. If so, this code is a prime candidate for optimization, including parallelization. But before parallelizing stregexp code, we wanted to confirm SunSpider's conclusions by profiling real web pages.

The short story is: surprisingly, stregexp code takes less than about 5% of JavaScript execution time in real web pages, much less than the 60% our data shows that it occupies in SunSpider. The rest of this post is the long story: our profiling method, results, and more detailed conclusions.

What we wanted to profile


Our question was, “What percentage of JavaScript execution time is spent in Spidermonkey code implementing RegExp and String methods?” To answer this question, we needed to know

  • t: the total time spent interpreting JavaScript

  • r: the time spent in code implementing RegExp
    methods

  • s: the time spent in code implementing String
    methods


This data, along with a modest understanding of the Spidermonkey code, allows us to compute the percentages of JavaScript time spent in the implementations of RegExp (100r/t) and String (100s/t) methods. We would have liked to have simply computed a single stregexp percent time as 100(r+s)/t, but more care was necessary: the JavaScript String class offers three public methods, replace, search, and match, that accept RegExp arguments. As one would expect, their implementation is a wrapper around RegExp code. To avoid double counting RegExp code, we wanted more precision than just r and s, and so we decided to further time the individual methods of RegExp and String (smatch, sreplace, and so forth).

We of course also had to decide on which JavaScripts to gather performance data. In addition to SunSpider, we chose a smattering of real-world sites intended to be representative of the typical browsing of one of the authors. The particular sites chosen are listed below.

    Tests
  • SunSpider suite as a whole

  • SunSpider regexp benchmark alone (regexp-dna)

  • CNN and NY Times

  • Slashdot and Fark

  • Google Maps

  • Google Mail

  • Malicious regexp that causes exponential-squared behavior in JS


The “malicious regexp” was selected to sanity-check the profiling code. It is based on an idea from this page by Russ Cox. Because it causes artificial, worst-case behavior of the stregexp code, it should show that code taking very close to 100% of total execution time.

How we profiled stregexp code


The method is quite simple: we manually inserted timing probes both around the main JavaScript interpreter loop, to compute t above, and around the stregexp code, to compute r, s, etc. This looks like

void
regexpFoo ()
{
float64 start = gettime ();

/* ... original code ...*/

globalTimings->regexpFooTime += (gettime () - start);
}

We considered instrumenting JavaScript code directly and using a sampling profiler like gprof or sysprof, but rejected both. Automatically instrumenting JavaScript code is not as easy as it sounds, and besides, JavaScript only provides millisecond-resolution timers. This also slows down JavaScript considerably. Using a *prof profiler is better, but, unfortunately,
the size of the Firefox codebase makes it difficult to extract detailed information about small modules like the JavaScript stregexp code. It's also impossible to only profile websites' JavaScript execution, and ignore time taken by the Firefox user interface.

Running each test was simple: we opened Firefox, loaded the web site(s) under test, and followed a sequence of steps intended to simulate a normal browsing experience. For example, when testing Google Maps, we searched for one location, zoomed in and out of the map, searched for another, panned around, searched for restaurants, then opened “information bubbles” for a few locations.

We need to say a bit more about testing the SunSpider suite: we ran it normally (loaded it and clicked “Start Now!”), but instead of using SunSpider's reported perfomance, we used our own profiling inside Spidermonkey. This means that we record stregexp performance over all of SunSpider's tests, not just its string and regexp ones.

While each test ran, our profiling code printed a sequence of accumulated performance data, once per call into the JavaScript interpreter. The numbers at each “sample” were the running totals t, r, s, etc., described above. So each performance sample is a snapshot of the percentages of time taken by stregexp versus everything else, over all JavaScript code executed up to that sample. (In particular, from the last sample, we can compute the total percentage of time stregexp has taken while Firefox has been open.) Taking samples allows us to show graphically how stregexp code has been important or less important over time; this is interesting because it might be very important while a page loads
(to parse e-mails, for example), and not important in the application's steady state.

Profiling results


For each test, we show four graphs below. The first is “Time in regexp code vs. other JS.” This plots the percentage 100r/t over time. The x-axis on the graph is the particular performance “sample”, described above, from which the y-axis values were calculated (so the x-axis roughly corresponds to time). The second graph “Time spent in string code vs. everything else” is similar to the first, except that it shows how the percentage 100s/t changes over time.

The third graph “Time spent in each regexp function”, breaks down the regexp time r shown in the first graph among the specific regexp functions over time. The x-axis is the same as in the first and second graph. The fourth graph is similar to the third, but shows string methods.

It's worth explaining in more detail one data series in the third graph: “bookkeeping”. This is the time spent in regexp code but outside of the main regexp interpreter, including setting up the memory allocator, preparing the match results to be returned to caller, etc. (For Spidermonkey geeks: regexp interpreter time is that spent in ExecuteREBytecode(); bookkeeping is the time spent in js_ExecuteRegExp() minus that in ExecuteREBytecode().)

You might notice that in the graphs of the “Malicious regexp” and “Regexp-DNA” results, there are many data points, even though both tests only make a single call to the JavaScript interpreter. This is because we didn't successfully filter all Firefox UI code from the results; only some calls were
filtered. Dave Mandelin suggested a fix to us, but we haven't implemented it yet.

(Apologies for the less-than-ideal layout of the graphs below. Blogger is limited in this regard.)


Malicious regexp






Regexp-dna benchmark from SunSpider






SunSpider






Google Mail






Google Maps






CNN and NY Times






Slashdot and Fark







Conclusions


It appears that regexp and string code does not particularly affect the performance of real web sites. Of all the “real” pages, regexp and string code accounted for no more than about five percent of the total time. This suggests that the performance of these pages will perhaps not be affected much by optimizing this code. A corollary of this is that it appears that the SunSpider benchmark weighs string code disproportionately high (~60%) compared to its use in the real world.

Of the string methods, it appears that String.replace() is approximately the most expensive in the real world; only Gmail behaved differently, with String.split() dominating. Of the time spent in String.replace(), approximately half was devoted to “bookkeeping time.”

13 comments:

Olly said...

I wonder if this a self-perpetuating thing?

People aren't using string/regexp functionality, so there seems to be little point in optimising them. But perhaps people aren't using them a great deal because they're expensive and slow?

It's like Microsoft's approach to performance on IE: People aren't presently using all that much javascript on the "top 100" sites so they aren't putting all that much work into making it faster (when compared with Squirrel/Trace/V8/monkey/fish/extreme/dude/sweet). But then perhaps people simply aren't using it because the performance isn't great?

Anonymous said...

Do you also need to buy goods Guangdao foot shopping and worry about acid? wholesale
And discount china wholesale stores also did not
have time Car video
to do some MP3 player
shopping With MP4 player
more and block mp4 watches
the development Men's outerwear
Women's outerwear
Mens outerwear
skin care products
wholesale mp3
wholesale mobile phones
digital camera wholesale
consumer electronics of networks, Internet psp accessories
shopping is wedding dresses
also more wholesale silver jewelry
convenient, now you wedding dress
only need bluetooth headset
to Ceramic tile
sit in memory cards
front of the wholesale digital cameras
computer, drinking wholeslae clothing
coffee, visit wholesale clothing
the website can be wholesale furniture
elected to their gps devices
favorite wholesale mp3
products, we Memory Card
can be here for Memory Stick
you More wholesale furniture
choices, many wholesale
practical, durable, wholesale atv
affordable, attractive wholesale electronics
merchandise, wholesale jewelry
there's the same wholesale handbags
for you, we gps devices
will provide wholesale shoes
you wholesale electronics
with quality wholesale t shirts
service! I hope wholesale digital cameras
you can Wholesale jewelry
here in our shopping pleasure to welcome you!

Anonymous said...

There aren't many games in my 28 years of playing video games that I genuinely love as much as Final Fantasy X. I think it's the greatest video game ever made, and was just mind-blowing when it first came out. I got the opportunity to share this game with someone that I really cared about and it made the game even more of a moving experience for me. world of warcraft goldbuy wow goldcheap wow goldwow power levelingwow powerlevelingeverquest 2 goldeq2 platfinal fantasy 11 cheap gilbuy ffxi gilffxi gilfinal fantasy xi gilmaple story mesosmaplestory mesosI've always kept my video gaming to myself for fear of tarnishing it by sharing it with someone I was dating in the event things didn't work out, but I took the chance for once and it really paid off. maplestory mesolotro goldlotr goldlord of the ring goldrunescape goldrunescape moneysilkroad goldbuy silkroad golddofus kamaskamas dofuswarhammer goldbuy warhammer goldflyff penyabuy flyff goldflyff moneyAlthough things didn't work out in the end, it was very special to be able to share something I love so much with another person I was close to. So this is a thank you to them for being a part of my life for a while and for sharing in something I love as much as video games and for sitting up with me late while I was trying to beat Seymour Flux. eve iskeve online iskarchlord goldbuy archlord goldstar wars galaxiesswg creditsCheap warhammer goldrunescape itemsworld of warcraft goldwow power levelcheap wow goldwow power levelingwow powerlevelingbuy wow goldcheap ffxi gilI'll always hold onto the two Final Fantasy action figures as a momento of the entire experience. I wish you could have been there when I finally finished the game, ffxi gilfinal fantasy gilMaple Story Mesosmaple story accountmaplestory MesosLOTRO Goldlord of the rings goldLOTR Golddofus kamaskamas dofusrunescape moneyrunescape powerlevelingrunescape goldArchLord goldarchlord powerlevelingarchlord itemsflyff penyaflyff cheapflyff moneyWarhammer goldbuy warhammer goldEverQuest 2 goldeq2 platbut I found the ending of the game kind of fitting considering the way things went for us at the end of our time together. Here's to you

damage restoration said...

Very interesting read! Thanks for the post!
hdtv antennaindoor antennaplasma mountsoutdoor antenna

volkan said...

seks shop

volkan said...

penis büyütücü hap

Anonymous said...

Free DSi
Free PSP
Free Xbox 360

Anonymous said...

Weaknesses of World Of Warcraft Gold the client-server model used by World of Warcraft have been wow power levelingexploited in order to crash the cluster of servers that aoc goldmake up a realm. Exploits also include characters being able to instantly Cheapest Wow Goldchange location or teleport. The situationbecame worse cheap wow goldwhen trying to coordinate activities across a number of playersor guilds on the same realm.World of Warcraft Lead Producer, stated that new realms would be introduced to warhammer goldrelieve the burden on existing ones. Existing realms would be upgraded.

Anonymous said...

インプラント is wonderful.
M&A is wonderful.
ボイトレ is wonderful.
注文住宅 千葉 is wonderful.
クレジットカード 申込 is wonderful.
東横線 土地 is wonderful.
カラコン is wonderful.
エルメス is wonderful.
婚約指輪 is wonderful.
ウエディングドレス is wonderful.
リングピロー is wonderful.
霊園 is wonderful.
レゴ is wonderful.
まつげエクステ is wonderful.
インプラント 大阪 is wonderful.
IPビジネスフォン is wonderful.
債務整理 is wonderful.
民事再生 is wonderful.
自己破産 is wonderful.
過払い金 is wonderful.
任意整理 is wonderful.
募金 is wonderful.
リサイクルショップ is wonderful.
オフィス家具 is wonderful.
外壁塗装 is wonderful.
渋谷区 不動産 is wonderful.
ウォーターサーバー is wonderful.
フランチャイズ 独立 is wonderful.
地デジ is wonderful.
投資情報 is wonderful.
妊娠 出血 is wonderful.
ブライダル エステ is wonderful.
バイク便 全国 is wonderful.
東横線 土地 is wonderful.
FX 初心者 is wonderful.
ハーレー is wonderful.
アイオン rmt is wonderful.
お祭り 景品 is wonderful.
Tシャツ 通販 is wonderful.
IHCWAY 利用者 is wonderful.
店舗デザイン 関西 is wonderful.
結婚 悩み is wonderful.
貸事務所 is wonderful.
語学留学 is wonderful.
野田市 一戸建て is wonderful.
店舗内装 is wonderful.
マンション大規模修繕工事 is wonderful.
エステ 京都 is wonderful.
パーティー会場 is wonderful.
埼玉 一戸建て is wonderful.
ヨガ 教室 is wonderful.
コミュニケーション 能力 is wonderful.
トレー is wonderful.

sex shop said...

http://www.sexigeceler.com

Anonymous said...

Lần 3
和歌山 デリヘル
神戸 デリヘル
姫路 デリヘル
大阪 デリヘル
京都 デリヘル
大阪 デリヘル
神戸 デリヘル
和歌山 デリヘル
奈良 デリヘル
京都 デリヘル
神戸 デリヘル
姫路 デリヘル
奈良 デリヘル
京都 デリヘル
大阪 デリヘル
大阪 デリヘル
神戸 アルバイト
福原 ソープ

vkzoe said...

Don't hesitate any more, check out here:

Vkamobi ---Chinese Mobile Phones Supplier
Cool Cell Phones
Cell Phones Accessories
Quality Car Electronics
Funny Video Games
Wholesale Computers
Free Shipping Sciphone i9+++
Air Phone NO.4
Sciphone i68 4G,Dual sim cards WiFi cell phone with Ultra Thin Flat Touch Screen
Free Shipping Flying F080, quadband dual sim card tv mobile phone with dual cameras flashlight
Ciphone C9 OS VS Windows Mobile 6.5 GPS G-sensor Dual Compass WIFI Smart Phone
X10 MID Touch Screen Tablet PC
PinPhone 3GS
Free Shipping Flying F080
Have a great shopping time in Vkamobi

Unknown said...

I am working at Rsorder.com, which is providing cheap runescape gold ,rs items, runescape money , rs account and rs powerleveling with fast delivery.What you say is very funny and your thought rs gold is so new , which is also easy to be understood. However, i also want to say i am hope for more here. Better to remain silent and be thought a fool that to speak and remove all cheap rs gold doubt.