摘要：C# 的类型系统构建在 .NET 的类型系统之上，而众所周知 .NET 是一个有具现化泛型的类型系统的平台，意味着泛型参数不仅不会被擦除，还会根据泛型参数来分发甚至特化代码。

Brainfuck 是由 Urban Müller 在 1993 年创造的一门非常精简的图灵完备的编程语言。

正所谓大道至简，这门编程语言简单到语法只有 8 个字符，每一个字符对应一个指令，用 C 语言来描述的话就是：

然后只需要提供一个已经初始化为 0 的字节数组作为内存、一个指向数组的指针、以及用于输入输出的两个字节流就能够让程序运行了。

比如 Hello World! 程序就可以写成：

既然要用 C# 类型系统来构建 Brainfuck 的编译器，我们需要首先对 C# 类型系统有一些认知。

C# 的类型系统构建在 .NET 的类型系统之上，而众所周知 .NET 是一个有具现化泛型的类型系统的平台，意味着泛型参数不仅不会被擦除，还会根据泛型参数来分发甚至特化代码。

例如：

更进一步，因为 .NET 泛型在运行时会根据类型参数对代码进行特化，比如：

我们可以前往 godbolt 看看 .NET 的编译器对上述代码产生了什么机器代码：

可以看到我代入不同的类型参数进去，会得到各自特化后的代码。

有了上面的知识，我想知道在这套类型系统之上，.NET 的编译器到底能生成多优化的代码，那接下来我们进行一些小的测试。

比如十六进制数位 0、6、C 可以分别表示为：

这里我们给 Value加了[MethodImpl(MethodImplOptions.AggressiveInlining)]确保这个方法会被编译器 inline。

如此一来，如果我们想表达一个 0x1234abcd，我们就可以用Int来表达。

这里我们同样去 godbolt 看看 .NET 编译器给我们生成了怎样的代码：

那么性能方面放心了之后，我们就可以开始搞 Brainfuck 编译器了。

Brainfuck 编译分为两个步骤，一个是解析 Brainfuck 源代码，一个是产生编译结果。

对于 Brainfuck 源代码的解析，可以说是非常的简单，从左到右扫描一遍源代码就可以，这里就不详细说了。问题是怎么产生编译结果呢？

这里我们选择使用类型来表达一个程序，因此编译结果自然也就是类型。

我们需要用类型来表达程序的结构。

Brainfuck 程序离不开 4 个基本操作：

移动指针

操作内存

输入

输出

然后我们就可以定义各种操作了。

首先是移动指针，我们用两个泛型参数分别表达移动指针的偏移量和下一个操作：

然后是操作内存：

有了上面的 4 种基本操作之后，我们就需要考虑程序控制流了。

首先，我们的程序最终毕竟是要停下来的，因此我们定义一个什么也不干的操作：

有了上面的东西，我们就可以用类型表达 Brainfuck 程序了。

我们来看看最基础的程序：Hello World!。

上面这个实现可能不是很直观，那我们换一种非常直观的实现：

这段程序很粗暴的分别把内存从左到右写成 Hello World!的每一位，然后把指针移回到开头后逐位输出。

不过这么看 Hello World! 还是太长了，不适合用来一上来就展示，我们换个简单点的输出 123：

表达这个程序的类型自然就是：

Stop>>>>>>>>>>> // 停止
这里为了简洁，我把数字全都带入了数字类型，不然会变得很长。例如实际上49应该表达为Int。AddData>>>>>>>>>>
.Run(0, stackalloc byte[8], Console.OpenStandardInput, Console.OpenStandardOutput);

即可。

我们可以借助 C# 的 Type Alias，这样我们就不需要每次运行都打那么一大长串的类型：

using Print123 = AddData>>>>>>>>>>;

Print123.Run(0, stackalloc byte[8], Console.OpenStandardInput, Console.OpenStandardOutput);

那我们上 godbolt 看看 .NET 给我们的 Brainfuck 程序产生了怎样的机器代码？

push rbp
push r15
push r14
push r13
push rbx
lea rbp, [rsp+0x20]
mov rbx, rsi
mov r15, r8
movsxd rsi, edi
add rsi, rbx
add byte ptr [rsi], 49 ; '1'
inc edi
movsxd rsi, edi
add rsi, rbx
add byte ptr [rsi], 50 ; '2'
inc edi
movsxd rsi, edi
add rsi, rbx
add byte ptr [rsi], 51 ; '3'
lea r14d, [rdi-0x02]
movsxd rsi, r14d
movzx rsi, byte ptr [rbx+rsi]
mov rdi, r15
mov rax, qword ptr [r15]
mov r13, qword ptr [rax+0x68]
call [r13]System.IO.Stream:WriteByte(ubyte):this
inc r14d
movsxd rsi, r14d

mov rdi, r15

inc r14d
movsxd rsi, r14d

mov rdi, r15

mov eax, r14d
pop rbx
pop r13
pop r14
pop r15
pop rbp
ret

这不就是

*(ptr++) = '1';
*(ptr++) = '2';
*ptr = '3';
ptr -= 2;
WriteByte(*(ptr++));
WriteByte(*(ptr++));
WriteByte(*ptr);

