Leo's blog

建议麦当劳

一直觉得应该找一个形式把读过的论文以除了组会分享报告之外的形式记录下来。最近看到同学的论文阅读分享,终于决定也开始写blog。

今天看的这篇是 Self-Instruct , 是最近很火的 instruct tuning(给LLM增加 follow instruct 的能力)方法。之前InstructGPT等方法都是需要人工标注的instruct数据(在SFT阶段),这篇工作提出,既然LLM的能力已经足够强,只需要构造Prompt,从LLM中挖掘instruct信息,从而来tune自己。

本质上,作者证明了『可以从 few-shot 能力很强的LLM来bootstrap出一套 SFT 数据集,从而得到 zero-shot 或者说 Instruct-tuned LLM』。

作者来自华盛顿大学,感觉是要投今年的ACL。他们声称用GPT3达到了类似 text-davinci-001 (仅SFT的InstructGPT)的效果,比用 SuperNaturalInstructions 数据集训练的效果类似。这篇文章发布于22年12月,当时chatgpt刚发布不久,所以只对比了 InstructGPT?(好像跟ChatGPT也没法比)。

Stanford 也用这个方法,用 text davinci 003 造了个数据集后基于 LLaMa 训练了 Alpaca 模型,在7B这样一个参数量下达到了相当惊艳的效果。这也是证明 instruct tuning 不需要花很多钱就能做到的一个证据?Alpaca开源了他们生成的52k个instruction,这可能是 llm 的 stable diffusion moment 的开端?

Introduction

作者先讲了最近大家都在做 instruction tuning 的工作,说现在的方法都需要人工构建instruct数据集。于是,他们提出self-instruct方法,视图让LLM自我构建一个 instruct 的数据集,来做到自己训练自己:从一个很短的(175个)人手写的数据集来bootstrap,主要有一下步骤:

  1. 要求模型生成新任务的instruction
    1. 利用现有的任务描述,让模型生成新的任务和新的指令。通常,模型会定义一些新的任务出来
  2. 生成 input-output pair
  3. 过滤掉重复的和低质量的pair
  4. 然后把他们添加到 task pool 中
    方法结构图

总结一下贡献:

  1. 提出 self-instruct 方法
  2. 跑了很多实验来证实有效性
  3. 开放了52k个instructions
    1. (alpaca 开放了用同样方法构建的、基于text-davinci-003的数据)

Method

Instruction Generation

第一步是生成一些新的task和instruction。他们使用以下的prompt来生成:

1
2
3
4
5
6
7
Come up with a series of tasks:

Task1: {from pool}
Task2: {from pool}
...
Task8: {from pool}
Task9:

简单来讲就是让模型进行 in-context learning. 用175个人写的instruction来初始化 task pool,之后每次随机选6个人写的和2个机器生成的task来生成新的task。

Classification Task Identification

因为后续的步骤对于 Classification 任务和其他任务的处理方法不同(在这里,他们把 有有限的、小的输出label集合的任务定义为分类任务),他们用了原版GPT3的few shot learning 来做这个分类,用了12个分类任务的instruction和19个非分类任务的instruction作为prompt。

Instance Generation

第三步是用task来生成一些任务的 input-output pair。作者认为,传统的方法先生成input再生成output,在分类任务上会有类别不平衡的问题。所以,对于分类任务,他们用了 output-first 的方法:先生成可能的label,再根据这些label生成可能的输入。

Filtering and Post-processing

为了保证instruct的多样性,他们仅当新的instruction和旧的的 rouge-l 分数小于 0.7 时才会把它加入到 task pool 中。同时,他们排除了常见的llm无法解决的问题的关键词(image等)。最后,在生成 instance 的时候,他们去掉了完全相同的或者有相同input的。

Finetuning the LM

最后一步是用这些数据来finetune LM。 为了保证鲁棒性,他们混和多种prompt(如是否添加 Task: 等)。

实验结果

