Technology

Chart Type 《大数据经典论文解读》 三驾马车学习 Spark 内存管理及调优 Yarn学习 从Spark部署模式开始讲源码分析 容器狂占内存资源怎么办? 多角度理解一致性 golang io使用及优化模式 Flink学习 c++学习 学习ebpf go设计哲学 ceph学习 学习mesh kvm虚拟化 学习MQ go编译器 学习go 为什么要有堆栈 汇编语言 计算机组成原理 运行时和库 Prometheus client mysql 事务 mysql 事务的隔离级别 mysql 索引 坏味道 学习分布式 学习网络 学习Linux go 内存管理 golang 系统调用与阻塞处理 Goroutine 调度过程 重新认识cpu mosn有的没的 负载均衡泛谈 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go channel codereview gc分析 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes扩缩容 神经网络模型优化 直觉上理解深度学习 如何学习机器学习 TIDB源码分析 什么是云原生 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 共识算法 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全访问机制 jvm crash分析 Prometheus 学习 Kubernetes监控 容器日志采集 Kubernetes 控制器模型 容器狂占资源怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes类型系统 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言那些事儿 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 如何分发计算 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记 log4j学习 为什么netty比较难懂? 回溯法 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 OpenTSDB 入门 spring事务小结 分布式事务 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker namespace和cgroup Linux网络源代码学习——整体介绍 zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 深度学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM执行 git maven/ant/gradle/make使用 再看tcp kv系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go基础 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

Architecture

实时训练 分布式链路追踪 helm tensorflow原理——python层分析 如何学习tensorflow 数据并行——allreduce 数据并行——ps 机器学习中的python调用c 机器学习训练框架概述 embedding的原理及实践 tensornet源码分析 大模型训练 X的生成——特征工程 tvm tensorflow原理——core层分析 模型演变 《深度学习推荐系统实战》笔记 keras 和 Estimator tensorflow分布式训练 分布式训练的一些问题 基于Volcano的弹性训练 图神经网络 pytorch弹性分布式训练 在离线业务混部 RNN pytorch分布式训练 CNN 《动手学深度学习》笔记 pytorch与线性回归 多活 volcano特性源码分析 推理服务 kubebuilder 学习 mpi 学习pytorch client-go学习 tensorflow学习 提高gpu 利用率 GPU与容器的结合 GPU入门 AI云平台 tf-operator源码分析 k8s批处理调度 喜马拉雅容器化实践 Kubernetes 实践 学习rpc BFF 生命周期管理 openkruise学习 可观察性和监控系统 基于Kubernetes选主及应用 《许式伟的架构课》笔记 Kubernetes webhook 发布平台系统设计 k8s水平扩缩容 Scheduler如何给Node打分 Scheduler扩展 controller 组件介绍 openkruise cloneset学习 controller-runtime源码分析 pv与pvc实现 csi学习 client-go源码分析 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 资源调度泛谈 业务系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 serverless 泛谈 概率论 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 架构大杂烩 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念入门 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 用户登陆 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 当我在说模板引擎的时候,我在说什么 用户认证问题 资源的分配与回收——池 消息/任务队列


《编译原理之美》笔记——后端部分

2020年02月20日

简介

我们使用的语言抽象程度越来越高,每一次抽象对下一层的复杂性做了屏蔽,因此使用起来越来越友好。而编译技术,则帮你一层层地还原这个抽象过程,重新转换成复杂的底层实现。

程序和操作系统的关系

程序视角的堆栈结构

操作系统加载可执行文件到内存的,并且定位到代码区里程序的入口开始执行。操作系统看到的是一个个指令 和 一个个内存地址

为什么会有一块动态内存区域?os 启动的时候, 一波三折, 不停的往内存加载更大的程序, 第一波占用的内存第二波就干别的用了。c 语言手动malloc 和 free,其实微观上,汇编语言也是在字节层面上不停地malloc和free

os 提供systemcall malloc 内存,但没有提供 systemcall malloc 一个heap 或 stack 出来。

生成代码

做完语义分析以后,编译器这时可以直接生成目标代码,因为编译器已经完全理解了程序的含义,并把它表示成了带有语义信息的 AST、符号表等数据结构。生成目标代码的工作,叫做后端工作。做这项工作有一个前提,就是编译器需要懂得目标语言,也就是懂得目标语言的词法、语法和语义,这样才能保证翻译的准确性。通常来说,目标代码指的是汇编代码,它是汇编器(Assembler)所能理解的语言,跟机器码有直接的对应关系。汇编器能够将汇编代码转换成机器码。

熟练掌握汇编代码对于初学者来说会有一定的难度。但更麻烦的是,对于不同架构的 CPU,还需要生成不同的汇编代码,这使得我们的工作量更大。所以,我们通常要在这个时候增加一个环节:先翻译成中间代码(Intermediate Representation,IR)。

遍历 AST 手工生成汇编代码

AST 的每个节点有各种属性,遍历节点时,针对节点属性类型做相应处理。生成汇编代码的过程,基本上就是基于 AST 拼接字符串

case PlayScriptParser.ADD:
    // 为加法运算申请一个临时的存储位置,可以是寄存器和栈
    address = allocForExpression(ctx);
    bodyAsm.append("\tmovl\t").append(left).append(", ").append(address).append("\n");  //把左边节点拷贝到存储空间
    bodyAsm.append("\taddl\t").append(right).append(", ").append(address).append("\n");  //把右边节点加上去
    break;

翻译程序的入口generate

  1. 生成一个.section 伪指令,表明这是一个放文本的代码段。
  2. 遍历 AST 中的所有函数,调用 generateProcedure() 方法为每个函数生成一段汇编代码,再接着生成一个主程序的入口。
  3. 在一个新的 section 中,声明一些全局的常量(字面量)

    public String generate() { StringBuffer sb = new StringBuffer();

     // 1.代码段的头
     sb.append("\t.section  __TEXT,__text,regular,pure_instructions\n");
    
     // 2.生成函数的代码
     for (Type type : at.types) {
         if (type instanceof Function) {
             Function function = (Function) type;
             FunctionDeclarationContext fdc = (FunctionDeclarationContext) function.ctx;
             visitFunctionDeclaration(fdc); // 遍历,代码生成到bodyAsm中了
             generateProcedure(function.name, sb);
         }
     }
    
     // 3.对主程序生成_main函数
     visitProg((ProgContext) at.ast);
     generateProcedure("main", sb);
    
     // 4.文本字面量
     sb.append("\n# 字符串字面量\n");
     sb.append("\t.section  __TEXT,__cstring,cstring_literals\n");
     for(int i = 0; i< stringLiterals.size(); i++){
         sb.append("L.str." + i + ":\n");
         sb.append("\t.asciz\t\"").append(stringLiterals.get(i)).append("\"\n");
     }
    
     // 5.重置全局的一些临时变量
     stringLiterals.clear();
        
     return sb.toString();  }
    

