Summary: | [WHLSL] checkDuplicateFunctions() should not be O(n^2) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Product: | WebKit | Reporter: | Myles C. Maxfield <mmaxfield> | ||||||||
Component: | WebGPU | Assignee: | 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
Myles C. Maxfield
2019-05-22 21:14:50 PDT
Either that or sorting the array with more than just the name. Will fix this. Stealing from Myles. Created attachment 371371 [details]
patch
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 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 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 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 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. Created attachment 371407 [details]
patch for landing
Comment on attachment 371407 [details] patch for landing Clearing flags on attachment: 371407 Committed r246115: <https://trac.webkit.org/changeset/246115> All reviewed patches have been landed. Closing bug. Myles informed me this broke some layout tests on a debug build. Going to build and test now. (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 (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 |