Execution time ContiguousArray vs Array

No, it doesn't, at least not if the original problem is the same as the one demonstrated by the program in the description of SR-7637. I've tested and verified that this issue remains (in default toolchain of Xcode 10 beta 1, and in development snapshot 2018-06-06).

I guess that you thought the original issue was gone because your new test program is not affected by the original problem, and this is probably because the func is now being passed as a closure (Ah, the predictability of Swift performance!).


Looks to me like they are all about the same (since it's just a single run of each, and the times would probably fluctuate a bit between repeated runs), what do you mean by the problem coming back for lazy?


When I run your program, with a slight modification of wrapping the content of your test function in a for-loop, so that each test is performed more than once (so we can see the fluctuations in time of repeated trials), then there is not much difference between the four cases.

I'm using Xcode 10 beta 1 (and -O / release build, -swift-version 4.2), and I've tried both the default toolchain and the most recent dev snapshot. See the exact results in Details.

Note that I included the results of a debug build at the end, as that's the only way I can see a significant slow down for the lazy ones compared to the others. (But all four are between 30 and 90 times slower than in a release build.)

Details

The modification I did to your code:

func test(_ name: String, _ storageType: String, _ function: (Int) -> [Int]) {
    for _ in 0 ..< 5 { // <-- I added this
        let start = Date()
        let result = function(1_000_000)
        let end = Date()
        print("\(name) \(storageType) biggest: \(result.last ?? 0) time: \(end.timeIntervalSince(start))")
    }
}

With default toolchain of Xcode 10 beta 1, release build:

for    Array           biggest: 999983 time: 0.013331055641174316
for    Array           biggest: 999983 time: 0.012892007827758789
for    Array           biggest: 999983 time: 0.011870980262756348
for    Array           biggest: 999983 time: 0.011000990867614746
for    Array           biggest: 999983 time: 0.010987043380737305
for    ContiguousArray biggest: 999983 time: 0.012047052383422852
for    ContiguousArray biggest: 999983 time: 0.011559009552001953
for    ContiguousArray biggest: 999983 time: 0.011247992515563965
for    ContiguousArray biggest: 999983 time: 0.010803937911987305
for    ContiguousArray biggest: 999983 time: 0.010781049728393555
lazy   Array           biggest: 999983 time: 0.011129975318908691
lazy   Array           biggest: 999983 time: 0.011131048202514648
lazy   Array           biggest: 999983 time: 0.010547995567321777
lazy   Array           biggest: 999983 time: 0.010286927223205566
lazy   Array           biggest: 999983 time: 0.010206937789916992
lazy   ContiguousArray biggest: 999983 time: 0.010246038436889648
lazy   ContiguousArray biggest: 999983 time: 0.010326981544494629
lazy   ContiguousArray biggest: 999983 time: 0.010244965553283691
lazy   ContiguousArray biggest: 999983 time: 0.011294007301330566
lazy   ContiguousArray biggest: 999983 time: 0.010947942733764648

With Development Snapshot 2018-06-06, release build:

for    Array           biggest: 999983 time: 0.014073014259338379
for    Array           biggest: 999983 time: 0.01243603229522705
for    Array           biggest: 999983 time: 0.012018918991088867
for    Array           biggest: 999983 time: 0.011536002159118652
for    Array           biggest: 999983 time: 0.011247038841247559
for    ContiguousArray biggest: 999983 time: 0.011636972427368164
for    ContiguousArray biggest: 999983 time: 0.011552095413208008
for    ContiguousArray biggest: 999983 time: 0.011477947235107422
for    ContiguousArray biggest: 999983 time: 0.011501073837280273
for    ContiguousArray biggest: 999983 time: 0.012168049812316895
lazy   Array           biggest: 999983 time: 0.01273202896118164
lazy   Array           biggest: 999983 time: 0.011597990989685059
lazy   Array           biggest: 999983 time: 0.011325955390930176
lazy   Array           biggest: 999983 time: 0.011317968368530273
lazy   Array           biggest: 999983 time: 0.011630058288574219
lazy   ContiguousArray biggest: 999983 time: 0.011358976364135742
lazy   ContiguousArray biggest: 999983 time: 0.011302947998046875
lazy   ContiguousArray biggest: 999983 time: 0.0121079683303833
lazy   ContiguousArray biggest: 999983 time: 0.011568069458007812
lazy   ContiguousArray biggest: 999983 time: 0.012079000473022461

With default toolchain of Xcode 10 beta 1, DEBUG build:

for    Array           biggest: 999983 time: 0.6173779964447021
for    Array           biggest: 999983 time: 0.6165099143981934
for    Array           biggest: 999983 time: 0.6127970218658447
for    Array           biggest: 999983 time: 0.6117799282073975
for    Array           biggest: 999983 time: 0.6133040189743042
for    ContiguousArray biggest: 999983 time: 0.32653796672821045
for    ContiguousArray biggest: 999983 time: 0.3264739513397217
for    ContiguousArray biggest: 999983 time: 0.32669806480407715
for    ContiguousArray biggest: 999983 time: 0.32600200176239014
for    ContiguousArray biggest: 999983 time: 0.32672107219696045
lazy   Array           biggest: 999983 time: 1.0019129514694214
lazy   Array           biggest: 999983 time: 0.994049072265625
lazy   Array           biggest: 999983 time: 1.0054988861083984
lazy   Array           biggest: 999983 time: 1.0101089477539062
lazy   Array           biggest: 999983 time: 1.012789011001587
lazy   ContiguousArray biggest: 999983 time: 0.7068800926208496
lazy   ContiguousArray biggest: 999983 time: 0.7070260047912598
lazy   ContiguousArray biggest: 999983 time: 0.7070150375366211
lazy   ContiguousArray biggest: 999983 time: 0.7148840427398682
lazy   ContiguousArray biggest: 999983 time: 0.7186750173568726

Also, don't forget the fastest and most stable variant!

The variant of the SieveOfEratosthenes func with an "alternative inner loop" in SR-7637, is still more than 2 times faster than the for… and lazy… variants, and it will be fast no matter if Array or ContiguousArray is used, and no matter if it is passed as a closure or called directly.

We could probably demonstrate this by writing a new version of the demo program of SR-7637, and include your for… and lazy… variants, as well as this while… variant:

func whileSieveOfEratosthenes<Storage: Possibles>(makeStorage: () -> Storage) -> [Int] {
    var possibles = makeStorage()
    let limit = possibles.count - 1
    var result = [Int]()
    for i in 2 ... limit where possibles[i] {
        var j = i * i
        while j <= limit {  // <-- Using a while loop like this here.
            possibles[j] = false
            j += i
        }
        result.append(i)
    }
    return result
}

And compare how the three variants perform when used with Array or ContiguousArray and when they are passed to a test function as a closure or called directly. I think this would be an interesting test that might perhaps help the devs fixing the issue(s) behind these inconsistencies.

I will write and add this test here when I get the time.

1 Like