[SR-7632] Initializing an Int Array with 2000 elements takes more than 4 seconds

[swift-ci]

Previous ID	SR-7632
Radar	rdar://problem/29358447
Original Reporter	andreasw (JIRA User)
Type	Bug
Status	Closed
Resolution	Done

Environment

Ubuntu 17.10, Swift 4.1, Dell Latitude

Additional Detail from JIRA

Votes	0
Component/s	Compiler
Labels	Bug
Assignee	andreasw (JIRA)
Priority	Medium

md5: c140d89b8695a1d83b04eca03543c3fc

Issue Description:

Compilation of

let x = [0, 1, 2, 3, ..., 2000]

takes >4 seconds on my laptop.

The same in C++ with clang takes less than 0.2 seconds.

int x[] = {0, 1, 2, 3, ..., 2000}

It gets worse with 5.000 or 20.000 elements, numbers that are not unusual when working with large predefined matrices.

I generated the elements with bash:

seq -s, 2000

[belkadan]

cc @xedin

[swift-ci]

Comment by Andreas Wendleder (JIRA)

The offending functions found with perf:

+ 59,26% 8,09% swift swift [.] (anonymous namespace)::SILVerifier::visitSILInstruction
+ 58,37% 57,89% swift swift [.] swift::DominanceInfo::properlyDominates
+ 45,00% 0,24% swift swift [.] swift::SILInstructionVisitor<(anonymous namespace)::SILVerifier, void>::visit
+ 27,87% 0,02% swift swift [.] (anonymous namespace)::SILVerifier::visitSILBasicBlock
+ 25,01% 6,50% swift swift [.] swift::constraints::ConstraintGraph::gatherConstraints
+ 15,41% 2,21% swift swift [.] swift::constraints::ConstraintGraph::contractEdges
+ 12,22% 1,97% swift swift [.] llvm::SmallPtrSetImpl<swift::TypeVariableType*>::insert
+ 11,17% 6,93% swift swift [.] llvm::SmallPtrSetImplBase::insert_imp_big
+ 5,91% 5,27% swift swift [.] swift::constraints::ConstraintGraph::lookupNode
+ 4,59% 1,07% swift swift [.] swift::constraints::ConstraintSystem::checkTypeOfBinding
+ 4,07% 0,01% swift swift [.] swift::constraints::ConstraintSystem::getPotentialBindings
+ 3,48% 2,96% swift swift [.] llvm::SmallPtrSetImplBase::Grow
+ 0,94% 0,33% swift swift [.] swift::constraints::ConstraintGraphNode::getAdjacency

[swift-ci]

Comment by Andreas Wendleder (JIRA)

perf top from a release build without assertions (which also gets rid of SILVerifier):

18,72% swift [.] swift::constraints::ConstraintGraph::contractEdges()
18,66% swift [.] swift::constraints::ConstraintGraph::gatherConstraints(swift::TypeVariableType*, llvm::SmallVectorImpl<swift::constraints::Constraint*>&, swift::constraints::ConstraintGraph::GatheringKind)
16,38% swift [.] llvm::SmallPtrSetImplBase::Grow(unsigned int)
13,09% swift [.] llvm::SmallPtrSetImplBase::insert_imp_big(void const*)
11,83% swift [.] swift::constraints::ConstraintGraph::lookupNode(swift::TypeVariableType*)
5,54% swift [.] swift::constraints::ConstraintGraphNode::getAdjacency(swift::TypeVariableType*)
4,55% [kernel] [.] 0xffffffffa3400348

[xedin]

I think @rudkx has a couple of ideas how to use Type::join to optimize this. andreasw (JIRA User) meanwhile you can workaround the problem by giving array explicit contextual type.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

I tried

let x: Array<Int> = [ Int(1), Int(2), ..., Int(2000) ]

which is not better (~30s). Or do you think of something else?

[swift-ci]

Comment by Andreas Wendleder (JIRA)

After reading https://forums.swift.org/t/proposal-t-literal-should-construct-t-using-the-appropriate-literal-protocol-if-possible/2861

I tried:

let x: Array<Int> = [1 as Int, 2 as Int, ..., 2000 as Int]

which takes 0,3s which is much better. With 5.000 elements it is 1,2s, for 10.000 4,4s, for my matrix size of 50.000 it is 1m58s which is still not acceptable.