generateProcedure() 方法把函数转换成汇编代码

  1. 生成函数标签、序曲部分的代码、设置栈顶指针、保护寄存器原有的值等。
  2. 接着是函数体,比如本地变量初始化、做加法运算等。
  3. 最后是一系列收尾工作,包括恢复被保护的寄存器的值、恢复栈顶指针,以及尾声部分的代码。

    private void generateProcedure(String name, StringBuffer sb) { // 1.函数标签 sb.append(“\n## 过程:”).append(name).append(“\n”); sb.append(“\t.globl ”).append(name).append(“\n”); sb.append(“”).append(name).append(“:\n”); // 2.序曲 sb.append(“\n\t# 序曲\n”); sb.append(“\tpushq\t%rbp\n”); sb.append(“\tmovq\t%rsp, %rbp\n”); // 3.设置栈顶 // 16字节对齐 if ((rspOffset % 16) != 0) { rspOffset = (rspOffset / 16 + 1) * 16; } sb.append(“\n\t# 设置栈顶\n”); sb.append(“\tsubq\t$”).append(rspOffset).append(“, %rsp\n”); // 4.保存用到的寄存器的值 saveRegisters(); // 5.函数体 sb.append(“\n\t# 过程体\n”); sb.append(bodyAsm); // 6.恢复受保护的寄存器的值 restoreRegisters(); // 7.恢复栈顶 sb.append(“\n\t# 恢复栈顶\n”); sb.append(“\taddq\t$”).append(rspOffset).append(“, %rsp\n”); // 8.如果是main函数,设置返回值为0 if (name.equals(“main”)) { sb.append(“\n\t# 返回值\n”); sb.append(“\txorl\t%eax, %eax\n”); } // 9.尾声 sb.append(“\n\t# 尾声\n”); sb.append(“\tpopq\t%rbp\n”); sb.append(“\tretq\n”);

     // 10.重置临时变量
     rspOffset = 0;
     localVars.clear();
     tempVars.clear();
     bodyAsm = new StringBuffer();  }
    

二进制文件格式和链接

汇编器可以把每一个汇编文件都编译生成一个二进制的目标文件,或者叫做一个模块。在一个文件中调用另一个文件的函数时,并不知道函数的地址。所以,汇编器把这个任务推迟,交给链接器去解决。就好比你去饭店排队吃饭,首先要拿个号(函数的标签),但不知道具体坐哪桌。等叫到你的号的时候(链接过程),服务员才会给你安排一个确定的桌子(函数的地址)。

链接可以被分为编译时链接、加载时链接,以及运行时链接三种类型。

  1. “静态链接”中的“静态”,实际上是指在用户准备执行这个程序前,它正常运行所依赖的全部代码实现便已经“静静地躺在那里”,成为了整个可执行文件的一部分。
  2. 使用动态链接编译的程序,编译器只会为这些依赖代码在可执行程序文件中留下用于临时占位的“槽”。而只有当用户开始调用程序时,相关代码才会被真正加载到内存。 通常来说,在编译程序时,我们会对那些基础且常见的公有代码库(如 libc、libm、libthread 等)采用动态链接。这些系统库已经成为支持现代操作系统正常运作的一部分,因此在大多数情况下它们都不可或缺。而对于应用程序独有的那部分实现,我们一般采用静态链接,让它们能够直接成为二进制可执行文件的一部分。

Linux 平台上的 .o 目标文件实际上是一种被称为“可重定位文件”的 ELF 文件类型。每一个可重定位目标文件内都存在有一个符号表,它包含了该文件对应源码内使用到的所有全局变量和函数信息。

  1. 符号解析,是指为每一个外部符号引用,找到一个与之关联的符号定义。当有重名的多个符号定义存在时,链接器会按照一定规则来选择适用的版本。如果链接器在搜索完所有输入的目标文件后,仍存在无法被解析的符号,它便会终止程序处理,并抛出类似 “undefined reference to symbol” 的错误信息。
  2. 重定位,
    1. 链接器会将输入的多个目标文件的同类型 Section 进行合并
    2. 并为它们和所有程序使用到的符号分配运行时的 VAS 地址。
    3. 借助重定位表中的信息,链接器可以对上一步中得到的外部符号,进行地址及值上的修正(链接前,由于尚不清楚这些符号定义的真实所在位置,因此会使用默认值(比如 0)来作为它们在机器代码中的地址占位符。)。

在 Linux 下,目标文件、共享对象文件、二进制文件,都是采用 ELF 格式。这些二进制文件的格式跟加载到内存中的程序的格式是很相似的。这样有什么好处呢?它可以迅速被操作系统读取,并加载到内存中去,加载速度越快,也就相当于程序的启动速度越快。

