Python schneller als D ?? IO-Operationen scheinen D langsamer zu machen ... was ist los?

Question

Ich schrieb eine Sprache für virtuelle Maschinen zum Assembly-Übersetzer für einen Computer-System-Kurs, den ich belegte (mit dem nand2tetris-Lehrplan). Ich habe es ursprünglich in Python geschrieben, aber seit ich D lerne, dachte ich, ich würde es übersetzen. D ist syntaktisch sehr nah an Python, also war es nicht zu schwierig. Ich nahm an, dass D, eine Performance-Sprache und kompiliert, mindestens so schnell wie Python und in einer großen Datei wäre, viel schneller wäre. Aber das Gegenteil ist wahr! Trotz identischer Algorithmen lief D konsistent etwas langsamer als Python, wenn ich eine sehr große Datei kompilierte. Bei einer Datei mit einer Länge von etwa 500000 Zeilen benötigte Python konsistent etwa 2,6 Sekunden, während D konsistent etwa 3 benötigte. Dies ist keine große Lücke, aber es ist bemerkenswert, dass Python überhaupt schneller ist.

Ich möchte nicht vorschlagen, dass ich naiv genug bin zu denken, dass Python tatsächlich schneller ist als D insgesamt; In diesem Fall scheint es jedoch zumindest so zu sein, dass D nicht intuitiv schneller ist. Ich würde es begrüßen, wenn Sie einige Angaben zu möglichen Leistungseinbußen in meinem D-Code machen würden. Ich denke, der Engpass könnte bei IO-Operationen liegen, aber ich bin mir nicht sicher.

Der Quellcode ist unten. Die Details sind nicht so wichtig; Einige Assemblersprachenvorlagen werden zugewiesen, und dann erfolgt ein linearer Durchlauf durch die Sprache der virtuellen Maschine, wobei jeder Befehl in einen äquivalenten Assemblercode übersetzt wird.

EDIT: nach der Neukompilierung der D-Code mit dmd -O -release -inline -m64, D kommt der Sieger mit einer Zeit von 2.20s auf den Eingang. Es bleibt jedoch die Frage, warum D mit fast identischem Code langsamer zu sein scheint als Python.

EDIT 2: den Rat von unten mit, ich wechselte von einer einfachen Liste von Strings verwenden, um ein appender!string() verwendet und verbessern die Zeit von einem merklichen Betrag. Es lohnt sich jedoch zu erwähnen, dass, wenn Sie eine Reihe von Zeichenketten in einer appender haben, tun, um sie mit einem Befehl wie in einer Datei nicht schreiben:

auto outputfile = File("foo.txt","w"); 
foreach(str; my_appender.data) 
    outputfile.write(str); 

vielmehr stattdessen schreiben so etwas wie:

auto outputfile = File("foo.txt","w"); 
outputfile.write(my_appender.data); 

Das zweite Beispiel gibt Ihnen eine kleine Leistungssteigerung gegenüber einem einfachen string[]. Aber die Verwendung des ersten gab mir einen enormen Leistungshit und verdoppelte die Ausführungszeit.

zu einem appender!string() ändern, die Zusammenstellung der oben genannten großen Datei etwa 2,75 Sekunden gedauert (auf Python 2.8), wo das Original genommen hatte darüber 3. tun, und auch die Optimierungsflags in dmd verwendet, ergab eine Gesamtzusammenstellung Zeit von 1.98 Sekunden! :)

Python:

#!/usr/bin/python 

import sys 

operations_dict = {"add":"+", "sub":"-", 
        "and":"&", "or":"|", 
        "not":"!", "neg":"-", 
        "lt":"JLT", "gt":"JGT", 
        "eq":"JEQ", "leq":"JLE", 
        "geq":"JGE"} 

vars_dict = {"this":("THIS","M"), 
      "that":("THAT","M"), 
      "argument":("ARG","M",), 
      "local":("LCL","M",), 
      "static":("f.%d","M",), 
      "temp":("TEMP","A",)} 

start = "@SP\nAM=M-1\n" 
end = "@SP\nM=M+1\n" 

binary_template = start + "D=M\n\ 
@SP\n\ 
AM=M-1\n\ 
M=M%sD\n" + end 

unary_template = start + "M=%sM\n" + end 

