Integer vs Boolean array Swift Performance

Question

I tried executing Sieve Of Eratosthenes algorithm using a large Integer array and a large Bool array.

The integer version seems to execute MUCH faster than the boolean one. What is the possible reason for this?

import Foundation

var n : Int = 100000000;

var prime = [Bool](repeating: true, count: n+1)
var p = 2
let start = DispatchTime.now()
while((p*p)<=n)
{
    if(prime[p] == true)
    {
        var i = p*2
        while (i<=n)
        {
            prime[i] = false
            i = i + p
        }
    }
    p = p+1
}
let stop = DispatchTime.now()    
let time = (Double)(stop.uptimeNanoseconds - start.uptimeNanoseconds) / 1000000.0

print("Time = \(time) ms")

Boolean array execution time : 78223.342295 ms

import Foundation

var n : Int = 100000000;

var prime = [Int](repeating: 1, count: n+1)
var p = 2
let start = DispatchTime.now()
while((p*p)<=n)
{
    if(prime[p] == 1)
    {
        var i = p*2
        while (i<=n)
        {
            prime[i] = 0
            i = i + p
        }
    }
    p = p+1
}
let stop = DispatchTime.now()

let time = (Double)(stop.uptimeNanoseconds - start.uptimeNanoseconds) / 1000000.0

print("Time = \(time) ms")

Integer array execution time : 8535.54546 ms

This not relevant, perhaps, but you should never say `if prime[p] == true`. If `prime[p]` is a Bool, it _is_ a condition: `if prime[p]`. — matt, Dec 11 '16 at 17:51
"What is the possible reason for this?" Why not ask Instruments to tell you where the time is being spent? No need to guess (or ask us to do it for you). — matt, Dec 11 '16 at 17:52
Did you compile *both* versions in Release mode (with optimizations)? On my iMac it is approx 950 ms (Bool version) vs 1600 ms (Int version) — Martin R, Dec 11 '16 at 17:59
@MartinR With optimizations the Bool version does perform faster. But why is it not the same case without optimizations? — Goku, Dec 11 '16 at 18:11

score 1 · Answer 1 · answered Dec 11 '16 at 20:22

(A partial answer ...)

As @MartinR mentions in his comments to the question, there is no such major difference between the two cases if you build for release mode (with optimizations); the Bool case is slightly faster due its smaller memory footprint (but equally fast as e.g. UInt8 which has the same footprint).

Running instruments to profile the (non-optimized) debug build, we clearly see that the array element access & assignment is the culprit for the Bool case (an as far as my brief testing has seen; for all types except the integer ones, Int, UInt16, and so on).

We can further ascertain that its not the writing part in particular that yields the overhead, but rather the repeated accessing of the i:th element.

The same explicit read-access tests for an array of integer elements show no such large overhead.

It would almost seem as if the random element access is, for some reason, not working as it should (for non-integer types) when compiling with debug build config.

score 1 · Accepted Answer · edited May 23 '17 at 11:45

TL, DR:

Do not attempt to optimize your code in a Debug build. Always run it through the Profiler. Int was faster then Bool in Debug but the oposite was true when run through the Profiler.
Heap allocation is expensive. Use your memory judiciously. (This question discusses the complications in C, but also applicable to Swift)

Long answer

First, let's refactor your code for easier execution:

func useBoolArray(n: Int) {
    var prime = [Bool](repeating: true, count: n+1)
    var p = 2

    while((p*p)<=n)
    {
        if(prime[p] == true)
        {
            var i = p*2
            while (i<=n)
            {
                prime[i] = false
                i = i + p
            }
        }
        p = p+1
    }
}

func useIntArray(n: Int) {
    var prime = [Int](repeating: 1, count: n+1)
    var p = 2

    while((p*p)<=n)
    {
        if(prime[p] == 1)
        {
            var i = p*2
            while (i<=n)
            {
                prime[i] = 0
                i = i + p
            }
        }
        p = p+1
    }
}

Now, run it in the Debug build:

let count = 100_000_000
let start = DispatchTime.now()

useBoolArray(n: count)
let boolStop = DispatchTime.now()

useIntArray(n: count)
let intStop = DispatchTime.now()

print("Bool array:", Double(boolStop.uptimeNanoseconds - start.uptimeNanoseconds) / Double(NSEC_PER_SEC))
print("Int array:", Double(intStop.uptimeNanoseconds - boolStop.uptimeNanoseconds) / Double(NSEC_PER_SEC))

// Bool array: 70.097249517
// Int array: 8.439799614

So Bool is a lot slower than Int right? Let's run it through the Profiler by pressing Cmd + I and choose the Time Profile template. (Somehow the Profiler wasn't able to separate these functions, probably because they were inlined so I had to run only 1 function per attempt):

let count = 100_000_000
useBoolArray(n: count)
// useIntArray(n: count)

// Bool: 1.15ms
// Int: 2.36ms

Not only they are an order of magnitude faster than Debug but the results are reversed to: Bool is now faster than Int!!! The Profiler doesn't tell us why how so we must go on a witch hunt. Let's check the memory allocation by adding an Allocation instrument:

Ha! Now the differences are laid bare. The Bool array uses only one-eight as much memory as Int array. Swift array uses the same internals as NSArray so it's allocated on the heap and heap allocation is slow.

When you think even more about it: a Bool value only take up 1 bit, an Int takes 64 bits on a 64-bit machine. Swift may have chosen to represent a Bool with a single byte, while an Int takes 8 bytes, hence the memory ratio. In Debug, this difference may have caused all the difference as the runtime must do all kinds of checks to ensure that it's actually dealing with a Bool value so the Bool array method takes significantly longer.

Moral of the lesson: don't optimize your code in Debug mode. It can be misleading!

Integer vs Boolean array Swift Performance

2 Answers2

Long answer