Wie schnell ist Swift?

Ich bin ein passionierter Lotto-Spieler! Aber da mir mein Geld zu schade ist, um es beim Fenster rauszuwerfen bzw. dem Staat zu schenken, simuliere ich das Lottospielen nur. Z.B. in Java oder in Swift.

Mein erster Versuch, einen Lottosimulator in Swift zu programmieren, endete aber mit einer bösen Überraschung. Das Programm war grottenlangsam! Also bin ich der Sache auf den Grund gegangen. Soviel vorweg: Schuld waren Swifts Arrays und Dictionary. Die sind komfortabel in der Handhabung, aber nicht unbedingt schnell.

Update 10.2.2015: Ich habe die Benchmarktests gerade mit XCode 6.3beta / Swift 1.2 wiederholt. Lesen Sie die Updates am Ende des Beitrags!

Vorbemerkungen

Geschwindigkeitstests mit Swift dürfen Sie nie im Playground durchführen. Aussagekräftige Messwerte erhalten Sie nur, wenn Sie ein Release-Kompilat durchführen (kein Debug-Kompilat). Um eine Release-Version zu kompilieren, führen Sie in Xcode Product/Scheme/Edit Scheme aus, wählen den Eintrag Run und das Dialogblatt Info aus und stellen dort die Build Configuration auf
Release um.

XCode-Einstellungen, um ein Release-Kompilat durchzuführen

Testumgebung: Ich habe meine Tests für den Xcode-Projekttyp OS X — Command Line Tool auf einem iMac durchgeführt (i7-CPU mit 2,8 GHz).

Lottosimulator 1: kurzer Code, langsam

Die erste Version meines Lottosimulators sah so aus:

import Foundation

// diese Zahlen müssen geordnet sein!
let meineZahlen = [1, 6, 12, 14, 25, 33]

var lotto: [Int]
var cnt=0

do {
  var set:[Int:Bool] = [:]  // leeres Dictionary erzeugen
  do {                      // Ziehung simulieren
    set[ Int(arc4random_uniform(49))+1 ] = true
  } while(set.count<6)
  // Keys des Dictionary in sortiertes Array umwandeln
  lotto = sorted(Array(set.keys), <)

  cnt++
  if cnt % 100_000 == 0 {
    println("Bisher (cnt) Ziehungen")
  }
  // Schleife ausführen, bis beide Arrays übereinstimmen
} while meineZahlen != lotto

println("Sechs Richtige nach (cnt) Versuchen")

Die äußere Schleife läuft also solange, bis eine mit Zufallszahlen durchgeführte Ziehung den eigenen sechs »Glückszahlen« entspricht. Die innere Schleife simuliert Lotto-Ziehungen: Dabei werden solange Zufallszahlen zwischen 1 und 49 Elemente in ein Dictionary eingetragen, bis dieses aus sechs Elementen besteht. Die Schlüssel dieser sechs Einträge entsprechen den Zahlen einer Ziehung. Der Sinn des Dictionaries besteht darin, Doppelgänger unter den Lottozahlen zu vermeiden. Die Keys werden nun in ein sortiertes Array umgewandelt, das unkompliziert mit meineZahlen verglichen werden kann.

Statistisch gesehen sind durchschnittlich rund 15 Millionen simulierte Ziehungen erforderlich, bis das Programm die Erfolgsmeldung »Sechs Richtige« ausgibt. (Auf die Superzahl, die Erkennung von fünf übereinstimmenden Zahlen und andere Sonderfälle habe ich verzichtet.) Auf meinem iMac dauert das rund 10 Minuten — deutlich länger als erwartet.

Benchmarktests

Warum ist das Programm so langsam? Mein erster Verdacht bestand darin, dass es am Erzeugen der Zufallszahlen liegt. Ein kurzer Test beweist aber das Gegenteil. Swift summierte 100 Millionen Zufallszahlen in weniger als 3 Sekunden.

let start = NSDate()
var sum=0
for _ in 1...100_000_000 {
  sum += Int(arc4random_uniform(100))
}
let end = NSDate()
let seconds = end.timeIntervalSinceDate(start)
println("fertig nach (seconds) Sekunden")

Mein nächster Verdächtiger war das Dictionary, das ich zum bequemen Erzeugen von Lottozahlen missbraucht habe. Natürlich geht es auch ohne Dictionary, wenn die sechs Lottozahlen einfach in einem Array gespeichert werden. Allerdings muss nun beim Einfügen jeder neuen Zufallszahl überprüft werden, ob diese nicht schon vorkommt. Es darf keine Doppelgänger geben. Das macht den Code etwas unübersichtlicher, aber schon um den Faktor 10 schneller als die erste Variante mit dem Dicionary.