在 ELF 格式中,代码和数据也是分开的。这样做的好处是,程序的代码部分,可以在多个进程中共享,不需要在内存里放多份。放一份,然后映射到每个进程的代码区就行了。而数据部分,则是每个进程都不一样的,所以要为每个进程加载一份。

IR中间表达式

前文通过 从 AST 生成汇编代码 的过程是比较机械的。

IR 在高级语言和汇编语言的中间,与高级语言相比,IR 丢弃了大部分高级语言的语法特征和语义特征,比如循环语句、if 语句、作用域、面向对象等等,它更像高层次的汇编语言;而相比真正的汇编语言,它又不会有那么多琐碎的、与具体硬件相关的细节。

IR看做是一种高层次的汇编语言,主要体现在:

  1. 它可以使用寄存器,但寄存器的数量没有限制
  2. 控制结构也跟汇编语言比较像,比如有跳转语句,分成多个程序块,用标签来标识程序块等;
  3. 使用相当于汇编指令的操作码。这些操作码可以一对一地翻译成汇编代码,但有时一个操作码会对应多个汇编指令。

IR 格式

  1. 三地址代码,学习用途
  2. LLVM 的 IR,工业级

    1. 静态单赋值(SSA),也就是每个变量(地址)最多被赋值一次,它这种特性有利于运行代码优化算法;
    2. 有更多的细节信息。比如整型变量的字长、内存对齐方式等等
    3. LLVM 汇编则带有一个类型系统。它能避免不安全的数据操作,并且有助于优化算法。
    4. 在 LLVM 汇编中可以声明全局变量、常量

int fun1(int a, int b){
    int c = 10;
    return a + b + c;
}

前端工具 Clang生成 LLVM 的汇编码clang -emit-llvm -S fun1.c -o fun1.ll

LLVM优化后的编码clang -emit-llvm -S -O2 fun1.c -o fun1.ll

define i32 @fun1(i32, i32) local_unnamed_addr #0 {
    %3 = add i32 %0, 10
    %4 = add i32 %3, %1
    ret i32 %4
}

LLVM IR对象模型

LLVM提供了代表 LLVM IR 的一组对象模型,我们只要生成这些对象,就相当于生成了 IR,比通过字符串拼接来生成 LLVM 的 IR方便。

int fun1(int a, int b){
    return a+b;
}

直接从 fun1() 函数生成 IR

Module *mod = new Module("fun1.ll", TheModule);
//函数原型
vector<Type *> argTypes(2, Type::getInt32Ty(TheContext));
FunctionType *fun1Type = FunctionType::get(Type::getInt32Ty(TheContext), //返回值是整数
    argTypes, //两个整型参数
    false);   //不是变长参数
//函数对象
Function *fun = Function::Create(fun1Type, 
    Function::ExternalLinkage,   //链接类型
    "fun1",                      //函数名称
    TheModule.get());            //所在模块
//设置参数名称
string argNames[2] = {"a", "b"};
unsigned i = 0;
for (auto &arg : fun->args()){
    arg.setName(argNames[i++]);
}
//创建一个基本块
BasicBlock *BB = BasicBlock::Create(TheContext,//上下文
            "",     //基本块名称
            fun);  //所在函数
Builder.SetInsertPoint(BB);   //设置指令的插入点
//把参数变量存到NamedValues里面备用
NamedValues.clear();
for (auto &Arg : fun->args())
    NamedValues[Arg.getName()] = &Arg;
//做加法
Value *L = NamedValues["a"];
Value *R = NamedValues["b"];
Value *addtmp = Builder.CreateAdd(L, R);
//返回值
Builder.CreateRet(addtmp);
//验证函数的正确性
verifyFunction(*fun);
Function *fun1 = codegen_fun1();     //在模块中生成Function对象
TheModule->print(errs(), nullptr);   //在终端输出IR