作者先在 super-naturalinstructions 数据集上跑了和 t0、gpt3的对比试验,发现加上self-instruct后效果先祖很好、能和instructGPT接近。

同时,在一套新的instruct set 上进行了人工评分:

效果和 InstructGPT_001 类似。

结论

作者证明了可以用 LLM 来生成自己的训练数据,也就是说,只需要花几百刀(作者说用了$338左右)来调用OpenAI的API就可以复现一个InstructGPT。同时,后续stanford释出的数据集和alpaca模型也都证明了这个方法的有效性。

作者自己说,缺点包括会强化LLM的bias(如性别、种族等)。我感觉,是否能改善LLM的safeness也许要更多试验。

下面是我在这学期的《编译原理》课程的作业。记录在此,请读者批评指正!

基础软件包括什么?回答这个问题,只需要看计算机科学与技术专业的本科生学的四大基础课程:《计算机组成原理》、《数据库原理》、《操作系统》、《编译原理》。在计算机相关的任何应用都无法脱离这四门基础课程的知识,同理,计算机在工程领域的软件中,EDA软件、数据库、操作系统以及编译器是四种最基础的基础软件。下面,本文以世界以及中国的编译器软件为例讨论我国基础软件现状。

国际上,知名的编译器有 GNU (Gnu is Not Unix) 组织的 『GCC (the GNU Compiler Collection)』是Linux中最知名的编译器,也是世界范围内应用最广泛的编译器,支持C、C++、Objective-C、Fortran等多种语言。由UIUC研发,并被苹果公司广泛应用的『LLVM编译基础设施(Low-Level Virtual Machine Compiler Infrastructure)』通过分离编译器前后端并通过LLVM这一中间语言桥接,实现了多种语言与ISA支持,并提供强大的优化能力。除了上述两个开源的编译器之外,也有大量闭源的编译器被广泛应用:由Intel公司开发的 『ICC (Intel C++ Compiler)』主要面向Intel平台,由于其出色的定向(面向Intel x86和amd64架构CPU)的优化能力以及向量化(vectorization)能力,被广泛应用在HPC场景。由微软公司开发的『MSVC(MicroSoft Virtual C++)』主要面向Win/x86场景,随后适配amd64以及arm32、arm64架构,作为Win 32开发的主要编译器,也得到了广泛的应用。

更现代的语言在实现能够自举的编译器时,主要有两种思路。第一种是如Go语言,从0开始实现编译器,没有任何依赖,甚至不依赖于系统汇编器,而是自己实现了一套全新的汇编器。第二种是如Rust语言,实现面向LLVM中间语言的编译器前端,使得可以直接适配LLVM所支持的所有ISA,并获得其优秀的优化能力。也正因如此,rustc的工程量十分小,但是其输出的LLVM的质量显著低,使得在编译一个同样的程序时,其相比与GCC系列编译器的速度慢5-10倍[1]。同时,一些新的语言也同时采用两种方式,如微软公司的TypeScript语言,可以通过其编译器配合巴别塔(the BabelJS)转译为JavaScript,也可以通过另一个编译器编译为运行在嵌入式设备上的二进制代码。这俩类思路各有利弊,前者工程量更大,需要自己支持各类ISA以及各类优化,但是更为自由。后者程序产物需要依赖现有工具链,但是工程量更小,开发更为便捷。

现有的『国产』编译器中,『太极(Taichi)』[2]收获了很多的关注。作为一门领域特定的编程语言(Domain Specific Programming Language),其具有优秀的GPU开发能力,相较CUDA等传统库,更容易上手、使用。另一个获得广泛关注乃至争议的语言是『木兰』。木兰作为一款面向嵌入式平台的小型编译器,由于在宣传上的失误以及广大群众对于『中芯』等项目的恐惧,木兰受到了很大的批评以及指责。笔者个人认为,单从技术上来看,在面向嵌入式平台的同时提供基于Python的『套皮』模拟器,是十分正常且合理的,并不能因其使用了Python而受到批评。

