performance - Swift Dictionary slow even with optimizations: doing uncessary retain/release?

Question

The following code, which maps simple value holders to booleans, runs over 20x faster in Java than Swift 2 - XCode 7 beta3, "Fastest, Aggressive Optimizations [-Ofast]", and "Fast, Whole Module Optimizations" turned on. I can get over 280M lookups/sec in Java but only about 10M in Swift.

When I look at it in Instruments I see that most of the time is going into a pair of retain/release calls associated with the map lookup. Any suggestions on why this is happening or a workaround would be appreciated.

The structure of the code is a simplified version of my real code, which has a more complex key class and also stores other types (though Boolean is an actual case for me). Also, note that I am using a single mutable key instance for the retrieval to avoid allocating objects inside the loop and according to my tests this is faster in Swift than an immutable key.

EDIT: I have also tried switching to NSMutableDictionary but when used with Swift objects as keys it seems to be terribly slow.

EDIT2: I have tried implementing the test in objc (which wouldn't have the Optional unwrapping overhead) and it is faster but still over an order of magnitude slower than Java... I'm going to pose that example as another question to see if anyone has ideas.

EDIT3 - Answer. I have posted my conclusions and my workaround in an answer below.

public final class MyKey : Hashable {
    var xi : Int = 0
    init( _ xi : Int ) { set( xi ) }  
    final func set( xi : Int) { self.xi = xi }
    public final var hashValue: Int { return xi }
}
public func == (lhs: MyKey, rhs: MyKey) -> Bool {
    if ( lhs === rhs ) { return true }
    return lhs.xi==rhs.xi
}

...
var map = Dictionary<MyKey,Bool>()
let range = 2500
for x in 0...range { map[ MyKey(x) ] = true }
let runs = 10
for _ in 0...runs
{
    let time = Time()
    let reps = 10000
    let key = MyKey(0)
    for _ in 0...reps {
        for x in 0...range {
            key.set(x)
            if ( map[ key ] == nil ) { XCTAssertTrue(false) }
        }
    }
    print("rate=(time.rate( reps*range )) lookups/s")
}

and here is the corresponding Java code:

public class MyKey  {
    public int xi;
    public MyKey( int xi ) { set( xi ); }
    public void set( int xi) { this.xi = xi; }

    @Override public int hashCode() { return xi; }

    @Override
    public boolean equals( Object o ) {
        if ( o == this ) { return true; }
        MyKey mk = (MyKey)o;
        return mk.xi == this.xi;
    }
}
...
    Map<MyKey,Boolean> map = new HashMap<>();
    int range = 2500;    
    for(int x=0; x<range; x++) { map.put( new MyKey(x), true ); }

    int runs = 10;
    for(int run=0; run<runs; run++)
    {
        Time time = new Time();
        int reps = 10000;
        MyKey buffer = new MyKey( 0 );
        for (int it = 0; it < reps; it++) {
            for (int x = 0; x < range; x++) {
                buffer.set( x );
                if ( map.get( buffer ) == null ) { Assert.assertTrue( false ); }
            }
        }
        float rate = reps*range/time.s();
        System.out.println( "rate = " + rate );
    }

Answer 1

After much experimentation I have come to some conclusions and found a workaround (albeit somewhat extreme).

First let me say that I recognize that this kind of very fine grained data structure access within a tight loop is not representative of general performance, but it does affect my application and I'm imagining others like games and heavily numeric applications. Also let me say that I know that Swift is a moving target and I'm sure it will improve - perhaps my workaround (hacks) below will not be necessary by the time you read this. But if you are trying to do something like this today and you are looking at Instruments and seeing the majority of your application time spent in retain/release and you don't want to rewrite your entire app in objc please read on.

What I have found is that almost anything that one does in Swift that touches an object reference incurs an ARC retain/release penalty. Additionally Optional values - even optional primitives - also incur this cost. This pretty much rules out using Dictionary or NSDictionary.

Here are some things that are fast that you can include in a workaround:

a) Arrays of primitive types.

b) Arrays of final objects as long as long as the array is on the stack and not on the heap. e.g. Declare an array within the method body (but outside of your loop of course) and iteratively copy the values to it. Do not Array(array) copy it.

Putting this together you can construct a data structure based on arrays that stores e.g. Ints and then store array indexes to your objects in that data structure. Within your loop you can look up the objects by their index in the fast local array. Before you ask "couldn't the data structure store the array for me" - no, because that would incur two of the penalties I mentioned above :(

All things considered this workaround is not too bad - If you can enumerate the entities that you want to store in the Dictionary / data structure you should be able to host them in an array as described. Using the technique above I was able to exceed the Java performance by a factor of 2x in Swift in my case.

If anyone is still reading and interested at this point I will consider updating my example code and posting.

EDIT: I'd add an option: c) It is also possible to use UnsafeMutablePointer<> or Unmanaged<> in Swift to create a reference that will not be retained when passed around. I was not aware of this when I started and I would hesitate to recommend it in general because it's a hack, but I've used it in a few cases to wrap a heavily used array that was incurring a retain/release every time it was referenced.