优化代码

  1. 代码优化的目标,是优化程序对计算机资源的使用。我们平常最关心的就是 CPU 资源,有时候还会有其他目标,比如代码大小、内存占用大小、磁盘访问次数、网络通讯次数等等。
  2. 从代码优化的对象看,大多数的代码优化都是在 IR 上做的,而不是在前一阶段的 AST 和后一阶段汇编代码上进行的

    1. 在 AST 上也能做一些优化,但它抽象层次太高,含有的硬件架构信息太少,难以执行很多优化算法。
    2. 在汇编代码上进行优化会让算法跟机器相关,当换一个目标机器的时候,还要重新编写优化代码。
  3. 优化的范围

    1. 本地优化,针对代码基本块的优化
    2. 全局优化,超越基本块的范围进行分析,我们需要用到控制流图CFG ,是一种有向图,它体现了基本块之前的指令流转关系。一个函数(或过程)里如果包含多个基本块,可以表达为一个 CFG。这种针对一个函数、基于 CFG 的优化,叫做全局优化
    3. 过程间优化,跨越函数的边界,对多个函数之间的关系进行优化

独立于机器的优化

一些优化的场景

  1. 代数优化, x:=x*8 ==> x:=x<<3
  2. 常数折叠, x:=20*3 ==> x:=60
  3. 删除不可达的基本块, 比如 if 2<0
  4. 删除公共子表达式, x:=a+b;y:=a+b ==> x:=a+b;y:=x 减少一次a+b计算
  5. 拷贝传播和常数传播
  6. 死代码删除
  7. 内联, person.getName() 正常翻译涉及到函数调用 ==> 跳过方法的调用,直接根据对象的地址计算出 name 属性的地址,然后直接从内存取值就行

在做全局优化时,情况就要复杂一些:代码不是在一个基本块里简单地顺序执行,而可能经过控制流图(CFG)中的多条路径。如果没有循环,属于有向无环图。否则,就是一个有向有环图。我们对其进行数据流分析,便有机会去除其中的无效变量,甚至直接删掉某个分支的代码。PS:这便是让数学中的图、“半格”理论有了用武之地。

依赖于机器的优化

代码生成部分 主要考虑三点:

  1. 指令的选择。同样一个功能,可以用不同的指令或指令序列来完成,而我们需要选择比较优化的方案:生成更简短的代码;从多种可能的指令中选择最优的。==> 树覆盖算法
  2. 寄存器分配。每款 CPU 的寄存器都是有限的,我们要有效地利用它。==> 寄存器共享原则 ==> 图染色算法
  3. 指令重排序。计算执行的次序会影响所生成的代码的效率。在不影响运行结果的情况下,我们要通过代码重排序获得更高的效率。 算法排序的关键点,是要找出代码之间的数据依赖关系 ==> 数据的依赖图,给图中的每个节点再加上两个属性:一是操作类型,因为这涉及它所需要的功能单元;二是时延属性,也就是每条指令所需的时钟周期。==> List Scheduling算法

我们通常会把 CPU 看做一个整体,把 CPU 执行指令的过程想象成,依此检票进站的过程,改变不同乘客的次序,并不会加快检票的速度。所以,我们会自然而然地认为改变顺序并不会改变总时间。但当我们进入 CPU 内部,会看到 CPU 是由多个功能部件构成的。一条指令执行时要依次用到多个功能部件,分成多个阶段,虽然每条指令是顺序执行的,但每个部件的工作完成以后,就可以服务于下一条指令。在执行指令的阶段,不同的指令也会由不同的单元负责。所以在同一时刻,不同的功能单元其实可以服务于不同的指令。

