- 博客(49)
- 收藏
- 关注
RSS订阅原创 快速开平方根算法
人们很早就在Quake3源代码中发现了类似如下的C代码，它可以快速的求1/sqrt(x)，在3D图形向量计算方面应用很广float invSqrt(float x){float xhalf = 0.5 * x;int i = *(int*)&x; // get bits for floating valuei = 0x5f3759df - (i >> 1); // gives
2016-04-26 12:02:13
51800
5
原创 容器中的int
这篇讨论下larva在容器含int的优化处理方式，仅对内置类型list和dict做了相关优化，具体以list为例如上篇末尾所说，由于相当多的程序并非简单的整数计算，而是需要数据结构，因此larva的规定“下标运算返回object类型”会在这些程序中使得类型推导派不上用场，例如，我们做一个矩阵运算，即便矩阵中都是整数，也不得不采用object计算的方式，严重影响效率，而如果采用拆箱装箱的
2014-11-01 19:12:22
1089
原创 larva的类型推导
上一篇说了，类型推导一般来说是一个CSP问题，所以larva采用简化问题的办法，用简单的算法来获得相对更高的收益，采用的办法主要是简化问题，麻烦的事情一律不做首先考虑到的一点是，即便我已经有了算法来做完全的类型推导，也不一定面向程序来做优化，一个larva程序由若干模块组成，如果对整个程序来做优化，可能一个很小的改动就产生不同的结果，比如一个模块有一个函数f：func f(n):
2014-10-23 19:21:23
1164
原创 再议类型推导
在前面的理论部分，讲过静态类型推导，不过当时只是提到了概念，主要是为了证明这玩意是比较复杂的，之所以有必要再议一下，是因为这个对larva的效率还是挺重要的，事实上我只做了一个很简单的推导算法，就将larva在dhrystone上的速度提了一倍；另一方面也是之前讲的比较简略，再深入一下前面讨论反向运算的时候提到，常见计算机的CPU只能直接处理整数和浮点计算（地址不在这次讨论范围），不考
2014-10-22 17:04:27
1379
原创 反向运算和增量赋值
如果抛开具体实现讨论理论，就有些太过抽象，所以下面和之后如无特殊说明，默认以larva的目前实现为背景，即python实现的编译器和转成java执行CPU只能直接处理很基础的数据类型，如果简化一下，可以归类为寻址、整数（一般在ALU、乘法器、除法器、移位器等计算，含指针/地址计算）和浮点数（一般有专门的FPU），一个程序可能有成百上千的类型，但归根到底都是由地址、整数、浮点数等组成的复
2014-10-20 19:18:29
1370
原创 运算优先级、结合性、求值顺序、副作用和顺序点
标题中这几个概念，是很多C/C++程序员在表达式上容易出问题或不清楚的地方，虽然这些概念在很多语言都有体现，但C里面特别明显，所以就以C语言为例子总结下运算符优先级比较简单，就是指在一个存在多个运算的表达式中，各运算的计算先后顺序，比如a+b*c是先算乘法等。而结合性就是指优先级同级的运算连续的时候，从左到右还是从右到左然而就是这么两个最简单的概念，如果去网上搜，或一些C语言的书籍
2014-10-15 20:19:13
4303
8
原创 代码单步展开
结合前面lambda的例子，列表解析式看上去也可以这样做出python中的效果：func main(): i = [0] l = [for i[0] in range(10)]这样就可以把解析式循环中的值带出来了，不过larva并没有实现这个语法，强制规定了for的左值表达式只能是简单的变量名或只有变量名组成的解包列表，因为我觉得还是规定为临时变量和当前环境没有互相影响比较好
2014-10-14 14:19:52
580
原创 lambda的实现
一开始我并没打算在larva实现前面说的解析式和这篇要说的lambda，因为当时觉得解析式可以用循环来代替，lambda则可以用可调用对象代替，但后面发现还是做了比较好，毕竟这俩东西太方便了，如果没有的话代码写起来很啰嗦。其实碰到的第一个问题是列表解析式，因为我本来觉得，对我来说lambda使用的地方不是很多（虽然很多人喜欢用），不过在开始做列表解析式的时候，我忽然想到python中的map函数，
2014-10-13 14:12:59
912
原创 列表&字典解析式
python的一个特色就是提供列表/字典/集合等数据结构的解析式，比如：[i * i for i in xrange(100) if i % 2 == 0]表示一个包含0到99的所有偶数的平方的列表larva也实现了这种语法，不过稍微有些区别，其实要实现一模一样的也可以，不过最后没这么做首先是没做多重嵌套的for和if，python中没有限制列表解析式的for和i
2014-10-12 17:10:19
1508
原创 解包赋值
解包赋值是一个方便代码编写的语法特性，在一个赋值语句中可将右边表达式的值自动解开赋值给左边，如：a, b = t简单看上去相当于：a = t[0]b = t[1]不过若t的位置是一个表达式，则下面这样做就必须用一个临时变量来防止重复求值，事实上这个代码和解包并不等价，解包赋值的具体步骤更复杂一点：首先，计算右边的表达式，以及左边的各左值元素中的需计算部分（如果有的话，比如a[i
2014-10-12 16:25:54
2683
原创 代码流程分析
在larva的语义和流程分析上，我偷了很大的懒，基本等于没做，因为觉得做起来太麻烦了流程分析可以在一段语法上完全没有问题的代码中，找出可能有问题的代码，这个不同编译器支持程度也不同，其实在绝大多数情况下，不做这个问题也不大，不过larva面对了一个相关的不可逃避的问题，因为它和python一样有一个特性：若一个函数或方法最后没有return，则自动return一个空对象，larva中是
2014-10-12 12:22:47
701
原创 运算符优先级相关问题
larva运算符系统大体上抄python，不过也有一些区别，简单总结一下运算符和表达式解析相关的问题问题一：没有实现乘方运算**，原因也简单在编译器的注释里面写了，**用得不多，是唯一一个右结合的二元运算，即a**b**c等同于a**(b**c)，不留心会出现问题另外，**运算和单目运算关系较为复杂，比如-a**b等同于-(a**b)，根据python的文档，**运算优先级比单目运
2014-10-02 23:29:55
970
原创 缩进词法分析
接下来会对larva实现的部分细节做一些分析，先看下编译器对于缩进词法的分析用缩进来区分代码块或缩进参与词法、语法，python可能不是首创，不过大概是其中最有名的语言之一，相关的争议也一直不断，其实别说这个了，就连C语言中大括号是否应该另起一行都能争个几十年正方认为，缩进可以让代码更美观，不过美观不美观也是一个主观看法，在这方面，反方提出，如果代码比较长，根据缩进区分代码
2014-10-02 18:36:19
1603
原创 动态类型的静态化实现
为便于开发，larva采用动态类型，于是首先遇到的一个问题就是，在转化为java的时候，如何处理动态类型带来的问题。乍一看，这个不是很复杂，已经有前车之鉴了，Cython就可以把python代码直接转化成C代码，我的做法和Cython有相似之处，但考虑效率问题，做了一点修改 （虽然第一版本并不实现class语法来自定义类，不过在论述这个问题的时候，假定有自定义类，因为主要矛盾就在自定义类的属性
2014-09-06 10:52:31
1105
原创 larva设计思路
接下来，开始动真格的，设计实现一个语言，或者确切说是一个相对实用的语言 虽然已经写了很多的理论相关，不过实际要做的时候，并没必要都用上，因为可以利用已有的东东做基础；同样的，也没有必要实现用户态并发之类的特性，至少在能预见的版本中，我只是需要其计算能力而已。另一个原因是，语言实现是一个很麻烦的事情，假如有一个团队，或可以容忍很长的时间，则可以各方面都做得好些，可惜人力时间都不够，还要做出一
2014-09-06 10:48:55
1191
原创 收集循环引用
一个实用的垃圾收集器大体上应该满足以下条件 一、消除悬空指针和内存泄露 二、不能给程序运行带来过高的额外开销，一般来说要控制在10% 三、尽量减少停顿时间，使得运行平稳 四、内存管理方面局部性尽量好 其中第一条没什么好说的，肯定要符合，至于第四条，当然也很重要，局部性做好了可以成倍提高运行速度，不过，如果都是内存操作，就算没做好速度一般也可以接受了，在老式的系统中，由于会用
2014-09-06 10:44:48
782
原创 短停顿收集
即便用追踪式收集辅助引用计数，在很多时候停顿时间依然不可接受，原因有几点： 一、虽然引用计数可以保证不产生循环的对象能实时回收，但存在很多这类对象是挂在循环引用数据结构上的，比如两个对象互相引用，而他们各自又挂了很多int和string数据，即是一个例子。由于这些对象的回收也是在停顿期，实时性不是那么好 二、循环引用本身并不罕见，双链表、树等数据结构都存在这种情况，实际工作中很多复杂的业务
2014-09-06 10:43:17
914
原创 雪崩效应
标记-清除和节点复制这两种简单的追踪式垃圾收集，往往会导致程序在运行期卡顿，在一些特定场景下甚至很明显。谈起这个问题，很多时候会以客户端程序，即有人机交互的情况下，从软件体验角度来说，但广义上来说，只要是实时系统，都会受到这个影响，客户端的程序只要不是像大型游戏这种，一般来说内存占用也不多，因此卡顿并不是很明显，但如果是实时性要求比较高的服务器程序就不同了，比如我一个之前在网易的朋友就谈到，他们的
2014-09-06 10:41:54
2967
1
原创 节点复制
节点复制是另一种追踪式收集，在回收阶段和标记-清除采用了不同的策略，简单地说，标记-清除主动释放垃圾，而节点复制是将可达集拷贝出来，然后统一回收整块内存 前面说过，据统计80%~98%的对象在建立之后很快就会销毁，由此可以预见，在正常情况下，当启动垃圾回收的时候，可达集和垃圾集合是不成比例的，堆空间中很可能只有少部分的内容可达，剩下都是垃圾，标记-清除算法的时间和对象数量相关，而节点复制由
2014-09-06 10:39:56
966
原创 伪多项式复杂度
上篇的标记算法中，谈到这个O(K)的算法是一个指数级复杂度的算法，其实对那道题目本身来说，K是固定的，既然不是输入，那也无所谓复杂度，之所以有O(K)这种说法，是把K当做一种输入了，这是看待输入的角度问题，倒不用深究。考虑一个更简化的算法（python代码，设输入n是正整数）： def f(n): i = 0 while i < n: i += 1 这
2014-09-06 10:37:49
4400
原创 版本号标记
这是一个处理需要反复标记的问题的一个小技巧，以一个ACM形式的题目为例： 输入：第一行是一个数字N，表示N个case，之后每个case第一行是一个数字M，表示这个case有M个数字输入，接下来是M个数字，每个数字范围是0 输出：对每个case，输出M个数字去重后的数量 当然，这题本身没什么难度，弄个hash_set就行了，不过为了说明问题，我们假定做题的人比较笨，使用bitmap：
2014-09-06 10:35:27
920
原创 标记-清除
标记-清除是主流的追踪式收集算法的一种，和引用计数相比，追踪式收集是一种间接方法，与程序耦合性很低，简单地说，就是程序在需要的时候只管申请内存，使用时也不用像引用计数机制要做实时地维护，直到一定条件（一般是已申请内存空间达到一定阈值），进程暂停执行，由垃圾收集器回收垃圾，然后继续执行，当然如果收集之后还是内存不足，就报错。很多语言的主流实现都使用追踪式收集，比如java，C#等 追踪式收集
2014-09-06 10:33:44
1376
原创 引用计数
引用计数是垃圾收集中一种直接方式，其基本策略是每个对象维护一个引用计数，用于表示外界有多少地方引用自己，当有新的引用到这个对象的时候，计数+1，反之一个到这个对象的引用被拆除的时候，计数-1，当计数为0的时候，说明没有人引用这个对象了，这个对象就被销毁。由于直观，容易理解，引用计数在最早实现垃圾收集的lisp，以及早期的java中都使用过，python则是到现在还都一直在用 注：由于上篇已经论
2014-09-06 10:30:49
1669
原创 垃圾收集简述
在计算机领域，垃圾收集这个词确切说是堆内存自动回收，因为广义上讲，所谓垃圾也包括内存之外的一些东西，比如不再使用的文件句柄，但这些东西一般不算在这个概念里，这个名字大概是一开始取了个形象的名字 从历史看，垃圾回收技术既古老又年轻，现代的高级语言，基本都会将垃圾回收结合在语言设计里面，可能很多人想不到的是，垃圾回收早在上世纪60年代就已经在lisp中实现了，而在之后长达三十多年的时间里，这门
2014-09-06 10:28:38
716
原创 AOT和JIT
一个程序的编译过程可以是步骤迭代式的，即每一轮步骤结束后得到的结果都可独立运行，比如，先构造AST再输出字节码，中间状态AST也是可以解释执行的。由于编译的本质就是代码转换，因此对一个语言可以有多个独立的编译器，每个负责一轮步骤 AOT Compiler和JIT Compiler就是针对编译形式做的分类： AOT：Ahead Of Time，指在运行前编译，比如普通的静态编译 JI
2014-09-06 10:17:28
17423
原创 非随机行为和代码优化
语言的实现是一个很复杂的过程，这个复杂并非说它很难，虽然的确有一些难点，但总的来说并不是那么难以理解，复杂和简单相对，是指细节很多，很多事情需要具体到情况来讨论，比如龙书讲优化的部分，很多都是小的优化点；还有一些可能矛盾的地方，需要多种方案配合处理，比如前述静态类型推导，虽然纯粹的静态和动态类型都很容易实现，但要想各取所长就很麻烦了 幸运的是，至少在计算机领域，很多东西是非随机性的，语言也
2014-09-06 10:13:39
703
原创 用户态并发：事件驱动
上篇末尾有个地方说错了，分时调度的yield过程应该是： env.running_queue.add(this); this.stat = STAT_YIELD; return; 需要将this加入到running_queue，否则这个线程就死了 有了分时调度，就可以实现计算密集型的程序的并发执行，不过绝大多数程序显然不是这种，程序多多少少都会进入阻塞等待，比如IO，锁，s
2014-09-06 10:05:00
1005
原创 用户态并发：基本框架
前述关于线程的栈大小问题，其实栈是可以动态增长的，只不过为了效率问题，一般都是固定的，这是一个实现相关，并非线程的原罪；不过说的第二点，线程调度需要陷入内核，这个的确非常影响效率。而协程没有这两个问题，首先所有协程本质是可以在一个线程里面执行，一个协程切换的时候是暂时返回，执行栈都是复用的，随便开个比较大的空间就行了，协程的状态在堆上申请，可以按需申请，因此协程可以开很多很多，百万级都没问题；另一
2014-09-06 09:59:56
735
原创 协程
就一个简单实现的语言来说，如果有并发需求，像之前说的直接使用宿主环境的线程，加上必要的调度控制即可实现需求，但如果要求比较高，触发到上篇讲的线程和单线程异步的相关缺陷，一个较普遍的解决办法是采用用户态并发，即对于os内核来说，进程只有一个或少数几个线程，而对于源语言来说，接口和使用线程别无二致，由虚拟机实现对这些“线程”的调度，虚拟机的实现则可以一定程度简化、优化调度算法和内存占用，从而达到高并发
2014-09-06 09:57:15
775
原创 GIL并发控制
如果一个语言要实现支持并发执行的接口，则一般来说需要在并发控制上下功夫，原因就是前面说的，由于虚拟机实现的细节问题，直接依赖宿主环境的并发容易出问题。简单地，以使用宿主的线程为例。假如源语言的线程对应宿主环境的真线程，那么同步操作就需要用到线程间的互斥量，比如锁，信号量等 一个程序需要并发，一般来说有三个原因： 一，为充分利用多核cpu资源，提高计算速度。这个原因是很重要，但在实际中其
2014-09-06 09:48:31
878
原创 无锁环形队列，volatile和乱序执行
这里说的环形队列是一种内存通讯机制，本身这个机制和语言没有什么关系，不过上篇提到了volatile语法和acquire/release语义，就以这个机制做一个例子，C语言实现。这方面的内容涉及到一些现有的语言实现的东西 环形队列的数据结构是一个数组，简单起见我们认为通讯内容就是一个个int，则定义一个int数组和头尾索引： 方便起见可以约定：head表示队列首元素的索引，tail表
2014-09-06 09:31:49
2592
1
原创 并发执行
以我的经验，一提到并发执行，90%的人都会提到线程，的确这玩意用的很广泛，综合来说各方面都还可以。虽然很多语言都内置了线程库，C++11也有了，但严格来说线程是跟操作系统相关，具体说，如果操作系统支持线程，则语言的线程库简单封装下就可以了，如果操作系统不支持（如一些unix系统），那就比较麻烦了，简单的可以去掉线程库，或接口返回异常，复杂的可能自己实现一个用户态的线程机制 一个语言实现中如
2014-09-06 09:25:45
873
原创 运行时环境
AST或字节码的解释过程只是在代码过程层面，不足以成为一个完整的运行，因为程序计算是需要数据和存储空间的，光有代码跑不起来，需要运行时环境，至少要有数据，实际情况中还需要一些其他信息。为讨论方便，在解释器中将运行时环境抽象为前述的env对象，通过一些接口来实现存取，这里先只讨论单执行序列，不考虑并发 env在前面的分析中总共就涉及了三个接口，get，set和set_exception（当然
2014-09-06 09:15:23
1414
原创 threaded code和指令预测
在解释字节码执行的虚拟机中，一般都会有上一篇说的switch结构，而字节码的类型显然不止前面列出的那些，一个很简单的语言都可能有上百个字节码，于是引入了另一个问题，假设用C或C++实现，在很多编译器中，switch实际会被编译成一连串的if...else if... ... ...else，执行的时候，每条指令都从头开始判断，执行某些指令时，需要成百甚至上千的比较次数，严重影响运行效率。当然这
2014-09-06 09:05:26
1506
原创 字节码解释执行
字节码的解释执行和AST的解释执行有类似之处，而且更简单，因为树形结构已经展开成顺序了，以栈虚拟机为例，为方便起见，假设所有的指令都在一个指令数组里，每个元素是一个指令对象，有code和arg两个属性，解释器入口： Object execute(Inst[] inst_list, Object[] func_arg); 由于continue和break已经被jmp指令代替了，这里我们认为e
2014-09-06 09:01:36
1662
原创 寄存器虚拟机
前面说到，虚拟机是真机的一种模拟，而栈虚拟机模拟的是基于栈计算的机器，和现在常见的基于寄存器的硬件机器不同，于是相应的也有基于寄存器的虚拟机，不过这个虚拟机可能跟真机差别比较大 首先可以看看真机用寄存器的原因，计算机的存储有一个规律，访问速度越快的存储，单价（单位容量的成本）越高，因此实际实现的时候，容量会很受限，反之因为便宜而容量可以很大的存储，储存速度就慢，访问速度（或单价）从高到底大
2014-09-06 09:00:12
2210
原创 栈虚拟机字节码
虽然AST可以直接解释执行，实现也不复杂，但大部分语言，比如java，python，ruby（1.9版本之后）使用虚拟机解释字节码执行。字节码和AST的执行有很强的一致性，但字节码执行机制可以实现一些更细粒度的控制 这里的虚拟机是指执行一种低级语言字节码的虚拟机，这个限定可能强了些，比方说，前面说的一个AST解释器，也可以看做是一种虚拟机，因为理论上是可以有一个机器解释AST执行，但这里我
2014-09-06 08:52:14
995
原创 AST解释执行
语法和语义分析的结果是抽象语法树AST，再往后编译原理还有代码生成及优化的很大一部分，但如果只是做一个执行器，到AST为止就可以解释执行了，当然就算不生成AST，解析执行也可以，只是基于之前说过的原因，极少采用解析执行的方式 目前的大多数解释执行的语言，都是在虚拟机解释字节码执行，这个后面再说，它只是把AST的解释串行化了而已，事实上ruby在1.9版本之前是解释AST执行的，到1.9整合
2014-09-06 08:48:24
4207
原创 语法和语义分析
顾名思义，一个命令式语言是由一个个“命令”为单元组成，不过一般很少用命令这个词，而是细分一下，比较低级的语言用指令（instruction），高低的语言一般认为是一个语句（statement，以后简称stmt），词法分析只将一段高级语言代码分解成一个个词，接下来还要做语句层面的分析，最终目标是生成抽象语法树（ast） 代码： a = 1; s = 0; while (a
2014-09-06 08:44:02
3389
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人