Swift's Dictionary is slow even with -Ofast

Question

I'm implementing what is essentially a cache using a Dictionary in Swift. The performance is well short of what I would expect. I've read some of the other questions, for example this one about array sorting that seem to suggest that -Ofast is the answer (if you're prepared to accept the changes it brings with it). However, even when compiled -Ofast, performance compares poorly to other languages. I'm using Swift version 1.0 (swift-600.0.34.4.8).

The following is a boiled-down example which illustrates the problem:

import Foundation

class Holder {
    var dictionary = Dictionary<Int, Int>()

    func store(#key: Int, value: Int) {
        dictionary[key] = value
    }
}

let holder = Holder()

let items = 5000

for (var i: Int = 0; i < 5000; i++) {
    holder.store(key: i, value: i)
}

Compiled with -O3 it takes more than two seconds to run:

xcrun swift -sdk $(xcrun --show-sdk-path --sdk macosx) -O3 Test.swift && time ./Test

real    0m2.295s
user    0m2.176s
sys     0m0.117s

Compiling with -Ofast yields a 3-4x improvement:

xcrun swift -sdk $(xcrun --show-sdk-path --sdk macosx) -Ofast Test.swift && time ./Test

real    0m0.602s
user    0m0.484s
sys     0m0.117s

By comparison, this Java implementation:

import java.util.Map;
import java.util.HashMap;

public class Test {
    public static void main(String[] args) {
        Holder holder = new Holder();
        int items = 5000;
        for (int i = 0; i < items; i++) {
            holder.store(i, i);
        }
    }
}

class Holder {
    private final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    public void store(Integer key, Integer value) {
        map.put(key, value);
    }
}

is ~6x faster again:

javac Test.java && time java Test

real    0m0.096s
user    0m0.088s
sys     0m0.021s

Is it simply the cost of copying the Dictionary as it's mutated and stored in the Holder instance that's causing Swift to fare so badly? Removing Holder and accessing the Dictionary directly would suggest that it is.

This code:

import Foundation

var dictionary = Dictionary<Int, Int>()

let items = 5000

for (var i: Int = 0; i < 5000; i++) {
    dictionary[i] = i
}

is significantly faster:

$ xcrun swift -sdk $(xcrun --show-sdk-path --sdk macosx) -O3 NoHolder.swift && time ./NoHolder

real    0m0.011s
user    0m0.009s
sys     0m0.002s

$ xcrun swift -sdk $(xcrun --show-sdk-path --sdk macosx) -Ofast NoHolder.swift && time ./NoHolder

real    0m0.011s
user    0m0.007s
sys     0m0.003s

While it provides a (hopefully) interesting data point, accessing the Dictionary directly isn't possible in my situation. Is there anything else I can do to get closer to this level of performance with Swift in its current form?

Answer 1

TL;DR It's Beta.

I would think that the answer right now is just that Swift is in beta, the tools are in beta, and a lot of optimizations are yet to be done. Replicating your "Holder" class example in Obj-C shows that even it is quite a bit faster at the same -Ofast level.

@import Foundation;

@interface Holder : NSObject

@property NSMutableDictionary *dictionary;
- (void)storeValue:(NSInteger)value forKey:(NSString *)key;

@end

@implementation Holder

- (instancetype)init {
   self = [self initWithDict];
    return self;
}


- (instancetype)initWithDict {
    if (!self) {
        self = [super init];
        _dictionary = [NSMutableDictionary dictionary];
    }

    return self;
}

- (void)storeValue:(NSInteger)value forKey:(NSString *)key {
    [self.dictionary setValue:@(value) forKey:key];
}

@end

int main(int argc, const char * argv[]) {

    Holder *holder = [Holder new];

    for (NSInteger i = 0; i < 5000; i++) {
        [holder storeValue:i forKey:[NSString stringWithFormat:@"%ld", i]];
    }

}

The Obj-C is fast out of the gate.

time ./loop 

    real    0m0.013s
    user    0m0.006s
    sys     0m0.003s

The similarities in time to the NoHolder example you give is a good indication at how much optimization the Obj-C compiler is doing.

Taking a look at the assembly for the -O3 and -Ofast levels in Swift show there is a big difference in the amount of safety checking done. Looking at the Obj-C assembly shows that, well, there is just a lot less of it to be performed. Since the key to making a program fast is to make it not need to do much…

OS-X-Dos-Equis:~ joshwisenbaker$ wc -l objc.txt 
     159 objc.txt
OS-X-Dos-Equis:~ joshwisenbaker$ wc -l oFast.txt 
    3749 oFast.txt

(Edit: Update with results of finalizing the Holder class.)

So another interesting wrinkle is the use of the @final decoration on the class definition. If you know that your class is never going to be subclassed then try adding the keyword like this: @final class Holder

As you can see it also normalizes the performance when compiled the same way.

OS-X-Dos-Equis:~ joshwisenbaker$ swift -sdk $(xcrun --show-sdk-path --sdk macosx) -Ofast bench.swift && time ./bench

real    0m0.013s
user    0m0.007s
sys     0m0.003s

Even using just -O3 the @final works magic.

OS-X-Dos-Equis:~ joshwisenbaker$ swift -sdk $(xcrun --show-sdk-path --sdk macosx) -O3  bench.swift && time ./bench

real    0m0.015s
user    0m0.009s
sys 0m0.003s

Again, I think the differences you are seeing in performance is probably down to the current optimization levels when compiled.

Answer 2

Until Xcode 6 is closer to release and Apple disables debugging code and finished the optimizer, Why not simply declare your var as an NSMutableDictionary?

That it's field proven and quite fast.

class Holder {
    var dictionary = NSMutableDictionary()
    func store(#key: Int, value: Int) {
        dictionary[key] = value
    }
}

You can change it back later when/if Dictionary gives similar or better performance.

Update:

I tried the above code in a unit test for testPerformanceHolder()

Optimized with -O3 It completes in .013 seconds on average – about 7x faster than the Java example.

Answer 3

Unfortunately I get much worse results.

I modified the Java code to avoid timing the start up, increased the number of loops to get more repeatable timing, and checked the results to prevent the JVM from optimising the loop away:

import java.util.Map;
import java.util.HashMap;

public class HolderTest {
  private static final int items = 1_000_000;

  public static void main(String[] args) {
    final long start = System.nanoTime();
    final Holder holder = new Holder();
    for (int i = 0; i < items; i++) {
      holder.store(i, i);
    }
    final long finish = System.nanoTime();
    System.out.println("time = " + (finish - start) / 1_000_000.0 + " ms, holder 0 = " + holder.map.get(0) + ", holder " + (items - 1) + " = " + holder.map.get(items - 1));
  }
}

class Holder {
  final Map<Integer, Integer> map = new HashMap<>();

  public void store(Integer key, Integer value) {
    map.put(key, value);
  }
}

Similarly the Swift code:

import Foundation

class Holder {
    var dictionary = Dictionary<Int, Int>()

    func store(#key: Int, value: Int) {
        dictionary[key] = value
    }
}

let start = CFAbsoluteTimeGetCurrent()
let holder = Holder()
let items = 1_000_000
for i in 0 ..< items {
    holder.store(key: i, value: i)
}
let finish = CFAbsoluteTimeGetCurrent()
println("time = \((finish - start) * 1000.0) ms, holder 0 = \(holder.dictionary[0]), holder \(items - 1) = \(holder.dictionary[items - 1])")

And I got 300 ms for Java and 20 s (!) for Swift :(

This is on 6.1.

Update 1:

Changing to NSMutableDictionary gave much better performance.

sunzero-ln:HolderTest lov080$ swift -sdk $(xcrun --show-sdk-path --sdk macosx) -Ounchecked main.swift time = 647.060036659241 ms, holder 0 = Optional(0), holder 999999 = Optional(999999)

Still 2 times slower than Java, but much better!

Update 2:

It seems that even though I asked for -)unchecked in Xcode I wasn't getting it (probably some other setting I need as well :( ). From the command line the Swift version using the Swift dictionary gives:

sunzero-ln:HolderTest lov080$ swift -sdk $(xcrun --show-sdk-path --sdk macosx) -Ounchecked main.swift time = 303.406000137329 ms, holder 0 = Optional(0), holder 999999 = Optional(999999)

IE the same as Java - hurray :)

Answer 4

Update for Swift 4.2: I get speeds of 130 - 180ms using Holder testing class from @howard-lovatt.

Speed tip #1: Place all code, including looping test methods, in a separate source file if you're testing using playgrounds.

Speed tip #2: A speed increase of about 1.5 - 3x can be achieved in this case by preallocating the dictionary to the proper size: var dictionary = Dictionary<Int, Int>(minimumCapacity: 1_000_000)