Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SR-6947] DoubleWidth compile time. GenericSignatureBuilder::enumeratePairedRequirements. #49495

Closed
atrick opened this issue Feb 7, 2018 · 8 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself

Comments

@atrick
Copy link
Member

atrick commented Feb 7, 2018

Previous ID SR-6947
Radar rdar://37300852
Original Reporter @atrick
Type Bug
Status Resolved
Resolution Done
Additional Detail from JIRA
Votes 0
Component/s Compiler
Labels Bug
Assignee None
Priority Medium

md5: 205feff3be612eca85bed9ad56477f1e

Issue Description:

Adding the DoubleWidth benchmark broke the benchmark suite for practical purposes.
It should take under 4 minutes to build the benchmarks. Now it takes closer to 20 minutes.
This five-fold increase is actually much worse on machines with more
cores, so this is also our draining our CI. I'll need to disable the benchmark for now.

You can reproduce the compile time bug with this tiny 20 line program that takes over 15 minutes to compile:

private typealias Int128 = DoubleWidth<Int64>
private typealias Int256 = DoubleWidth<Int128>
private typealias Int512 = DoubleWidth<Int256>
private typealias Int1024 = DoubleWidth<Int512>

public func foo() {
var sum = 0
let (q, r) =
(Int128(Int64.max) * 16)
.quotientAndRemainder(dividingBy: numericCast(16))
sum += Int(q * r)

let x =
DoubleWidth<DoubleWidth<DoubleWidth<Int8>>>(
Int64.max / numericCast(4))
let y = DoubleWidth<DoubleWidth<Int8>>(Int32.max)

let xx = Int1024(x)
let yy = Int512(y)
let (q3, r3) = yy.dividingFullWidth((xx.high, xx.low))
sum -= Int(q3 - r3)
}

Almost all the time appears to be spent in
`swift::GenericSignature::enumeratePairedRequirements(llvm::function_ref<bool (swift::Type, llvm::ArrayRef<swift::Requirement>)>)` const

Note that there is also an an extreme amount of specialization happenening, but that's the intention of the DoubleWidth API. Disabling specialization would actually break the API's contract. If the specialization is a problem, then we really have a stdlib bug and
DoubleWidth should be not be shipped as-is.

@atrick
Copy link
Member Author

atrick commented Feb 7, 2018

There are actually multiple compile-time problems here, and potentially an issue with exposing a stdlib type like this in the first place.

@DougGregor, I have a radar for the GenericSignatureBuilder here. Obviously we either need to cache something or a faster implementation.

<rdar://problem/37300852> SR-6947 DoubleWidth compile time. GenericSignatureBuilder::(enumeratePairedRequirements.

@eeckstein has a separate radar for the code size problem.

astmus (JIRA User) is following the introduction of this type in the stdlib. I don't think it should be exposed to users until we know that the compiler problems can be fixed.

@DougGregor
Copy link
Member

Minor historical note: the pulled DoubleWidth out of Swift 4.1 due to code-size problems, so despite having been in the tree for a long time, we haven't shipped it.

@benrimmington
Copy link
Collaborator

Maksym Moisieiev is following the introduction of this type in the stdlib.

Should that be @moiseev?

@atrick
Copy link
Member Author

atrick commented Feb 7, 2018

@benrimmington Yes, thanks. I autocompleted "mois".

@moiseev
Copy link
Mannequin

moiseev mannequin commented Feb 7, 2018

/cc @natecook1000 and @xwu

@xwu
Copy link
Collaborator

xwu commented Feb 8, 2018

🙁

I apologize for blowing up CI. The benchmark has served its initial purpose in showing that revisions to the division algorithm produce a 700% boost in optimized runtime performance. Now, I guess, it's a test case for compiler performance.

Without particular experience in the area, I have to wonder if this is only the first example (because we have a standard library type designed that way) of potentially pathological behavior arising from conditional conformance and recursive generic parameters in the context of complex protocol hierarchies–i.e., something that can arise in user code and not something truly unique to `DoubleWidth`.

In the meantime, one thought is whether, at least with respect to compile-time problems, we could ship a slightly limited `DoubleWidth` that supports only non-`DoubleWidth` base integer types (i.e., `DoubleWidth<Base> where Base : _BasicFixedWidthInteger`) instead of keeping the type hidden for yet another release.

@atrick
Copy link
Member Author

atrick commented Feb 8, 2018

There's no reason to think the compiler problems are specific to DoubleWidth. It's just that the stdlib should not vend a type that we know isn't going to be well supported in the compiler. And I want that support to be a complete long-term rethink of the design, not a few partial short-term workarounds.

If we can ship the same functionality without recursive generic parameters, that would be great. We would be much better positioned in the future if it turns out that we can't compile the recursive generic case as efficiently.

@slavapestov
Copy link
Member

It looks like this performance issue was fixed a while ago; I added Andy's code to test/Prototypes/DoubleWidth.swift.gyb and built it with -O -Xllvm -sil-partial-specialization -Xllvm -sil-inline-generics. We spend very little time in the GSB or the requirement machine, respectively, when the requirement machine is off and on.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself
Projects
None yet
Development

No branches or pull requests

5 participants