412340 - JS propagated string literals should not be re-hashed/re-atomized

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect, P2)

Description

[Brendan Eich [:brendan]]

Since Igor's fix to make ATOM-tagged jsids be JSString jsvals, there's no point in rehashing or re-atomizing if we can detect that a computed property name is a string already interned in the atom table. A flag in JSString should be enough if we can safely clear it when GC finds the string still alive but with zero atom table references.

Igor, do you have cycles for this? Any better idea that fits in the beta 3 time remaining is welcome. This seems do-able to me.

/be

Comment 1

[Igor Bukanov]

This should be straightforward especially given the fact that GC does not need to deal with the flag. Currently the hash entry is preserved as long as the corresponding string is alive, see bug 386265 comment 15. 

Comment 2

[Igor Bukanov]

Attachment: patch to collect hashing stats

After each GC the patch prints stats about atomizing JSString versus atomizing char array. Here is an output from the browser start up until I opened few windows with gmail/yahoo/msn/dn.no/gazeta.ru :

JSString/all hashes: 2661/18091 (14.71%), rehashes/JSString: 2661/2661 (100.00%)
JSString/all hashes: 5445/48663 (11.19%), rehashes/JSString: 5441/5445 (99.93%)
JSString/all hashes: 13174/72829 (18.09%), rehashes/JSString: 13162/13174 (99.91%)

-- browser show empty window at this point

JSString/all hashes: 21169/86077 (24.59%), rehashes/JSString: 21157/21169 (99.94%)
JSString/all hashes: 21191/86183 (24.59%), rehashes/JSString: 21179/21191 (99.94%)
JSString/all hashes: 21203/86205 (24.60%), rehashes/JSString: 21191/21203 (99.94%)
JSString/all hashes: 41946/160492 (26.14%), rehashes/JSString: 41820/41946 (99.70%)
JSString/all hashes: 100078/247232 (40.48%), rehashes/JSString: 99656/100078 (99.58%)
JSString/all hashes: 116902/272011 (42.98%), rehashes/JSString: 116410/116902 (99.58%)
JSString/all hashes: 117999/273368 (43.16%), rehashes/JSString: 117488/117999 (99.57%)
JSString/all hashes: 128780/284917 (45.20%), rehashes/JSString: 128252/128780 (99.59%)
JSString/all hashes: 181892/344647 (52.78%), rehashes/JSString: 181362/181892 (99.71%)
JSString/all hashes: 229182/399402 (57.38%), rehashes/JSString: 228645/229182 (99.77%)
JSString/all hashes: 258449/447907 (57.70%), rehashes/JSString: 257659/258449 (99.69%)


The stats are typical: gradually most of the calls to js_AtomizeString is done for jSString instances as opposed to char array (like during parsing) and virtually all of JSString instances that JS_AtomizeString receives are already hashed.

Comment 3

[Igor Bukanov]

Attachment: patch to collect hashing stats v2

The new patch adds the stats about how often the same string is rehashed:

JSString/all hashes: 2661/18091 (14.71%), rehashes/JSString: 2661/2661 (100.00%), same_string/rehashes: 2626/2661 (98.68%)
JSString/all hashes: 5445/48663 (11.19%), rehashes/JSString: 5441/5445 (99.93%), same_string/rehashes: 5380/5441 (98.88%)
JSString/all hashes: 13174/72829 (18.09%), rehashes/JSString: 13162/13174 (99.91%), same_string/rehashes: 13016/13162 (98.89%)

-- after starting the browser

