StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POPython faster than D?? IO operations seem to slow D down a lot... what's going on?
text
Body
copied!<p>I wrote a virtual machine language to assembly translator for a computer systems course I'm taking (using the nand2tetris curriculum). I originally wrote it in Python, but since I'm learning D, I thought I'd translate it. D is fairly close to Python syntactically, so it wasn't too difficult. I assumed that D, being a performance language and compiled, would be at least as fast as Python and on a large file, would be much faster. But the opposite is true! Despite identical algorithms, D consistently performed slightly slower than python when I constructed a very large file to compile. On a file approximately 500000 lines long, python consistently took about 2.6 seconds to complete, while D consistently took about 3. This isn't an enormous gap, but it's notable that python would be at all faster.</p> <p>I don't want to suggest that I'm naive enough to think that python is actually faster than D overall; however, in this instance it seems at the very least that D is not intuitively faster. I'd appreciate some input on possible sources of performance decreases in my D code. I think the bottleneck might be on IO operations, but I'm not sure.</p> <p>The source code is below. The details aren't that important; some assembly language templates are allocated and then there's a linear pass through the virtual machine language, translating each instruction to an equivalent block of assembly code.</p> <p><strong>EDIT:</strong> after recompiling the D code using <code>dmd -O -release -inline -m64</code>, D comes out the victor with a time of 2.20s on the input. However, the question still remains of why with almost identical code, D seems to perform slower than python.</p> <p><strong>EDIT 2:</strong> using the advice from below, I switched from using a simple list of strings, to using an <code>appender!string()</code>, and improved the time by a noticeable amount. It's worth mentioning however, that if you have a bunch of strings in an <code>appender</code>, <strong>do not</strong> write them to a file with a command like:</p> <pre><code>auto outputfile = File("foo.txt","w"); foreach(str; my_appender.data) outputfile.write(str); </code></pre> <p>Rather instead, write something like:</p> <pre><code>auto outputfile = File("foo.txt","w"); outputfile.write(my_appender.data); </code></pre> <p>The second example will give you a small performance increase over using a simple <code>string[]</code>. But using the first one gave me a huge performance hit, doubling the execution time.</p> <p>Changing to an <code>appender!string()</code>, the compilation of the aforementioned large file took about 2.75 seconds (to Python's 2.8), where the original had taken about 3. Doing this, and also using the optimization flags in <code>dmd</code>, gave a total compilation time of <code>1.98</code> seconds! :)</p> <p>Python:</p> <pre><code>#!/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() </code></pre> <p>D:</p> <pre><code>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); } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload