Suboptimal compile times using 5.3.2 compiler

[iainsmith]

While benchmarking a different project, I noticed that the compilation / type checking of StrideCollection.offsetBackward is the bottleneck when building swift-algorithms. On a 2019 8 Core MacBook Pro using Xcode 12.4 a small refactor reduced compiling Stride.swift from 6.5s -> 1s, so that it is no longer the bottleneck in the build graph.

Swift Algorithms version: 0.2.1/ main
Swift version:

Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0

Checklist

• If possible, I've reproduced the issue using the main branch of this package
• I've searched for existing GitHub issues

Steps to Reproduce

• Install and select the 5.3.2 toolchain
• Update package.swift to include debug flags below
• Compile in Xcode and navigate to Stride.swift -> StrideCollection.offsetBackward
• View issues in Xcode
• (Optional) Run xclogparser parse --project swift-algorithms --reporter html to generate the screenshots below
  • https://github.com/MobileNativeFoundation/XCLogParser

targets: [
    .target(
      name: "Algorithms",
      dependencies: [
        .product(name: "RealModule", package: "swift-numerics"),
      ],
      swiftSettings: [.unsafeFlags([
        "-driver-time-compilation",
        "-Xfrontend",
        "-debug-time-compilation",
        "-Xfrontend",
        "-debug-time-function-bodies",
        "-Xfrontend",
        "-debug-time-expression-type-checking",
        "-Xfrontend",
        "-warn-long-function-bodies=500",
        "-Xfrontend",
        "-warn-long-expression-type-checking=500",
      ])]),
    .testTarget(
      name: "SwiftAlgorithmsTests",
      dependencies: ["Algorithms"]),
  ]

Screenshots

Before	After

Proposed fix

-    let distance = i == endIndex
-      ? -((base.count - 1) % stride + 1) + (n - 1) * -stride
-      : n * -stride
+    // We typically use the ternary operator but that stresses out the compiler.
+    // To avoid slow build times for consumers, we use the longhand below.
+    let distance: Int
+    if i == endIndex {
+      distance = -((base.count - 1) % stride + 1) + (n - 1) * -stride
+    } else {
+      distance = n * -stride
+    }

Expected behavior

Users build time shouldn't be unnecessarily impacted by using swift-algorithms.

Actual behavior

Builds for consumers are slower than necessary. As swift-algorithms is likely to be early in a dependency graph, this is likely to affect users overall build times.

[LucianoPAlmeida]

Hum, that is interesting ... can you reproduce this using Swift 5.4 in Xcode 12.5? I just quickly tested and was not able to see this issue.
Also, I believe some time difference should be expected from one to another but huge time diff may not come only from being a ternary expr or an if stmt ... is more that in the if case solver type checks both sides separately and also contextual type (from let distance: Int helps). But my guess in the ternary expr is that the let distance type has to be inferred and solver have to do a bit more work to ensure both sides inferred types match(this last one I'not sure should have an impact on time) but since there is no contextual type, it may cause some more work(overloads to attempt) for +/- operators.

Just for curiosity what happens if you specify a contextual type like

let distance: Int = i == endIndex
      ? -((base.count - 1) % stride + 1) + (n - 1) * -stride
      : n * -stride

Ping @xedin, since I couldn't see on 5.4 maybe this was an issue that was fixed?
Found an old ticket for a similar case on https://bugs.swift.org/browse/SR-1577

[iainsmith]

Hi @LucianoPAlmeida,

Thanks for the quick response. I don't have access to Xcode 12.5, but I've used swiftenv with the benchmark script below to compare results between the 5.3.2 & 5.4 toolchains using swift build

Swift Version	Commit	Average total time
5.4	2327673 (0.2.1)	~5s
5.3.2	2327673 (0.2.1)	~9.5s
5.4	4aab786 (long form)	~5s
5.3.2	4aab786 (long form)	~5s

Adding the type hint didn't show any improvements to the results on 2327673 using either toolchain.

It's great to see this is fixed in 5.4, unfortunately for us we're stuck on an older version of Xcode for a while. From my perspective I'd prefer to get this upstreamed rather than use a fork, but I can understand the case to prefer people to upgrade.

benchmark script

#!/usr/bin/env zsh
# usage ./benchmark.sh {swift-versions e.g: 5.3.2 5.4}

function benchmark() {
    commit=`git rev-parse --short HEAD` # Doesn't account for local changes 
    swift_version=`swift --version | grep -E -o "(\d\.\d?\.?\d)" | head -n 1`
    file_name="${swift_version}-${commit}-time.txt"

    rm -f $file_name
    touch $file_name

    repeat 5 {
        swift package clean && { time swift build >/dev/null ; } 2>> $file_name
    }
    echo "Saved results to ${file_name}"
}

swift_versions=( "$@" )
for version in $swift_versions; do
    echo "Benchmarking $version"
    swiftenv local $version
    benchmark
done

[LucianoPAlmeida]

Awesome, thanks for testing and confirming :)

Adding the type hint didn't show any improvements to the results on 2327673 using either toolchain.

That is interesting, I would expect that to make at least some difference, but right maybe that's related to the problem ...

It's great to see this is fixed in 5.4, unfortunately for us we're stuck on an older version of Xcode for a while. From my perspective I'd prefer to get this upstreamed rather than use a fork, but I can understand the case to prefer people to upgrade.

My comment was more just curious about the type checker issue in itself and what may be going on in the solver in this case, no problem with the changes =]

[iainsmith]

My comment was more just curious about the type checker issue in itself and what may be going on in the solver in this case, no problem with the changes =]

@LucianoPAlmeida thanks for clarifying.