当然了,不是所有的指令都可以并行,导致无法并行的原因有几个:

  1. 数据依赖约束,如果后一条指令要用到前一条指令的结果,那必须排在它后面。如果有因为使用同一个存储位置,而导致不能并行的,可以用重命名变量的方式消除,这类约束被叫做伪约束,比如

    1. 先写再写:如果指令 A 写一个寄存器或内存位置,B 也写同一个位置,就不能改变 A 和 B 的执行顺序,不过我们可以修改程序,让 A 和 B 写不同的位置。
    2. 先读后写:如果 A 必须在 B 写某个位置之前读某个位置,那么不能改变 A 和 B 的执行顺序。除非能够通过重命名让它们使用不同的位置。
  2. 资源约束

    1. 功能部件约束,如果只有一个乘法计算器,那么一次只能执行一条乘法运算。
    2. 指令流出约束,指令流出部件一次流出 n 条指令。
    3. 寄存器约束,寄存器数量有限,指令并行时使用的寄存器不可以超标。

在我国大力促进芯片研发的背景下,如果现在有一个新的 CPU 架构,新芯片需要编译器的支持才可以。你要实现各种指令选择的算法、寄存器分配的算法、指令排序的算法来反映这款 CPU 的特点。对于这个难度颇高的任务,LLVM 的 TableGen 模块会给你提供很大的帮助。这个模块能够帮助你为某个新的 CPU 架构快速生成后端。你可以用一系列配置文件定义你的 CPU 架构的特征,比如寄存器的数量、指令集等等。一旦你定义了这些信息,TableGen 模块就能根据这些配置信息,生成各种算法,如指令选择器、指令排序器、一些优化算法等等。这就像编译器前段工具可以帮你生成词法分析器,和语法分析器一样,能够大大降低开发一个新后端的工作量,所以说,把 LLVM 研究透彻,会有助于你在这样的重大项目中发挥重要作用。

把每次只处理一个数据的指令,叫做 SISD(Single Instruction Single Data),一次只处理一个数据的计算,叫做标量计算。对应的有一类叫做 SIMD(Single Instruction Multiple Data)的指令,一次可以同时处理多个数据的计算,叫做矢量计算。它在一个寄存器里可以并排摆下 4 个、8 个甚至更多标量,构成一个矢量。比如寄存器是 256 位的,可以支持同时做 4 个 64 位数的计算。平常写的程序,编译器也会优化成,尽量使用 SIMD 指令来提高性能。

在代码里,我们会用到寄存器,并且还会用专门的寄存器分配的算法来优化寄存器。可是对于高速缓存,我们没有办法直接控制。那我们有什么办法呢?答案是提高程序的局部性(locality),这个局部性又分为两个:

  1. 时间局部性。一个数据一旦被加载到高速缓存甚至寄存器,我们后序的代码都能集中访问这个数据,别等着这个数据失效了再访问,那就又需要从低级别的存储中加载一次。
  2. 空间局部性。当我们访问了一条数据之后,很可能马上访问跟这个数据挨着的其他数据。CPU 在一次读入数据的时候,会把相邻的数据都加载到高速缓存,这样会增加后面代码在高速缓存中命中的概率。

提高局部性这件事情,更多的是程序员的责任,编译器能做的事情不多。不过,有一种编译优化技术,叫做循环互换优化(loop interchange optimization)可以让程序更好地利用高速缓存和寄存器。

即时编译JIT

JIT Compilation 的全称为 “Just-In-Time Compilation”,翻译过来为“即时编译”。其最显著的特征是代码的编译过程发生在程序的执行期间,而非执行之前。

传统的 JIT 编译器在实际动态生成机器码前,会首先对原始代码或其相应的 IR 中间代码进行一系列的分析(profiling)。通过这些分析过程,编译器能够找到可以通过 JIT 编译进行性能优化的“关键代码路径”。这里的取舍重点在于:对这些代码进行运行时优化而得到的性能提升收益,需要高于进行优化时所产生的性能开销。

