permutations(ofCount:) is slow in a debuggable environment

[markd2]

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

• 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
• I've searched for existing GitHub 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

Instruments profile of a Debug build.
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

[kylemacomber]

I'm seeing a similar discrepancy between debug and release for permutations(ofCount:) on my machine: 20 seconds in debug and 0.2 seconds in release. We should see what we can do to close this gap.

Note: for this specific problem I think combinations(ofCount:) is sufficient and it runs in 0.8 seconds for me in debug and 0.08 in release.

[markd2]

Yep, noticed the combinations thing (it's been sooooo long since my math degree...) after I had hit the problem, did the loops, and moved on before writing the issue %-)

[kylemacomber]

Thanks for taking the time to open the issue!

[yabalaban]

Excuse me for bumping this in 2023, but for those who are interested in the reason behind: performance difference in release/debug is due to generics specialisation optimisation which is a part of the whole module optimisation.