Swift Array Performance Issue?

Question

I'm not sure if there is an issue or not, so i'm just gonna write it down. I'm developing using swift, xcode 7.2 , on iphone 5s. And calculating execution time using NSDate.timeIntervalSinceReferenceDate()

I created 2 arrays, one with 200,000 elements and one with 20. and try to have random access to their elements. accessing elements on big one is almost 55 times slower! i know its bigger but isn't this O(1) ?

I also tried the same on java and the accessing speed is the same for big and small array.

From CFArrayheader in apple documentation, i found this:

Accessing any value at a particular index in an array is at worst O(log n), but should usually be O(1).

but it think this cant be true based on the numbers i've tested.

I know i didn't make a big test or anything special, but the fact that its not working is really messing with my head! i kinda need this for what i'm working on. and the algorithm is not working on swift and iOS and its working on java and android.

    let bigSize:Int = 200000
    var bigArray = [Int](count:bigSize,repeatedValue:0)

    let smallSize:Int = 20
    var smallArray = [Int](count:smallSize,repeatedValue:0)

    for i in 0..<bigSize
    {
        bigArray[i] = i + 8 * i
    }
    for i in 0..<smallSize
    {
        smallArray[i] = i + 9 * i
    }
    let indexBig = Int(arc4random_uniform(UInt32(bigSize)) % UInt32(bigSize))
    let indexSmall = Int(arc4random_uniform(UInt32(smallSize)) % UInt32(smallSize))

    var a = NSDate.timeIntervalSinceReferenceDate()
    print(bigArray[indexBig])
    var b = NSDate.timeIntervalSinceReferenceDate()
    print(b-a) \\prints 0.000888049602508545
    a = NSDate.timeIntervalSinceReferenceDate()
    print(smallArray[indexSmall])
    b = NSDate.timeIntervalSinceReferenceDate()
    print(b-a) \\prints 6.90221786499023e-05

java : (accessing one element is so fast on java and its on pc, so i access more elements, but same number on both arrays)

    int bigSize = 200000;
    int[] bigArray = new int[bigSize];
    Random rand = new Random();
    int smallSize = 20;
    int[] smallArray = new int[smallSize];
    for(int i = 0;i < bigSize;i++)
        bigArray[i] = i + i * 8;
    for(int i = 0;i < smallSize;i++)
        smallArray[i] = i + i * 8;
    int smallIndex = rand.nextInt(smallSize);
    int bigIndex = rand.nextInt(bigSize);
    int sum = 0;
    long a = System.currentTimeMillis();
    for(int i = 0;i < 10000;i++)
    {
        sum += bigArray[rand.nextInt(bigSize)];
    }
    System.out.println(sum);
    long b = System.currentTimeMillis();
    System.out.println(b-a); //prints 2
    a = System.currentTimeMillis();
    sum = 0;
    for(int i = 0; i < 10000;i++)
    {
        sum += smallArray[rand.nextInt(smallSize)];
    }
    System.out.println(sum);       
    b = System.currentTimeMillis();
    System.out.println(b - a); //prints 1

Answer 1

If you change the order of your two tests, you'll find that the performance is flipped. In short, the first test runs more slowly than the second one, regardless of whether it's the small array or the big one. This is a result of some dynamics of print. If you do a print before you perform the tests, the delay resulting from the first print is eliminated.

A better way to test this would be to create a unit test, which (a) repeats the subscript operator many times; and (b) uses measureBlock to repeat the test a few times to check for standard deviation and the like.

When I do that, I find the access time is indistinguishable, consistent with O(1). This were my unit tests:

let bigSize: Int = 200_000
let smallSize: Int = 20

func testBigArrayPerformance() {
    let size = bigSize

    let array = Array(0 ..< size).map { $0 + 8 * $0 }

    var value = 0

    measureBlock {
        let baseIndex = Int(arc4random_uniform(UInt32(size)))
        for index in 0 ..< 1_000_000 {
            value += array[(baseIndex + index) % size]
        }
    }

    print(value)
    print(array.count)
}

func testSmallArrayPerformance() {
    let size = smallSize

    let array = Array(0 ..< size).map { $0 + 8 * $0 }

    var value = 0

    measureBlock {
        let baseIndex = Int(arc4random_uniform(UInt32(size)))
        for index in 0 ..< 1_000_000 {
            value += array[(baseIndex + index) % size]
        }
    }

    print(value)
    print(array.count)
}

Admittedly, I've added some mathematical operations that change the index (my intent was to make sure the compiler didn't do some radical optimization that removed my attempt to repeat the subscript operation), and the overhead of that mathematical operation will dilute the subscript operator performance difference. But, even when I simplified the index operator, the performance between the two renditions was indistinguishable.