Compile time exceeded. Anything wrong?


(Hbucius Smith) #1

Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It is
very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

*best wishes for you *


(Jens Persson) #2

When compiling that from the command line, I get the following (after about
6 seconds):

test.swift:7:18: error: cannot assign through subscript: 'dp' is a 'let'
constant
        dp[0][0] = 0
        ~~ ^
/.../

After fixing that (changing let dp to var dp), it will compile
successfully, still taking a very long time though. This usually means that
some expression(s) in the code happen to be a bit hard on the type checker
(in its current state).
I tried the latest dev snapshot and it is a bit faster, perhaps 3 s instead
of 6.

Anyway, here is a logically equivalent rewrite which will compile faster:

class Solution {
    func rob(nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),
                            count: 2)
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in 1 ..< nums.count {
          let dp_iMinus1_0 = dp[i - 1][0]
          let dp_iMinus1_1 = dp[i - 1][1]
            dp[i][0] = max(dp_iMinus1_0, dp_iMinus1_1)
            dp[i][1] = dp_iMinus1_0 + nums[i]
        }
        return 0
    }
}

···

On Mon, Jun 5, 2017 at 2:32 PM, Hbucius Smith via swift-users < swift-users@swift.org> wrote:

Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It is
very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

*best wishes for you *

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Greg Power) #3

What version of Swift are you using, and what exactly do you mean by 'Xcode cannot stop’? It seems like you might be using an older version of Swift, and have hit upon a compiler bug/performance issue that has since been fixed.

This code fails to compile for me in Swift 3.1:

'let dp' should be 'var dp'

With that fixed, the code takes ~10 seconds to compile (which is much longer than I would expect).

IIRC, the Swift compiler has a hard time with multidimensional arrays (maybe someone else could enlighten us on why that’s the case). Adapting your code to use a single array brings down the compile time to something much more reasonable, although the code becomes somewhat less intuitive:

class Solution {
    
    func rob(nums: [Int]) -> Int {
        
        guard nums.count > 0 else { return 0 }
        
  let stride: Int = 2
        var dp: [Int] = Array.init(repeating: 0, count: nums.count * stride)
        
        dp[0] = 0
        dp[1] = nums[0]
        
        for i in 1 ..< nums.count {
            
            let base = i * stride
            let prevBase = (i - 1) * stride
            dp[base] = max(dp[prevBase], dp[prevBase + 1])
            dp[base + 1] = dp[prevBase] + nums[i]
            
        }
        
        return 0
        
    }
    
}

If you’re using an older version of Swift and are in a position to update - I’d suggest making the change. Otherwise I’d recommend avoiding multidimensional arrays (if possible).

Greg

···

On 5 Jun 2017, at 10:32 pm, Hbucius Smith via swift-users <swift-users@swift.org> wrote:

Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It is very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count: nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

best wishes for you
_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Geordie J) #4

When compiling that from the command line, I get the following (after about 6 seconds):

test.swift:7:18: error: cannot assign through subscript: 'dp' is a 'let' constant
        dp[0][0] = 0
        ~~ ^
/.../

After fixing that (changing let dp to var dp), it will compile successfully, still taking a very long time though. This usually means that some expression(s) in the code happen to be a bit hard on the type checker (in its current state).
I tried the latest dev snapshot and it is a bit faster, perhaps 3 s instead of 6.

Anyway, here is a logically equivalent rewrite which will compile faster:

class Solution {
    func rob(nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var dp = Array.init(repeating: Array.init(repeating: 0, count: nums.count),
                            count: 2)
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in 1 ..< nums.count {
            let dp_iMinus1_0 = dp[i - 1][0]
            let dp_iMinus1_1 = dp[i - 1][1]
            dp[i][0] = max(dp_iMinus1_0, dp_iMinus1_1)
            dp[i][1] = dp_iMinus1_0 + nums[i]

Just a nitpick: this isn’t functionally equivalent to the original code (dp[i][1] = dp[i][0] + nums[i]), because dp[i][0] might have actually changed on the previous line. But you can return this line to the original version without any effect on the compile time (less than 250ms on my machine).

I think the compile time issue is that max() is a generic function that takes any Comparable, so the type checker seems to go berserk trying to ensure the term is satisfiable.

If you create a non-generic replacement for max in the same file:

private func myMax(_ x1: Int, _ x2: Int) -> Int {
    return (x1 >= x2) ? x1 : x2
}

… and replace the assignment to max(dp[i - 1][0], ……) in the for loop with myMax(dp[i - 1][0], ….)

The compile time will be just as fast as the one that swaps out the internal elements (on my machine it’s actually about 10% faster with the non-generic max).

Regards,
Geordie

···

Am 06.06.2017 um 09:02 schrieb Jens Persson via swift-users <swift-users@swift.org>:

        }
        return 0
    }
}