JSString/all hashes: 21204/86112 (24.62%), rehashes/JSString: 21192/21204 (99.94%), same_string/rehashes: 21035/21192 (99.26%)
JSString/all hashes: 36792/105470 (34.88%), rehashes/JSString: 36778/36792 (99.96%), same_string/rehashes: 36612/36778 (99.55%)
JSString/all hashes: 46764/184154 (25.39%), rehashes/JSString: 46608/46764 (99.67%), same_string/rehashes: 46229/46608 (99.19%)
JSString/all hashes: 119826/274966 (43.58%), rehashes/JSString: 119309/119826 (99.57%), same_string/rehashes: 118137/119309 (99.02%)
JSString/all hashes: 161466/338847 (47.65%), rehashes/JSString: 160426/161466 (99.36%), same_string/rehashes: 158445/160426 (98.77%)
JSString/all hashes: 190564/418304 (45.56%), rehashes/JSString: 189503/190564 (99.44%), same_string/rehashes: 187280/189503 (98.83%)
JSString/all hashes: 190602/418349 (45.56%), rehashes/JSString: 189541/190602 (99.44%), same_string/rehashes: 187318/189541 (98.83%)
JSString/all hashes: 226524/469299 (48.27%), rehashes/JSString: 225225/226524 (99.43%), same_string/rehashes: 222888/225225 (98.96%)
JSString/all hashes: 228307/477105 (47.85%), rehashes/JSString: 226997/228307 (99.43%), same_string/rehashes: 224637/226997 (98.96%)
JSString/all hashes: 239703/496506 (48.28%), rehashes/JSString: 238374/239703 (99.45%), same_string/rehashes: 235943/238374 (98.98%)
JSString/all hashes: 241424/500313 (48.25%), rehashes/JSString: 240089/241424 (99.45%), same_string/rehashes: 237647/240089 (98.98%)
JSString/all hashes: 257563/518344 (49.69%), rehashes/JSString: 256223/257563 (99.48%), same_string/rehashes: 253622/256223 (98.98%)
JSString/all hashes: 278035/545463 (50.97%), rehashes/JSString: 276694/278035 (99.52%), same_string/rehashes: 274060/276694 (99.05%)
JSString/all hashes: 295553/576287 (51.29%), rehashes/JSString: 294197/295553 (99.54%), same_string/rehashes: 291449/294197 (99.07%)
JSString/all hashes: 308157/590117 (52.22%), rehashes/JSString: 306783/308157 (99.55%), same_string/rehashes: 303842/306783 (99.04%)
JSString/all hashes: 315694/599703 (52.64%), rehashes/JSString: 314320/315694 (99.56%), same_string/rehashes: 311370/314320 (99.06%)
JSString/all hashes: 329078/615873 (53.43%), rehashes/JSString: 327699/329078 (99.58%), same_string/rehashes: 324638/327699 (99.07%)
JSString/all hashes: 339814/627691 (54.14%), rehashes/JSString: 338433/339814 (99.59%), same_string/rehashes: 335281/338433 (99.07%)
JSString/all hashes: 349198/638475 (54.69%), rehashes/JSString: 347816/349198 (99.60%), same_string/rehashes: 344197/347816 (98.96%)
JSString/all hashes: 374744/668713 (56.04%), rehashes/JSString: 373332/374744 (99.62%), same_string/rehashes: 367285/373332 (98.38%)
JSString/all hashes: 374835/668895 (56.04%), rehashes/JSString: 373423/374835 (99.62%), same_string/rehashes: 367376/373423 (98.38%)
JSString/all hashes: 388711/684249 (56.81%), rehashes/JSString: 387297/388711 (99.64%), same_string/rehashes: 381140/387297 (98.41%)
JSString/all hashes: 410138/712905 (57.53%), rehashes/JSString: 408714/410138 (99.65%), same_string/rehashes: 402122/408714 (98.39%)
JSString/all hashes: 422739/728596 (58.02%), rehashes/JSString: 421307/422739 (99.66%), same_string/rehashes: 414525/421307 (98.39%)
JSString/all hashes: 441763/751859 (58.76%), rehashes/JSString: 440326/441763 (99.67%), same_string/rehashes: 433339/440326 (98.41%)
JSString/all hashes: 458547/771003 (59.47%), rehashes/JSString: 457107/458547 (99.69%), same_string/rehashes: 450032/457107 (98.45%)
JSString/all hashes: 463988/777587 (59.67%), rehashes/JSString: 462548/463988 (99.69%), same_string/rehashes: 455473/462548 (98.47%)

Comment 4

[Igor Bukanov]

