apple / apple/swift-algorithms
permutations(ofCount:) is slow in a debuggable environment
- Dominant language
- Swift
- Stars
- 6.3k
- Forks
- 483
- PR merge metrics
- No merged PRs in 30d
Description
Hi!
TL;DR - `permutations(ofCount:)` is slow in debug builds, taking tens of seconds vs explicit nested for loops taking a fraction of a second. Release builds are fine. Hopefully there's a way to mitigate this problem in debug builds so I can use the algorithm along with being able to use the debugger.
_(also, in retrospect, I am confusing permutations and combinations, so I should have used combination here %-) It works fine in Debug-mode. But the issue still stands of the long time to do the permutation work in debug-land)_
Using version 0.2.1
### Checklist
- [X] If possible, I've reproduced the issue using the `main` branch of this package. _I have not, but notice that there aren't any changes since 0.2.1 was cut_
- [X] I've searched for [existing GitHub issues](https://github.com/apple/swift-algorithms/issues)
### Steps to Reproduce
Attached is a project you can run. Look in ContentView.swift for `aoc1_2` and use the `#if` there to choose between the `permutations` version and one that's nested for loops. Run and click the _Permute_ button to run.
TL;DR:
From AdventOfCode 2020, day 1: https://adventofcode.com/2020/day/1 with a 200 element array. Find the triple of elements in the array that add to 2020, then return their product.
```
for perm in stuff.permutations(ofCount: 3) {
if perm[0] + perm[1] + perm[2] == 2020 {
let solution = perm[0] * perm[1] * perm[2]
print("FOUND IT \(solution)")
break
}
```
### Expected behavior
The permutations runs in amount of time similar to a simple for-loop equivalent
### Actual behavior
In Debug mode, it's two orders of magnitude slower, due of course to Swift's lack of optimizations to enhance debuggability. It'd be nice if it were possible to use this algorithm (maybe others? I haven't investigated any others yet) in a debuggable environment. Right now, waiting 25+ seconds for each edit/run/test/curse cycle is a long time.
In release mode, the times are short enough to where it doesn't impact workflow (outside of not being able to debug things outside of print statements)
Sample project:
[Permutation.zip](https://github.com/apple/swift-algorithms/files/6633806/Permutation.zip)
Instruments profile of a Debug build.
[Permutations-instruments.trace.zip](https://github.com/apple/swift-algorithms/files/6633844/Permutations-instruments.trace.zip) . just a quick glance, a lot of time is spent in memory (nanov2) allocation
My timing results
```
// Xcode 12.2, MacBook Pro (16-inch, 2019), Catalina
// debug mode
// permutations - 22.7 seconds
// for loops - 0.25 seconds
// release mode
// permutations - 0.25 seconds
// for loops - 0.002 seconds
//
// Xcode 13-beta-1, M1 mini, Big Sur.
// debug mode
// permutations - 9.2 seconds
// for loops - 0.113 seconds
// release mode
// permutations - 0.127 seconds
// for loops - 0.001 seconds
```
Contributor guide
Research direction
Start with the reproduction in ContentView.swift, using its #if switch to compare permutations(ofCount:) with the nested-loop version. Review the supplied Instruments profile for allocation hotspots and rerun the listed debug and release timings. Done means the permutation workload no longer has the reported extreme debug-mode slowdown without regressing release behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- swift
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100