comp_template = start + "D=M\n\ 
@SP\n\ 
AM=M-1\n\ 
D=M-D\n\ 
@COMP.%d.TRUE\n\ 
D;%s\n\ 
@COMP.%d.FALSE\n\ 
0;JMP\n\ 
(COMP.%d.TRUE)\n\ 
@SP\n\ 
A=M\n\ 
M=-1\n\ 
@SP\n\ 
M=M+1\n\ 
@COMP.%d.END\n\ 
0;JMP\n\ 
(COMP.%d.FALSE)\n\ 
@SP\n\ 
A=M\n\ 
M=0\n" + end + "(COMP.%d.END)\n" 

push_tail_template = "@SP\n\ 
A=M\n\ 
M=D\n\ 
@SP\n\ 
M=M+1\n" 

push_const_template = "@%d\nD=A\n" + push_tail_template 

push_var_template = "@%d\n\ 
D=A\n\ 
@%s\n\ 
A=%s+D\n\ 
D=M\n" + push_tail_template 

push_staticpointer_template = "@%s\nD=M\n" + push_tail_template 

pop_template = "@%d\n\ 
D=A\n\ 
@%s\n\ 
D=%s+D\n\ 
@R13\n\ 
M=D\n\ 
@SP\n\ 
AM=M-1\n\ 
D=M\n\ 
@R13\n\ 
A=M\n\ 
M=D\n" 

pop_staticpointer_template = "@SP\n\ 
AM=M-1\n\ 
D=M\n\ 
@%s\n\ 
M=D" 


type_dict = {"add":"arithmetic", "sub":"arithmetic", 
        "and":"arithmetic", "or":"arithmetic", 
        "not":"arithmetic", "neg":"arithmetic", 
        "lt":"arithmetic", "gt":"arithmetic", 
        "eq":"arithmetic", "leq":"arithmetic", 
        "geq":"arithmetic", 
        "push":"memory", "pop":"memory"} 

binary_ops = ["add", "sub", "and", "or"] 
unary_ops = ["not", "neg"] 
comp_ops = ["lt", "gt", "eq", "leq", "geq"] 


op_count = 0 
line_count = 0 
output = ["// Assembly file generated by my awesome VM compiler\n"] 

def compile_operation(op): 
    global line_count 

    if (op[0:2] == "//") or (len(op.split()) == 0): 
     return "" 

    # print "input: " + op 
    operation = op.split()[0] 
    header = "// '" + op + "' (line " + str(line_count) + ")\n" 
    line_count += 1 

    if type_dict[operation] == "arithmetic": 
     return header + compile_arithmetic(op) 
    elif type_dict[operation] == "memory": 
     return header + compile_memory(op) 

def compile_arithmetic(op): 
    global op_count 
    out_string = "" 
    if op in comp_ops: 
     out_string += comp_template % (op_count, operations_dict[op], op_count, \ 
      op_count, op_count, op_count, op_count) 
     op_count += 1 
    elif op in unary_ops: 
     out_string += unary_template % operations_dict[op] 
    else: 
     out_string += binary_template % operations_dict[op] 
    return out_string 

def compile_memory(op): 
    global output 
    instructions = op.split() 
    inst = instructions[0] 
    argtype = instructions[1] 
    val = int(instructions[2]) 
    if inst == "push": 
     if argtype == "constant": 
      return push_const_template % val 
     elif argtype == "static": 
      return push_staticpointer_template % ("f." + str(val)) 
     elif argtype == "pointer": 
      if val == 0: 
       return push_staticpointer_template % ("THIS") 
      else: 
       return push_staticpointer_template % ("THAT") 
     else: 
      return push_var_template % (val, vars_dict[argtype][0], vars_dict[argtype][1]) 
    elif inst == "pop": 
     if argtype != "constant": 
      if argtype == "static": 
       return pop_staticpointer_template % ("f." + str(val)) 
      elif argtype == "pointer": 
       if val == 0: 
        return pop_staticpointer_template % "THIS" 
       else: 
        return pop_staticpointer_template % "THAT" 
      else: 
       return pop_template % (val, vars_dict[argtype][0], vars_dict[argtype][1]) 

def main(): 
    global output 

    if len(sys.argv) == 1: 
     inputfname = "test.txt" 
    else: 
     inputfname = sys.argv[1] 
    outputfname = inputfname.split('.')[0] + ".asm" 

    inputf = open(inputfname) 
    output += ["// Input filename: %s\n" % inputfname] 
    for line in inputf.readlines(): 
     output += [compile_operation(line.strip())] 

    outputf = open(outputfname, 'w') 
    for outl in output: 
     outputf.write(outl) 

    outputf.write("(END)\n@END\n0;JMP"); 
    inputf.close() 
    outputf.close() 
    print "Output written to " + outputfname 