即时编译JIT的场景之一——提升系统性能:在第一次编译时,你可以让 LLVM,仅运行少量的优化算法,这样编译速度比较快,马上就可以运行。而对于被多次调用的函数,你可以让 LLVM 执行更多的优化算法,生成更优化版本的目标代码。而运行时所收集的某些信息,可以作为某些优化算法的输入,像 Java 和 JavaScript 都带有这种多次生成目标代码的功能。PS:代码最终是一段机器码,如果某一个部分被经常使用,那么这部分机器码可以被拎出来进行深度优化替换掉原来的机器码。这个特点应用到 rpc 就是:如果让我们刚启动的应用就承担像停机前一样的流量,这会使应用在启动之初就处于高负载状态,从而导致调用方过来的请求可能出现大面积超时,进而对线上业务产生损害行为,所以要启动预热。

  提前编译(AOT) 即时编译(JIT)
目标代码的加载 应用程序会被操作系统加载,目标代码被放到了代码区 需要为这种动态生成的目标代码,申请内存,并给内存设置可执行权限
目标代码的链接 在静态编译的时候,链接程序最重要的工作,就是重定位(Relocatable),各个符号的地址,包括全局变量、常量的地址和函数的地址 编写的程序里的所有全局变量,和函数,都会被放到一个符号表里,在符号表里记录下它们的地址。这样,引用它们的函数就知道正确的地址了。
还可以使用动态链接访问共享库中的代码

IT Compilation:一种特殊的程序执行方式其流程可大致总结为(不同文章例子不同,仅辅助理解):

  1. 读入源代码(包含 ASCII 形式的指令序列);
  2. 调用 bfJITCompile 函数,将源代码编译为机器码;这些生成的二进制机器码将被存放在一个 std::vector 对象中以备后续使用。
  3. 调用 allocateExecMem 函数,将机器码动态分配在可执行的内存段上;
     uint8_t* allocateExecMem(size_t size) {
         // mmap 函数是一个由 C 标准库提供的系统调用,通过该函数,我们可以在当前进程的 VAS(Virtual Address Space)中创建一个映射。这个映射可以指向一个具体的文件、或者是一个匿名空间。
         return static_cast<uint8_t*>(
             mmap(
             NULL,
             size, 
             PROT_READ | PROT_WRITE | PROT_EXEC,     // PROT_EXEC将这段申请的匿名内存空间标记为“可执行”
             MAP_PRIVATE | MAP_ANONYMOUS, 
             -1,
             0));
     }
    
  4. 调用 VM::exec 函数,通过 OSR 转移执行流程;将程序的指令执行流程转移至这段内存的起始位置处
  5. 代码执行完毕后再次转移回主流程;
  6. 执行一些清理善后工作。

动态申请内存,加载目标代码到内存,并赋予内存可执行的权限。jit.cpp

/*
 * 机器码,对应下面函数的功能:
 * int foo(int a){
 *     return a + 2;
 * }
 */
