5

私が取っているコンピューター システム コース (nand2tetris カリキュラムを使用) 用に、仮想マシン言語からアセンブリへのトランスレーターを作成しました。元々は Python で書いていたのですが、D を学んでいるので翻訳しようと思いました。D は構文的に Python にかなり近いので、それほど難しくはありませんでした。私は、D はパフォーマンス言語であり、コンパイル済みであるため、少なくとも Python と同じくらい高速で、大きなファイルでははるかに高速であると想定していました。しかし、真逆です！同一のアルゴリズムにもかかわらず、コンパイルする非常に大きなファイルを構築した場合、D は常に python よりもわずかに遅く実行されました。約 500000 行の長さのファイルでは、python は一貫して完了までに約 2.6 秒かかりましたが、D は一貫して約 3 秒かかりました。

Python が実際に D よりも全体的に高速であると考えるほど単純であるとは言いたくありません。ただし、この例では、少なくとも D は直感的に高速ではないようです。私の D コードでパフォーマンスが低下する可能性のある原因について、いくつかの意見をいただければ幸いです。ボトルネックはIO操作にあるのではないかと思いますが、よくわかりません。

ソースコードは以下です。詳細はそれほど重要ではありません。いくつかのアセンブリ言語テンプレートが割り当てられた後、仮想マシン言語を介した線形パスが存在し、各命令がアセンブリ コードの同等のブロックに変換されます。

編集:を使用して D コードを再コンパイルした後dmd -O -release -inline -m64、D は入力で 2.20 秒の時間で勝者になります。しかし、ほとんど同じコードを使用しているのに、なぜ D は Python よりもパフォーマンスが遅いように見えるのかという疑問が残ります。

編集 2:以下のアドバイスを使用して、文字列の単純なリストの使用から の使用に切り替えappender!string()、時間を大幅に改善しました。ただし、 に大量の文字列がある場合は、次のようなコマンドでそれらをファイルに書き込まないappenderでください。

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

代わりに、次のように記述します。

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

2 番目の例では、単純なstring[]. しかし、最初のものを使用すると、パフォーマンスが大幅に向上し、実行時間が 2 倍になりました。

に変更すると、前述の大きなファイルのコンパイルappender!string()には (Python の 2.8 に対して) 約 2.75 秒かかりましたが、元のファイルでは約 3秒かかりました。:)dmd1.98

パイソン:

#!/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);
}
4

2 に答える 2

6

output変数の使用( Appenderdocs ) :

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());
   //...
}

type_dictまた、を次のように変更しint[string]て、整数定数で使用することをお勧めします。

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) {
    //...
}
//...

カスタムの代わりにcanFindメソッド (ドキュメント) を使用しますis_in。または試してみてくださいSortedRange（docs）。

于 2013-02-11T23:14:24.350 に答える
0

割り当ての数を最小限に抑え、通常は追加用に最適化されるため、std.array.appenderメイン関数で配列連結の代わりに for outputを使用してみることをお勧めします。appenderを試すこともできますreserve。

//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);
   ...
}
于 2013-02-11T16:24:49.853 に答える