if __name__ == "__main__": 
    main() 

D:

import std.stdio, std.string, std.conv, std.format, std.c.stdlib; 

string[string] operations_dict, type_dict; 
string[][string] vars_dict; 
string[] arithmetic, memory, comp_ops, unary_ops, binary_ops, lines, output; 
string start, end, binary_template, unary_template, 
     comp_template, push_tail_template, push_const_template, 
     push_var_template, push_staticpointer_template, 
     pop_template, pop_staticpointer_template; 
int op_count, line_count; 

void build_dictionaries() { 
    vars_dict = ["this":["THIS","M"], 
       "that":["THAT","M"], 
       "argument":["ARG","M"], 
       "local":["LCL","M"], 
       "static":["f.%d","M"], 
       "temp":["TEMP","A"]]; 

    operations_dict = ["add":"+", "sub":"-", 
        "and":"&", "or":"|", 
        "not":"!", "neg":"-", 
        "lt":"JLT", "gt":"JGT", 
        "eq":"JEQ", "leq":"JLE", 
        "geq":"JGE"]; 

    type_dict = ["add":"arithmetic", "sub":"arithmetic", 
        "and":"arithmetic", "or":"arithmetic", 
        "not":"arithmetic", "neg":"arithmetic", 
        "lt":"arithmetic", "gt":"arithmetic", 
        "eq":"arithmetic", "leq":"arithmetic", 
        "geq":"arithmetic", 
        "push":"memory", "pop":"memory"]; 

    binary_ops = ["add", "sub", "and", "or"]; 
    unary_ops = ["not", "neg"]; 
    comp_ops = ["lt", "gt", "eq", "leq", "geq"]; 
} 

bool is_in(string s, string[] list) { 
    foreach (str; list) 
     if (str==s) return true; 
    return false; 
} 

void build_strings() { 
    start = "@SP\nAM=M-1\n"; 
    end = "@SP\nM=M+1\n"; 

    binary_template = start ~ "D=M\n" 
    "@SP\n" 
    "AM=M-1\n" 
    "M=M%sD\n" ~ end; 

    unary_template = start ~ "M=%sM\n" ~ end; 

    comp_template = start ~ "D=M\n" 
    "@SP\n" 
    "AM=M-1\n" 
    "D=M-D\n" 
    "@COMP.%s.TRUE\n" 
    "D;%s\n" 
    "@COMP.%s.FALSE\n" 
    "0;JMP\n" 
    "(COMP.%s.TRUE)\n" 
    "@SP\n" 
    "A=M\n" 
    "M=-1\n" 
    "@SP\n" 
    "M=M+1\n" 
    "@COMP.%s.END\n" 
    "0;JMP\n" 
    "(COMP.%s.FALSE)\n" 
    "@SP\n" 
    "A=M\n" 
    "M=0\n" ~ end ~ "(COMP.%s.END)\n"; 

    push_tail_template = "@SP\n" 
    "A=M\n" 
    "M=D\n" 
    "@SP\n" 
    "M=M+1\n"; 

    push_const_template = "@%s\nD=A\n" ~ push_tail_template; 

    push_var_template = "@%s\n" 
    "D=A\n" 
    "@%s\n" 
    "A=%s+D\n" 
    "D=M\n" ~ push_tail_template; 

    push_staticpointer_template = "@%s\nD=M\n" ~ push_tail_template; 

    pop_template = "@%s\n" 
    "D=A\n" 
    "@%s\n" 
    "D=%s+D\n" 
    "@R13\n" 
    "M=D\n" 
    "@SP\n" 
    "AM=M-1\n" 
    "D=M\n" 
    "@R13\n" 
    "A=M\n" 
    "M=D\n"; 

    pop_staticpointer_template = "@SP\n" 
    "AM=M-1\n" 
    "D=M\n" 
    "@%s\n" 
    "M=D"; 
} 

void init() { 
    op_count = 0; 
    line_count = 0; 
    output = ["// Assembly file generated by my awesome VM compiler\n"]; 
    build_strings(); 
    build_dictionaries(); 
} 

string compile_operation(string op) { 
    if (op.length == 0 || op[0..2] == "//") 
     return ""; 
    string operation = op.split()[0]; 
    string header = "// '" ~ op ~ "' (line " ~ to!string(line_count) ~ ")\n"; 
    ++line_count; 

    if (type_dict[operation] == "arithmetic") 
     return header ~ compile_arithmetic(op); 
    else 
     return header ~ compile_memory(op); 
} 