On Mon, Jun 5, 2017 at 2:32 PM, Hbucius Smith via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It is very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count: nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

best wishes for you

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Geordie J) #5

I doubt it'll be "fixed" in the next release (which came out less than 24
hours ago), but I gather type checker speed optimisations and fixing
crashes are ongoing goals of the compiler team. With no guarantees or
expectations, you may find your code compiles in an acceptable time with
Swift 4 (Xcode 9).

Cheers,
Geordie

···

On Tue 6. Jun 2017 at 12:29, <www.hbu.cn@163.com> wrote:

thanks, guys! dp array should be var, not let, but the compile run too
slow. It indeed a bug. Optimizing the code for the compiling time is
really a headache for coders. I am using the Xcode 8.1. Hoping it can be
fixed in next release.

*best wishes for you *

2017-06-06 8:57 GMT+08:00 Geordie J <geojay@gmail.com>:

Am 06.06.2017 um 09:02 schrieb Jens Persson via swift-users < >> swift-users@swift.org>:

When compiling that from the command line, I get the following (after
about 6 seconds):

test.swift:7:18: error: cannot assign through subscript: 'dp' is a 'let'
constant
        dp[0][0] = 0
        ~~ ^
/.../

After fixing that (changing let dp to var dp), it will compile
successfully, still taking a very long time though. This usually means that
some expression(s) in the code happen to be a bit hard on the type checker
(in its current state).
I tried the latest dev snapshot and it is a bit faster, perhaps 3 s
instead of 6.

Anyway, here is a logically equivalent rewrite which will compile faster:

class Solution {
    func rob(nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),
                            count: 2)
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in 1 ..< nums.count {
          let dp_iMinus1_0 = dp[i - 1][0]
          let dp_iMinus1_1 = dp[i - 1][1]
            dp[i][0] = max(dp_iMinus1_0, dp_iMinus1_1)
            dp[i][1] = dp_iMinus1_0 + nums[i]

Just a nitpick: this isn’t functionally equivalent to the original code
(dp[i][1] = dp[i][0] + nums[i]), because dp[i][0] might have actually
changed on the previous line. But you can return this line to the original
version without any effect on the compile time (less than 250ms on my
machine).

I think the compile time issue is that max() is a generic function that
takes any Comparable, so the type checker seems to go berserk trying to
ensure the term is satisfiable.

If you create a non-generic replacement for max in the same file:

private func myMax(_ x1: Int, _ x2: Int) -> Int {
    return (x1 >= x2) ? x1 : x2
}

… and replace the assignment to *max(dp[i - 1][0], ……)* in the for loop
with *myMax(dp[i - 1][0], ….)*

The compile time will be just as fast as the one that swaps out the
internal elements (on my machine it’s actually about 10% faster with the
non-generic *max*).

Regards,
Geordie

        }
        return 0
    }
}

On Mon, Jun 5, 2017 at 2:32 PM, Hbucius Smith via swift-users < >> swift-users@swift.org> wrote:

Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It
is very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

*best wishes for you *

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


#6

thanks, guys! dp array should be var, not let, but the compile run too
slow. It indeed a bug. Optimizing the code for the compiling time is
really a headache for coders. I am using the Xcode 8.1. Hoping it can be
fixed in next release.

*best wishes for you *

···

2017-06-06 8:57 GMT+08:00 Geordie J <geojay@gmail.com>:

Am 06.06.2017 um 09:02 schrieb Jens Persson via swift-users < > swift-users@swift.org>:

When compiling that from the command line, I get the following (after
about 6 seconds):

test.swift:7:18: error: cannot assign through subscript: 'dp' is a 'let'
constant
        dp[0][0] = 0
        ~~ ^
/.../

After fixing that (changing let dp to var dp), it will compile
successfully, still taking a very long time though. This usually means that
some expression(s) in the code happen to be a bit hard on the type checker
(in its current state).
I tried the latest dev snapshot and it is a bit faster, perhaps 3 s
instead of 6.

Anyway, here is a logically equivalent rewrite which will compile faster:

class Solution {
    func rob(nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),
                            count: 2)
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in 1 ..< nums.count {
          let dp_iMinus1_0 = dp[i - 1][0]
          let dp_iMinus1_1 = dp[i - 1][1]
            dp[i][0] = max(dp_iMinus1_0, dp_iMinus1_1)
            dp[i][1] = dp_iMinus1_0 + nums[i]

Just a nitpick: this isn’t functionally equivalent to the original code
(dp[i][1] = dp[i][0] + nums[i]), because dp[i][0] might have actually
changed on the previous line. But you can return this line to the original
version without any effect on the compile time (less than 250ms on my
machine).

I think the compile time issue is that max() is a generic function that
takes any Comparable, so the type checker seems to go berserk trying to
ensure the term is satisfiable.

If you create a non-generic replacement for max in the same file:

private func myMax(_ x1: Int, _ x2: Int) -> Int {
    return (x1 >= x2) ? x1 : x2
}

… and replace the assignment to *max(dp[i - 1][0], ……)* in the for loop
with *myMax(dp[i - 1][0], ….)*

The compile time will be just as fast as the one that swaps out the
internal elements (on my machine it’s actually about 10% faster with the
non-generic *max*).

Regards,
Geordie

        }
        return 0
    }
}

On Mon, Jun 5, 2017 at 2:32 PM, Hbucius Smith via swift-users < > swift-users@swift.org> wrote:

Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It is
very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

*best wishes for you *

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Jens Persson) #7

You're right that it's not functionally eq, sorry about that.
I filed https://bugs.swift.org/browse/SR-5093 containing a reduced example
program to demonstrate the issue..
Haven't tested it with anything later than the 2017-06-02 snapshot.
But it shows that it's not just max that is the problem.
/Jens

···

On Tue, Jun 6, 2017 at 4:51 AM, Geordie Jay <geojay@gmail.com> wrote:

I doubt it'll be "fixed" in the next release (which came out less than 24
hours ago), but I gather type checker speed optimisations and fixing
crashes are ongoing goals of the compiler team. With no guarantees or
expectations, you may find your code compiles in an acceptable time with
Swift 4 (Xcode 9).

Cheers,
Geordie

On Tue 6. Jun 2017 at 12:29, <www.hbu.cn@163.com> wrote:

thanks, guys! dp array should be var, not let, but the compile run too
slow. It indeed a bug. Optimizing the code for the compiling time is
really a headache for coders. I am using the Xcode 8.1. Hoping it can be
fixed in next release.

*best wishes for you *

2017-06-06 8:57 GMT+08:00 Geordie J <geojay@gmail.com>:

Am 06.06.2017 um 09:02 schrieb Jens Persson via swift-users < >>> swift-users@swift.org>:

When compiling that from the command line, I get the following (after
about 6 seconds):

test.swift:7:18: error: cannot assign through subscript: 'dp' is a 'let'
constant
        dp[0][0] = 0
        ~~ ^
/.../

After fixing that (changing let dp to var dp), it will compile
successfully, still taking a very long time though. This usually means that
some expression(s) in the code happen to be a bit hard on the type checker
(in its current state).
I tried the latest dev snapshot and it is a bit faster, perhaps 3 s
instead of 6.

Anyway, here is a logically equivalent rewrite which will compile faster:

class Solution {
    func rob(nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),
                            count: 2)
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in 1 ..< nums.count {
          let dp_iMinus1_0 = dp[i - 1][0]
          let dp_iMinus1_1 = dp[i - 1][1]
            dp[i][0] = max(dp_iMinus1_0, dp_iMinus1_1)
            dp[i][1] = dp_iMinus1_0 + nums[i]

Just a nitpick: this isn’t functionally equivalent to the original code
(dp[i][1] = dp[i][0] + nums[i]), because dp[i][0] might have actually
changed on the previous line. But you can return this line to the original
version without any effect on the compile time (less than 250ms on my
machine).

I think the compile time issue is that max() is a generic function that
takes any Comparable, so the type checker seems to go berserk trying to
ensure the term is satisfiable.

If you create a non-generic replacement for max in the same file:

private func myMax(_ x1: Int, _ x2: Int) -> Int {
    return (x1 >= x2) ? x1 : x2
}

… and replace the assignment to *max(dp[i - 1][0], ……)* in the for loop
with *myMax(dp[i - 1][0], ….)*

The compile time will be just as fast as the one that swaps out the
internal elements (on my machine it’s actually about 10% faster with the
non-generic *max*).

Regards,
Geordie

        }
        return 0
    }
}

On Mon, Jun 5, 2017 at 2:32 PM, Hbucius Smith via swift-users < >>> swift-users@swift.org> wrote:

Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It
is very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count:
nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

*best wishes for you *

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org
https://lists.swift.org/mailman/listinfo/swift-users


