Bekanntlich kann CPython Code nicht parallel in Betriebssystem-Threads ausführen. Es gibt den Global Interpreter Lock (GIL), der verhindert, dass dies passiert. Auf einem Computer mit mehr als einer CPU (dem Standard heutzutage), kämpfen alle paar Millisekunden die CPUs um den GIL, was dazu führt, dass die Laufzeit von CPython in diesem Fall deutlich schlechter als das theoretische Maximum ist.
Dieses Python-Programm braucht auf meinem Rechner etwa 9,5s:
def count_down(n):
while n > 0:
n -= 1
count_down(100000000)
Teile ich die Arbeit in 2 Threads auf, sollte die Zeit in etwa die selbe bleiben. Tatsächlich dauert es 30% länger. Das Programm benötigt 12,5s:
def count_down(n):
while n > 0:
n -= 1
import threading
t1 = threading.Thread(target=count_down, args=(100000000 / 2,))
t2 = threading.Thread(target=count_down, args=(100000000 / 2,))
t1.run()
t2.run()
Könnte ich zwei (der vier) CPUs in meinem Rechner nutzen, sollte die Laufzeit eher bei 5s liegen. Doch schon die 30% für den Kampf der CPUs um den GIL schmerzen.
Hier ist ein äquivalentes Go-Programm. Ich musste den Zähler um zwei Nullen erweitern, damit es etwa 3,6s benötigt (wenigstens ist der Go-Compiler nicht schlau genug, diesen sinnlosen Benchmark wegzuoptimieren):
package main
func countDown(n int64) { for n > 0 { n-- } }
func main() { countDown(10000000000) }
Go nennt seine Threads Goroutines. (Streng genommen sind Goroutinen etwas anderes, aber da sie auf Threads abgebildet werden, setze ich das hier mal gleich.) Sie können mit dem Schlüsselwort go gestartet werden. Um auf das Ende eines Threads zu warten, nutze ich einen Channel. Das Hauptprogramm blockiert, um aus dem Channel etwas zu lesen. Die Goroutine schreibt am Ende einen Wert in den Channel, wenn sie fertig ist. Andernfalls würde sich das Programm (anders als Python) sofort beenden.
Auch dieses Programm läuft etwa 3,6s lang:
package main
var sync = make(chan int, 4)
func cd(n int64) { for n > 0 { n-- } sync <- 1 }
func main() { go cd(10000000000); <-sync }
Teile ich die Arbeit auf 2 Threads auf, bleibt die Zeit konstant. Auch Go nutzt standardmäßig nur eine CPU, hat allerdings nicht die Ineffizienz des CPython-GIL. Dafür muss man den Zugriff auf globale Ressourcen selbst synchronisieren, wenn Go-Routinen könnten parallel ausgeführt werden.
Mit der Umgebungsvariable GOMAXPROCS kann ich die Anzahl der zu benutzenden CPUs einstellen:
$ export GOMAXPROCS=2
Nun läuft mein Test in 1,9s. Die beiden Schleifen laufen parallel ab, wenn auch mit 5% Overhead. Da mein Notebook vier CPUs hat, kann ich auch vier Threads parallel ausführen -- aber mit spürbarem Overhead von 2,3s statt 1,9s, also 28%. Die Macher von Go sagen auch, der Grund, warum man die Anzahl der CPUs einstellen muss, ist, dass sie noch nicht zufrieden mit ihrem automatischen Scheduler sind. Kann ich verstehen.
(Siehe https://gist.github.com/2328371 für die Vorgeschichte)
Wenn ich noch while, > und -= (bzw. einfach -) in meinem Go-Python-Interpreter einbaue, kann ich count_down auch dort als Benchmark ausführen. Das gibt einen interessanten Basiswert für den Overhead, den der Interpreter hat.
type (
astWhile struct {
cond Expr
body Suite
}
astGt struct {
left, right Expr
}
astSub struct {
left, right Expr
}
)
func (self *astWhile) Exec(f *PyFrame) {
for {
if !self.cond.Eval(f).(bool) {
break
}
self.body.Exec(f)
}
}
func (self *astGt) Eval(f *PyFrame) PyValue {
left := self.left.Eval(f)
right := self.right.Eval(f)
switch l := left.(type) {
case PyInt:
r, ok := right.(PyInt)
if ok {
return l > r
}
}
panic("type error")
}
func (self *astSub) Eval(f *PyFrame) PyValue {
left := self.left.Eval(f)
right := self.right.Eval(f)
switch l := left.(type) {
case PyInt:
r, ok := right.(PyInt)
if ok {
return l - r
}
}
panic("type error")
}
Die folgenden Funktionen ergänzen den Parser:
func parseStmt(s *Scanner) Stmt {
...
if s.match("while") {
test := parseTest(s)
s.expect(":")
body := parseSuite(s)
s.expect("end")
return &astWhile{test, body}
}
...
}
func parseTest(s *Scanner) Expr {
e := parseExpr(s)
if s.match(">") {
e = &astGt{e, parseExpr(s)}
}
return e
}
func parseExpr(s *Scanner) Expr {
t := parseTerm(s)
if s.match("+") {
t = &astAdd{t, parseTerm(s)}
} else if s.match("-") {
t = &astSub{t, parseTerm(s)}
}
return t
}
Nun kann ich meinen Test ablaufen lassen:
f := NewFrame(nil, NewDict(), NewDict())
Parse([]byte("n=10000000 while n > 0: n=n-1 end")).Exec(f)
Das ich dabei auch den Aufwand messe, das Programm zu übersetzen, ist zu vernachlässigen.
Das Programm läuft in etwa 7,5s ab, hat allerdings Faktor 10 weniger zu tun als die CPython-Version.
Komme ich näher an die Laufzeit von CPython heran?
Lokale Variablen mit einem PyDict zu verwalten ist relativ ineffektiv. Besser ist die folgende Repräsentation, den typischerweise hat eine Funktion nur wenige lokale Variablen und bei 1-5 Variablen ist die lineare Suche wahrscheinlich schneller als eine vergleichsweise aufwendige Hash-Funktion:
type PyFrame struct {
back *PyFrame
names []PyStr
values []PyValue
globals PyDict
}
func (self *PyFrame) Get(name PyStr) PyValue {
n := self.names
for i, j := 0, len(n); i < j; i++ {
if n[i] == name {
return self.values[i]
}
}
...
}
func (self *PyFrame) Set(name PyStr, value PyValue) {
n := self.names
for i, j := 0, len(n); i < j; i++ {
if n[i] == name {
self.values[i] = value
return
}
}
panic("unknown name '" + name + "'")
}
Damit braucht mein Go-Programm noch 2s. CPython ist damit immer noch 2x schneller. Ich kann aber immer noch von einem AST-Interpreter auf eine VM wechseln und dort die lokalen Variablen direkt über einen Index ansprechen.
Hier ist der entsprechende Code als minimales eigenständiges Beispiel:
type Frame struct {
locals []interface{}
names []string
globals map[string]interface{}
index int
code []byte
consts []interface{}
stack []interface{}
}
func (f *Frame) push(v interface{}) {
f.stack = append(f.stack, v)
}
func (f *Frame) pop() interface{} {
l := len(f.stack) - 1
v := f.stack[l]
f.stack = f.stack[:l]
return v
}
func (f *Frame) execute() {
for {
c := f.code[f.index]
f.index++
switch c {
case 0:
f.push(f.consts[f.code[f.index]])
f.index++
case 1:
f.push(f.locals[f.code[f.index]])
f.index++
case 2:
f.locals[f.code[f.index]] = f.pop()
f.index++
case 3:
r := f.pop()
l := f.pop()
f.push(l.(int) > r.(int))
case 4:
r := f.pop()
l := f.pop()
f.push(l.(int) - r.(int))
case 5:
if !f.pop().(bool) {
f.index = int(f.code[f.index])
} else {
f.index++
}
case 6:
f.index = int(f.code[f.index])
case 7:
return
}
}
}
Leider ist dieser Code mit 2,5s sehr langsam, was ich mir zur Zeit nur so erklären kann, dass Go keine optimierte switch-Anweisung kennt. Viel effizienter als eine Sprunganweisung geht es eigentlich nicht. Ich hätte erwartet, dass so eine Funktion effizienter als ein AST-Interpreter ist.
Hm...
Eigentlich geht es mir jedoch um die Frage, was eine zusätzliche Synchronisation über einen Read-Write-Lock bei allen Zugriffen auf den (globalen) Kontext für eine Auswirkung hat. Dies wäre eine notwendige Anpassung, damit ich Go-Python-Code parallel in mehreren Goroutinen ausführen kann und diese Anpassung wirkt sich natürlich auch auf den Fall aus, das ich nur einen Thread habe.
Ein kurzer Test mit einem sync.RWMutex bei jedem Zugriff auf die lokale Variable n zeigt, dass die Laufzeit dadurch um Faktor 4 auf 8,4s. In der Praxis braucht man diese Synchronisation natürlich nur für globale Variablen, die vielleicht nicht so häufig sind, aber 30.000.000 Lock-Opertionen kosten 6,4s. Ist man bereit, diesen Preis zu zahlen? Möglicherweise findet man mit einer persistent map einen effizienteren Datentyp, den man allerdings nach dem Vorbild von Clojure erst für Go entwickeln müsste. Oder man macht aus jeder Ressource, auf die ein konkurrierender Zugriff erfolgen kann, eine Goroutine, mit der man dann über einen Channel kommuniziert.
Stefan