2016q3 Homework jit-compiler

contributed by <kaizsv>

閱讀資料

廖健富同學的筆記紀錄了 DynAsm 及 Compiler, Interpreter, JIT的差異。

詳細閱讀第三方 DynAsm 教學及所有 DynAsm 指令，試著找出作業可能會用到的指令。

jit-x64 優化

參考我去年的筆記，去年的github這次只做2種優化。原本的數據如下。

prog	ms
awib.b	93.7
mandelbrot.b	4059.5
hanoi.b	10017.6

縮減連續的 `< > - +`

prog	ms
awib.b	52.0
mandelbrot.b	1324.2
hanoi.b	4946.2

int contraction(char **p)
{
	char target = **p;
	int offset = 1;

	(*p)++;

	// ignore character that is not brainfuck operator
	while (**p == target || !strchr("<>,.+-[]", **p)) {
		offset = (**p == target) ? offset + 1 : offset;
		(*p)++;
	}

	(*p)--;

	return offset;
}

除了找連續的< > - +外，原始碼可能存在 brainfuck operator 之外的字元，例如空白鍵，因此這裡多了一個strchr()的判斷忽略 brainfuck 以外的 operator。跟原始版比起來大約提升了 1倍。

clear loop pattern `[-]`

prog	ms
awib.b	43.2
mandelbrot.b	1292.5
hanoi.b	139.5

int clear_loop(char *p)
{
	return (*(p+1) == '-' && *(p+2) == ']');
}

尋找簡單的 clear loop pattern [-]，直接把該位置設成 0，在hanoi.b優化的較明顯，大約提升了 70 倍。

去年還有做其它的 pattern 有進一步的效能提升，這次把重心放在 concurrency / parallelism。

concurrency / parallelism

我寫不出來，紀錄下我看不懂的地方。

bukkake - parallel brainfuck

先看bukkake.c，它多加了三個運算子。

*: 會呼叫threadpool_spawn在 thread pool 產生一個 thread
\n: 會呼叫到bu_close bu_exit，但還看不懂實際的作用，官網的解釋為離開 thread
|: barrier 帶有一個 mutex lock，可以 block 住目前的 thread 直到所有 thread 完成

for (pc = 0; pc < filestatus.st_size; pc++) {
    if (exec[pc] == '\n') {
        num_rows++;
        column = 0;
        continue;
    } else if (num_rows == 0 && exec[pc] == '*') {
        has_spawns = 1;
    }
    column += 1;
    if (column > longest_row) {
         longest_row = column;
    }
}

JIT 會先對檔案做前處理，先