Bug 20589 – PropertyMap speedup

• Status: RESOLVED
• Resolution: INVALID
• Component: JavaScriptCore

[Zoltan Herczeg]

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

[Zoltan Herczeg]

Created attachment 23097 [details]
Diff for table size 1

[Zoltan Herczeg]

Created attachment 23098 [details]
Diff for table size 2

[Zoltan Herczeg]

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]

Created attachment 23108 [details]
SunSpider with lookup table size: 1

[Zoltan Herczeg]

Created attachment 23109 [details]
SunSpider with lookup table size: 2

[Zoltan Herczeg]

Created attachment 23110 [details]
WindScorpion with lookup table size: 1

[Zoltan Herczeg]

Created attachment 23111 [details]
WindScorpion with lookup table size: 2

[Zoltan Herczeg]

What is your opinion? How can I make this patch better?

Thanks in advance

[Cameron Zwarich (cpst)]

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]

Created attachment 23162 [details]
Diff for table size 1 /b

[Zoltan Herczeg]

Created attachment 23163 [details]
Diff for table size 2 /b

[Zoltan Herczeg]

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]

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]

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]

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]

Created attachment 23252 [details]
Diff for table size 1 /c

[Zoltan Herczeg]

Created attachment 23253 [details]
Diff for table size 2 /c

[Zoltan Herczeg]

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]

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]

Created attachment 23272 [details]
Patch for recording cache hits.

[Geoffrey Garen]

Created attachment 23273 [details]
Cache hit results

[Geoffrey Garen]

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 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 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]

> +#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]

Created attachment 23317 [details]
Diff for table size 1 /d

[Zoltan Herczeg]

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]

(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 on attachment 23317 [details]
Diff for table size 1 /d

r- because the inline cache has solved this problem.