Finding matching Node instances in an array - running slow

Question

I have encountered a performance issue in Swift. I compared the same method between C# and Swift: Swift is much slower than C#.

Here is the code I'm working with. Could some one help me to speed it up in Swift?

CSharp version (for reference only - it takes 73 ticks):

var nodes = new Node[328];
 for (int i = 0; i < nodes.Length; i++)
 {
 nodes[i] = new Node();
 }
 var oneNode = new Node();
 var count = 1;
 Stopwatch sw = Stopwatch.StartNew();
 foreach(var node in nodes)
 {
 if (oneNode.Equals(node))
 {
 count++;
 }
 }
 sw.Stop();
 Console.WriteLine(sw.ElapsedMilliseconds);

Swift version (it takes 1.78 ms):

import Foundation
public class Node : Equatable {
 var cost : Int = 0
 var x : Int = 100
 var y : Int = 100
}
public func == (a : Node, b : Node) -> Bool {
 return (a.x == b.x) && (a.y == b.y)
}
var t = NSDate()
let a = [Node](count: 328, repeatedValue: Node())
let b = Node()
var count = 1
for i in a {
 if i == b {
 count++
 }
}
var elapsed = t.timeIntervalSinceNow * -1000
println(elapsed)

• Martin R: Did you compile and run the Swift code in the "Release" configuration to enable compiler optimizations?
• Howard: Excellent! I switch to release mode and the performance is pretty good in emulator. While I deployed into iPhone. It slows down again. What special settings I need to configure?
• Martin R: The iPhone processor is generally slower than a desktop processor, so you cannot really compare the numbers. Or did you run the C# code on the device as well? – I do not see much room for improvement in your code. Do you really need the number of matching nodes? If only the existence is needed then the find() function could be used. Or store the nodes in a sorted array or perhaps a tree, this allows faster searching algorithms. – Also (if possible) use struct Node instead of class Node, this should be faster.
• Howard: I tested with debug on real device, the performance is terrible bad. I think the release mode fixed my problem. Please answer this question and I will mark it as answer.
• Bruno Costa: Isn't that method the same as return 1 or 329?

Answer 1

What's absolutely crucial when doing time comparisons between languages is that we make sure we're actually testing the same thing. In this case, we're not.

But before I get into that into too much detail, I'm going to suggest a slightly better method of testing this code.

First of all, I've moved the actual running code (everything but the class declaration and the == function definition) into an IBAction method so that I can press a button and test it multiple times all in the same build.

Second, I'm going to change the definition of the class for this test to assign random values to its properties. So the class definition will look like this for my test:

public class Node : Equatable {
 var cost : Int = 0
 var x : Int = Int(arc4random_uniform(100))
 var y : Int = Int(arc4random_uniform(100))
}

This forces the timing to be a little more realistic since branch prediction might easily figure out that the result of == is always true and just fly through our loop.

And third of all, I'm going to test with a much larger array. I want 10,000 elements. This may be unrealistically large for actual usage, but when testing speed and trying to optimize time, it's good to work with very large sample sizes.

So, without changing anything else, this is what I'm going to test, and I will include results from the time profiler:

public class Node : Equatable {
 var cost : Int = 0
 var x : Int = Int(arc4random_uniform(100))
 var y : Int = Int(arc4random_uniform(100))
}
public func == (a : Node, b : Node) -> Bool {
 return (a.x == b.x) && (a.y == b.y)
}
class ViewController: UIViewController {
 @IBAction func test(sender: UIButton) {
 var t = NSDate()
 let a = [Node](count: 10_000, repeatedValue: Node())
 let b = Node()
 var count = 1
 for i in a {
 if i == b {
 count++
 }
 }
 var elapsed = t.timeIntervalSinceNow * -1000
 println(elapsed)
 }
}

Completely as written, and using whatever optimization defaults you get when you create a new project in Swift, this takes my desktop 47-50 milliseconds. On an iPad Mini, this takes about 265-270 milliseconds.

enter image description here

This is the time profile of the code I posted. I pressed the button to run the test 8 times. Notice a few lines:

• 84.9% is where our Swift version of our IBAction method is. The first 15.1 percent is the time it took to launch our app, initialize, run the view controller, receive the touch events, etc. The other 84.9% is code that runs from inside our IBAction method.
• 1.1% is how much of the total time is spent comparing our Node objects with our custom == function. The array is 10,000 elements large, and we're iterating through it completely 8 times. We're calling the == function 80,000 times, and it only takes 1.1% of the total time. Our == function is perfectly fine.

The code that's taking the most time is here:

enter image description here

Unfortunately, we can't see exactly what these are. They're all from within the Swift library though. And since Swift is still growing and rapidly changing, it'll probably be a while before the Time Profiler actually gives us the actual method names for these.

I tried moving code around, trying to get different results, but they're all pretty much the same. I suspected that the array initialization was taking up about half the time and tried moving that out of the timer, but it doesn't seem to make a difference.

What I can tell you though, is this:

1. Your == method, which is what is all that you've written which is being tested here, is perfectly fast. It takes almost no time at all.
2. It's relatively well known that at this point in time, Swift is absolutely horrendous with accessing arrays in loops like this. But Swift is very much so a growing and evolving language. Hopefully the Apple engineers are working on improving it.

• Howard: Thanks, as I tested, the speed is badly affect by the build condition. When I switch from debug to release to run, it becomes the same speed as the C# one. While it is slower running on the iPhone, but it is acceptable. Lack of experience on iOS development.
• nhgrif: Slower processors run code slower. That is to be expected. Did you test the C# code on the same device to be sure you had an apples-to-apples?
• Howard: Unfortunately not; I will try it with Xamarin.iOS later to see how the performance is.