由此可见,对于基础语言(如C++、C)的编译器,我国还是显著依赖于世界范围内的开源编译器,并没有实现真正的『自主』。那么,下一个需要讨论的问题就是使用开源编译器『安全』吗?如果不经过任何代码审计就拿来使用,显然是不安全的。无论是在编译的生成结果中嵌入恶意代码,还是在标准库中故意暴露漏洞,都有可能对软件造成很大的破坏。比如,对于安全要求较高的地方,如OpenSSL等密码学库,都不依赖于标准库提供的随机数生成器,而是选择自己实现随机数生成器(密码学的大部分算法都要求随机数具有足够的熵。如果随机数不够强,攻击者就可以找到攻击向量)。

但是,对于一个平台,除非从硬件到固件到软件都是自主设计或者经过安全审计的,否则总有一些环节需要『信任』。如,在上述的例子中,OpenSSL选择不信任编译器标准库提供的随机数(定然,也一定程度上因为功能性和强度的需求),选择自己实现随机数生成器。但是,在生成随机数的算法依赖与操作系统提供的真随机数作为种子。凭什么说操作系统提供的真随机数种子是可以信任的呢?如果使用在线服务生成真随机数(如random.org声称提供基于大气噪音生成的真随机数),又凭什么说这些服务是可以信任的呢?如果依赖CPU硬件提供的、基于电气热噪声的随机数,也同样存在这个信任问题。对于开源操作系统提供的基于用户输入的真随机数,可以通过审计操作系统源码的方式来确保真实性,但是其他随机数生成方式仍然存在信任问题。因此,大公司往往采用自主设计的随机数生成硬件来采样随机数,避免暴露攻击向量给攻击者,如Cloudflare公司提供SSL服务,需要大量的、具有足够熵的随机数,因此其采用自主设计的『熔岩灯随机数(LavaRand)』[3]硬件生成随机数。

『生成可信的随机数』这个小问题都有如此复杂的信任问题,更不要说复杂问题以及完整的工程的信任问题了。如,现有的操作系统提供的对于应用程序安全性全部依赖于CPU硬件提供的内核态与应用态的隔离,但是如果CPU本身是不可信的呢?Intel x86前日爆出一个隐藏的,用于修改微码的指令[4]。该指令虽然对于现有系统的安全性没有危害,但是不禁引人思考:如果CPU中有一个隐藏的指令,可以不经授权直接从用户态提升到内核态,那么现代操作系统提供的所有安全保证都会像气球一样,一触即溃。

既然如此,那么,是否有必要投入编译器等基础软件的开发呢?经过以上的讨论,答案显然是『有』。对于已有成熟开源产品的应用场景,如编译器或操作系统,我们可以采取审计源码的方式,维护一个我们可控的分支。对于没有成熟开源产品的领域,如EDA软件,我们则要投入精力开发。面向消费领域,可能实现很高的安全性没有很大的意义,但是对于国防领域和科研领域,安全性则是重中之重。但是,实现自主的这条路任重而道远。我们通过自主实现编译器、汇编器、链接器,实现了编译软件的可控,接下来要面对的就是操作系统的安全问题;我们通过编写操作系统或者审计操作系统源码来保证操作系统的安全性,接下来要面对的就是CPU的安全问题;我们通过自主实现CPU来保证安全性,接下来还要面对外设的安全性问题:如果网卡中有后门怎么办?由此可见,在追求安全、可控的道路上没有终点。现有来看,基础软件中,开源编译器、操作系统、数据库等不存在所谓『卡脖子』问题,但是如EDA等工程领域的软件,我们仍然受制于人(如中芯和海思等,被列入实体清单后无法使用EDA软件)。但是,尽管过程艰难,最终的目标仍然是有必要的,需要坚持的走下去。