吗？可以看到我们代码里的抽象全都被 .NET 给优化干净了。

而前面那个不怎么直观的 Hello World! 代码则编译出：

AddData<8, Loop<
AddPointer<1, AddData<4, Loop<
AddPointer>>>>>>>>>,
AddPointer<1, AddData<1, AddPointer<1, AddData<1, AddPointer<1, AddData<-1, AddPointer<2, AddData<1,
Loop,
AddPointer>

AddPointer>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
JIT 编译

如果我们想以 JIT 的形式运行 Brainfuck 代码，那如何在运行时生成类型然后运行代码呢？我们在 .NET 中有完善的反射支持，因此完全可以做到运行时创建类型。

比如根据数字来生成数字类型：

var type = GetNum(42);

static Type GetHex(int hex)
{
return hex switch
{
0 => typeof(Hex0),
1 => typeof(Hex1),
2 => typeof(Hex2),
3 => typeof(Hex3),
4 => typeof(Hex4),
5 => typeof(Hex5),
6 => typeof(Hex6),
7 => typeof(Hex7),
8 => typeof(Hex8),
9 => typeof(Hex9),
10 => typeof(HexA),
11 => typeof(HexB),
12 => typeof(HexC),
13 => typeof(HexD),
14 => typeof(HexE),
15 => typeof(HexF),
_ => throw new ArgumentOutOfRangeException(nameof(hex)),
};
}

static Type GetNum(int num)
{
var hex0 = num & 0xF;
var hex1 = (num >>> 4) & 0xF;
var hex2 = (num >>> 8) & 0xF;
var hex3 = (num >>> 12) & 0xF;
var hex4 = (num >>> 16) & 0xF;
var hex5 = (num >>> 20) & 0xF;
var hex6 = (num >>> 24) & 0xF;
var hex7 = (num >>> 28) & 0xF;
return typeof(Int).MakeGenericType(GetHex(hex7), GetHex(hex6), GetHex(hex5), GetHex(hex4), GetHex(hex3), GetHex(hex2), GetHex(hex1), GetHex(hex0));
}

同理也可以用于生成各种程序结构上。

Runvar run = (EntryPoint)Delegate.CreateDelegate(typeof(EntryPoint), type.GetMethod("Run")!);
run(0, memory, input, output);

delegate int EntryPoint(int address, Span memory, Stream input, Stream output);
AOT 编译

那如果我不想 JIT，而是想 AOT 编译出来一个可执行文件呢？

你会发现，因为编译出的东西是类型，因此我们不仅可以在 JIT 环境下跑，还能直接把类型当作程序 AOT 编译出可执行文件！只需要编写一个入口点方法调用Runusing HelloWorld = AddData<8, Loop<
AddPointer<1, AddData<4, Loop<
AddPointer>>>>>>>>>,
AddPointer<1, AddData<1, AddPointer<1, AddData<1, AddPointer<1, AddData<-1, AddPointer<2, AddData<1,
Loop,
AddPointer>

AddPointer>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>;

static void Main
{
HelloWorld.Run(0, stackalloc byte[16], Console.OpenStandardInput, Console.OpenStandardOutput);
}

然后调用 AOT 编译：

dotnet publish -c Release -r linux-x64 /p:PublishAot=true /p:IlcInstructionSet=native /p:OptimizationPreference=Speed
即 C++ 世界里的，OptimizationPreference=Speed则是-O2运行编译后的程序就能直接输出。

这里我们采用一段用 Brainfuck 编写的 Mandelbrot 程序进行性能测试，代码见 Pastebin。

它运行之后会在屏幕上输出：

这段程序编译出来的类型也是非常的壮观：

去掉所有空格之后类型名称足足有 165,425 个字符！

这里我们采用 5 种方案来跑这段代码：

C 解释器：C 语言编写的 Brainfuck 解释器直接运行

GCC：用 Brainfuck 翻译器把 Brainfuck 代码翻译到 C 语言后，用 gcc -O3 -march=native编译出可执行程序后运行

Clang：用 Brainfuck 翻译器把 Brainfuck 代码翻译到 C 语言后，用 clang -O3 -march=native编译出可执行程序后运行

.NET JIT：通过 JIT 现场生成类型后运行，统计之前会跑几轮循环预热

.NET AOT：通过 .NET NativeAOT 编译出可执行程序后运行

测试环境：

系统：Debian GNU/Linux 12 (bookworm)

CPU：13th Gen Intel(R) Core(TM) i7-13700K

RAM：CORSAIR DDR5-6800MHz 32Gx2

项目运行时间（毫秒）排名比例C 解释器4874.658755.59GCC901.022531.03Clang881.717721.01.NET JIT925.159641.06.NET AOT872.228711.00

最后 .NET AOT 在这个项目里取得了最好的成绩，当然，这离不开 .NET 类型系统层面的零开销抽象。

来源：opendotnet

标签： 编译器 brainfuck brainfuck编译器

本文地址：http://news.43b.com.cn/a/570422.html

免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!