(In reply to comment #3)
> Created an attachment (id=297402) [details]
> patch to collect hashing stats v2

The stats tells that detecting hashed strings would avoid more than 50% of string hashes. But then it smells like a bad usage of API. I.e. why does the code in the browser need to rehash the same string instance repeatedly? I think it would be better to patch that code instead.

Comment 5

[Igor Bukanov]

Attachment: patch to collect hashing stats v3

The new version allows to see what of those same string rehashes comes from call_resolve from jsfun.c and what from js_ValueToStringAtom (called by JS_ValueToId). Here is the updated stats:

JSString/all hashes: 2661/18091 (14.71%), rehashes/JSString: 2661/2661 (100.00%), same_string/rehashes: 2626/2661 (98.68%), call_resolve-value_to_id/same_string: 90-2536/2626 (3.43-96.57%)
JSString/all hashes: 5445/48663 (11.19%), rehashes/JSString: 5441/5445 (99.93%), same_string/rehashes: 5380/5441 (98.88%), call_resolve-value_to_id/same_string: 197-5154/5380 (3.66-95.80%)
JSString/all hashes: 13174/72829 (18.09%), rehashes/JSString: 13162/13174 (99.91%), same_string/rehashes: 13016/13162 (98.89%), call_resolve-value_to_id/same_string: 472-12497/13016 (3.63-96.01%)
JSString/all hashes: 21281/86189 (24.69%), rehashes/JSString: 21269/21281 (99.94%), same_string/rehashes: 21112/21269 (99.26%), call_resolve-value_to_id/same_string: 1617-19448/21112 (7.66-92.12%)
JSString/all hashes: 23026/90508 (25.44%), rehashes/JSString: 23014/23026 (99.95%), same_string/rehashes: 22857/23014 (99.32%), call_resolve-value_to_id/same_string: 1837-20973/22857 (8.04-91.76%)
JSString/all hashes: 42689/160727 (26.56%), rehashes/JSString: 42563/42689 (99.70%), same_string/rehashes: 42236/42563 (99.23%), call_resolve-value_to_id/same_string: 4353-37666/42236 (10.31-89.18%)
JSString/all hashes: 101211/247931 (40.82%), rehashes/JSString: 100789/101211 (99.58%), same_string/rehashes: 100082/100789 (99.30%), call_resolve-value_to_id/same_string: 7175-92637/100082 (7.17-92.56%)
JSString/all hashes: 118206/273157 (43.27%), rehashes/JSString: 117714/118206 (99.58%), same_string/rehashes: 116523/117714 (98.99%), call_resolve-value_to_id/same_string: 7613-108640/116523 (6.53-93.23%)
JSString/all hashes: 154053/314876 (48.92%), rehashes/JSString: 153516/154053 (99.65%), same_string/rehashes: 148617/153516 (96.81%), call_resolve-value_to_id/same_string: 10075-138272/148617 (6.78-93.04%)
JSString/all hashes: 189113/363105 (52.08%), rehashes/JSString: 188545/189113 (99.70%), same_string/rehashes: 182826/188545 (96.97%), call_resolve-value_to_id/same_string: 13648-168892/182826 (7.47-92.38%)
JSString/all hashes: 266161/474319 (56.11%), rehashes/JSString: 265586/266161 (99.78%), same_string/rehashes: 259810/265586 (97.83%), call_resolve-value_to_id/same_string: 33387-226101/259810 (12.85-87.03%)
JSString/all hashes: 307554/530190 (58.01%), rehashes/JSString: 306474/307554 (99.65%), same_string/rehashes: 300326/306474 (97.99%), call_resolve-value_to_id/same_string: 41067-258917/300326 (13.67-86.21%)
JSString/all hashes: 338863/587935 (57.64%), rehashes/JSString: 337522/338863 (99.60%), same_string/rehashes: 331076/337522 (98.09%), call_resolve-value_to_id/same_string: 47220-283508/331076 (14.26-85.63%)
JSString/all hashes: 352204/613105 (57.45%), rehashes/JSString: 350832/352204 (99.61%), same_string/rehashes: 344198/350832 (98.11%), call_resolve-value_to_id/same_string: 48727-295123/344198 (14.16-85.74%)
JSString/all hashes: 377974/644466 (58.65%), rehashes/JSString: 376521/377974 (99.62%), same_string/rehashes: 365309/376521 (97.02%), call_resolve-value_to_id/same_string: 51454-313507/365309 (14.09-85.82%)
JSString/all hashes: 391040/659109 (59.33%), rehashes/JSString: 389584/391040 (99.63%), same_string/rehashes: 378334/389584 (97.11%), call_resolve-value_to_id/same_string: 52422-325564/378334 (13.86-86.05%)
JSString/all hashes: 398886/668674 (59.65%), rehashes/JSString: 397430/398886 (99.63%), same_string/rehashes: 386180/397430 (97.17%), call_resolve-value_to_id/same_string: 52422-333410/386180 (13.57-86.34%)
JSString/all hashes: 406653/678227 (59.96%), rehashes/JSString: 405197/406653 (99.64%), same_string/rehashes: 393947/405197 (97.22%), call_resolve-value_to_id/same_string: 52422-341177/393947 (13.31-86.60%)
JSString/all hashes: 412732/685726 (60.19%), rehashes/JSString: 411276/412732 (99.65%), same_string/rehashes: 400026/411276 (97.26%), call_resolve-value_to_id/same_string: 52422-347256/400026 (13.10-86.81%)
JSString/all hashes: 419564/694052 (60.45%), rehashes/JSString: 418108/419564 (99.65%), same_string/rehashes: 406858/418108 (97.31%), call_resolve-value_to_id/same_string: 52422-354088/406858 (12.88-87.03%)
JSString/all hashes: 428130/704650 (60.76%), rehashes/JSString: 426674/428130 (99.66%), same_string/rehashes: 415424/426674 (97.36%), call_resolve-value_to_id/same_string: 52422-362654/415424 (12.62-87.30%)

Comment 6

[Igor Bukanov]

The stats from the above points to the culprit of the same-string-rehashing: it is the resolve hooks that receives jsval, not jsid, as as such they are forced to rehash via jsval->id conversion. I guess a simple way to fix that would be in jsobj.c to cache the id and then compare against that cache when atomizing strings.

Comment 7

[Igor Bukanov]

(In reply to comment #6)
> I guess a simple way to fix that would be
> in jsobj.c to cache the id and then compare against that cache when atomizing
> strings.

Alternatively something like JSCLASS_NEW_NEW_RESOLVE can be added that receives the jsid, not jsval. 

Comment 8

[Brendan Eich [:brendan]]

Igor: I would rather tag JSString -- that would address the issue found by sayrer via SunSpider, right? That was not going through fun_resolve, it was merely value propagating literal strings into computed property name (indexed) contexts.

/be

Comment 9

[Igor Bukanov]

Attachment: resolve id caching

Here is a patch to verify that most same-string-rehashing happens due to resolve hooks. With the patch applied the statst shows that the amount of rehashes drops from 50-60% down to 12%.

JSString/all hashes: 2661/18091 (14.71%), rehashes/JSString: 109/2661 (4.10%), same_string/rehashes: 74/109 (67.89%), call_resolve-value_to_id/same_string: 0-74/74 (0.00-100.00%)
JSString/all hashes: 6287/53106 (11.84%), rehashes/JSString: 310/6287 (4.93%), same_string/rehashes: 245/310 (79.03%), call_resolve-value_to_id/same_string: 0-212/245 (0.00-86.53%)
JSString/all hashes: 15489/83628 (18.52%), rehashes/JSString: 632/15489 (4.08%), same_string/rehashes: 476/632 (75.32%), call_resolve-value_to_id/same_string: 0-425/476 (0.00-89.29%)
JSString/all hashes: 15489/83628 (18.52%), rehashes/JSString: 632/15489 (4.08%), same_string/rehashes: 476/632 (75.32%), call_resolve-value_to_id/same_string: 0-425/476 (0.00-89.29%)
JSString/all hashes: 22145/90644 (24.43%), rehashes/JSString: 676/22145 (3.05%), same_string/rehashes: 515/676 (76.18%), call_resolve-value_to_id/same_string: 0-464/515 (0.00-90.10%)
JSString/all hashes: 22194/90794 (24.44%), rehashes/JSString: 676/22194 (3.05%), same_string/rehashes: 515/676 (76.18%), call_resolve-value_to_id/same_string: 0-464/515 (0.00-90.10%)
JSString/all hashes: 22235/90894 (24.46%), rehashes/JSString: 676/22235 (3.04%), same_string/rehashes: 515/676 (76.18%), call_resolve-value_to_id/same_string: 0-464/515 (0.00-90.10%)
JSString/all hashes: 41978/163549 (25.67%), rehashes/JSString: 1200/41978 (2.86%), same_string/rehashes: 869/1200 (72.42%), call_resolve-value_to_id/same_string: 0-648/869 (0.00-74.57%)
JSString/all hashes: 59223/204859 (28.91%), rehashes/JSString: 3281/59223 (5.54%), same_string/rehashes: 2766/3281 (84.30%), call_resolve-value_to_id/same_string: 0-2492/2766 (0.00-90.09%)
JSString/all hashes: 117315/275831 (42.53%), rehashes/JSString: 15415/117315 (13.14%), same_string/rehashes: 14245/15415 (92.41%), call_resolve-value_to_id/same_string: 0-13971/14245 (0.00-98.08%)
JSString/all hashes: 166775/333834 (49.96%), rehashes/JSString: 32327/166775 (19.38%), same_string/rehashes: 24453/32327 (75.64%), call_resolve-value_to_id/same_string: 0-24179/24453 (0.00-98.88%)
JSString/all hashes: 203131/377691 (53.78%), rehashes/JSString: 34380/203131 (16.93%), same_string/rehashes: 25818/34380 (75.10%), call_resolve-value_to_id/same_string: 0-25536/25818 (0.00-98.91%)
JSString/all hashes: 244761/437969 (55.89%), rehashes/JSString: 35995/244761 (14.71%), same_string/rehashes: 27033/35995 (75.10%), call_resolve-value_to_id/same_string: 0-26731/27033 (0.00-98.88%)
JSString/all hashes: 307459/529633 (58.05%), rehashes/JSString: 38644/307459 (12.57%), same_string/rehashes: 29293/38644 (75.80%), call_resolve-value_to_id/same_string: 0-28962/29293 (0.00-98.87%)
JSString/all hashes: 312220/546557 (57.12%), rehashes/JSString: 38871/312220 (12.45%), same_string/rehashes: 29476/38871 (75.83%), call_resolve-value_to_id/same_string: 0-29145/29476 (0.00-98.88%)
JSString/all hashes: 324161/568415 (57.03%), rehashes/JSString: 39895/324161 (12.31%), same_string/rehashes: 30415/39895 (76.24%), call_resolve-value_to_id/same_string: 0-30084/30415 (0.00-98.91%)
JSString/all hashes: 336736/582397 (57.82%), rehashes/JSString: 40966/336736 (12.17%), same_string/rehashes: 31390/40966 (76.62%), call_resolve-value_to_id/same_string: 0-31059/31390 (0.00-98.95%)
JSString/all hashes: 359701/613097 (58.67%), rehashes/JSString: 42915/359701 (11.93%), same_string/rehashes: 32729/42915 (76.26%), call_resolve-value_to_id/same_string: 0-32390/32729 (0.00-98.96%)
JSString/all hashes: 373271/629899 (59.26%), rehashes/JSString: 43995/373271 (11.79%), same_string/rehashes: 33648/43995 (76.48%), call_resolve-value_to_id/same_string: 0-33309/33648 (0.00-98.99%)
JSString/all hashes: 393333/654841 (60.07%), rehashes/JSString: 50136/393333 (12.75%), same_string/rehashes: 35391/50136 (70.59%), call_resolve-value_to_id/same_string: 0-35052/35391 (0.00-99.04%)
JSString/all hashes: 411179/675394 (60.88%), rehashes/JSString: 51876/411179 (12.62%), same_string/rehashes: 37054/51876 (71.43%), call_resolve-value_to_id/same_string: 0-36715/37054 (0.00-99.09%)
JSString/all hashes: 428002/694632 (61.62%), rehashes/JSString: 53568/428002 (12.52%), same_string/rehashes: 38685/53568 (72.22%), call_resolve-value_to_id/same_string: 0-38346/38685 (0.00-99.12%)

Comment 10

[Igor Bukanov]

(In reply to comment #8)
> Igor: I would rather tag JSString -- that would address the issue found by
> sayrer via SunSpider, right? That was not going through fun_resolve, it was
> merely value propagating literal strings into computed property name (indexed)
> contexts.

With the resolve caching patch the amount of same-string-caching drops from 50%-60% to 12% * 0.72 = 8.6%. So these are the resolve hooks, not a generic literal propagation.

Comment 11

[Brendan Eich [:brendan]]

(In reply to comment #10)
> With the resolve caching patch the amount of same-string-caching drops from
> 50%-60% to 12% * 0.72 = 8.6%. So these are the resolve hooks, not a generic
> literal propagation.

On what benchmark or workload? I thought you were testing gmail sessions, not SunSpider -- sorry if I missed something. Sayrer can point you to the benchmark or just run it with your patch and post stats, I bet.

/be

Comment 12

[Igor Bukanov]

(In reply to comment #10)
> With the resolve caching patch the amount of same-string-caching drops from
> 50%-60% to 12% * 0.72 = 8.6%. So these are the resolve hooks, not a generic
> literal propagation.
> 

Actually the situation is worse. Without the patch the stats looks like:

rehashes/JSString 426674/428130 (99.66%)

with the patch at about the same point with normal browsing:

rehashes/JSString: 53568/428002 (12.25%)

That is, the resolve hooks are responsible for 88% of all JSString hashing. 

Comment 13

[Brendan Eich [:brendan]]

Agree we want to fix the resolve problem, but if we can kill two birds (or more) with one stone (string tagging when atomizing), why not? Code costs seem similar and small.

/be

Comment 14

[Igor Bukanov]

(In reply to comment #11)
> On what benchmark or workload? 

That was for normal browsing with pages showing mail.google.com/bugzilla.mozilla.org/msn.com/yahoo.com/dn.no/gazeta.ru/usavich.tv .

I thought you were testing gmail sessions, not
> Sayrer can point you to the benchmark
> or just run it with your patch and post stats, I bet.

That would be very nice. 

(In reply to comment #13)
> Agree we want to fix the resolve problem, but if we can kill two birds (or
> more) with one stone (string tagging when atomizing), why not? Code costs seem
> similar and small.


Still I suspect that just fixing the culprits of the problem would be a better approach that can spare JSString bit for other things. With NEW_NEW resolve hook it would be possible to avoid JS_ValueToId calls at all simplifying the code, and the problem exposed by the benchmark most likely will show another suboptimal code pattern.

Comment 15

[Robert Sayre]

looks like cvs diff failed in v3. Here are the numbers with v2 applied:

sayrer@usun:$ Linux_All_OPT.OBJ/js -f ~/dev/jstests/string-fasta.js 
sayrer@usun:$ more /tmp/hashstats.txt 
JSString/all hashes: 175168/175590 (99.76%), rehashes/JSString: 175167/175168 (100.00%), same_string/rehashes: 175167/175167 (100.00%)

Comment 16

[Brendan Eich [:brendan]]

The culprit with SunSpider is in its JS code, if we do not tag strings or do some data flow analysis equivalent to that in effect. Any JS that does

  foo = "id";
  ...
  obj[foo] = ...; // or ... = obj[foo]

will rehash foo's value, the string "id", in SpiderMonkey -- NEW_NEW_RESOLVE has nothing to do with it, of course, and there's no ad-hoc patch I can see other than indeed knowing (string flag bit in length, or perhaps we could do something completely different but equivalent involving u.chars or where it points) that "id" was not computed via "i" + "d", rather came from the string literal.

/be

Comment 17

[Brendan Eich [:brendan]]

(In reply to comment #16)
> points) that "id" was not computed via "i" + "d", rather came from the string
> literal.

or (I should have written) "was that string literal".

/be

Comment 18

[Igor Bukanov]

Attachment: v1

The patch uses an extra bit from JSString.length to store the atomized status of the string. The patch added macros JSFLATSTR_(CHARS|LENGTH) to make sure that no code accesses JSString.(length|u.chars) unless it knows that this not an atomized string.

Comment 19

[Igor Bukanov]

Attachment: v2

The new version optimizes js_AtomizeString to avoid an extra unlocking if it is known that the string is flat and can be made immune with single bit clearing operation.

Comment 20

[Igor Bukanov]

Attachment: diff -b version of v2

Comment 21

[Brendan Eich [:brendan]]

Comment on attachment 297568 [details] [diff] [review]
v2

>     JS_ASSERT((flags &
>                ~(ATOM_PINNED | ATOM_INTERNED | ATOM_TMPSTR | ATOM_NOCOPY))
>               == 0);

Pre-existing ultra-nit, but would be nicer to fit on one line:

    JS_ASSERT(!(flags & ~(ATOM_PINNED|ATOM_INTERNED|ATOM_TMPSTR|ATOM_NOCOPY)));

>+        return (JSAtom *)v;

Does JSAtom (an anonymous struct typedef, and we never declare the struct IIRC) serve any purpose any longer?

>+                    /*
>+                     * Transfer ownership of str->chars to GC-controlled
>+                     * string.

Comment should say "str->u.chars", or could be a one-liner: /* Finish handing off chars to the GC'ed key string. */

>+ * A flat string with JSSTRFLAG_ATOMIZED set means that the string is hashed
>+ * as an atom.The flag is used to avoid re-hashing of the already atomized

Space after period, and "already-atomized".

>+ * JSSTRFLAG_MUTABLE should be used only if the string is flat and
>+ * JSSTRFLAG_DEPENDENT is unset. JSSTRFLAG_ATOMIZED is only used with the

Nit: s/only used/used only/.

> #define JSSTRING_CHARS_AND_END(str, chars_, end)                              \
>     ((void)((end) = JSSTRING_IS_DEPENDENT(str)                                \
>                   ? JSSTRDEP_LENGTH(str) + ((chars_) = JSSTRDEP_CHARS(str))   \
>-                  : ((str)->length & ~JSSTRFLAG_MUTABLE) +                    \
>-                    ((chars_) = (str)->u.chars)))
>-
>-#define JSSTRING_LENGTH_BITS        (sizeof(size_t) * JS_BITS_PER_BYTE        \
>-                                     - JSSTRFLAG_BITS)
>-#define JSSTRING_LENGTH_MASK        JSSTRING_BITMASK(JSSTRING_LENGTH_BITS)
>+                  : (JSFLATSTR_LENGTH(str) +                                  \
>+                     ((chars_) = JSFLATSTR_CHARS(str)))))

The : (else) addition expression is overparenthesized.

>+/*
>+ * Specific macro to get the length and characters of a flat string.
>+ */
>+#define JSFLATSTR_LENGTH(str)                                                 \
>+    ((void)(JS_ASSERT(!JSSTRING_IS_DEPENDENT(str))),                          \
>+     (str)->length & JSSTRING_LENGTH_MASK)
>+
>+#define JSFLATSTR_CHARS(str)                                                  \
>+    ((void)(JS_ASSERT(!JSSTRING_IS_DEPENDENT(str))),                          \
>+     (str)->u.chars)

The JS_ASSERT macro calls are over-parenthesized.

> /* Specific mutable string manipulation macros. */
> #define JSSTRING_SET_MUTABLE(str)                                             \
>     ((void)(JS_ASSERT(!JSSTRING_IS_DEPENDENT(str)),                           \
>             (str)->length |= JSSTRFLAG_MUTABLE))
> 
> #define JSSTRING_CLEAR_MUTABLE(str)                                           \
>     ((void)(JS_ASSERT(!JSSTRING_IS_DEPENDENT(str)),                           \
>             (str)->length &= ~JSSTRFLAG_MUTABLE))
> 
>+/* Macro to set the atomized flag. */
>+#define JSSTRING_SET_ATOMIZED(str)                                            \
>+    ((void)(JS_ASSERT(!JSSTRING_IS_DEPENDENT(str)),                           \
>+            JS_ASSERT(!JSSTRING_IS_MUTABLE(str)),                             \
>+            (str)->length |= JSSTRFLAG_ATOMIZED))

Worth commenting on the runtime's atom table lock serializing JSSTRING_CLEAR_MUTABLE and JSSTRING_SET_ATOMIZED races under js_AtomizeString, and how other calls to JSSTRING_{SET,CLEAR}_MUTABLE are made only on single-threaded (newborn, in the case of JSSTRING_SET_MUTABLE) strings. Also the intentional lack of JSSTRING_CLEAR_ATOMIZED.

> #define JSSTRDEP_CHARS(str)                                                   \
>     (JSSTRING_IS_DEPENDENT(JSSTRDEP_BASE(str))                                \
>      ? js_GetDependentStringChars(str)                                        \
>-     : JSSTRDEP_BASE(str)->u.chars + JSSTRDEP_START(str))
>+     : JSFLATSTR_CHARS(JSSTRDEP_BASE(str)) + JSSTRDEP_START(str))

(Here is a + expr on right of : in ternary that is nicely *not* over-parenthesized.)

Thanks, great to have this patch; it was something I thought about in the old days but deferred (optimize later, meaning now).

/be

Comment 22

[Igor Bukanov]

(In reply to comment #21)
> Does JSAtom (an anonymous struct typedef, and we never declare the struct IIRC)
> serve any purpose any longer?

The JSAtom* exists only as a typedef. It is useful for type safety. On the other hand given that under the typical browser load there are less than 100 double atoms I think it would made sense to stop atomizing doubles and just ensure that they are unique per script. Then JSAtom* can be replaced by JSString* + asserts that strings are atomized. It should simplify code.

Comment 23

[Igor Bukanov]

Attachment: v3

Changes from v2 besides addressing the nits:

JSSTRING_CLEAR_MUTABLE clear the flag only when it is set for thread-safety - see comments in jsstr.h. As an alternative I considered keep JSSTRING_CLEAR_MUTABLE as its is but change js_AtomizeString to always set the atomized flag on its result even when the string was hashed. But tolerating such flip-flop races of mutable/atomized flags requires much more analysis than simply preventing the atomized flag from being ever cleared.

Since all same-string hashes comes from js_ValueToStringAtom, the new version checks for the already hashed string there, not in js_AtomizeAtom, to have less ifs in the latter and more optimized code in the former.

As most callers of js_ValueToStringAtom prefer the id, not atom, the patch makes the function to return the id and changes its name to js_ValueToStringId.

Comment 24

[Igor Bukanov]

Attachment: v2-v3 delta

Comment 25

[Igor Bukanov]

Attachment: v3b

The new version tries to improve the language in comments.

Comment 26

[Igor Bukanov]

Attachment: v2-v3b delta

Comment 27

[Igor Bukanov]

Attachment: v3c

Here is more comment fixes.

Comment 28

[Igor Bukanov]

Attachment: v2 - v3c delta

Here is a delta to see the changes since the reviewed v2.

Comment 29

[Igor Bukanov]

Attachment: v4

The new version consistently uses idval as the name of variable holding the value for the property and fixes JS_SetWatchPoint to use propid, not idval, when calling OBJ_GET_PROPERTY and OBJ_GET_ATTRIBUTES.

Comment 30

[Igor Bukanov]

Attachment: v2 - v4 delta

Here is a delta to see the changes since the reviewed v2.

Comment 31

[Igor Bukanov]

Attachment: v5

Here is a patch with a better version of value to id conversion.

Comment 32

[Igor Bukanov]

Attachment: v2 - v5 delta

Here is a delta to see the changes since the reviewed v2.

Comment 33

[Brendan Eich [:brendan]]

Comment on attachment 297730 [details] [diff] [review]
v5

>+    /*
>+     * Optimize for the common case when v is the already atomized string. The
>+     * comment in jsstr.h before the JSSTRING_SET_ATOMIZED macro explains why
>+     * this is thread-safe. The extra rooting via lastAtom (that would be
>+     * otherwise done in js_js_AtomizeString) ensures the caller that the
>+     * resulting id at least weakly rooted.

Suggest rewording as follows:

    /*
     * Optimize for the common case where v is an already-atomized string. The
     * comment in jsstr.h before the JSSTRING_SET_ATOMIZED macro's definition
     * explains why this is thread-safe. The extra rooting via lastAtom (which
     * would otherwise be done in js_js_AtomizeString) ensures the caller that
     * the resulting id at least weakly rooted.
     */

Wraps better this way too.

>+ * A flat string with JSSTRFLAG_ATOMIZED set means that the string is hashed
>+ * as an atom. The flag is used to avoid re-hashing of the already-atomized

s/The flag/This flag/

>+ * Specific macros to manipulate atomized and mutable flags. It is safe to use
>+ * them without extra locking due to the following properties:

s/them/these/

>+ *
>+ *   * We do not have a macro like JSSTRING_CLEAR_MUTABLE as a string remains

JSSTRING_CLEAR_ATOMIZED, right?

>+ *     atomized until the GC collects it.
>+ *
>+ *   * A thread may call JSSTRING_SET_MUTABLE only when it is the only thread
>+ *     accessing the string until a later call to JSSTRING_CLEAR_MUTABLE.
>+ *
>+ *   * Multiple threads can call JSSTRING_CLEAR_MUTABLE but the macro clears

Suggest "actually clears", not just "clears"

>+ *     the mutable flag only when the flag is set and only one thread accesses

Suggest "only when the flag is set -- in which case there can be only one thread accessing the string (see previous property)."

>+ *     the string.
>+ *
>+ *  Thus, when multiple threads access the string, JSSTRING_SET_ATOMIZED is
>+ *  the only macro that can update the length field of the string by changing
>+ *  the mutable bit from 0 to 1. We call the macro only after the string has
>+ *  been hashed. When some thread in js_ValueToStringId see that the flag is

"some thread ... sees"

>+ *  set, it knows that the string was atomized.
>+ *
>+ *  On the other hand, if the thread see that the flag is unset, that can be a

"thread sees"

Suggest replacing "that can be" with "it could be seeing".

>+ *  stalled value when another has just atomized the string and set the flag.

s/stalled/stale/

Suggest "another thread" not just "another"

>+ *  But the only consequence of this is an extra call to js_AtomizeString. The
>+ *  function would find that the string was cached and return it with the

Maybe "already hashed" instead of "cached".

r=me with these nits picked.

/be

Comment 34

[Igor Bukanov]

Attachment: v5b

Here is the version to check in with the nits addressed.

Comment 35

[Igor Bukanov]

Attachment: v5 - v5b delta

Comment 36

[Igor Bukanov]

I checked in the patch from comment 34 to the trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%252Fcvsroot&date=explicit&mindate=1200711122&maxdate=1200711452&who=igor%25mir2.org

Comment 37

[Igor Bukanov]

To tinderbox observers: fxdbug-win32-tb  failed after the check in of the patch. If fxdbug-win32-tb would continue to fail, please back out yje patch.

Comment 38

[Reed Loden [:reed]]

Backed out due to consistent orange on fxdbug-win32-tb.

Comment 39

[Igor Bukanov]

Since it is not clear what caused the orange, I will file as separated bugs the changes from the patch to add flat string macros and js_ValueToStringAtom->js_ValueToStringId refactoring.

Comment 40

[Igor Bukanov]

(In reply to comment #38)
> Backed out due to consistent orange on fxdbug-win32-tb.

Actually that was not a consistent orange since after the first orange the box went back to green. I guess that is called bad luck especially given that backing have not helped.

Comment 41

[Igor Bukanov]

Attachment: v6

This is the previous version updated to remove changes that went into bug 413104.

Comment 42

[Brendan Eich [:brendan]]

Comment on attachment 298039 [details] [diff] [review]
v6

>+    /*
>+     * Optimize for the common case where v is an already-atomized string. The
>+     * comment in jsstr.h before the JSSTRING_SET_ATOMIZED macro's definition
>+     * explains why this is thread-safe. The extra rooting via lastAtom (which
>+     * would otherwise be done in js_js_AtomizeString) ensures the caller that
>+     * the resulting id at least weakly rooted.

"is" needed before "at least weakly rooted."

>+/*
>+ * Macros to manipulate atomized and mutable flags of flat strings. It is safe
>+ * to use these without extra locking due to the following properties:
>+ *
>+ *   * We do not have a macro like JSFLATSTR_CLEAR_ATOMIZED as a string
>+ *     remains atomized until the GC collects it.
>+ *
>+ *   * A thread may call JSFLATSTR_SET_MUTABLE only when it is the only thread
>+ *     accessing the string until a later call to JSFLATSTR_CLEAR_MUTABLE.
>+ *
>+ *   * Multiple threads can call JSFLATSTR_CLEAR_MUTABLE but the macro
>+ *     actually clears the mutable flag only when the flag is set -- in which
>+ *     case only one thread can access the string (see previous property).
>+ *
>+ *  Thus, when multiple threads access the string, JSFLATSTR_SET_ATOMIZED is
>+ *  the only macro that can update the length field of the string by changing
>+ *  the mutable bit from 0 to 1. We call the macro only after the string has
>+ *  been hashed. When some threads in js_ValueToStringId see that the flag is
>+ *  set, it knows that the string was atomized.
>+ *
>+ *  On the other hand, if the thread sees that the flag is unset, it could be
>+ *  seeing a stale value when another thread has just atomized the string and
>+ *  set the flag. But this can lead only to an extra call to js_AtomizeString.
>+ *  This function would find that the string was already hashed and return it
>+ *  with the atomized bit set.

Nit: last two paragraphs have two spaces after the * column, instead of one space.

r/a=me with these picked.

/be

Comment 43

[Igor Bukanov]

Attachment: v6b

Here is the patch to address the nits from comment 42.

Comment 44

[Igor Bukanov]

Attachment: v6c

Here is the patch I am going to check in. The previous one does not addressed all nits about bad English in comments.

Comment 45

[Igor Bukanov]

I checked in the patch from comment 44 to the trunk:

http://bonsai.mozilla.org/cvsquery.cgi?module=PhoenixTinderbox&branch=HEAD&cvsroot=%252Fcvsroot&date=explicit&mindate=1201094220&maxdate=1201094253&who=igor%25mir2.org

Comment 46

[Mike Schroepfer]

Just a note that this improved Txul by around 3-4%:

http://graphs.mozilla.org/#spst=range&spss=1201091396.4544635&spse=1201102331.8412986&spstart=1200873600&spend=1201378906&bpst=Cursor&bpstart=1201091396.4544635&bpend=1201102331.8412986&m1tid=53214&m1bl=0&m1avg=0&m2tid=53250&m2bl=0&m2avg=0&m3tid=53232&m3bl=0&m3avg=0&m4tid=53268&m4bl=0&m4avg=0

Comment 47

[Mike Moening]

This patch causes ASSERT to fire in multi-threaded JS embedding.
See bug# 415474 for details.  
Asking for permission to re-open this bug...

Comment 48

[Mike Moening]

Commented out this line:

JS_ASSERT(JSSTRING_IS_ATOMIZED(key));

in jsatom.c and now multi-threaded apps run fine.
How can I fix this ASSERT for multi-threaded embeddings?

Comment 49

[Brendan Eich [:brendan]]

Do not reopen this bug. It was fixed, with a followup bug introduced, which we can track with the bug you filed at bug 415474.

/be