笔者一直以来关注国产软件和硬件的开发,见证了汉芯、龙芯、木兰、太极等项目的兴衰,一直想总结一下个人对于这方面的观点。这次借助作业这个机会,有感而发,陈述一下自己的观点,不知不觉已经写了这么多。请老师同学们批评指正!


  1. Why does rust compile a simple program 5-10 times slower than gcc/clang? - stack overflow[EB/OL]. https://stackoverflow.com/questions/37362640/why-does-rust-compile-a-simple-program-5-10-times -slower-than-gcc-clang/37365065. ↩︎

  2. HU Y. The taichi programming language[C/OL]//SIGGRAPH ’20: ACM SIGGRAPH 2020 Courses. Association for Computing Machinery, 2020: 1–50. https://doi.org/10.1145/3388769.3407493. ↩︎

  3. Randomness 101: Lavarand in production[EB/OL]. https://blog.cloudflare.com/randomness-101-lav arand-in-production/. ↩︎

  4. Undocumented x86 instructions in intel cpus that can modify microcode | hacker news[EB/OL]. https: //news.ycombinator.com/item?id=26519693. ↩︎

随想 有关乱码

首先给出几种常见『乱码』:

1
2
3
4
5
6
md5 378e3ce9f0c8243012cb32cedde1ad31
sha1 b4d254b6620924a05e95bf76f5dace64edcf9086
sha256 3e9818cc4bf74e65419e72f89104dca674dcb215c1487dd25fed541cd6363d72
base32 MNUGC3THNJUWC3TMOVQW43LBBI======
base64 Y2hhbmdqaWFubHVhbm1hCg==
密码哈希函数 $2y$10$P5DEiAiuSr0XT9085ioTQeIW9QrrnGEkSvdJSPmlGDnvcANlvFDwm

本文的重点不在于怎么判断常见乱码,但是还是简单介绍一下:

  • $$分割的,可能是密码哈希函数的输出或者是JWT
  • 后面可能有=,内容是字母和+/或者-_,可能是base64系列。如果只有大、小写字母,可能是base32。如果有+/,是传统base64 or base32。如果有-_,是urlsafe的base64 or base32
  • base64解码后的内容如果不是utf-8,可能是哈希函数的输出。看长度(多少bit)
  • hex看长度。常见的md5和sha系列哈希的长度。

正视『乱码』

之前一直觉得『乱码』这个词被滥用了。

遇到一串自己看不懂的东西,就把他称为『乱码』。我一直觉得这个词不太合适,因为这串东西在别人眼里很可能是能看懂的,有意义的。但是,我本人一直也找不到一个非常恰当的称呼,因此一直没有在意。

直到某次给Golang提issue的时候,Google的工作人员分析我的程序,看到一串『乱码』。他是这么描述的:

image-20211129110312524

『这个字符串在我来看是乱码,你知道是什么吗?』

确实,用『我看来是乱码』一词形容无疑更为准确。由于对密码哈希函数的不熟悉(也十分正常),看不出这串字符串是什么,但是无疑,它是有意义的,不是无意义的。

为什么今天突然想到写这个东西呢?总有一些人,认为这串东西自己看不懂就没有意义。有一次和别人一起调试一个程序的时候,他描述我的程序『输出了乱码』。在我反复多次强调『让我看看输出』之后,仍然坚持认为乱码没有意义,没有发给我看。实际上,那段程序输出的就是形如$2y$10$P5DEi...的哈希值。

所以,当别人的程序输出了一些我们看不懂的东西的时候,不要只描述为『输出乱码』,请复制乱码内容,一起询问可能能看出这是什么的人。

个人题解,和比赛官方无关,仅供参考

Changing problem statement during contest

It is well known that we should not change the problem statement during the contest. But, we also know that a company named “Hua***” liked to change problem statement during the contest .

There were some breathtaking errors in the problem statements during the 2021 ICPC Asia Regionals Online Contest (I). So, naturally, we needed to change these statements.

For example, problem A needs change. As we all know, the word “lexicographic” means "order of the dictionary(字典序), ‘a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols.’ ", but somehow the person who wrote this problem misinterpreted the word as “ascending”.

