Bug 198155

Summary: [WHLSL] checkDuplicateFunctions() should not be O(n^2)
Product: WebKit Reporter: Myles C. Maxfield <mmaxfield>
Component: WebGPUAssignee: Saam Barati <saam>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, dino, ews-watchlist, jonlee, mmaxfield, rmorisset, saam, sroberts, webkit-bug-importer
Priority: P1 Keywords: InRadar
Version: Other   
Hardware: Unspecified   
OS: Unspecified   
Attachments:
Description Flags
patch
mmaxfield: review+, ews-watchlist: commit-queue-
Archive of layout-test-results from ews211 for win-future
none
patch for landing none

Description Myles C. Maxfield 2019-05-22 21:14:50 PDT
Should be pretty easy to migrate it to using a HashSet.
Comment 1 Robin Morisset 2019-05-23 10:28:56 PDT
Either that or sorting the array with more than just the name.
Comment 2 Radar WebKit Bug Importer 2019-05-30 20:29:28 PDT
<rdar://problem/51288811>
Comment 3 Saam Barati 2019-06-03 16:40:39 PDT
Will fix this. Stealing from Myles.
Comment 4 Saam Barati 2019-06-04 20:32:28 PDT
Created attachment 371371 [details]
patch
Comment 5 EWS Watchlist 2019-06-05 01:02:44 PDT
Comment on attachment 371371 [details]
patch

Attachment 371371 [details] did not pass win-ews (win):
Output: https://webkit-queues.webkit.org/results/12381524

New failing tests:
imported/blink/compositing/layer-creation/iframe-clip-removed.html
Comment 6 EWS Watchlist 2019-06-05 01:02:47 PDT
Created attachment 371381 [details]
Archive of layout-test-results from ews211 for win-future

The attached test failures were seen while running run-webkit-tests on the win-ews.
Bot: ews211  Port: win-future  Platform: CYGWIN_NT-10.0-17763-3.0.5-338.x86_64-x86_64-64bit
Comment 7 Myles C. Maxfield 2019-06-05 06:06:21 PDT
Comment on attachment 371371 [details]
patch

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

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:60
> +        unsigned hash = IntHash<size_t>::hash(m_function->parameters().size());
> +        hash ^= m_function->name().hash();

I thought IntegerHasher was better?

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:68
> +        // Note: We can't take into account return type in this hash function unless
> +        // we're a cast, since we want two functions with different return types,
> +        // but all things else equal, to be "equal" with respect to finding duplicates.
> +        // Casts with different return types are always *not* equal to each other from
> +        // the perspective of duplicate detection.

I'm not sure this comment provides anything that the next two lines don't provide.

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:93
> +        // At this point, we have the same name, and the same parameters. We're only *not* a duplicate now if
> +        // we're a cast with a different return type. If we're not a cast, we're now a duplicate. We don't
> +        // allow overloading of return types. If we're a cast, we're not a duplicate if our return types 
> +        // are different.

Ditto

> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:175
> +        // Native function declarations are never equal to each other. So we don't need
> +        // to add them to the set, because they can't collide with each other. Instead, we
> +        // just check that no user-defined function is a duplicate.

Can we actually enforce this? If Native functions ever do collide, we should know about it. Maybe ASSERT() instead of returning false in this case?

> Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLArrayType.h:69
> +        return WTF::IntHash<unsigned>::hash(m_numElements) ^ m_elementType->hash();

I thought IntegerHasher was better?

> Source/WebCore/Modules/webgpu/WHLSL/AST/WHLSLPointerType.h:63
> +        return this->Base::hash() ^ StringHasher::computeLiteralHash("pointer");

ditto
Comment 8 Saam Barati 2019-06-05 09:16:00 PDT
Comment on attachment 371371 [details]
patch

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

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:60
>> +        hash ^= m_function->name().hash();
> 
> I thought IntegerHasher was better?

Do you mean instead of IntHash or String::hash? IntHash is what we use for something like HashSet<unsigned/size_t/int/intptr/etc>, which uses Wang's int32/int64 hash. I don't think IntegerHashser is a better hash function than that.

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:68
>> +        // the perspective of duplicate detection.
> 
> I'm not sure this comment provides anything that the next two lines don't provide.

