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

I also checked NSArray and NSMutableArray, no enhancement :( — Vahid
– Vahid, Commented Aug 22, 2016 at 5:25
Also, let us know what optimization settings you used. It can affect array performance. — Rob
– Rob, Commented Aug 22, 2016 at 5:43
@Rob i see 3 options here and none of them are helping to increase the performance. (None, Fast, Fast whole modular ...) — Vahid
– Vahid, Commented Aug 22, 2016 at 5:50

Rob · Accepted Answer · 2016-08-22 18:08:13Z

4

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.

edited Aug 22, 2016 at 18:08

answered Aug 22, 2016 at 6:41

Rob

441k74 gold badges851 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

HAS Over a year ago

Ha! That's interesting, do you know why the second test runs a lot faster? Is it the measuring (NSDate) or something different?

Rob Over a year ago

It looks like it might be the first print is spinning something up. If I print("foo") before assigning a, the difference goes away. But that's not a silver bullet, either, as this is a general class of problem when benchmarking, where many little things that can manifest themselves in the same manner, depending upon what the compiler does as well as what is going on behind the scenes with an API. That's why, when doing benchmarks, it's good to vary the order of tests and to repeat the tests many times, so such considerations can be isolated and/or diminished.

invisible squirrel Over a year ago

This reminds me that when I test on device, it takes a few moments for background processes to finish after the app starts up. It causes the UI to be laggy just for a moment initially, after which performance is fine.

Rob Over a year ago

Yeah, when I tested the OP's code, that's the first thing I did (actually, I used dispatch_after, but it's the same idea). That's when I realized that general app startup activity wasn't the problem.

Collectives™ on Stack Overflow

Swift Array Performance Issue?

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related