Naturally, during reasonable contests, what he needs to do is to update the testcase data, changing it from ascending order to lexicographic order, matching the problem statement, then rejudge all submissions of
this problem. But, he doesn’t think it that way. “Why changing testcase data while we can change the problem statement?” Surely he didn’t know that submitting “Wrong Answer” would add penalty(罚时) to the team’s time cost. I mean, otherwise, why would he do this?

Can you help him change all “lexicographic” to “ascending”?

Input

The first line of input contains a integer $n$. $(1 \leq n \leq 100)$.

In the following $n$ lines, each line contains a string. It is guaranteed that the length of the string is less than $100$ characters, and the string only contains a to z.

Output

Output updated problem statements, replace all lexicographic by ascending.

Examples

Example 1

Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
14
print
the
labels
of
all
the
busiest
nodes
in
lexicographic
order
separated
by
spaces

Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
print
the
labels
of
all
the
busiest
nodes
in
ascending
order
separated
by
spaces

Example 2

Input

1
2
1
whoalexicographic

Output

1
whoalexicographic

In the first example, we replace “lexicographic” on the 10th line to
“ascending”.

In the second example, we do nothing because we don’t need to replace
word containing “lexicographic”.

题解

题目难度:简单。

阅读题面之后会发现是一个非常简单的字符串比较。循环 $n$ 次,每次读入一个字符串,如果是lexicographic就替换为ascending就好了。

标准答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <string.h>
int main() {
char input_string[101];
// 注意,存储长度为100的字符串,数组长度需要是101
const char *lexicographic = "lexicographic";
int n;
scanf("%d", &n);
for(int i = 0; i < n; ++ i) {
// scanf 传入的是地址
// input_string 是数组名字,本身就是地址,不需要加
// 取地址符 &
// 了解更多: https://zh.cppreference.com/w/c/language/array
scanf("%s", input_string);
if (strcmp(input_string, lexicographic) == 0) {
// 相等,输出ascending
printf("ascending\n");
} else {
// 不相等,原样输出
printf("%s\n", input_string);
}
}
// 别忘了return 0
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
while (n--) {
// 定义字符串 a
string a;
// 读入
cin >> a;
// 如果等于lexicographic,就替换为ascending
if (a == "lexicographic") {
a = "ascending";
}
// 输出
cout << a << endl;
}
return 0;
}

建议麦当劳。

最近经常说这句话。发现,在很多时候麦当劳都是几个人聚餐的最优解:

  • 可能有回民
  • 可能有人不吃辣、醋
  • 可能有人不吃鱼羊海鲜

绝大部分情况下,麦当劳都覆盖了至少一部分一个人爱吃的东西。因此,本站的description改成:

建议麦当劳。

PS: 发现过去一年我吃了至少5000元的麦当劳。

背景