// eine Million Lottoziehungen simulieren
for _ in 1...1_000_000 {
  var n=0
  // Array zur Speicherung der Lottozahlen 
  var lotto =  [Int](count:6, repeatedValue:0) 
  do {
    // Zufallszahl an der Position n einfügen
    lotto[n] =  Int(arc4random_uniform(49))+1
    // Doppelgängertest
    for i in 0..<n {
      if lotto[i] == lotto[n] {
        n--       // die n-te Lottozahl ist ein Doppel-
        break     // gänger, wird wegen n-- neu erzeugt
      }
    }
    n++
  } while(n<6)    // Schleife ausführen, bis sechs Zahlen vorliegen
  sort(&lotto,<)  // sortieren
}

Aber damit ist das Ende der Fahnenstange noch nicht erreicht. Mit etwas Glück ist mir aufgefallen, dass ich das Array lotto nicht eine Million mal neu erzeugen muss. Also habe ich die betreffende Zeile oberhalb der for-Schleife angeordnet, ohne mir davon Wunder zu versprechen. Doch genau dieses Wunder traf ein. Die Rechenzeit sank auf meinem Testrechner von 2,7 auf 0,4 Sekunden, also ca. auf ein Siebtel. Oder, anders formuliert: Im obigen Code beansprucht die Zeile var lotto = [Int](count:6, repeatedValue:0) unglaubliche 85 Prozent der Rechenzeit!

// wie oben, aber mit dem Recycling des lotto-Arrays
// sieben Mal schneller!
var lotto = [Int](count:6, repeatedValue:0) // <-- neu platziert
for _ in 1...1_000_000 {
  var n=0
  do { ... }      // wie oben
  n++
  } while(n<6)    
  sort(&lotto,<)  
}

Im Versuch, den Algorithmus weiter zu optimieren, habe ich den Datentyp des Arrays von Int auf UInt8 umgestellt — ohne Erfolg. Die Rechenzeit blieb im Rahmen der Messgenauigkeit unverändert. Optimierungspotenzial habe ich dann nur noch bei sort gefunden: Ohne sort sinkt die Rechenzeit nochmals auf die Hälfte. Die Zahlen müssen aber sortiert werden, damit sie mit dem ebenfalls geordneten Glückszahlen verglichen werden können. Wenn Sie das Programm also weiter optimieren wollten, könnten Sie versuchen, einen effizienteren Sortieralgorithmus zu implementieren. Darauf habe ich verzichtet.

Lottosimulator 2: Swift zeigt, was es kann

Mit dem so gewonnen Wissen habe ich dann die endgültige Version des Lottosimulators fertiggestellt. Der Code sieht so aus:

import Foundation

// diese Zahlen müssen geordnet sein!
let meineZahlen = [1, 6, 12, 14, 25, 33]

var lotto =  [Int](count:6, repeatedValue:0)
var cnt=0
do {
  // Lottoziehung simulieren
  var n=0
  do {
    lotto[n] =  Int(arc4random_uniform(49))+1
    for i in 0..<n {  // Doppelgängertest
      if lotto[i] == lotto[n] {
        n--    // die n-te Lottozahl ist ein Doppel-
        break  // gänger, neu erzeugen
      }
    }
    n++
  } while(n<6)
  sort(&lotto,<)
  cnt++
  if cnt % 100_000 == 0 {
    println("Bisher (cnt) Ziehungen")
  }
} while meineZahlen != lotto
println("Sechs Richtige nach (cnt) Versuchen")

Diese Programmversion war bei meinen Tests ca. um den Faktor 70 schneller als die ursprüngliche Version.

Fazit

Die Arrays und Dictionary in Swift bieten viel Flexibilität, die aber auf Kosten der Geschwindigkeit geht. Besonders ineffizient ist das Erzeugen von Arrays.

Swift 1.2 (Update 10.2.2015)

Gestern hat Apple XCode 6.3 Beta mit einem verbesserten Swift-Compiler freigegeben. Die Release Notes versprechen nicht nur diverse Neuerungen, sondern auch Geschwindigkeitssteigerungen. Also habe ich mir mein Lotto-Beispiel nochmals angesehen (zugegebenermaßen kein hochwissenschaftlicher Benchmark-Test …).

Langer Rede kurzer Sinn:

Der Umgang mit Dictionarys und speziell das Erzeugen von Arrays ist viel schneller geworden. Der »Lottosimulator 1« läuft nun ca. sieben Mal so schnell!
Auch die optimierte Variante, also der »Lottosimulator 2«, ist schneller geworden, wenn auch nur um ca. 10 bis 15%.
Trotz der Verbesserungen des Compilers lohnt sich die händische Optimierung weiterhin. Die Variante 2 ist immer noch um den Faktor 11 schneller als Variante 1.

kofler.info