(Geordie J) #8

Interesting, I guess it’s anything with multiple possible function overloads then! It looks pretty trivial though to figure out the two components before trying to figure out which function, which should lead to the result in a reasonable time. There must be something else going on. Good work on filing the bug! Hope this gets fixed soon.

Geordie

···

Am 06.06.2017 um 22:49 schrieb Jens Persson <jens@bitcycle.com>:

You're right that it's not functionally eq, sorry about that.
I filed https://bugs.swift.org/browse/SR-5093 containing a reduced example program to demonstrate the issue..
Haven't tested it with anything later than the 2017-06-02 snapshot.
But it shows that it's not just max that is the problem.
/Jens

On Tue, Jun 6, 2017 at 4:51 AM, Geordie Jay <geojay@gmail.com <mailto:geojay@gmail.com>> wrote:
I doubt it'll be "fixed" in the next release (which came out less than 24 hours ago), but I gather type checker speed optimisations and fixing crashes are ongoing goals of the compiler team. With no guarantees or expectations, you may find your code compiles in an acceptable time with Swift 4 (Xcode 9).

Cheers,
Geordie

On Tue 6. Jun 2017 at 12:29, <www.hbu.cn@163.com <mailto:www.hbu.cn@163.com>> wrote:
thanks, guys! dp array should be var, not let, but the compile run too slow. It indeed a bug. Optimizing the code for the compiling time is really a headache for coders. I am using the Xcode 8.1. Hoping it can be fixed in next release.

best wishes for you

2017-06-06 8:57 GMT+08:00 Geordie J <geojay@gmail.com <mailto:geojay@gmail.com>>:

Am 06.06.2017 um 09:02 schrieb Jens Persson via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>>:

When compiling that from the command line, I get the following (after about 6 seconds):

test.swift:7:18: error: cannot assign through subscript: 'dp' is a 'let' constant
        dp[0][0] = 0
        ~~ ^
/.../

After fixing that (changing let dp to var dp), it will compile successfully, still taking a very long time though. This usually means that some expression(s) in the code happen to be a bit hard on the type checker (in its current state).
I tried the latest dev snapshot and it is a bit faster, perhaps 3 s instead of 6.

Anyway, here is a logically equivalent rewrite which will compile faster:

class Solution {
    func rob(nums: [Int]) -> Int {
        guard nums.count > 0 else { return 0 }
        var dp = Array.init(repeating: Array.init(repeating: 0, count: nums.count),
                            count: 2)
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in 1 ..< nums.count {
            let dp_iMinus1_0 = dp[i - 1][0]
            let dp_iMinus1_1 = dp[i - 1][1]
            dp[i][0] = max(dp_iMinus1_0, dp_iMinus1_1)
            dp[i][1] = dp_iMinus1_0 + nums[i]

Just a nitpick: this isn’t functionally equivalent to the original code (dp[i][1] = dp[i][0] + nums[i]), because dp[i][0] might have actually changed on the previous line. But you can return this line to the original version without any effect on the compile time (less than 250ms on my machine).

I think the compile time issue is that max() is a generic function that takes any Comparable, so the type checker seems to go berserk trying to ensure the term is satisfiable.

If you create a non-generic replacement for max in the same file:

private func myMax(_ x1: Int, _ x2: Int) -> Int {
    return (x1 >= x2) ? x1 : x2
}

… and replace the assignment to max(dp[i - 1][0], ……) in the for loop with myMax(dp[i - 1][0], ….)

The compile time will be just as fast as the one that swaps out the internal elements (on my machine it’s actually about 10% faster with the non-generic max).

Regards,
Geordie

        }
        return 0
    }
}

On Mon, Jun 5, 2017 at 2:32 PM, Hbucius Smith via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Hi Swift-Users,

    when I compiled the code, Xcode cannot stop, I do not know why. It is very strange. Can anyone help ? Here is the code. I am using Xcode 8.1

class Solution {

    func rob(nums: [Int]) -> Int {

        guard nums.count > 0 else { return 0 }

        let dp = Array.init(repeating: Array.init(repeating: 0, count: nums.count),

                            count: 2)

        dp[0][0] = 0

        dp[0][1] = nums[0]

        for i in 1 ..< nums.count {

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])

            dp[i][1] = dp[i - 1][0] + nums[i]

        }

        return 0

    }

}

best wishes for you

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users

_______________________________________________
swift-users mailing list
swift-users@swift.org <mailto:swift-users@swift.org>
https://lists.swift.org/mailman/listinfo/swift-users