uint8_t machine_code[] = {
        0x55, 0x48, 0x89, 0xe5,
        0x8d, 0x47, 0x02, 0x5d, 0xc3
};
// 执行动态生成的机器码。
int main(int argc, char **argv) {
    //分配一块内存,设置权限为读和写
    void *mem = mmap(NULL, sizeof(machine_code), PROT_READ | PROT_WRITE,
                     MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
    if (mem == MAP_FAILED) {
        perror("mmap");
        return 1;
    }
    //把机器码写到刚才的内存中
    memcpy(mem, machine_code, sizeof(machine_code));
    //把这块内存的权限改为读和执行。从安全角度出发,操作系统给每个内存区域,设置了不同的权限,代码区具备可执行权限,所以我们才能运行程序。
    if (mprotect(mem, sizeof(machine_code), PROT_READ | PROT_EXEC) == -1) {
        perror("mprotect");
        return 2;
    }
    //用一个函数指针指向这块内存,并执行它
    int32_t(*fn)(int32_t) = (int32_t(*)(int32_t)) mem;
    int32_t result = fn(1);
    printf("result = %d\n", result);
    //释放这块内存
    if (munmap(mem, sizeof(machine_code)) == -1) {
        perror("munmap");
        return 3;
    }
    return 0;
}

未来发展

从某种意义上看,从计算机诞生到现在,我们编写程序的方式一直没有太大的进步。最早,是通过在纸带或卡片上打孔,来写程序;后来产生了汇编语言和高级语言。但是,写程序的本质没有变化,我们只是在用更高级的方式打孔。

云计算改变编程模式

当一个软件服务 1 万个用户的时候,增加一个功能可能需要 100 人天的话;针对服务于 1 百万用户的系统,增加同样的功能,可能需要几千到上万人天。同样的,如果功能不变,只是用户规模增加,你同样要花费很多人天来修改系统。那么你可以看出,整体的复杂性是多个因素相乘的结果,而不是简单相加。云计算最早承诺,当我们需要更多计算资源的时候,简单增加一下就行了。然而,现有软件的架构,其实离这个目标还很远。那有没有可能把这些复杂性解耦,使得复杂性的增长变成线性或多项式级别(这里是借助算法复杂性的理论)的呢?

  1. 基础设施的复杂性,队列、分库分表、负载均衡、服务注册发现、监控等
  2. 部署复杂性,代码、分支、编译、测试、配置、灰度发布、回滚等
  3. API 的复杂性,能否让 API 调用跟普通语言的函数调用一样简单

编程环境会逐渐跟云平台结合起来,让 API 调用跟普通语言的函数调用一样简单,让开发平台来处理上述复杂性。根据计算机语言的发展规律,我们总是会想办法建立更高的抽象层次,把复杂性隐藏在下层。就像高级语言隐藏了寄存器和内存管理的复杂性一样。要求新的编程语言从更高的一个抽象层次上,做编译、转换和优化。我们只需要编写业务逻辑就可以了,当应用规模扩大时,真的只需要增加计算资源就行了;当应用需求变化时,也只需要修改业务逻辑,而不会引起技术细节上的很多工作量。能解决这些问题的软件,就是云原生的编程语言及其基础设施

还可能实现编程环境本身的云化,电脑只负责代码编辑的工作,代码本身放在云上,编译过程以及所需的类库也放在云上。

其它

  线程上下文 函数上下文
组成 虚拟地址空间
寄存器
cpu上下文
函数栈帧
指令寄存器 %pc %rip
栈寄存器 用户栈在用户切换内存空间时切换
内核栈current_task 指向当前的 task_struct
用户栈顶指针在内核栈顶部的 pt_regs 结构
内核栈顶指针%rsp
%rbp指向栈帧的底部
%rsp指向栈帧的顶部
调度方/切换方 操作系统 程序自己/编译器

编译原理要把计算机组成、数据结构、算法、操作系统,以及离散数学中的某些知识都用上。

  1. 指令选择、寄存器分配和指令排序,都是NP Complete的。这个时候,如果提前已经知道什么是NP Complete,那么马上就对这类算法有概念,也马上想到可以用什么样的方式来对待这类问题。
  2. 编译原理中很多算法都是基于树和图的,所以对这两个数据结构的理解也会有帮助。
  3. 至于计算机组成原理,跟后端技术的关联很密切。
  4. 程序运行时的环境,内存管理等内容,则跟操作系统有关。

编程语言是自举的,指的是说,我们能用自己写出来的程序编译自己。但是自举,并不要求这门语言的第一个编译器就是用自己写的。比如,这里说到的 Go,先是有了 Go 语言,我们通过 C++ 写了编译器 A。然后呢,我们就可以用这个编译器 A,来编译 Go 语言的程序。接着,我们再用 Go 语言写一个编译器程序 B,然后用 A 去编译 B,就得到了 Go 语言写好的编译器的可执行文件了。这个之后,我们就可以一直用 B 来编译未来的 Go 语言程序,这也就实现了所谓的自举了。所以,即使是自举,也通常是先有了别的语言写好的编译器,然后再用自己来写自己语言的编译器