Will remove.
Comment 9 Saam Barati 2019-06-05 09:17:31 PDT
Comment on attachment 371371 [details]
patch

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

>> Source/WebCore/Modules/webgpu/WHLSL/WHLSLCheckDuplicateFunctions.cpp:175
>> +        // just check that no user-defined function is a duplicate.
> 
> Can we actually enforce this? If Native functions ever do collide, we should know about it. Maybe ASSERT() instead of returning false in this case?

That's what the ASSERT below does:
if (!ASSERT_DISABLED) ASSERT(add(nativeFunctionDeclaration.get()));

I'm going to remove the !ASSERT_DISABLED part, since that's redundant with just using ASSERT.
Comment 10 Saam Barati 2019-06-05 09:22:11 PDT
Created attachment 371407 [details]
patch for landing
Comment 11 WebKit Commit Bot 2019-06-05 10:40:28 PDT
Comment on attachment 371407 [details]
patch for landing

Clearing flags on attachment: 371407

Committed r246115: <https://trac.webkit.org/changeset/246115>
Comment 12 WebKit Commit Bot 2019-06-05 10:40:29 PDT
All reviewed patches have been landed.  Closing bug.
Comment 13 Saam Barati 2019-06-05 12:51:39 PDT
Myles informed me this broke some layout tests on a debug build. Going to build and test now.
Comment 14 Shawn Roberts 2019-06-05 13:53:42 PDT
(In reply to Saam Barati from comment #13)
> Myles informed me this broke some layout tests on a debug build. Going to
> build and test now.

I was able to verify these 18 fail on Debug, there may be more, it looks like there's been 9-18 webgpu/whlsl tests getting reference mismatches when run after r246115

webgpu/whlsl-arbitrary-vertex-attribute-locations.html
webgpu/whlsl-dereference-pointer-should-type-check.html
webgpu/whlsl-do-while-loop-break.html
webgpu/whlsl-do-while-loop-continue.html
webgpu/whlsl-do-while-loop.html
webgpu/whlsl-dot-expressions.html
webgpu/whlsl-ensure-proper-variable-lifetime-2.html
webgpu/whlsl-ensure-proper-variable-lifetime-3.html
webgpu/whlsl-ensure-proper-variable-lifetime.html
webgpu/whlsl-loops-break.html
webgpu/whlsl-loops-continue.html
webgpu/whlsl-loops.html
webgpu/whlsl-nested-dot-expression-rvalue.html
webgpu/whlsl-nested-loop.html
webgpu/whlsl-return-local-variable.html
webgpu/whlsl-store-to-property-updates-properly.html
webgpu/whlsl-while-loop-break.html
webgpu/whlsl-while-loop-continue.html
Comment 15 Saam Barati 2019-06-05 14:29:46 PDT
(In reply to Shawn Roberts from comment #14)
> (In reply to Saam Barati from comment #13)
> > Myles informed me this broke some layout tests on a debug build. Going to
> > build and test now.
> 
> I was able to verify these 18 fail on Debug, there may be more, it looks
> like there's been 9-18 webgpu/whlsl tests getting reference mismatches when
> run after r246115
> 
> webgpu/whlsl-arbitrary-vertex-attribute-locations.html
> webgpu/whlsl-dereference-pointer-should-type-check.html
> webgpu/whlsl-do-while-loop-break.html
> webgpu/whlsl-do-while-loop-continue.html
> webgpu/whlsl-do-while-loop.html
> webgpu/whlsl-dot-expressions.html
> webgpu/whlsl-ensure-proper-variable-lifetime-2.html
> webgpu/whlsl-ensure-proper-variable-lifetime-3.html
> webgpu/whlsl-ensure-proper-variable-lifetime.html
> webgpu/whlsl-loops-break.html
> webgpu/whlsl-loops-continue.html
> webgpu/whlsl-loops.html
> webgpu/whlsl-nested-dot-expression-rvalue.html
> webgpu/whlsl-nested-loop.html
> webgpu/whlsl-return-local-variable.html
> webgpu/whlsl-store-to-property-updates-properly.html
> webgpu/whlsl-while-loop-break.html
> webgpu/whlsl-while-loop-continue.html

Fixed in:
https://trac.webkit.org/changeset/246128/webkit