June 5, 2014

Swift, tail recursion optimization, and looping

Posted in iPhone development, mac development tagged , , , at 5:18 pm by tetontech

Continuing my exploration of Swift I decided to try to see if Swift supported tail recursion optimization. To over simplify, a compiler can optimize a tail recursive function, one where the call to itself is part of the return statement of the function, to keep the application from failing due to the stack overflowing. The compiler does this by turning the recursive call into a loop. It ‘loopifys’ your recursive function since loops don’t push new function calls onto the stack.

Here is the Swift code I tried out. In it I call a function named recurse that pops the last element of of an Array and passes the reduced Array to itself again. The intent isn’t to calculate something useful, just to do tail recursion.

    func recurse(var aList:Array<Int>)->(){
        if aList.count == 0{
            return
        }
        aList.removeLast()
        return recurse(aList)
    }

I decided that 10,000 recursive calls would probably cause a stack overflow if the compiler didn’t optimize the recursion. You can play with that number to see if it was large enough. I also decided to test while and for loops to see if there was any significant speed differences between the approaches. I put the following code in a viewDidLoad method of my ViewController.

        var huge = Int[](count: 10_000, repeatedValue: 5)
        var clone = huge.copy()
        var recurseClone = huge.copy()
        
       //recursion
        var before:Double = NSDate.timeIntervalSinceReferenceDate()
        recurse(recurseClone)
        var diff:Double = NSDate.timeIntervalSinceReferenceDate() - before
        
        println("recurse milliseconds: \(diff * 1000)")

        before = NSDate.timeIntervalSinceReferenceDate()
        //while loop
        while clone.count > 0{
            clone.removeLast()
        }
        diff = NSDate.timeIntervalSinceReferenceDate() - before
        
        println("while loop milliseconds: \(diff * 1000)")

        before = NSDate.timeIntervalSinceReferenceDate()
        //for loop
        for ;huge.count > 0; huge.removeLast() {}
        diff = NSDate.timeIntervalSinceReferenceDate() - before
        println("for loop milliseconds: \(diff * 1000)")

 

There was a speed difference, maybe due to the optimizations being applied to the loop code, but I didn’t see it as significant. It appeared that most of the time was spent in modifying the array size, as I expected it would.

Here are the results I got on my 2011 macbook

    recurse milliseconds: 5031.8089723587
    while loop milliseconds: 4869.86601352692
    for loop milliseconds: 4389.14501667023

 

In my opinion the time difference is insignificant given the operation being performed.

Advertisements

2 Comments »

  1. Interesting test. Did you check what the memory usage of the app was, in either instruments or Xcode during the different approaches? I can imagine that pure performance wasn’t affected but I’m very interested in the memory efficiency of tail recursion.

    • tetontech said,

      I haven’t done anything exhaustive, When I run the app without calling the recurse function Xcode indicates around 100 MB memory use during what appears to be the recursion operation. Without the call to recurse the app uses around 12 MB to do the loops. This difference may be due to the copying of the array that Swift does as it is passed to and then modified within functions.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: