Bug 198155 – [WHLSL] checkDuplicateFunctions() should not be O(n^2)

• Status: RESOLVED
• Resolution: FIXED
• Component: WebGPU

[Myles C. Maxfield]

Should be pretty easy to migrate it to using a HashSet.

[Robin Morisset]

Either that or sorting the array with more than just the name.

[Radar WebKit Bug Importer]

<rdar://problem/51288811>

[Saam Barati]

Will fix this. Stealing from Myles.

[Saam Barati]

Created attachment 371371 [details]
patch

[EWS Watchlist]

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

[EWS Watchlist]

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

[Myles C. Maxfield]

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

[Saam Barati]

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.

[Saam Barati]

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.

[Saam Barati]

Created attachment 371407 [details]
patch for landing

[WebKit Commit Bot]

Comment on attachment 371407 [details]
patch for landing

Clearing flags on attachment: 371407

Committed r246115: <https://trac.webkit.org/changeset/246115>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.

[Saam Barati]

Myles informed me this broke some layout tests on a debug build. Going to build and test now.

[Shawn Roberts]

(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

[Saam Barati]

(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