疫情期间的手记 Week3


已经隔离一个月多了。校内的情况已经好起来了,但是整个上海的情况比较糟糕。目前还是封校状态。

本周任务:

  • 组合作业 周五
  • 算法 贪心 下周一
  • 概率论作业
  • 高级编译 写完解释器

4.11

看了一整天 JIT,发现网上好多 demo 都是基于 brainf**k 解释器的。大概原理就是它们会找循环然后把循环给 compiled 起来成为 x86 code,执行方式是直接内嵌汇编(把这段存在内存里的 x86 code 强制转换为函数指针,跳转执行)

仍然对我们的 JIT 有点迷。我们这个应该是从 LLVM IR 入手的,JIT 生成的是 riscv assembly,那如何做这个 context switch?如果是 method-based 当然好做,但是如果基本单元是 basic block,感觉有点奇怪,而且效率不一定高吧。

不过大体的思想是知道了。话说原来高级语言的后端也叫 virtual machine,感觉很奇妙。看了一些知名虚拟机的案例,Hotspot VM 有两个 compiler,client compiler 采用的是保守的优化策略(注重 compile time),server compiler 采用的是激进的优化策略(注重 compile quality)。微软的 .NET 虚拟机叫 CLR。还有大名鼎鼎的 V8,一个 JavaScript Engine(这又是什么新名字,应该也是虚拟机),以及 oracle 最新的 graal。

JIT 为什么快?相比解释执行,快在缓存了字节码——因为解释执行的大头(对于 fetch-dispatch-execute 循环,其实 execute 不是大头,主要的是不断循环中 fd 的那些 overhead)在于解释器本身的代码,当然是不如直接跑机器码的(当然我对我们作业这个存疑),而且 JIT 还有一些优化,更厉害一点;相比 AOT,JIT 的信息更多,profiling 后能进行更充分的优化。不过它的缺点就是:效率不一定快,而且还占用 runtime。

代码没写多少,难以下笔啊。给项目起了个响亮的名字——DarkSwordVM,dsvm,因为也许会像黑暗剑一样太监。复用了一些 Masterball 的代码,不过很多估计是要重写了(codegen 部分应该可以再用?不是很清楚)

4.12

今天课很多,但是越来越不爱听课了。os 还是在讲 fs,机器学习开始讲树模型了。算法继续 dp,讲了 dp 的单调队列优化(经典滑窗最值)、斜率优化。

鉴证了一下午,做了很多奇怪的测试,感觉测试结果也是奇奇怪怪的,但是里面的问题还挺好玩的。

写了一会儿 interpreter。还是基于 antlr 解析 llvm,虽然它比较线性,但是语法还是有点复杂的。

把宝石之国的最后一集看了,感觉完结得挺仓促了(可能经费不够用了),但是改编的也不错,让动画也构成了一个整体。就是悬念有点多。

4.13

星期三。摸鱼日。

上午的概率论成功完整地被核酸冲掉了。经典核酸排队背单词。回来看了一下,好像还是在讲积分的性质。

回来抢到了麦当劳,感觉非常的不错(xie kui),后面有点困就昏睡了,一直睡到了下午三点多,挂了个 ZY-INS。

继续推进 interpreter 进度。这周内写完吧。

把概率论第九次作业做完了,量有点多。

明天晚上之前要确定机器学习选题,组合作业也得做。今天看了一会儿各方面的研究成果,还是没想好选啥。(Transformer 为啥有个这个表情:

感觉看着好好笑啊)

4.14

昨天熬夜熬太迟了,今天差点没起来。

os 终于开始讲 IO 了(虽然 DMA 啥的作业好像都体验过了),晕晕乎乎地继续做完看没看完的 paper,终于确定选题选 CTR Prediction。现在的问题:一是要弄啥模型,二是 GPU 上哪整。罢了,这周末先搞算法好了。

下午学子讲坛,摸鱼;算法课,讲了四边形不等式优化 dp,具体就是说对一类区间 dp,代价满足四边形不等式,使得其决策具有单调性,故 for 中间点的时候可以有一个上界、一个下界,复杂度从 \(n^3\) 降到 \(n^2\)。

晚上做明天交的组合作业。感觉难度比起上次低了,但是第六题实在不会做(搜了下好像叫 Chvatal-Erdos 定理?)

再晚写了会儿 interpreter。果然 memory 还是要用 byte 来仿真。

本周 DDL 已干掉两个,周末任务:算法 + 解释器写完。虽然算法延迟了但还是写完为好。周末再把 notebook3 做了,反向传播和多层感知机,有点神秘。

4.15

This image has an empty alt attribute

啊,周五,你好温柔。

早上听概率论,讲的是可测函数的几种收敛:a.e. 收敛、a.e. 一致收敛和依测度收敛。

下午是组合,主要讲作业题。讲了 Chvatal-Erdos 定理(据说是 Erdos 在一辆车上想出来的?)

晚上因为女朋友发了张别人网课用薇尔莉特的模型,突然心血来潮开始玩 VSeeFace,最后也是捏了几个 vrm 皮,成功体验一波虚拟主播的感觉。而且这玩意儿可以很方便推流到腾讯会议,挺方便整活儿的。

依然按照周五惯例,并没有做什么事。

4.16 & 4.17

This image has an empty alt attribute

很忙的周末。首先是解决 JIT 解释器的大锅,最后终于跑通了(跑了个 a+b problem),然后是团委的工作也收拾掉了,以及编译器 code review 结束。

周末花了好多时间写 OJ——其实大多时间都花在想怎么实现简单,以及设计功能上。不过还是对 JavaScript 不太熟悉。以后好好加油吧。

周末学弟们机考,老年选手也跟着看了看题,并且成功在考试时做掉一题(其实是线段树水题 qaq),感觉算法水平下降了不少。

算法作业想了第一题(虽然有点乱),第二题 k=1 有了点思路。

周末最重要的当然是摸鱼。但是下周感觉是个死亡周,努力活下去!本周的任务基本算全部完成,不错。

声明:没有风会经过的旅店|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 疫情期间的手记 Week3


如飞蛾之赴火,岂焚身之可吝。