[SR-7703] Creating an array with 10.000 elements is slow with optimization.

[swift-ci]

Previous ID	SR-7703
Radar	rdar://problem/40334734
Original Reporter	andreasw (JIRA User)
Type	Bug

Attachment: Download

Additional Detail from JIRA

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

md5: a9f53d8799e79775521d84b544cb5974

is duplicated by:

• [SR-9235] RedundantLoadElimination is slow with a large static array. #51723

Issue Description:

After #50173 and #50231 were fixed, compiling large arrays works fine without optimization, in a non-asserting build where the SILVerifier is disabled (still waiting for #50242).

Switching on -O slows down compilation again. See the attached Makefile how I create an array of 10.000 Int elements. Compiling with -O takes 16 seconds.

Here are the offending functions from perf:

+ 58,96% 0,05% swift swift [.] (anonymous namespace)::RedundantLoadElimination::run ▒
+ 57,33% 2,04% swift swift [.] (anonymous namespace)::BlockState::processStoreInst ▒
+ 50,06% 28,52% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMa▒
+ 32,62% 2,89% swift swift [.] swift::LSLocation::isMayAliasLSLocation ▒
+ 32,01% 0,05% swift swift [.] swift::LSLocation::enumerateLSLocation ▒
+ 31,97% 0,07% swift swift [.] swift::LSLocation::enumerateLSLocations ▒
+ 21,43% 10,09% swift swift [.] swift::LSBase::hasIdenticalProjectionPath ▒
+ 18,76% 4,43% swift swift [.] swift::AliasAnalysis::alias ▒
+ 11,32% 11,25% swift swift [.] swift::ProjectionPath::computeSubSeqRelation ▒
+ 10,97% 10,95% swift swift [.] swift::ProjectionPath::hasNonEmptySymmetricDifference ▒
+ 8,96% 8,95% swift swift [.] swift::ValueEnumerator<swift::ValueBase*, unsigned long>::getIndex ▒
+ 8,49% 0,00% swift swift [.] swift::SILPassManager::runFunctionPasses ▒
+ 8,42% 0,00% swift swift [.] swift::SILPassManager::runPassOnFunction ▒
+ 6,72% 0,01% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMa▒
+ 5,37% 5,36% swift swift [.] llvm::DenseMapBase<llvm::DenseMap<(anonymous namespace)::AliasKeyTy, swift::AliasAnalysis:▒
+ 5,35% 0,00% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMa▒

[dcci]

cc: @eeckstein / @gottesmm

[swift-ci]

Comment by Andreas Wendleder (JIRA)

(Temporarily) Disabling the RedundantLoadElimination pass brings it down to 1.3 seconds.

[gottesmm]

@swift-ci create

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Xcode 7.1 is still unusable with this.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

I put together a nice little diagram showing the quadratic complexity of RLE:

https://docs.google.com/spreadsheets/d/16VakcOYvcwZbmPRLxO_1HcLUwCx0xEVT5mXWYsYnQjY/edit?usp=sharing

It shows that RLE is the worst offender in compile times with large matrices.

In effect, compiling an array with one million elements would take roughly 80 hours with Swift, whereas g++ with optimisation takes less than 4 seconds, and Python compiles and executes it within less than 2 seconds. I attached a new Makefile for C++ and Python.

Inlining is also a problem but this is already addressed in #51712.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

After #51712 was fixed this is the last remaining artefact that exhibits quadratic complexity with large arrays.

Please have a look at https://docs.google.com/spreadsheets/d/16VakcOYvcwZbmPRLxO_1HcLUwCx0xEVT5mXWYsYnQjY/edit#gid=0

I will have more information the next days.

cc @eeckstein @gottesmm trentxintong (JIRA User) @atrick

[swift-ci]

Comment by Andreas Wendleder (JIRA)

This is not a duplicate and not resolved with Swift 5.

Compiling 10.000 elements with optimisation takes 68 seconds on macOS 10.14.3 and Xcode 10.2 with Swift 5.0

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Performance numbers with Xcode 10.2.1 and snapshot 2019-04-16 and 10.000 elements:

Xcode 10.2.1: 35 seconds

Snapshot: 30 seconds.

Commits 4e9a9cc and 8f47439 from @eeckstein seem to help only a little bit.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.0.1 on Linux: 10.000 elements: 14 seconds.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.1 macOS: 10.000 elements: 20 seconds.

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.1.1 Linux: 5.000 elements: 6.9s

Perf trace:

+ 64,64% 0,00% swift swift [.] swift::SILPassManager::runFunctionPasses
+ 64,44% 0,01% swift swift [.] swift::SILPassManager::runPassOnFunction
+ 56,37% 0,08% swift swift [.] (anonymous namespace)::RedundantLoadElimination::run
+ 46,88% 0,00% swift swift [.] swift::SILPassManager::execute
+ 46,34% 0,00% swift swift [.] swift::SILPassManager::executePassPipelinePlan
+ 37,34% 20,76% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm
+ 37,20% 1,50% swift swift [.] (anonymous namespace)::BlockState::processStoreInst
+ 26,81% 0,11% swift swift [.] swift::LSLocation::enumerateLSLocations
+ 26,69% 0,04% swift swift [.] swift::LSLocation::enumerateLSLocation
+ 24,84% 0,03% swift swift [.] (anonymous namespace)::DeadStoreElimination::run
+ 23,47% 1,41% swift swift [.] swift::LSLocation::isMayAliasLSLocation
+ 20,78% 4,16% swift swift [.] swift::AliasAnalysis::alias
+ 17,86% 0,03% swift swift [.] (anonymous namespace)::DSEContext::processInstruction
+ 17,47% 7,85% swift swift [.] swift::LSBase::hasIdenticalProjectionPath
+ 11,56% 0,53% swift swift [.] (anonymous namespace)::DSEContext::processStoreInst
+ 10,50% 10,48% swift swift [.] swift::ValueEnumerator<swift::ValueBase*, unsigned long>::getIndex
+ 9,59% 9,56% swift swift [.] swift::ProjectionPath::computeSubSeqRelation

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.2.4 Linux:

5.000 elements: 6.2s

10.000 elements: 25.4s

[swift-ci]

Comment by Andreas Wendleder (JIRA)

Swift 5.3.3 Linux:

10.000 elements: 16s

C++ (gcc or clang): 0.04s

Python: 0.04s

[gonsolo]

Swift 5.7 Linux:

10.000 elements:

Swift: 5s
C++ (gcc): 0.028s
C++ (clang): 0.051s
Python: 0.048s

Related bugs:
#51712
#51723
#51762

My collection of swift bugs (with only these remaining): https://github.com/gonsolo/swift_bugs

cc @eeckstein @gottesmm @atrick