[SR-7702] SILVerifier ist still very slow with large arrays.

[swift-ci]

Previous ID	SR-7702
Radar	None
Original Reporter	andreasw (JIRA User)
Type	Bug
Status	Reopened
Resolution

Attachment: Download

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Bug
Assignee	@eeckstein
Priority	Medium

md5: 67d071791112b24d8587652a110980c4

Issue Description:

Commit 6529787 by @eeckstein fixed quadratic behaviour in basic blocks for the SILVerifier reported in #50173.

But performance is still under par. For 10.000 Int elements it takes more than 4 seconds and gets unusable for matrix sizes of 50.000 elements.

See attached Makefile.

+ 76,33% 0,54% swift swift [.] swift::SILInstructionVisitor<(anonymous namespace)::SILVerifier, void>::visit
+ 76,11% 73,23% swift swift [.] (anonymous namespace)::SILVerifier::visitSILInstruction
+ 51,63% 0,31% swift swift [.] (anonymous namespace)::SILVerifier::visitSILBasicBlock
+ 14,17% 0,25% swift swift [.] (anonymous namespace)::SILVerifier::visitSILFunction
+ 7,58% 0,00% swift swift [.] swift::SILFunction::verify
+ 7,52% 0,00% swift swift [.] swift::SILModule::verify
+ 6,07% 0,03% swift swift [.] (anonymous namespace)::CallEmission::apply
+ 5,67% 0,03% swift swift [.] swift::Lowering::SILGenFunction::emitApply
+ 5,52% 5,43% swift swift [.] llvm::StringRef::find_last_of
+ 5,41% 0,01% swift swift [.] swift::SILLocation::decode
+ 5,39% 0,01% swift swift [.] llvm::SourceMgr::getLineAndColumn

[swift-ci]

Comment by Andreas Wendleder (JIRA)

It gets worse with Swift 5: 36 seconds for 10.000 elements on macOS 10.14.3 with Xcode 10.2 and Swift 5.0.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

With the latest snapshot from 2019-04-16 it gets a little better:

10.000 elements: 5 seconds.

25.000 elements: 30 seconds.

I tested again because I saw commits 8f47439 and 4e9a9cc from @eeckstein.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.0.1 on Linux: 10.000 elements: 15 seconds.

+ 75,85% 0,04% swift swift [.] runOnFunctionRecursively ◆
+ 75,73% 0,01% swift swift [.] swift::SILInliner::inlineFunction ▒
+ 75,67% 0,02% swift swift [.] swift::SILInlineCloner::cloneInline ▒
+ 74,92% 74,28% swift swift [.] llvm::ilist_traits<swift::SILInstruction>::transferNodesFromList ▒
+ 37,57% 0,01% swift swift [.] swift::mergeBasicBlockWithSuccessor ▒
+ 37,52% 0,00% swift swift [.] swift::mergeBasicBlockWithSingleSuccessor ▒
+ 37,50% 0,03% swift swift [.] swift::SILBasicBlock::split ▒
+ 37,47% 0,03% swift swift [.] swift::SILBasicBlock::spliceAtEnd ▒
+ 20,58% 0,07% swift swift [.] swift::SILFunction::verify ▒
+ 20,35% 0,06% swift swift [.] (anonymous namespace)::SILVerifier::visitSILBasicBlock ▒
+ 20,27% 0,06% swift swift [.] swift::SILInstructionVisitor<(anonymous namespace)::SILVerifier, void>::visit ▒
+ 19,87% 19,16% swift swift [.] (anonymous namespace)::SILVerifier::visitSILInstruction ▒
+ 17,14% 0,00% swift swift [.] swift::SILModule::verify

It seems that the problem with the verifier is gone. Slow inlining remains which is tracked in SR-9223.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.1 macOS, 50.000 elements: 4s. I'm closing this now. Thanks.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

With Swift 5.1 this issue seems to be resolved.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.1.1 on Linux is still not good:

10.000 elements: 3.7s
20.000 elements: 14.4s

Perf trace for 5.000 elements:

+ 68,96% 0,37% swift swift [.] swift::SILFunction::verify
+ 67,38% 0,66% swift swift [.] (anonymous namespace)::SILVerifier::visitSILBasicBlock
+ 66,53% 0,49% swift swift [.] swift::SILInstructionVisitor<(anonymous namespace)::SILVerifier, void>::visit
+ 63,76% 58,92% swift swift [.] (anonymous namespace)::SILVerifier::visitSILInstruction
+ 57,29% 0,00% swift swift [.] swift::SILModule::verify

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.2.4 Linux:

20.000 elements: 17.6s.

[gonsolo]

Swift 5.7 Linux:

20.000 elements: 1.1s.

I think this can be closed, @shahmishal, @eeckstein .

[eeckstein]

Yes, sounds good