string compile_arithmetic(string op) { 
    if (is_in(op, comp_ops)) { 
     string out_string = format(comp_template, op_count, operations_dict[op], op_count, 
      op_count, op_count, op_count, op_count); 
     op_count += 1; 
     return out_string; 
    } else if (is_in(op, unary_ops)) 
     return format(unary_template, operations_dict[op]); 
    else 
     return format(binary_template, operations_dict[op]); 
} 

string compile_memory(string op) { 
    string[] instructions = op.split(); 
    string inst = instructions[0]; 
    string argtype = instructions[1]; 
    int val = to!int(instructions[2]); 
    if (inst == "push") { 
     if (argtype == "constant") { 
      return format(push_const_template, val); 
     } else if (argtype == "static") 
      return format(push_staticpointer_template, ("f." ~ to!string(val))); 
     else if (argtype == "pointer") 
      if (val == 0) 
       return format(push_staticpointer_template, "THIS"); 
      else 
       return format(push_staticpointer_template, "THAT"); 
     else 
      return format(push_var_template, val, vars_dict[argtype][0], vars_dict[argtype][1]); 
    } else { 
     if (argtype != "constant") { 
      if (argtype == "static") 
       return format(pop_staticpointer_template, ("f." ~ to!string(val))); 
      else if (argtype == "pointer") { 
       if (val == 0) 
        return format(pop_staticpointer_template, "THIS"); 
       else 
        return format(pop_staticpointer_template, "THAT"); 
      } 
      else 
       return format(pop_template, val, vars_dict[argtype][0], vars_dict[argtype][1]); 
     } else { 
      return ""; 
     } 
    } 
} 

void main(string args[]) { 
    init(); 
    if (args.length < 2) { 
     writefln("usage: %s <filename>", args[0]); 
     exit(0); 
    } 
    string inputfname = args[1]; 
    string outputfname = args[1].split(".")[0] ~ ".asm"; 

    auto inputf = File(inputfname, "r"); 
    output ~= format("// Input filename: %s\n", inputfname); 
    foreach (line; inputf.byLine) { 
     output ~= compile_operation(to!string(line).strip); 
    } 
    inputf.close(); 

    auto outputf = File(outputfname, "w"); 
    foreach (outl; output) 
     outputf.write(outl); 

    outputf.write("(END)\n@END\n0;JMP"); 
    outputf.close(); 
    writeln("Compilation successful. Output written to " ~ outputfname); 
} 

Answer 1

Für output variablen Einsatz Appender (docs):

import std.array : appender; 

void main() { 
    auto output = appender!string("// Assembly file generated by my awesome VM compiler\n"); 
    //... 
    output.put(format("// Input filename: %s\n", inputfname)); 
    foreach (line; inputf.byLine) { 
     output.put(compile_operation(line.to!string().strip())); 
    } 
    //... 
    outputf.write(output.data()); 
    //... 
} 

auch, schlage ich vor, dass Sie Ihre type_dict zu so etwas wie int[string] und es mit integer verwenden Konstanten ändern sollte.

int[string] type_dict; 

const TYPE_ARITHMETIC = 0, 
    TYPE_MEMORY = 1; 

//... 
type_dict = ["add": TYPE_ARITHMETIC, "push": TYPE_MEMORY]; // etc 
//... 

//... 
if (type_dict[operation] == TYPE_ARITHMETIC) { 
    //... 
} 
//... 

Verwenden canFind Methode (docs) anstelle von benutzerdefinierten is_in. Oder versuchen Sie es einmal mit SortedRange (docs).

Answer 2

Vielleicht möchten Sie versuchen, die Anzahl der Zuweisungen mit std.array.appender für die Ausgabe statt Array Verkettung in Ihre Hauptfunktion als appender minimiert und ist generell zum Anhängen optimiert Sie können auch mit reserve experimentieren.

//Note: untested code 
import std.array; 
auto output = appender!string(); 

void init() { 
    ... 
    output.put("// Assembly file generated by my awesome VM compiler\n"); 
    ... 
} 

void main() { 
    ... 
    output.put(format("// Input filename: %s\n", inputfname)); 
    foreach (line; inputf.byLine) { 
     output.put(compile_operation(to!string(line).strip)); 
    } 
    ... 
    foreach (outl; output.data) 
     outputf.write(outl); 
    ... 
}