最近在校内部署了我们开发的EduOJ以供数据结构与算法课程使用。OJ中使用了 clang 编译器以避免gcc编译器造成的坑(如#include</dev/random>能卡死编译器,以及某段很短的代码能产生数G的错误日志)。同时,按照惯例,开启了O2优化。

上线后不久,很多同学反映说OJ不好用。我问咋回事儿,同学说代码本地运行都是对的,提交到平台上之后就是错的了。相关代码片段如下:

  1. 这段代码运行结果和本地不一样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (head->next != nullptr) {
if (cnt == m) {
cout << p->data << ' ';

// del 是代码作者定义的一个函数,里面调用了
// delete p
del(p);
cnt = 0;
} else {
cnt += 1;
if (p->next != nullptr) {
p = p->next;
} else {
p = head->next;
}
}
}

可以看到,他在delete p后还访问了p->next

  1. 这段更离谱:
1
2
3
4
5
6
7
8
template<typename T> bool ArrayList<T>::append(T const& value) {
if(_size >= _capacity){ // border check;
cout<<"SIZE "<<_size<<" CAP "<<_capacity;
cout << " The List is overflow!" << endl;
return false;
}
_elem[_size++] = value;
}

会输出SIZE 0 CAP 2000 The List is overflow!

看到这里,你可能已经急了。明明size0cap2000,为什么if里的size >= cap会成立呢?先别急,接着看下面的代码:

  1. 这段代码很难找出错(所以建议跳过去不看):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
int main() {
int n, s, m, j, tempt, q, k, flag;
int count = 1;
int data[2020];
cin >> n >> s >> m;
tempt = s;
for (int i = 0; i < n; i++) {
data[i] = i + 1;
}
for (; count <= n; count++) { // 主要看这个for循环
for (k = 1, q = 0; k <= m; q++) {
if (data[(tempt + q - 1) % n] != 0)
k++;
}
if (count != n) {
cout << data[(tempt + q - 2) % n];
cout << ' ';
} else {
cout << data[(tempt + q - 2) % n];
return 0;
}
data[(tempt + q - 2) % n] = 0;
for (j = 1, flag = 0; flag != 1; j++) {
if (data[(tempt + q + j - 2) % n] != 0)
flag = 1;
else
flag = 0;
}
tempt = (tempt + q + j - 2) % n;
}
return 0;
}

但是,强大的Clang编译器有各种错误检查。我们编译的时候加上“未定义行为检测器”试试:

1
2
3
4
5
6
$ clang++ a.cpp -Wall --std=c++17 -fsanitize=undefined
$ ./a.out
6 1 1 // 这行是输入的
a.cpp:14:9: runtime error: index -1 out of bounds for type 'int [2020]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior a.cpp:14:9 in
1 2 3 4 5 6

会发现这个代码访问了数组里下标为-1的地方。

上面的几段代码有什么共同点呢?为什么在平台上的执行结果就和本地不一样呢?为什么这几段代码表现出来好像“平台不好用了”呢?要回答这个问题,首先要理解“未定义行为”的概念。

什么是未定义行为

在我们学习编程的过程中,可能都知道一些行为是“非法”的,是“错误”的,比如:

  1. 数组越界访问
  2. 解引用空指针
  3. 在对象的生命周期结束后访问对象
  4. 有返回类型的函数没有从return结束

但是,我们也仅仅知道这些行为是“错误”的,并不会知道这些行为为什么错误,会造成哪些后果。这些行为在c++语言标准里有一个名字:未定义行为(undefined behavior)。如:

控制流出有返回值的函数(除了 main)的结尾而不经过 return 语句是未定义行为。

翻译成人话就是,除了main之外的函数,如果他有返回值但是不经过return语句就结尾了,行为未定义。

标准中也明确给出了未定义行为的解释:

  • 未定义行为(undefined behavior,UB)——对程序的行为无任何限制。未定义行为的例子是数组边界外的内存访问,有符号整数溢出,空指针的解引用,在一个表达式中对同一标量多于一次的中间无序列点 (C++11 前)无序 (C++11 起)的修改,通过不同类型的指针访问对象,等等。编译器不需要诊断未定义行为(尽管许多简单情形确实会得到诊断),而且所编译的程序不需要做任何有意义的事。

甚至:

翻译成人话就是,如果发生未定义行为,编译器可以把这段代码编译为任何内容,包括但不限于删除你的所有文件,帮你定一杯咖啡,或者时间旅行。**这些都是严格符合C++语言标准的。**同时,不同的编译器也会对未定义行为采取不同的策略,所以很可能未定义行为的代码在不同编译器上运行结果不同。这样定义”未定义行为“就使得编译器优化更好:很多情况下既然结果未定义,就可以没有结果,因此编译器可以去掉未定义行为发生的代码分支,把代码优化为行为确定的结果。

不理解上面那段话什么意思?没关系,我们回过来看之前的那段代码:

1
2
3
4
5
6
7
8
template<typename T> bool ArrayList<T>::append(T const& value) {
if(_size >= _capacity){ // border check;
cout<<"SIZE "<<_size<<" CAP "<<_capacity;
cout << " The List is overflow!" << endl;
return false;
}
_elem[_size++] = value;
}

这段代码中实现了一个顺序表的append方法。看上去没什么问题:由于没有实现扩容算法,在末尾插入时首先要进行边界检查。如果边界检查通过,就把value放到elem里,并size++。但是,上面说了,这段代码的运行结果是if内条件永远成立,即使后面输出的时候size0cap2000。为什么会这样呢?这是不是编译器的Bug?

其实并不是。可能你已经注意到了:这个函数最后缺少return。因此,if内条件不成立的行为未定义。编译器发现了这一点,认为程序员会保证每次调用的时候if内条件都成立(否则就会出现未定义行为),因此直接去掉了if,把代码编译成了大概这个样子:

1
2
3
4
5
template<typename T> bool ArrayList<T>::append(T const& value) {
cout<<"SIZE "<<_size<<" CAP "<<_capacity;
cout << " The List is overflow!" << endl;
return false;
}

重新回顾这个优化的过程中编译器的思路:

  1. if内条件不成立的话,行为未定义。
  2. 未定义行为不好,写代码的人会避免未定义行为。
  3. 因此,写代码的人会保证每次调用的时候if内条件均成立。
  4. 因此可以去掉if

可以发现,整个优化过程中编译器严格的遵守了C++语言标准:

  • 如果if内条件成立,这样的执行结果自然是正确的
  • 如果if内条件不成立,那么行为未定义。既然行为未定义,那任何行为都是正确的,因此我执行if内条件成立的代码也是正确的行为。

因此,错的不是编译器,是整个世界你。编译器没那么多bug,当你以为编译器出了bug,绝大部分情况下是你写了bug。

当然,go编译器里还是不少bug的,这个之后再说

因此,到现在你应该知道了什么是未定义行为。任何包括未定义行为的代码运行结果恰好符合你的预期都是巧合任何时候不应该写有未定义行为的代码未定义行为会导致代码在不同平台不同编译器上运行结果不一致

未定义行为的危害

未定义行为对于代码的危害上面已经说的差不多了。你可能会觉得:顶多代码运行结果是错的,又会怎么样呢?**NAIVE!**前面说道,当遇到未定义行为时:

编译器可以把这段代码编译为任何内容,包括但不限于删除你的所有文件,帮你定一杯咖啡,或者时间旅行。这些都是严格符合C++语言标准的。

不要以为“删除你的所有文件”是危言耸听:有人发现在clang编译器下你真的可能因为未定义行为而格式化你的硬盘:

image-20210404121149762

这段代码首先定义了一个函数f1。在这个函数中,i会不断累加,直到溢出。有符号数溢出是未定义行为。于是,编译器没有给f1生成任何代码,只生成了一个label。

从右侧的汇编可以看到,f1label下面的代码就是f2函数,这个函数会格式化你的硬盘(在这个例子并没有真的格式化,注释掉了。)学过汇编的同学可能会发现,由于f1内没有任何代码,所以调用f1会执行你本来不想执行的f2函数。BOOM!你的硬盘被格式化了。

llvm的issue tracker中有关这个 “bug”的讨论还在进行中。一部分人认为应该“修复”:

This means UB is a potential safety/security problem, and we really should do something about it.

还有一部分人认为不应该:

All sorts of UB manifests in lots of security issues, right? Buffer overruns and the like (I guess this is a buffer overrun, of sorts).

同时,有些人认为应该修复,理由是为了debug更方便。llvm的开发者回复:

It’s not generally that simple - deciding where/how to “recover” from UB would be pretty difficult.

The Clang-advised way to deal with this would be to compile with -fsanitize=undefined

https://godbolt.org/z/3aW69c

example.cpp:4:29: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type ‘int’
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior example.cpp:4:29 in

大意是已经有足够强大的未定义行为检测器了,为了方便debug来改这个UB的行为不值得。

总之,不要写未定义行为,以及当你以为编译器错了,你错了。我的OJ同理,因为就是帮你调用编译器来编译代码而已…

0%