[rudkx]

I believe we have quadratic or worse behavior in the constraint graph edge contraction pass, which is showing up in these cases with large numbers of elements in a statically initialized array.

[rudkx]

There is definitely extra work happening in edge contraction, but that doesn't account for all the slowness here.

[xedin]

andreasw (JIRA User) problem with both Int(X) and 1 as Int is that creates disjunctions first for initializer overrides and latter for conversion (which is easily bound so that's what there is a big different between the two), could you try let x: [Int] = [1, 2, 3, 4, ...] as well that supposed to be a more linear case?

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Timings for let x: [Int] = [1, 2, 3, ..., x]

Elements	Time
1.000	0.163s
2.000	0.321s
5.000	1.465s
10.000	6.445s
20.000	28.713s
50.000	3m22.698s

Still unusable for my 50.000 element matrix. 🙁

This is a self-compiled swift with --release --no-assertions flags, otherwise it would be worse because of the SILVerifier.

The offending functions recorded with perf are:

+ 94,42% 18,36% swift swift [.] swift::constraints::ConstraintGraph::contractEdges
+ 76,45% 28,30% swift swift [.] swift::constraints::ConstraintGraph::gatherConstraints
+ 34,99% 19,50% swift swift [.] llvm::SmallPtrSetImplBase::insert_imp_big
+ 15,41% 13,66% swift swift [.] llvm::SmallPtrSetImplBase::Grow

[xedin]

Very interesting, @rudkx has an idea how to make contractEdges less expensive, because it doesn't have to iterate over type variables and gather constraints every time, instead it can iterate over constraints directly, so let's see, maybe there is an easy fix in here for this.

[xedin]

andreasw (JIRA User) I have PR for this if you want to give it a try - #16560

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Much better! I would say it's usable now, but still far from clang.

Elements	Time swiftc	Time clang
1.000	0.128s	0.150s
2.000	0.166s	0.150s
5.000	0.337s	0.152s
10.000	0.794s	0.157s
20.000	2.006s	0.172s
50.000	9.632s	0.205s

Numbers generated with:

echo "let x: [Int] = [" > linear.swift; seq -s, 1000 >> linear.swift; echo "]" >> linear.swift ; time swiftc linear.swift

echo -e "#include <vector>nstd::vector<int> x{" > linear.cc; seq -s, 1000 >> linear.cc; echo "};" >> linear.cc ; time clang -c linear.cc

Thanks very much.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

And for the sake of completeness the offending functions now:

+ 64,31% 64,17% swift swift [.] llvm::StringRef::find_last_of
+ 63,71% 0,07% swift swift [.] swift::Lowering::SILGenFunction::emitApply
+ 63,24% 0,01% swift swift [.] swift::SILLocation::decode
+ 63,19% 0,03% swift swift [.] llvm::SourceMgr::getLineAndColumn
+ 10,04% 0,17% swift swift [.] swift::ConstantFolder::processWorkList
+ 9,70% 0,06% swift swift [.] swift::recursivelyDeleteTriviallyDeadInstructions

[swift-ci]

Comment by Andreas Wendleder (JIRA)

This can be brought down to

Elements	Time
50.000	3.306s

when each element is written to its own line with

echo "let x: [Int] = [" > linear.swift; for i in $(seq 50000); do echo -e $i,; done >> linear.swift; echo "]" >> linear.swift ; time swiftc linear.swift

which means that the Source Manager is doing some redundant work while trying to find a newline for each element.

Maybe the Line Number Cache in SourceMgr helps.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Offending functions after that:

+ 29,14% 0,17% swift swift [.] swift::recursivelyDeleteTriviallyDeadInstructions
+ 27,86% 0,51% swift swift [.] swift::ConstantFolder::processWorkList
+ 27,58% 27,27% swift swift [.] llvm::SetVector<swift::SILInstruction*, std::vector<swift::SILInstruction*, std::allocator<swift::SILInstruction
+ 27,35% 0,04% swift swift [.] llvm::function_ref<void (swift::SILInstruction*)>::callback_fn<swift::ConstantFolder::processWorkList()::$_4>
+ 22,87% 0,00% swift swift [.] (anonymous namespace)::ConstantPropagation::run

[xedin]

Interesting, I think we need to CC performance people @eeckstein [email protected] (JIRA User) @bob-wilson

[swift-ci]

Comment by Andreas Wendleder (JIRA)

And for an array of Doubles:

echo "let x: [Double] = [" > linear.swift; for i in $(LANG=C seq -f%f 50000); do echo -e $i,; done >> linear.swift; echo "]" >> linear.swift ; time swiftc linear.swift

Elements	Time
50.000	29.746s

+ 62,20% 0,00% ld.gold x86_64-linux-gnu-ld.gold [.] 0xffffaa64f1ea9d69
+ 38,47% 0,00% ld.gold x86_64-linux-gnu-ld.gold [.] 0xffffaa64f1ead472
+ 28,58% 28,44% swift swift [.] llvm::MachineConstantPool::getConstantPoolIndex
+ 27,79% 0,11% swift swift [.] llvm::SelectionDAGISel::SelectAllBasicBlocks
+ 27,65% 0,01% swift swift [.] llvm::FastISel::selectInstruction
+ 27,64% 0,03% swift swift [.] (anonymous namespace)::X86FastISel::fastSelectInstruction
+ 27,47% 0,01% swift swift [.] (anonymous namespace)::X86FastISel::X86FastEmitStore
+ 27,42% 0,00% ld.gold x86_64-linux-gnu-ld.gold [.] 0xffffaa64f1ea9760
+ 27,37% 0,01% swift swift [.] llvm::FastISel::getRegForValue
+ 27,34% 0,02% swift swift [.] llvm::FastISel::materializeRegForValue

[swift-ci]

Comment by Andreas Wendleder (JIRA)

FWIW, I can throw arrays like that at clang++ and g++ as int, float and double, and even initialize a double array with 50.000 integer literals, and compile time always stays around 0.3s. That is what I would be expecting.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

And the original test without an explicit type is slower, too:

echo "let x = [" > linear.swift; seq -s, 10000 >> linear.swift; echo "]" >> linear.swift ; time swiftc linear.swift

Elements	Time
10.000	8.404s

+ 72,90% 0,06% swift swift [.] swift::constraints::ConstraintSystem::getPotentialBindings
+ 72,82% 16,13% swift swift [.] swift::constraints::ConstraintSystem::checkTypeOfBinding
+ 72,71% 0,03% swift swift [.] swift::constraints::ConstraintSystem::getPotentialBindingForRelationalConstraint
+ 69,35% 25,00% swift swift [.] swift::constraints::ConstraintGraph::gatherConstraints
+ 38,98% 24,39% swift swift [.] llvm::SmallPtrSetImplBase::insert_imp_big
+ 11,78% 10,42% swift swift [.] llvm::SmallPtrSetImplBase::Grow

[eeckstein]

I tried with an assert build of master and got ~1sec build time (on a good machine).
50% of time is spent in the type checker

[eeckstein]

Pavel's recent type checker change fixed the type checker issue.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Yes, Pavel resolved my first concern.

@eeckstein, You may try an array of 50.000 Doubles (my matrix size). Time on my moderately powered notebook is 40 seconds.

[eeckstein]

We have in fact a quadratic complexity here. It's in the SIL verifier. The verifier does not run in no-assert compiler builds, but I think the linux toolchains contain an assert build.

Without the verifier I got a 10000 element array compiled in 6s (vs 40s). The 6s are spent in the type checker. With an explicit type annotation on the array the time goes down to 0.5s.

There is also some overhead in the optimizer. When compiling with optimizations we spend 10s in the optimizer. This is a separate issue.

Anyway, thanks for reporting!

[xedin]

My changes (#16560 for type-checker got merged into master, should be available in the next nightly snapshot, but since you've ready tried them out I think should could just close this JIRA and open separate one for optimizer performance...

[swift-ci]

Comment by Andreas Wendleder (JIRA)

@xedin, an acknowledgement for spotting the right function (contractEdges) in the commit message would have been nice.

I opened another issue for the problem with the Source Manager. After that I will try an optimised build.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

The problem in contractEdges has been dealt with. I opened another issue for the problem with the Source Manager (#50231)

[xedin]

Sorry about that andreasw (JIRA User), and thanks for helping out with diagnosis!