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
Created attachment 23097 [details] Diff for table size 1
Created attachment 23098 [details] Diff for table size 2
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.
Created attachment 23108 [details] SunSpider with lookup table size: 1
Created attachment 23109 [details] SunSpider with lookup table size: 2
Created attachment 23110 [details] WindScorpion with lookup table size: 1
Created attachment 23111 [details] WindScorpion with lookup table size: 2
What is your opinion? How can I make this patch better? Thanks in advance
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?
Created attachment 23162 [details] Diff for table size 1 /b
Created attachment 23163 [details] Diff for table size 2 /b
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.
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.
The syntax of that patch is ok? I tried to follow the coding style of webkit. Can I help you in anything else?
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.
Created attachment 23252 [details] Diff for table size 1 /c
Created attachment 23253 [details] Diff for table size 2 /c
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?
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.
Created attachment 23272 [details] Patch for recording cache hits.
Created attachment 23273 [details] Cache hit results
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.
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"?
Comment on attachment 23253 [details] Diff for table size 2 /c Clearing the review flag on this patch, since I reviewed the other patch.
> +#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.
Created attachment 23317 [details] Diff for table size 1 /d
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.
(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. >
Comment on attachment 23317 [details] Diff for table size 1 /d r- because the inline cache has solved this problem.