WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
RESOLVED INVALID
20589
PropertyMap speedup
https://bugs.webkit.org/show_bug.cgi?id=20589
Summary
PropertyMap speedup
Zoltan Herczeg
Reported
2008-09-01 06:19:03 PDT
Dear Community, I was thinking about improving the PropertyMap lookup speed with a simple lookup table. The lookup contains 1 or 2 keys, and their assigned PropertyMapEntry reference (even if the reference is null, which means, the identifier is not exists in this map) The get/put/getLocation methods are checking the lookup fields first (they are inline methods now), and they call the old code on fail. Modified files: PropertyMap.cpp PropertyMap.h Performance improvements for SunSpider: Original code: Runtime: 2877.4ms +/- 0.2% Lookup table size: 1 key lookupHits: 2225393 times lookupMiss: 3159406 times That is 41.3% lookup hit ratio Performance: 2848.7ms +/- 0.2% -> 1.01% performance improvement Lookup table size: 2 keys lookupHits: 3331922 times lookupMiss: 2880252 times That is 53.6% lookup hit ratio Performance: 2850.7ms +/- 0.1% -> 0.94% performance improvement I will also send you the Windscorpion results when they are done. Do you have any ideas how can I improve this algorithm further? Thanks in advance
Attachments
Diff for table size 1
(18.12 KB, patch)
2008-09-01 06:20 PDT
,
Zoltan Herczeg
no flags
Details
Formatted Diff
Diff
Diff for table size 2
(20.14 KB, patch)
2008-09-01 06:20 PDT
,
Zoltan Herczeg
no flags
Details
Formatted Diff
Diff
SunSpider with lookup table size: 1
(3.88 KB, text/plain)
2008-09-02 01:35 PDT
,
Zoltan Herczeg
no flags
Details
SunSpider with lookup table size: 2
(3.94 KB, text/plain)
2008-09-02 01:35 PDT
,
Zoltan Herczeg
no flags
Details
WindScorpion with lookup table size: 1
(2.03 KB, text/plain)
2008-09-02 01:36 PDT
,
Zoltan Herczeg
no flags
Details
WindScorpion with lookup table size: 2
(2.10 KB, text/plain)
2008-09-02 01:36 PDT
,
Zoltan Herczeg
no flags
Details
Diff for table size 1 /b
(15.25 KB, patch)
2008-09-04 02:13 PDT
,
Zoltan Herczeg
no flags
Details
Formatted Diff
Diff
Diff for table size 2 /b
(17.44 KB, patch)
2008-09-04 02:14 PDT
,
Zoltan Herczeg
no flags
Details
Formatted Diff
Diff
Diff for table size 1 /c
(17.04 KB, patch)
2008-09-08 06:23 PDT
,
Zoltan Herczeg
ggaren
: review-
Details
Formatted Diff
Diff
Diff for table size 2 /c
(19.21 KB, patch)
2008-09-08 06:23 PDT
,
Zoltan Herczeg
no flags
Details
Formatted Diff
Diff
Patch for recording cache hits.
(3.13 KB, patch)
2008-09-08 15:00 PDT
,
Geoffrey Garen
no flags
Details
Formatted Diff
Diff
Cache hit results
(167.33 KB, text/plain)
2008-09-08 15:02 PDT
,
Geoffrey Garen
no flags
Details
Diff for table size 1 /d
(15.34 KB, patch)
2008-09-10 03:34 PDT
,
Zoltan Herczeg
ggaren
: review-
Details
Formatted Diff
Diff
Show Obsolete
(6)
View All
Add attachment
proposed patch, testcase, etc.
Zoltan Herczeg
Comment 1
2008-09-01 06:20:35 PDT
Created
attachment 23097
[details]
Diff for table size 1
Zoltan Herczeg
Comment 2
2008-09-01 06:20:54 PDT
Created
attachment 23098
[details]
Diff for table size 2
Zoltan Herczeg
Comment 3
2008-09-02 01:34:20 PDT
Hi, I made extensive testing and gather as much information as possible to help you. These are the results for WindScorpion benchmark suite: Original code: Runtime: 31882.0ms +/- 0.8% Lookup table size: 1 key lookupHits: 36211684 times lookupMiss: 52271769 times That is 40.9% lookup hit ratio Performance: 31795.5ms +/- 1.0% -> 0.3% performance improvement ( not significant!!! ) Lookup table size: 2 key lookupHits: 63370946 times lookupMiss: 24868347 times That is 71.8% lookup hit ratio Performance: 31083.9ms +/- 0.7% -> 2.57% performance improvement My conclusions: It seems the lookup table with 2 entries is more suitable for common JavaScript programs than the one with with only 1 entry, which is, on the contrary, slightly more suitable for optimized JavaScript code like SunSpider. I enclose all comparions for Sunspider and Windscorpion.
Zoltan Herczeg
Comment 4
2008-09-02 01:35:32 PDT
Created
attachment 23108
[details]
SunSpider with lookup table size: 1
Zoltan Herczeg
Comment 5
2008-09-02 01:35:52 PDT
Created
attachment 23109
[details]
SunSpider with lookup table size: 2
Zoltan Herczeg
Comment 6
2008-09-02 01:36:14 PDT
Created
attachment 23110
[details]
WindScorpion with lookup table size: 1
Zoltan Herczeg
Comment 7
2008-09-02 01:36:29 PDT
Created
attachment 23111
[details]
WindScorpion with lookup table size: 2
Zoltan Herczeg
Comment 8
2008-09-03 11:16:02 PDT
What is your opinion? How can I make this patch better? Thanks in advance
Cameron Zwarich (cpst)
Comment 9
2008-09-03 11:43:09 PDT
There were a lot of changes to property lookup made in
r36016
, so this no longer patches cleanly. Will it be possible to make a new version that patches against ToT?
Zoltan Herczeg
Comment 10
2008-09-04 02:13:16 PDT
Created
attachment 23162
[details]
Diff for table size 1 /b
Zoltan Herczeg
Comment 11
2008-09-04 02:14:05 PDT
Created
attachment 23163
[details]
Diff for table size 2 /b
Zoltan Herczeg
Comment 12
2008-09-04 02:17:55 PDT
Hi! I have updated the patches. By the way, kjs/StructureID.cpp was missing for JavaScriptCore.pri, so the project does not compiles under Qt now. Shall I make a patch for it? That is really a simple bug.
Zoltan Herczeg
Comment 13
2008-09-04 04:31:13 PDT
Here are the results: For lookup table Size is 1: SunSpider: 1.35% WindScorpion: 1.01% For lookup table Size is 2: SunSpider: 0.67% WindScorpion: 2.09% Still, the increase of the gain is reversed for SunSpider and WindScorpion.
Zoltan Herczeg
Comment 14
2008-09-05 05:11:00 PDT
The syntax of that patch is ok? I tried to follow the coding style of webkit. Can I help you in anything else?
Alexey Proskuryakov
Comment 15
2008-09-08 03:56:57 PDT
Please mark the patches for review by clicking an Edit link and setting review? flag to ensure that they do not get lost. Talking only about coding style: Please write ChangeLogs as per <
http://webkit.org/coding/contributing.html
>. You can use prepare-ChangeLog script to make a stub, and add actual information to it. + numLookupMiss++; We prefer prefix notation. It obviously makes no difference here, but for iterator objects, it can be faster, and it's good to use a common style everywhere. + if (m_u.table->keyLookup1 && m_u.table->keyLookup1 == rep) { + m_u.table->entryLookup1 = 0; + } We do not put braces around single line blocks.
Zoltan Herczeg
Comment 16
2008-09-08 06:23:23 PDT
Created
attachment 23252
[details]
Diff for table size 1 /c
Zoltan Herczeg
Comment 17
2008-09-08 06:23:57 PDT
Created
attachment 23253
[details]
Diff for table size 2 /c
Zoltan Herczeg
Comment 18
2008-09-08 06:31:40 PDT
PropertyMap.h requires the ReadOnly constant, which is defined by JSObject.h, which also includes PropertyMap.h . This is a circular reference. A simple workaround is that a constant is defined in PropertyMap.h, but I don't like it: #define JSOBJECT_READONLY (1 << 1) What should be better. And which one you prefer, table size 1 or table size 2?
Geoffrey Garen
Comment 19
2008-09-08 14:59:14 PDT
It surprised me that this patch was still a win, despite polymorphic inline caching, so I did an instrumented run of SunSpider to test which properties the cache helped with. I've attached the patch as patch-record-cache-hits.txt, and the results as cache-hits.txt.
Geoffrey Garen
Comment 20
2008-09-08 15:00:21 PDT
Created
attachment 23272
[details]
Patch for recording cache hits.
Geoffrey Garen
Comment 21
2008-09-08 15:02:16 PDT
Created
attachment 23273
[details]
Cache hit results
Geoffrey Garen
Comment 22
2008-09-08 15:06:33 PDT
The results indicate a few areas that we plan to cover with polymorphic inline cache: 1. Properties of primitive values, like "".charAt. 2. Global resolve, like "new Array". 3. Values that should have been cached but weren't, like Math.abs. (Not clear yet why the cache failed.) I don't think this overlap is an argument against caching in the property map, but I do think that, once we fix these holes in the inline cache, caching in the property map may turn out to be a net loss, in which case we should remove it at that time.
Geoffrey Garen
Comment 23
2008-09-08 16:34:18 PDT
Comment on
attachment 23252
[details]
Diff for table size 1 /c I prefer the 1 item cache because it's a bigger win on SunSpider, and it's simpler. I think the best way to solve the JSOBJECT_READONLY problem is simply to move the definition of property attributes into PropertyMap.h. +#if DUMP_PROPERTYMAP_STATS + static int numLookupHits; +#endif This change is invalid, since it will increase the size of a JavaScript object, which has a fixed size limit. I'm surprised that JavaScriptCore still builds with this change applied -- we have compile-time ASSERTs that should cause a build failure. I think the best solution is just to leave DUMP_PROPERTYMAP_STATS out of the patch. Alternatively, you could use a static counter in PropertyMap.cpp for these stats. (You've already done that for numLookupMiss.) That wouldn't be thread-safe, but that's OK, since it's just a debugging tool. I would also rename this #define to DUMP_PROPERTYMAP_CACHE_HITS, and move it to PropertyMap.cpp. I don't like the change to make a bunch of get and put wrapper functions around getInternal and putInternal functions. I think it bloats PropertyMap substantially. A better solution would be just to write the caching logic directly into all the existing get and put functions. I think the name "putLookup" is far too generic for a function in a class that already uses the word "put" to mean something else. "recordLookup" and "clearRecordedLookup" would be better names. "keyLookup1" is a pretty generic name too. How about "lastLookup"?
Geoffrey Garen
Comment 24
2008-09-08 16:34:40 PDT
Comment on
attachment 23253
[details]
Diff for table size 2 /c Clearing the review flag on this patch, since I reviewed the other patch.
Geoffrey Garen
Comment 25
2008-09-08 16:39:17 PDT
> +#if DUMP_PROPERTYMAP_STATS > + static int numLookupHits; > +#endif > > This change is invalid, since it will increase the size of a JavaScript object, > which has a fixed size limit. I'm surprised that JavaScriptCore still builds > with this change applied -- we have compile-time ASSERTs that should cause a > build failure.
Oops! I see now that numLookupHits is static, so it won't increase the object size. I'd still recommend moving it to the .cpp file, to match numLookupMiss, though.
Zoltan Herczeg
Comment 26
2008-09-10 03:34:50 PDT
Created
attachment 23317
[details]
Diff for table size 1 /d
Zoltan Herczeg
Comment 27
2008-09-10 03:42:48 PDT
Hi! The recent changes made me rebuild the patch from scratch and that took time (understanding the changes, testing, etc). It is not worth to move the cache logic into the cpp file, since there is no gain in that case. Unfortunatly, the changes eat up most of the gain. The reason is that the JSValue storing is cut from the Property Map, so we can't cache anything now.
Maciej Stachowiak
Comment 28
2008-09-13 14:35:43 PDT
(In reply to
comment #22
)
> The results indicate a few areas that we plan to cover with polymorphic inline > cache: > 1. Properties of primitive values, like "".charAt. > 2. Global resolve, like "new Array". > 3. Values that should have been cached but weren't, like Math.abs. (Not clear > yet why the cache failed.)
I fixed polymorphic inline caching to handle case 1, primitives, and case 2, functions on the Math object (and others). I believe Oliver is working on global resolves, but this may already remove most of the opportunities for improvement from this patch. Still worth testing though.
> > I don't think this overlap is an argument against caching in the property map, > but I do think that, once we fix these holes in the inline cache, caching in > the property map may turn out to be a net loss, in which case we should remove > it at that time. >
Geoffrey Garen
Comment 29
2008-10-24 13:18:48 PDT
Comment on
attachment 23317
[details]
Diff for table size 1 /d r- because the inline cache has solved this problem.
Note
You need to
log in
before you can comment on or make changes to this bug.
Top of Page
Format For Printing
XML
Clone This Bug