apple / apple/swift-algorithms

permutations(ofCount:) is slow in a debuggable environment

Open
#150 4 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.