contributed by <tundergod
>, <tempo jiji
>
sudo apt-get update
sudo apt-get install build-essential
sudo apt-get install gcc-5-multilib
sudo apt-get install lua5.2 lua-bitop
sudo apt-get install gcc-arm-linux-gnueabihf
sudo apt-get install qemu-user
make bench-jit-x64
progs/awib.b GOOD 111.3ms
progs/mandelbrot.b GOOD 4241.5ms
progs/hanoi.b GOOD 10967.4ms
- 中英文字間記得以空白隔開!
- 請更新分組頁面中的 github 連結
課程助教
Compiler:
Interpreter:
Jit-compiler(Just-in-time compiler):
BrainFuck透過一個data pointer
在一連串的data cell
裏進行不同的指令:
>
: data pointer往右移動
<
: data pointer往左移動
+
: 對data pointer目前所在的位置的資料加上1 byte
-
: 對data pointer目前所在的位置的資料減去1 byte
.
: 輸出data pointer目前所在位置的資料
,
: 輸入資料並存入data pointer目前的所在位置
[
: 如果data pointer目前的資料是0,那就跳到對應的]
的後一條指令。如果不是0,就繼續執行
]
: 無條件跳往之前對應的[
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>>.+++.------.--------.>+.>.
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
先把第一個元素的值+10再跑while迴圈[->+<]
作業上提到了6種的優化建議:
contraction:
+
,-
,<
,>
都整合成一條指令
for (char *p = read_file(argv[1]); *p; p++) {
unsigned int count = 1;//count at least be 1 because read an sym first
switch (*p) {
case '>':
while(*(++p) == '>')
count++;
*p--;
| add PTR, count
break;
......
}
}
+
,-
,<
,>
的case都依照上面的方法改進之後的效能:
progs/awib.b GOOD 59.9ms
progs/mandelbrot.b GOOD 1396.4ms
progs/hanoi.b GOOD 5478.8ms
Clear loops
[-]
的迭代改寫成*ptr = 0
case '[':
if (top == limit) err("Nesting too deep.");
if( *(p+1) == '-' && *(p+2) == ']'){
p += 2;
| mov byte[PTR], 0
}
progs/awib.b GOOD 91.9ms
progs/mandelbrot.b GOOD 4154.4ms
progs/hanoi.b GOOD 4606.7ms
Copy loops
[->+<]
運算式(第一個cell的值加到第二個去)改寫成 if( *(p+1) == '-' && *(p+2) == '>' && *(p+3)=='+' && *(p+4) == '<' && *(p+5) == ']'){
p += 5;
| mov al, byte[PTR]
| add byte[PTR+1], al
| mov byte[PTR], 0
break;
}
修改後的效能爲:
progs/awib.b GOOD 103.4ms
progs/mandelbrot.b GOOD 4271.1ms
progs/hanoi.b GOOD 10785.5ms
完全看不到任何的效果,這是因爲在測試程式中的[->+<]
太少了,分別爲12個,13個和53個
查看程式碼發現[->+<]
的數量非常少,反而位移兩次以上的非常多,就嘗試把所有[->>....+<<....]
都整合起來
//[->>...+...<<]
if( *(p+1) == '-' && *(p+2) == '>'){
unsigned int countsym = 1;
int n = 3;
while( *(p + n) == '>'){
countsym++;
n++;
}
if( *(p+2+countsym+1) == '+' && *(p + 2*countsym + 3) == ']'){
p = p + 3 + 2 * countsym;
| mov al, byte[PTR]
| add byte[PTR + countsym], al
| mov byte[PTR], 0
break;
}
發現執行時間更加慢了:
progs/awib.b GOOD 100.4ms
progs/mandelbrot.b GOOD 4274.0ms
progs/hanoi.b GOOD 11279.5ms
Multiplication loops
+++[->+++<]
Operation offsets
Scan loops
先把contraction,clear,copy的結合起來,執行時間爲:
progs/awib.b GOOD 48.7ms
progs/mandelbrot.b GOOD 1332.3ms
progs/hanoi.b GOOD 162.1ms
tundergod
tempo jiji
sysprog21
jit-compiler