Why is Swift so slow (timeout) in compiling this code?

gonsolo · November 12, 2022, 5:19pm

I filed a number of bugs some time ago about this issue:

In particular (some are somewhat fixed):

github.com/apple/swift

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

opened 05:37PM - 16 May 18 UTC

swift-ci

bug performance compiler optimized only SILOptimizer literals swift 5.8 expressions

| | | |------------------|-----------------…| |Previous ID | SR-7703 | |Radar | rdar://problem/40334734 | |Original Reporter | andreasw (JIRA User) | |Type | Bug | Attachment: [Download](https://user-images.githubusercontent.com/2727770/164962726-609178e9-916e-4761-be6e-6ef7b1f089ec.gz) <details> <summary>Additional Detail from JIRA</summary> | | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Bug | |Assignee | @eeckstein | |Priority | Medium | md5: a9f53d8799e79775521d84b544cb5974 </details> **is duplicated by**: * #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▒ ```

github.com/apple/swift

[SR-9223] Inliner exhibits slow compilation time with a large static array

opened 09:30AM - 12 Nov 18 UTC

closed 10:52PM - 03 May 23 UTC

swift-ci

bug duplicate performance compiler optimized only SILOptimizer literals swift 5.8 expressions

| | | |------------------|-----------------…| |Previous ID | SR-9223 | |Radar | None | |Original Reporter | andreasw (JIRA User) | |Type | Bug | |Status | Reopened | |Resolution | | Attachment: [Download](https://user-images.githubusercontent.com/2727770/164963023-2032c98f-d613-4230-ae5b-06cc8bd3b766.gz) <details> <summary>Environment</summary> <a href="Makefile" class="attachment">Makefile</a> </details> <details> <summary>Additional Detail from JIRA</summary> | | | |------------------|-----------------| |Votes | 0 | |Component/s | | |Labels | Bug | |Assignee | @atrick | |Priority | Medium | md5: c44b8d1ce0417361133fc33640032956 </details> **Issue Description:** Hi! Please see the attached Makefile and perf report. This time it's the inliner (and verifier). With 5.000 elements compiling takes less than 3 seconds, with 10.000 more than 15, with 15.000 37 seconds. It seems that commit bd28b0ea1b6ab1e981e1e591e10c42d5adcf71af (SILCloner and SILInliner rewrite) is the culprit. ``` + 71,47% 0,06% swift swift [.] runOnFunctionRecursively ◆ + 71,29% 0,01% swift swift [.] swift::SILInliner::inlineFunction ▒ + 71,22% 0,02% swift swift [.] swift::SILInlineCloner::cloneInline ▒ - 70,39% 70,19% swift swift [.] llvm::ilist_traits<swift::SILInstruction>::transferNodesFromList ▒ 70,19% runOnFunctionRecursively ▒ swift::SILInliner::inlineFunction ▒ + swift::SILInlineCloner::cloneInline ▒ + 35,74% 0,01% swift swift [.] swift::mergeBasicBlockWithSuccessor ▒ + 35,69% 0,01% swift swift [.] swift::mergeBasicBlockWithSingleSuccessor ▒ + 35,63% 0,03% swift swift [.] swift::SILBasicBlock::spliceAtEnd ▒ + 34,80% 0,04% swift swift [.] swift::SILBasicBlock::split ▒ + 20,74% 0,04% swift swift [.] swift::SILFunction::verify ▒ + 20,38% 0,26% swift swift [.] (anonymous namespace)::SILVerifier::visitSILBasicBlock ▒ + 20,07% 0,13% swift swift [.] swift::SILInstructionVisitor<(anonymous namespace)::SILVerifier, void>::visit ▒ + 19,46% 18,37% swift swift [.] (anonymous namespace)::SILVerifier::visitSILInstruction ▒ + 17,22% 0,00% swift swift [.] swift::SILModule::verify ``` The functions inlined are from the builtin `UInt` and `Array` classes.

github.com/apple/swift

[SR-9291] SIGSEGV with large array in SILGen

opened 09:20AM - 17 Nov 18 UTC

closed 04:38PM - 26 Apr 23 UTC

swift-ci

bug compiler SILGen crash literals swift 5.1 expressions

| | | |------------------|-----------------…| |Previous ID | SR-9291 | |Radar | rdar://problem/46279391 | |Original Reporter | andreasw (JIRA User) | |Type | Bug | Attachment: [Download](https://user-images.githubusercontent.com/2727770/164963035-2fd77d6b-9cbd-42bd-8d00-6e657896471f.gz) <details> <summary>Environment</summary> Linux with release no-assertions build of swift with the above mentioned patches applied.<a href="Makefile" class="attachment">Makefile</a> </details> <details> <summary>Additional Detail from JIRA</summary> | | | |------------------|-----------------| |Votes | 1 | |Component/s | Compiler | |Labels | Bug, CompilerCrash | |Assignee | None | |Priority | Medium | md5: f3b2ee52855e03d9f071a263a4b97f47 </details> **Issue Description:** I am trying to compile a large array (70.000 elements) with a release no-assertions build. Swift stops with: ``` <unknown>:0: error: unable to execute command: Segmentation fault <unknown>:0: error: compile command failed due to signal 11 (use -v to see invocation) ``` The stack trace is: ``` - thread #1, name = 'swift', stop reason = signal SIGSEGV: invalid address (fault address: 0xffffffffffffff22) - frame #0: 0x0000000000d0c321 swift`(anonymous namespace)::ArgEmitter::emit(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 2017 frame #1: 0x0000000000d0d1b0 swift`(anonymous namespace)::ArgEmitter::emitExpanded(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 816 frame #2: 0x0000000000d0bce0 swift`(anonymous namespace)::ArgEmitter::emit(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 416 frame #3: 0x0000000000d075a0 swift`(anonymous namespace)::ArgEmitter::emitTopLevel(swift::Lowering::ArgumentSource&&, swift::Lowering::AbstractionPattern) + 4656 frame #4: 0x0000000000d156c6 swift`(anonymous namespace)::CallSite::emit(swift::Lowering::SILGenFunction&, swift::Lowering::AbstractionPattern, swift::CanTypeWrapper<swift::SILFunctionType>, (anonymous namespace)::ParamLowering&, llvm::SmallVectorImpl<swift::Lowering::ManagedValue>&, llvm::SmallVectorImpl<(anonymous namespace)::DelayedArgument>&, llvm::Optional<swift::ForeignErrorConvention> const&, swift::ImportAsMemberStatus) && + 710 frame #5: 0x0000000000d15130 swift`(anonymous namespace)::CallEmission::emitArgumentsForNormalApply(swift::CanTypeWrapper<swift::FunctionType>&, swift::Lowering::AbstractionPattern&, swift::CanTypeWrapper<swift::SILFunctionType>, llvm::Optional<swift::ForeignErrorConvention> const&, swift::ImportAsMemberStatus, llvm::SmallVectorImpl<swift::Lowering::ManagedValue>&, llvm::Optional<swift::SILLocation>&, swift::CanTypeWrapper<swift::FunctionType>&) + 1200 frame #6: 0x0000000000d00a42 swift`(anonymous namespace)::CallEmission::apply(swift::Lowering::SGFContext) + 3202 frame #7: 0x0000000000cffd1a swift`swift::Lowering::SILGenFunction::emitApplyExpr(swift::Expr*, swift::Lowering::SGFContext) + 2218 frame #8: 0x0000000000ca8a83 swift`swift::ASTVisitor<(anonymous namespace)::RValueEmitter, swift::Lowering::RValue, void, void, void, void, void, swift::Lowering::SGFContext>::visit(swift::Expr*, swift::Lowering::SGFContext) + 83 frame #9: 0x0000000000caae08 swift`swift::ASTVisitor<(anonymous namespace)::RValueEmitter, swift::Lowering::RValue, void, void, void, void, void, swift::Lowering::SGFContext>::visit(swift::Expr*, swift::Lowering::SGFContext) + 9176 frame #10: 0x0000000000c9eba1 swift`swift::Lowering::SILGenFunction::emitExprInto(swift::Expr*, swift::Lowering::Initialization*, llvm::Optional<swift::SILLocation>) + 289 frame #11: 0x0000000000c93288 swift`swift::Lowering::SILGenFunction::emitPatternBinding(swift::PatternBindingDecl*, unsigned int) + 280 frame #12: 0x0000000000c9333d swift`swift::Lowering::SILGenFunction::visitPatternBindingDecl(swift::PatternBindingDecl*) + 45 frame #13: 0x0000000000c724af swift`swift::Lowering::SILGenModule::visitTopLevelCodeDecl(swift::TopLevelCodeDecl*) + 255 frame #14: 0x0000000000c72b3b swift`swift::Lowering::SILGenModule::emitSourceFile(swift::SourceFile*) + 811 frame #15: 0x0000000000c736d1 swift`swift::SILModule::constructSIL(swift::ModuleDecl*, swift::SILOptions&, swift::FileUnit*) + 273 frame #16: 0x0000000000c73b77 swift`swift::performSILGeneration(swift::FileUnit&, swift::SILOptions&) + 23 frame #17: 0x00000000004ca182 swift`performCompile(swift::CompilerInstance&, swift::CompilerInvocation&, llvm::ArrayRef<char const*>, int&, swift::FrontendObserver*, swift::UnifiedStatsReporter*) + 7410 frame #18: 0x00000000004c77be swift`swift::performFrontend(llvm::ArrayRef<char const*>, char const*, void*, swift::FrontendObserver*) + 3454 frame #19: 0x000000000047f01e swift`main + 670 frame #20: 0x00007ffff73f009b libc.so.6`__libc_start_main(main=(swift`main), argc=13, argv=0x00007fffffffdd88, init=<unavailable>, fini=<unavailable>, rtld_fini=<unavailable>, stack_end=0x00007fffffffdd78) at libc-start.c:308:16 frame #21: 0x000000000047d5aa swift`_start + 42 ``` I applied the two patches from @atrick fixing quadratic behaviour in the inliner: <https://github.com/apple/swift/pull/20630/commits> His comment was: > This is the SILGen assert for the initialization of 70k array elements: > `Assertion failed: (params.size() == labels.size()), function relabelParams, file /s/sown/swift/lib/AST/ASTContext.cpp, line 3784.` > This should be filed as a separate bug against SILGen. Someone may have thought it was ok to use 16 bits for a param index. @slavapestov might be interested since he added this assertion. I used the attached Makefile to generate the source.

github.com/apple/swift

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

opened 04:43PM - 16 May 18 UTC

closed 05:22PM - 04 Oct 22 UTC

swift-ci

bug performance compiler verifier SIL literals swift 5.2 expressions

| | | |------------------|-----------------…| |Previous ID | SR-7702 | |Radar | None | |Original Reporter | andreasw (JIRA User) | |Type | Bug | |Status | Reopened | |Resolution | | Attachment: [Download](https://user-images.githubusercontent.com/2727770/164962725-cfb7e0e8-f7af-40b2-8064-c1c48417de87.gz) <details> <summary>Additional Detail from JIRA</summary> | | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Bug | |Assignee | @eeckstein | |Priority | Medium | md5: 67d071791112b24d8587652a110980c4 </details> **Issue Description:** Commit 652978798467deb3825a6a0678621cadde00097b 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 ```

github.com/apple/swift

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

opened 09:16PM - 13 Nov 18 UTC

closed 01:45AM - 17 Nov 18 UTC

swift-ci

bug duplicate performance compiler optimized only SILOptimizer literals expressions

| | | |------------------|-----------------…| |Previous ID | SR-9235 | |Radar | None | |Original Reporter | andreasw (JIRA User) | |Type | Bug | |Status | Resolved | |Resolution | Duplicate | Attachment: [Download](https://user-images.githubusercontent.com/2727770/164963024-380e93bb-4da0-473b-bc45-7315f3453469.gz) <details> <summary>Environment</summary> <a href="Makefile" class="attachment">Makefile</a> </details> <details> <summary>Additional Detail from JIRA</summary> | | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Bug, Performance | |Assignee | None | |Priority | Medium | md5: 68468fc66829b4d2a218088ed7f66a10 </details> **duplicates**: * #50243 **Issue Description:** A large array with 5.000 or 10.000 elements massively slows down compilation. Here is a Makefile to generate such an array and a stack trace. ``` + 60,00% 0,01% swift swift [.] (anonymous namespace)::RedundantLoadElimination::run ◆ + 51,24% 4,69% swift swift [.] (anonymous namespace)::BlockState::processStoreInst ▒ + 41,50% 26,75% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMapInfo<swift::L▒ + 32,74% 3,33% swift swift [.] swift::LSLocation::isMayAliasLSLocation ▒ + 29,62% 0,15% swift swift [.] swift::LSLocation::enumerateLSLocations ▒ + 29,49% 0,08% swift swift [.] swift::LSLocation::enumerateLSLocation ▒ + 19,92% 0,00% swift swift [.] swift::SILPassManager::runFunctionPasses ▒ + 19,83% 0,01% swift swift [.] swift::SILPassManager::runPassOnFunction ▒ + 19,12% 5,04% swift swift [.] swift::AliasAnalysis::alias ▒ + 14,57% 14,52% swift swift [.] swift::ProjectionPath::computeSubSeqRelation ▒ + 10,29% 10,29% swift swift [.] swift::ProjectionPath::hasNonEmptySymmetricDifference ▒ + 9,06% 0,00% swift swift [.] swift::SILPassManager::execute ▒ + 7,26% 7,26% swift swift [.] swift::ValueEnumerator<swift::ValueBase*, unsigned long>::getIndex ▒ + 6,83% 6,82% swift swift [.] llvm::DenseMapBase<llvm::DenseMap<(anonymous namespace)::AliasKeyTy, swift::AliasAnalysis::AliasResult, ▒ + 5,97% 0,02% swift swift [.] llvm::DenseMapBase<llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMapInfo<swift::L▒ + 5,96% 0,00% swift swift [.] llvm::SmallDenseMap<swift::LSLocation, unsigned int, 32u, llvm::DenseMapInfo<swift::LSLocation>, llvm::d ```

github.com/apple/swift

[ConstraintGraph] Fix `contractEdges` to gather constraints only once

apple:master ← xedin:rdar-29358447

opened 10:16PM - 11 May 18 UTC

xedin

+115 -73

Currently we have this non-optimal behavior in `contractEdges` where for every …type variable it gathers constraints for its whole equivalence class before checking if any are "contractable", instead constraints could be gathered/filtered once which removes a lot of useless work.

You can see the quadratic complexity in this diagram:

It's quite common in rendering to include precomputed arrays:

github.com

mmp/pbrt-v4/blob/b44bc261e52accffc1eb8b0da9a804d38319538d/src/pbrt/util/sobolmatrices.cpp

// pbrt is Copyright(c) 1998-2020 Matt Pharr, Wenzel Jakob, and Greg Humphreys.
// The pbrt source code is licensed under the Apache License, Version 2.0.
// SPDX: Apache-2.0


// Copyright (c) 2012 Leonhard Gruenschloss (leonhard@gruenschloss.org)
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to
// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
// of the Software, and to permit persons to whom the Software is furnished to
// do
// so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

This file has been truncated. show original

I'd be interested in hearing about those. I can think of two:

Read JSON as above. Disadvantages: a) Has to be done every time b) Can't be deployed as a single binary.
Use another language (C, C++). Disadvantage: Clumsy.

Since the bugs are years old I wouldn't bet my hat on it.