Bug 160989

Summary: Make JSMap and JSSet faster
Product: WebKit Reporter: Saam Barati <saam>
Component: JavaScriptCoreAssignee: Saam Barati <saam>
Status: RESOLVED FIXED    
Severity: Normal CC: benjamin, commit-queue, fpizlo, ggaren, gskachkov, jfbastien, keith_miller, mark.lam, msaboff, oliver, ryanhaddad, sukolsak, ticaiolima, ysuzuki
Priority: P2    
Version: WebKit Local Build   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 161268, 161645, 164128    
Bug Blocks: 161744    
Attachments:
Description Flags
WIP
none
WIP
none
WIP
none
WIP
none
WIP
none
WIP
none
WIP
none
WIP
none
WIP
none
WIP
none
WIPP
none
WIP
none
WIP
none
patch
none
patch
none
patch
none
patch
fpizlo: review+
patch for landing
saam: commit-queue-
patch for landing
none
patch for landing none

Description Saam Barati 2016-08-18 18:48:47 PDT
Currently, I'm considering writing the whole thing in JS.
In my WIP, my map, with 10,000,000 entries with JSObject keys, is about 
- 60% slower to construct than the current implementation
- 2x faster to do lookups

(I'm currently implementing iteration to see what the perf difference is there).
Comment 1 Saam Barati 2016-08-18 20:58:15 PDT
Created attachment 286435 [details]
WIP

Still pretty rough, and there exist some bugs with iteration while mutating the map.
Comment 2 Saam Barati 2016-08-19 19:27:06 PDT
Created attachment 286517 [details]
WIP

Still rough. About 1% faster on ES6 sample bench, which isn't much.
But I'm just getting started on actually optimizing the hash table and
the various JS operations it uses.
Comment 3 Saam Barati 2016-08-21 20:30:18 PDT
Ok, so the patch that's up here as a WIP is actually about 8%
faster on Basic, but neutral on Air. I'm going to continue
trying to optimize it but there is a chance I'll just write
the same style of hash table in C++ and make get/has/etc an
intrinsic. I'll see if we end up spending meaningful time
in parts of the function that would benefit from being in C++
and then inlined as an intrinsic.
Comment 4 Saam Barati 2016-08-23 15:00:15 PDT
So this is a progression for Map related things, however,
I'm too tempted to write the hash table in C++ with an intrinsic
for Get/Has/etc to not try doing that. I suspect this might
give us another few percent in perf improvement.

I'm working on a few other patches ATM, then I'll get back to this.
Comment 5 Saam Barati 2016-08-24 20:43:38 PDT
Created attachment 286940 [details]
WIP

Starting to have a hashmap that works in C.
I still need to figure out a deallocation story for buckets when they're neither referenced by each other or by an iterator.
I'll probably start with ref counting.

Also, I think I have an implementation that works in the DFG with CSE for Map.get, but still need to emit
lowering code for various DFG nodes in FTL.
Comment 6 Filip Pizlo 2016-08-24 21:56:08 PDT
(In reply to comment #5)
> Created attachment 286940 [details]
> WIP
> 
> Starting to have a hashmap that works in C.
> I still need to figure out a deallocation story for buckets when they're
> neither referenced by each other or by an iterator.
> I'll probably start with ref counting.

Please make them GC cells!

This will mean:
- No destructor or finalizer on JSMap.
- Really fast allocation.  The GC can allocate faster than bmalloc, last I checked.
- No barrier when assigning buckets.
- No problem dealing with cycles if you want doubly-linked lists.

On the other hand, I can't really think of concrete benefits of ref counting buckets.

> 
> Also, I think I have an implementation that works in the DFG with CSE for
> Map.get, but still need to emit
> lowering code for various DFG nodes in FTL.
Comment 7 Saam Barati 2016-08-24 22:57:33 PDT
(In reply to comment #6)
> (In reply to comment #5)
> > Created attachment 286940 [details]
> > WIP
> > 
> > Starting to have a hashmap that works in C.
> > I still need to figure out a deallocation story for buckets when they're
> > neither referenced by each other or by an iterator.
> > I'll probably start with ref counting.
> 
> Please make them GC cells!
> 
> This will mean:
> - No destructor or finalizer on JSMap.
How can I avoid having a destructor if I want to allocate
a slab of memory to hold pointers to buckets? I guess I
could make the slab itself a GC object, but that seems
somewhat weird. Maybe you had something in mind or have
a better idea?

> - Really fast allocation.  The GC can allocate faster than bmalloc, last I
> checked.
> - No barrier when assigning buckets.
> - No problem dealing with cycles if you want doubly-linked lists.
> 
> On the other hand, I can't really think of concrete benefits of ref counting
> buckets.
> 
> > 
> > Also, I think I have an implementation that works in the DFG with CSE for
> > Map.get, but still need to emit
> > lowering code for various DFG nodes in FTL.
Comment 8 Saam Barati 2016-08-25 02:37:11 PDT
Created attachment 286953 [details]
WIP

I think it works in the FTL now.

CSE for hashing and hash table bucket lookups works for code like:
function foo(map, key) {
    if (map.has(key))
        return map.get(key);
}
Comment 9 Geoffrey Garen 2016-08-25 10:01:06 PDT
> How can I avoid having a destructor if I want to allocate
> a slab of memory to hold pointers to buckets? I guess I
> could make the slab itself a GC object, but that seems
> somewhat weird.

Yes, I think that's the suggestion -- similar to JSArray and JSObject butterflies.
Comment 10 Saam Barati 2016-08-25 19:18:21 PDT
Created attachment 287064 [details]
WIP

More is done now.
Comment 11 Filip Pizlo 2016-08-25 20:00:20 PDT
Comment on attachment 287064 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=287064&action=review

> Source/JavaScriptCore/runtime/JSMap.h:35
> +class HashMapBucket : public JSNonFinalObject {

Why not subclass JSCell?  That shaves off one word.

> Source/JavaScriptCore/runtime/JSMap.h:80
> +class HashMapBuffer : public JSNonFinalObject {

Subclass JSCell.

Even better: make the HashMapBuffer a copied-space storage object, like how butterflies, "fast" typed arrays, and the old map's storage work.  In tip-of-tree, copied-space storage allocation is the fastest way to allocate variable-sized stuff.  It even has in-place resizing!

> Source/JavaScriptCore/runtime/JSMap.h:170
> +class HashMapImpl : public JSNonFinalObject {

Ditto.
Comment 12 Filip Pizlo 2016-08-25 20:01:45 PDT
(In reply to comment #7)
> (In reply to comment #6)
> > (In reply to comment #5)
> > > Created attachment 286940 [details]
> > > WIP
> > > 
> > > Starting to have a hashmap that works in C.
> > > I still need to figure out a deallocation story for buckets when they're
> > > neither referenced by each other or by an iterator.
> > > I'll probably start with ref counting.
> > 
> > Please make them GC cells!
> > 
> > This will mean:
> > - No destructor or finalizer on JSMap.
> How can I avoid having a destructor if I want to allocate
> a slab of memory to hold pointers to buckets? I guess I
> could make the slab itself a GC object, but that seems
> somewhat weird. Maybe you had something in mind or have
> a better idea?

I think it makes more sense if you make it a copied space storage allocation.
Comment 13 Saam Barati 2016-08-26 13:54:14 PDT
Created attachment 287143 [details]
WIP

Took into account Fil's suggestions. Now it's just time to start cleaning things up and make a Set::set intrinsic.
I also need to take into account the delete count in the HashMap's load factor and also allow for rehashing to make the
backing store smaller. Also, I need to make sure my patch is spec compliant.
Comment 14 Caio Lima 2016-08-26 23:15:31 PDT
Comment on attachment 287143 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=287143&action=review

> Source/JavaScriptCore/runtime/JSMap.h:239
> +            index = (index + 1) & mask;

If I am not wrong, this logic here is to optimize (index + 1) % m_capacity, right? If yes, We need to assert in any place that  m_capacity is always a power of 2, otherwise this key collision solution can break. Imagine case where m_capacity is 7 (111b) and index is 0 (000b). So, mask is 6 (110b) and (index + 1) & mask => (001b) & (110b) = (000b). It is going to loop forever.
Comment 15 Caio Lima 2016-08-26 23:15:45 PDT
Comment on attachment 287143 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=287143&action=review

> Source/JavaScriptCore/runtime/JSMap.h:239
> +            index = (index + 1) & mask;

If I am not wrong, this logic here is to optimize (index + 1) % m_capacity, right? If yes, We need to assert in any place that  m_capacity is always a power of 2, otherwise this key collision solution can break. Imagine case where m_capacity is 7 (111b) and index is 0 (000b). So, mask is 6 (110b) and (index + 1) & mask => (001b) & (110b) = (000b). It is going to loop forever.
Comment 16 Caio Lima 2016-08-26 23:16:00 PDT
Comment on attachment 287143 [details]
WIP

View in context: https://bugs.webkit.org/attachment.cgi?id=287143&action=review

> Source/JavaScriptCore/runtime/JSMap.h:239
> +            index = (index + 1) & mask;

If I am not wrong, this logic here is to optimize (index + 1) % m_capacity, right? If yes, We need to assert in any place that  m_capacity is always a power of 2, otherwise this key collision solution can break. Imagine case where m_capacity is 7 (111b) and index is 0 (000b). So, mask is 6 (110b) and (index + 1) & mask => (001b) & (110b) = (000b). It is going to loop forever.
Comment 17 Saam Barati 2016-08-27 13:27:22 PDT
(In reply to comment #16)
> Comment on attachment 287143 [details]
> WIP
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=287143&action=review
> 
> > Source/JavaScriptCore/runtime/JSMap.h:239
> > +            index = (index + 1) & mask;
> 
> If I am not wrong, this logic here is to optimize (index + 1) % m_capacity,
> right? If yes, We need to assert in any place that  m_capacity is always a
> power of 2, otherwise this key collision solution can break. Imagine case
> where m_capacity is 7 (111b) and index is 0 (000b). So, mask is 6 (110b) and
> (index + 1) & mask => (001b) & (110b) = (000b). It is going to loop forever.

Yea we always keep m_capacity as a power of two. This is just done
now without assertions. I'll add assertions.
Comment 18 Saam Barati 2016-08-29 20:40:58 PDT
Created attachment 287367 [details]
WIP

WIP, currently I'm sharing an IR node for bot Map.has and Set.has, I need to think if this is sound or not.
I think iteration also may work now w.r.t being spec compliant.
Comment 19 Filip Pizlo 2016-08-29 21:02:45 PDT
(In reply to comment #18)
> Created attachment 287367 [details]
> WIP
> 
> WIP, currently I'm sharing an IR node for bot Map.has and Set.has, I need to
> think if this is sound or not.

It feels right if it's like Has(Set:) and Has(Map:), as in, you're using UseKinds for overloading. That's how UseKinds are meant to be used. 

> I think iteration also may work now w.r.t being spec compliant.
Comment 20 Saam Barati 2016-08-30 17:34:53 PDT
Created attachment 287466 [details]
WIP

I think I'm almost done, just need to clean up the code and go over all of it.
Comment 21 Saam Barati 2016-08-30 20:31:22 PDT
Created attachment 287475 [details]
WIP

more cleanup. Getting close. I need to make 32-bit work too.
Comment 22 Saam Barati 2016-08-31 20:52:54 PDT
Created attachment 287592 [details]
WIP

just stashing this diff here. I still need to write 32-bit implementation.
Comment 23 Saam Barati 2016-09-01 15:00:12 PDT
Created attachment 287687 [details]
WIPP

For EWS
Comment 24 WebKit Commit Bot 2016-09-01 15:01:23 PDT
Attachment 287687 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSMap.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.h:28:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/MapBase.cpp:57:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:52:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSSet.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:36:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/JSMap.cpp:34:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 9 in 52 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 25 Saam Barati 2016-09-01 16:25:28 PDT
Created attachment 287700 [details]
WIP

For EWS round two.
Comment 26 WebKit Commit Bot 2016-09-01 16:26:54 PDT
Attachment 287700 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSMap.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.h:28:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/MapBase.cpp:50:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:52:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSSet.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:36:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/JSMap.cpp:34:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 9 in 60 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 27 Saam Barati 2016-09-01 16:47:35 PDT
Created attachment 287702 [details]
WIP

try EWS again
Comment 28 WebKit Commit Bot 2016-09-01 16:50:56 PDT
Attachment 287702 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/JSMap.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.h:28:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/MapBase.cpp:50:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:52:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSSet.h:29:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:36:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/runtime/JSMap.cpp:34:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 9 in 60 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 29 Saam Barati 2016-09-01 19:23:32 PDT
Created attachment 287714 [details]
patch

I still want to add some micro benchmarks and some tests to make sure we don't CSE across side effects. However, I there is more than enough here to get feedback on.
Comment 30 WebKit Commit Bot 2016-09-01 19:25:23 PDT
Attachment 287714 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/ChangeLog:44:  Line contains tab character.  [whitespace/tab] [5]
ERROR: Source/JavaScriptCore/ChangeLog:45:  Line contains tab character.  [whitespace/tab] [5]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:53:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/ChangeLog:8:  You should remove the 'No new tests' and either add and list tests, or explain why no new tests were possible.  [changelog/nonewtests] [5]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 7 in 62 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 31 Saam Barati 2016-09-01 19:25:59 PDT
Comment on attachment 287714 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=287714&action=review

> PerformanceTests/ES6SampleBench/cli.js:33
> +driver.start(4);

Oops, I'll revert this
Comment 32 Filip Pizlo 2016-09-01 19:27:17 PDT
Comment on attachment 287714 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=287714&action=review

> Source/JavaScriptCore/jit/AssemblyHelpers.cpp:630
> +void AssemblyHelpers::WangsInt64Hash(GPRReg inputAndResult, GPRReg scratch)

I think we would call this wantsInt64Hash.
Comment 33 Saam Barati 2016-09-01 19:58:06 PDT
I have no idea why the linker is unhappy for debug builds, but OK for release builds. I'll look into it. I wonder if the bot just needs to do a clean build.
Comment 34 Yusuke Suzuki 2016-09-01 20:07:36 PDT
(In reply to comment #33)
> I have no idea why the linker is unhappy for debug builds, but OK for
> release builds. I'll look into it. I wonder if the bot just needs to do a
> clean build.

How about putting the decls in the header HashMapImpl.h? (I'm not sure it works.)

template<>
const ClassInfo HashMapBucket<HashMapBucketDataKey>::s_info;

template<>
const ClassInfo HashMapBucket<HashMapBucketDataKeyValue>::s_info;
Comment 35 Saam Barati 2016-09-02 11:08:18 PDT
Created attachment 287782 [details]
patch

I think debug builds now link
Comment 36 WebKit Commit Bot 2016-09-02 11:12:04 PDT
Attachment 287782 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/ChangeLog:44:  Line contains tab character.  [whitespace/tab] [5]
ERROR: Source/JavaScriptCore/ChangeLog:45:  Line contains tab character.  [whitespace/tab] [5]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:53:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/ChangeLog:8:  You should remove the 'No new tests' and either add and list tests, or explain why no new tests were possible.  [changelog/nonewtests] [5]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 7 in 63 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 37 Saam Barati 2016-09-02 12:48:48 PDT
Created attachment 287802 [details]
patch

with tests, and hopefully a gcc build fix
Comment 38 WebKit Commit Bot 2016-09-02 12:51:01 PDT
Attachment 287802 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/ChangeLog:44:  Line contains tab character.  [whitespace/tab] [5]
ERROR: Source/JavaScriptCore/ChangeLog:45:  Line contains tab character.  [whitespace/tab] [5]
ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:53:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/WebCore/ChangeLog:8:  You should remove the 'No new tests' and either add and list tests, or explain why no new tests were possible.  [changelog/nonewtests] [5]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 7 in 73 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 39 Saam Barati 2016-09-02 12:54:10 PDT
Created attachment 287803 [details]
patch

some style fixes
Comment 40 WebKit Commit Bot 2016-09-02 12:56:30 PDT
Attachment 287803 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:53:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 4 in 73 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 41 Saam Barati 2016-09-02 12:59:14 PDT
Some micro benchmarks:
VMs tested:
"og" at /Volumes/Data/WK/a/OpenSource/WebKitBuild/Release/jsc (r205305)
"change" at /Volumes/Data/WK/c/OpenSource/WebKitBuild/Release/jsc (r205305)

Collected 6 samples per benchmark/VM, with 6 VM invocations per benchmark. Emitted a call to gc() between sample
measurements. Used 1 benchmark iteration per VM invocation for warm-up. Used the jsc-specific preciseTime() function to
get microsecond-level timing. Reporting benchmark execution times with 95% confidence intervals in milliseconds.

                                                      og                      change                                      

basic-set                                       6.9067+-0.1796            6.6348+-0.3520          might be 1.0410x faster
dense-set                                    2082.9626+-38.8708    ^   1596.7453+-22.6343       ^ definitely 1.3045x faster
large-map-iteration-with-additions            308.2448+-15.6168    ^    279.8445+-4.0339        ^ definitely 1.1015x faster
large-map-iteration-with-mutation             177.1968+-4.2966     ^    157.2736+-7.0407        ^ definitely 1.1267x faster
large-map-iteration                            80.3809+-2.4450           79.1232+-4.3281          might be 1.0159x faster
map-for-each                                    4.6429+-0.4713            4.5304+-0.5044          might be 1.0248x faster
map-for-of                                     15.2826+-0.6587           14.3674+-0.6863          might be 1.0637x faster
map-has-get-cse-opportunity                   211.6554+-3.2528     ^     76.0506+-2.1236        ^ definitely 2.7831x faster
set-for-each                                    3.4934+-0.1058     ?      3.5638+-0.1159        ? might be 1.0201x slower
set-for-of                                      6.6213+-0.3864            6.5081+-0.2273          might be 1.0174x faster
sparse-set                                    122.7255+-1.9305     ^     57.1973+-0.3118        ^ definitely 2.1457x faster
Comment 42 Saam Barati 2016-09-02 12:59:32 PDT
ES6 Sample bench is also 8-10% progressed with my patch.
Comment 43 Darin Adler 2016-09-03 08:05:55 PDT
Comment on attachment 287803 [details]
patch

Windows build failures:

JSMap.obj : error LNK2019: unresolved external symbol "public: int __thiscall JSC::Structure::get(class JSC::VM &,class JSC::PropertyName,unsigned int &)" (?get@Structure@JSC@@QAEHAAVVM@2@VPropertyName@2@AAI@Z) referenced in function "public: static bool __cdecl JSC::JSObject::getOwnPropertySlot(class JSC::JSObject *,class JSC::ExecState *,class JSC::PropertyName,class JSC::PropertySlot &)" (?getOwnPropertySlot@JSObject@JSC@@SA_NPAV12@PAVExecState@2@VPropertyName@2@AAVPropertySlot@2@@Z) [C:\cygwin\home\buildbot\WebKit\WebKitBuild\Release\Source\JavaScriptCore\JavaScriptCore.vcxproj]
JSSet.obj : error LNK2001: unresolved external symbol "public: int __thiscall JSC::Structure::get(class JSC::VM &,class JSC::PropertyName,unsigned int &)" (?get@Structure@JSC@@QAEHAAVVM@2@VPropertyName@2@AAI@Z) [C:\cygwin\home\buildbot\WebKit\WebKitBuild\Release\Source\JavaScriptCore\JavaScriptCore.vcxproj]
Comment 44 Saam Barati 2016-09-06 10:36:49 PDT
(In reply to comment #43)
> Comment on attachment 287803 [details]
> patch
> 
> Windows build failures:
> 
> JSMap.obj : error LNK2019: unresolved external symbol "public: int
> __thiscall JSC::Structure::get(class JSC::VM &,class
> JSC::PropertyName,unsigned int &)"
> (?get@Structure@JSC@@QAEHAAVVM@2@VPropertyName@2@AAI@Z) referenced in
> function "public: static bool __cdecl
> JSC::JSObject::getOwnPropertySlot(class JSC::JSObject *,class JSC::ExecState
> *,class JSC::PropertyName,class JSC::PropertySlot &)"
> (?getOwnPropertySlot@JSObject@JSC@@SA_NPAV12@PAVExecState@2@VPropertyName@2@A
> AVPropertySlot@2@@Z)
> [C:
> \cygwin\home\buildbot\WebKit\WebKitBuild\Release\Source\JavaScriptCore\JavaSc
> riptCore.vcxproj]
> JSSet.obj : error LNK2001: unresolved external symbol "public: int
> __thiscall JSC::Structure::get(class JSC::VM &,class
> JSC::PropertyName,unsigned int &)"
> (?get@Structure@JSC@@QAEHAAVVM@2@VPropertyName@2@AAI@Z)
> [C:
> \cygwin\home\buildbot\WebKit\WebKitBuild\Release\Source\JavaScriptCore\JavaSc
> riptCore.vcxproj]

I'll look into this now.
Comment 45 Filip Pizlo 2016-09-06 10:45:27 PDT
Comment on attachment 287803 [details]
patch

View in context: https://bugs.webkit.org/attachment.cgi?id=287803&action=review

> Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:6477
> +        LValue map;

I would say:

LBasicBlock lastNext = m_out.insertNewBlocksBefore(loopStart);

Here, and then remove the assignment to lastNext below.  This ensures that if lowMapObject(), lowSetObject(), lowJSValue(), or any of the other things you do between here and the jump will insert their basic blocks before loopStart rather than after continuation.

> Source/JavaScriptCore/runtime/HashMapImpl.cpp:31
> +#include "SlotVisitorInlines.h"

Why not JSCInlines.h?

> Source/JavaScriptCore/runtime/HashMapImpl.h:28
> +#include "JSCJSValueInlines.h"

Why not JSCInlines.h?
Comment 46 Saam Barati 2016-09-06 12:42:22 PDT
Created attachment 288038 [details]
patch for landing
Comment 47 Saam Barati 2016-09-06 12:43:02 PDT
I'm letting EWS run. Hopefully windows now builds with an include I added. We shall see.
Comment 48 WebKit Commit Bot 2016-09-06 12:45:47 PDT
Attachment 288038 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/runtime/HashMapImpl.cpp:52:  Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons.  [readability/comparison_to_zero] [5]
ERROR: Source/JavaScriptCore/runtime/JSCJSValue.h:610:  The parameter name "a" adds no information, so it should be removed.  [readability/parameter_name] [5]
ERROR: Source/JavaScriptCore/bytecode/SpeculatedType.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
ERROR: Source/JavaScriptCore/dfg/DFGNodeType.h:392:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 4 in 75 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 49 Saam Barati 2016-09-06 13:31:15 PDT
Looks like windows build failure is related to Filip's previous patch moving TypedArray off of CopiedSpace.
Comment 50 Saam Barati 2016-09-06 13:43:53 PDT
Created attachment 288041 [details]
patch for landing
Comment 51 WebKit Commit Bot 2016-09-06 14:15:26 PDT
Comment on attachment 288041 [details]
patch for landing

Clearing flags on attachment: 288041

Committed r205504: <http://trac.webkit.org/changeset/205504>
Comment 52 WebKit Commit Bot 2016-09-06 14:15:33 PDT
All reviewed patches have been landed.  Closing bug.
Comment 53 WebKit Commit Bot 2016-09-06 14:33:53 PDT
Re-opened since this is blocked by bug 161645
Comment 54 Ryan Haddad 2016-09-06 14:37:59 PDT
(In reply to comment #53)
> Re-opened since this is blocked by bug 161645

Link to iOS device build failure:
https://build.webkit.org/builders/Apple%20iOS%209%20Release%20%28Build%29/builds/7443
Comment 55 Saam Barati 2016-09-06 15:12:14 PDT
(In reply to comment #54)
> (In reply to comment #53)
> > Re-opened since this is blocked by bug 161645
> 
> Link to iOS device build failure:
> https://build.webkit.org/builders/Apple%20iOS%209%20Release%20%28Build%29/
> builds/7443

Looking into this now, thanks.
Comment 56 Saam Barati 2016-09-06 15:52:05 PDT
Created attachment 288057 [details]
patch for landing
Comment 57 WebKit Commit Bot 2016-09-06 16:24:01 PDT
Comment on attachment 288057 [details]
patch for landing

Clearing flags on attachment: 288057

Committed r205520: <http://trac.webkit.org/changeset/205520>
Comment 58 WebKit Commit Bot 2016-09-06 16:24:09 PDT
All reviewed patches have been landed.  Closing bug.
Comment 59 Saam Barati 2016-09-06 16:57:31 PDT
landed 32-bit build fix in:
https://trac.webkit.org/changeset/205523
Comment 60 Filip Pizlo 2016-09-08 09:52:52 PDT
Comment on attachment 288057 [details]
patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=288057&action=review

> Source/JavaScriptCore/runtime/HashMapImpl.h:28


Please don't include *Inlines.h files from other header files.
Comment 61 Filip Pizlo 2016-09-08 09:55:02 PDT
Comment on attachment 288057 [details]
patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=288057&action=review

> Source/JavaScriptCore/runtime/HashMapImpl.h:155
> +        DeferGCForAWhile defer(vm.heap);

This seems really bad.  It means: please ignore the amount of memory I'm allocating for the purpose of deciding if I should GC.

I'm pretty sure you don't want that.
Comment 62 Saam Barati 2016-09-08 10:39:50 PDT
Comment on attachment 288057 [details]
patch for landing

View in context: https://bugs.webkit.org/attachment.cgi?id=288057&action=review

>> Source/JavaScriptCore/runtime/HashMapImpl.h:28
>> +#include "JSCInlines.h"
> 
> Please don't include *Inlines.h files from other header files.

I'll make a HashMapImplInlines.h

>> Source/JavaScriptCore/runtime/HashMapImpl.h:155
>> +        DeferGCForAWhile defer(vm.heap);
> 
> This seems really bad.  It means: please ignore the amount of memory I'm allocating for the purpose of deciding if I should GC.
> 
> I'm pretty sure you don't want that.

I was following the lead of what HashMapData was doing. I think the correct thing to do, is to have a normal
DeferGC in the caller of HashMapBuffer::create(), that way, the HashMapImpl guarantees a GC only happens after
it sets up its pointers in the right places. I don't think we need it to be DeferGCForAWhile
Comment 63 Filip Pizlo 2016-09-08 10:43:06 PDT
(In reply to comment #62)
> Comment on attachment 288057 [details]
> patch for landing
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=288057&action=review
> 
> >> Source/JavaScriptCore/runtime/HashMapImpl.h:28
> >> +#include "JSCInlines.h"
> > 
> > Please don't include *Inlines.h files from other header files.
> 
> I'll make a HashMapImplInlines.h

Would you then make everone who includes HashMapImplInlines.h into an Inlines.h header, too?

It turns out that you can just remove this include.  That's what I did in my CopiedSpace->MarkedSpace patch.

> 
> >> Source/JavaScriptCore/runtime/HashMapImpl.h:155
> >> +        DeferGCForAWhile defer(vm.heap);
> > 
> > This seems really bad.  It means: please ignore the amount of memory I'm allocating for the purpose of deciding if I should GC.
> > 
> > I'm pretty sure you don't want that.
> 
> I was following the lead of what HashMapData was doing. I think the correct
> thing to do, is to have a normal
> DeferGC in the caller of HashMapBuffer::create(), that way, the HashMapImpl
> guarantees a GC only happens after
> it sets up its pointers in the right places. I don't think we need it to be
> DeferGCForAWhile

It turns out that the correct thing to do is to remove DeferGC entirely.

Both Auxiliary MarkedSpace and CopiedSpace are engineered to allow a copied/auxiliary allocation that triggers GCs.  At some point, we started adding a lot of DeferGC's everywhere.  I don't think that was a good idea, because it creates a cargo cult: people think they have to use it but they don't know why.

So, I just removed the DeferGC.