从零开始使用docker搭建wordpress博客

  • 之前已经写了一个建站日记了Ubuntu 16.04 & Docker 搭建 WordPress,不过之前的版本有点像记流水账一样,现在有时间想重新组织语言,记录一下wordpress博客的搭建流程。
  • 这篇文章适用于那些不希望无脑搭建博客,但又希望以最简单的方式明明白白搭一个博客的读者取用。

本博客是由Wordpress搭建而成,如果你感兴趣的话,可以在博客中四处逛逛,看看这是不是可以解决你的需求的东西。实际上,Wordpress不仅仅可以搭建个人博客,而且还可以设计为公司主页,产品展示页面。接下来,我将从原理上介绍搭建Wordpress的流程。

WordPress博客的组成部分

PHP编写的后端逻辑

WordPress博客是一个使用PHP编写而成的博客系统,Wordpress使用PHP这个世界上最好的语言实现了网站的内部逻辑,诸如用户登录,插件管理等功能。至于PHP为什么是世界上最好的语言,有图为证↓。

至于PHP本身在Wordpress里面好用的一点,就是我们可以比较方便得修改它。比如这篇文章末尾的转载标签,就是通过手工修改PHP代码实现的(当然这里的手工也是通过博客页面上面的工具实现的),即使你不会PHP,只要知道在PHP语言中 <?php ... ?> 这个代码块内部实现的是程序逻辑,而代码块外面是我们需要显示的HTML代码就好了,也就是说,我们将希望修改的内容放在 <?php ... ?> 外面,就可以很轻松在程序母版上实现内容的添加。

搭载在Nginx服务器上

在PHP语言实现的站点逻辑的更上一层,是可以搭载该逻辑的服务器,由于服务器独立于实现逻辑(PHP程序和Nginx服务器的关系有点像C++语言和Linux系统一样)。主流的服务器有Nginx和Apache,在这里,我们使用Nginx,服务器本身的功能是监听端口,响应请求。

对于一个没有经过特殊设置的Wordpress博客系统,Nginx服务器将监听80端口(也就是我们使用HTTP访问IP没有指定端口时的默认端口)。网页访问者在该端口上的任何请求都会由Nginx解析,并调用指定的PHP程序渲染出我们希望的页面。

Mysql数据库储存网站数据

在结构上和Nginx服务端并列的,是数据库。数据库是一个为了实现数据的查询和储存设计出来的高性能系统,其功能也仅仅限于提供数据的储存于查询接口。诸如注册用户列表,文章内容等都是存在于数据库中的。Wordpress使用了Mysql数据库,这是一个基于表的关系型数据库,就效率上来说比其他数据库会好一些。

正在执行的一个PHP代码,在特定时候需要访问网站的数据(例如处理用户登录时,需要从数据库拉取指定用户的密码用以检验。)。这时,PHP程序将访问数据库,查询指定用户名对应的密码。

一个未经特殊设置的Mysql数据库,监听端口3306,而本机的其他程序,可以通过向该端口发送消息来与数据库交互。

多模块结合工作

在一般的情况下,打在了PHP网页逻辑的Nginx服务器是一个单一模块,Mysql是另一个模块。Nginx服务器在运行时会时不时地向3306端口发送请求以实现对数据库的查询。

两个模块力求尽可能的独立,这样,倘若因为错误的插件安装,你的网站逻辑部分崩了,你只需要重装Nginx-PHP模块,而不会丢失任何的用户数据。同理,对于数据库的修改也不会影响网站本身。

Docker是什么

Docker的原理

WordPress包含两个模块,他们各自的卸载与重装都不会对另一个模块产生影响。当你的服务器上不仅仅有Wordpress,还部署了其他的网站(这个情况实际上非常常见,谁也不能保证你的服务器永远只有一个博客),情况就不一样了。比如多个网站依赖于不同版本的服务端,或者网站各自的模块重装会互相影响等等…..

这时,我们就开始想Linux下面是否有类似于Python中的Anaconda一样的虚拟环境。倘若将这些模块装在互不影响的虚拟环境中,就可以实现相互独立了。或者说,有没有一个像虚拟机一样的东西,将Wordpress需要的两个模块分别运行在不同的虚拟机中,并使用一定的机制将它们关联在一起?这不,还真是有这么样一个虚拟环境,那就是Docker。

Docker在Linux中充当了虚拟机的角色,但是比虚拟机拥有更高的效率。也许是机智的Linux设计者早就预料好了有今天的需求,Linux的诸多设计使得在Docker这样的虚拟环境成为可能。在Docker中,一个虚拟环境的进程可以和主机进程并行运行(没有一个虚拟机一样的机器做翻译),并且从进程内部看,好像在一个与外界隔离的虚拟机中运行一样。

为了尝试说明Docker的原理,你只要知道下面的事实就好了——

  • Linux中有一个chroot指令,这条指令可以将接下来派生进程的根目录设置为主机的某一个目录,考虑如果有一个目录下有完备的/bin、/etc等Linux必备文件(本身Linux的就有Everything is Files的说法),那么我们使用了chroot将一个进程根目录设置为这个目录,那么看起来,这个进程接下来的运行就好像在一个全新的系统中运行一样!
  • 机智的Linux设计者还提供了其他东西,来解决诸如IP地址冲突,端口冲突的问题,总之,一个“虚拟机”中的进程可以实际运行在主机中而不干扰主机的任何工作。
  • Linux有文件映射与可持久化的机制,可以在一个固定文件版本的基础上,通过增量的方式快速构造另一个只有少量修改的文件版本(比如我有一个Ubuntu系统,我可以同时构造出一个安装了Wordpress的Ubuntu系统和安装了Mysql的Ubuntu系统,而总共占据了1个Ubuntu系统多一点的空间)。

确定了解了上述事实后,我们就很容易理解Docker究竟在干什么了——

Docker中存在两个概念,镜像与容器,镜像是一系列静态的文件打包,比如Ubuntu镜像,里面包含了所有Ubuntu运行需要的文件(也就是我们平常所看到的新的Ubuntu系统从根目录向下的所有文件);而容器则可以理解为可以运行、停止镜像,比如运行着的Ubuntu容器,在镜像的基础上,由于容器自身的运行,其内部的一些文件必然发生改变,Docker以花费极少的空间,用可持久化的方式追踪这些文件。而镜像和容器的关系是:一个镜像可以派生出多个容器,容器在运行并修改了自身后,又可以由特定docker命令固化为镜像。倘若之后读者成功建立了Docker容器,不妨到 /var/lib/docker/aufs/mnt 目录看看,你就知道容器是什么东西了。

在使用Docker建立出的纯净的系统中,我们可以从零开始搭建自己想要搭建的东西,自然而然就会有人建立一些常用环境的镜像并开源。这些镜像都收录于DockerHub中。比较著名的是Ubuntu镜像Mysql镜像以及WordPress镜像。当然,如果将整个系统镜像上传打包实际上是不妥的,用户并不能知晓这个镜像是如何制造出来的,故存在一个称之为Dockerfile的文件可以将生成这些镜像的方法“开源”,Dockerfile内部指名了这个镜像是基于什么镜像,并在该镜像基础上执行了哪些Bash命令得到的。比如我们需要基于Ubuntu镜像生成Mysql镜像可以理解为在Ubuntu镜像的文件系统中执行一条Mysql安装语句(当然,实际的实现可能会复杂一些)得到的新的文件系统。

使用Docker搭建一个博客

下面将介绍如何使用docker的原生命令建立一个Wordpress,该方法也可以在Wordpress的DockerHub镜像页面找到。不过这个方法可以被下一节中的Docker-Compose方法取代——

首先,我们先拉取我们需要的wordpress,以及mysql镜像

这里已经可以看到Docker镜像的文件系统的分层性质了,每一个十六进制的Tag都表示一个文件系统的版本。在生成mysql镜像的时候复用了wordpress镜像的一部分文件。这些文件就是这两个镜像所共有的Linux内核。

在DockerHub的Mysql页面,我们可以找到生成Mysql的容器的命令——

这里,输出结果 5f99a8d32f88f047da392fc764a5bf247a2b07440416a13942fb02891c0ce550 是新建出的容器ID,之后可以使用 docker ps 查看。在这一个步骤,我们建立了名为some-mysql的数据库容器,其密码为my-secret-pw,是基于mysql镜像建立的。

同理,在DockerHub的Wordpress页面,我们可以找到生成Wordpress容器的命令——

这里,我们新建了一个名为some-wordpress的Wordpress容器,依赖于名为wordpress的镜像。单独讲解一下–link参数的意义:由于两个容器互不干扰,可以理解为两个独立的主机,那么他们的通讯方法之一就是使用IP+端口通讯,那么这个参数的意义就是将some-mysql容器的IP地址储存在新建的some-wordpress容器的hosts文件中的一个名为mysql的项中,换句话说,之后再some-wordpress中,访问mysql:3306就能够访问到some-mysql的主机3306端口,进而建立起不同容器的通讯。而-p参数则代表将容器内部的80端口暴露为主机的8080端口。

更多细节有,docker常用的命令还有:

  • docker build :自己写一个Dockerfile,并让docker依照该Dockerfile新建一个镜像
  • docker ps -A :同时打印出由于各种错误导致停止的容器,而非正在运行的容器
  • docker stop :停止容器
  • docker restart :运行一个之前停止的容器

倘若之前的步骤没有任何问题的话,使用 docker ps 可以看到刚刚建立的两个进程正在运行。而如果有问题的话,也可以使用 docker ps -A 看到已经停止运行的容器,并用 docker logs <Container ID> 查看运行日志。

而访问主机的127.0.0.1:8080可以进入Wordpress的初始欢迎页面——

剩余部分就可以自由发挥啦~

Docker-Compose

Docker-Compose是一个可以将之前执行的一系列安装命令自动化的脚本。安装Compose可以按照官方文档的指示安装,由于这个依赖于平台,就不细讲了,如Linux可使用如下命令安装。

安装一个Wordpress使用Docker-Compose只需要在一个自定义的目录中,写一个如下的 Wordpress/docker-compose.yml 文件——

实际上,这个文件中的每一行,都是用来提供之前命令中需要的参数,而与上一节的内容对应,读者应该很容易了解每一行都在干什么——

  • 第一行是新建容器标识,仅仅用于内部的解析使用
  • 第二行是容器基于的镜像名称
  • 第三行、第四行表示内部端口和外部端口的映射
  • 第五行表示一些内部的设置,比如数据库密码等
  • 第六行用于连接mysql容器
  • 第七行是容器名
  • 后面mysql的部分相似

接着,使用 docker-compose -f Wordpress/docker-compose.yml up -d 命令启动。这一个命令可以得到上一节的相同结果。

更多细节是,docker-compose的up参数可以替换为stop、rm等命令。

注意事项

在本文中,我们将内部wordpress的80端口映射到了外部的8022端口,读者倘若希望仅仅建立博客的话,应该映射到外部80端口(因为80端口是HTTP请求的默认端口)。我这样做的原因是我的服务器上面搭载了不同的网站,而这些网站需要通过判断用户访问的域名来决定究竟将请求分发到那个处理容器中,因此在我的处理中,我还有一个外部的nginx服务器,用于域名的分发,将mhy12345.xyz这个域名下的所有访问都映射到8022端口上去,进而被容器截获。

原创文章地址:【从零开始使用docker搭建wordpress博客】转载时请注明出处mhy12345.xyz

无锁编程教程:强内存模型与弱内存模型


内存重排有非常多种类,但是并不是所有的内存重排都会经常发生。这决定于你是用的处理器类型以及你是用的工具链(toolchain)

一个内存模型告诉你,对于一个指定的处理器或工具链,究竟哪种类型的内存重排可能出现。需要时刻警醒,内存重排仅仅会在多线程无锁编程中才会显现。

经过一段时间的研究——查阅网上的资料以及亲手实验,我成功的将他们总结成为如下4种类型。在下图中,对于所有右边的模型,不仅满足其左侧模型的所有要求,并且还更近一步。通过图示,我们可以画出一条清晰地界限指定强/弱内存模型。

上图中,所有的实际的硬件类型都对应了一个硬件内存模型,而硬件内存模型又对应了一个内存重排的严格性等级。

在内存重排方面,不同类别的处理器表现不尽相同。不过这些表现只有在多核条件下才能表现出来,鉴于多核是当今的一个主流趋势,所以我们需要对这些内存顺序问题有所理解。

有了硬件内存模型,我们也有软件内存模型。技术上来说,当你编写并调试可移植的C11,C++11或Java的无锁代码,你只需要关心软件内存模型。但是了解了硬件内存模型,你可以知道为什么一个错误的代码在某些处理器上运行毫无问题。

弱内存模型

在一个弱的内存模型中,我们可能遇到所有的四种内存重排。这些重排我在之前的文章中已经讲解过了,在不影响单线程程序的情况下,任何的读写操作都会有概率互相交换顺序,这些重排源于编译器和处理器的共同作用。

当一个处理器是弱内存模型,我们倾向于说是“弱有序(weakly-ordered)”,我们又是也会称之为relaxed 内存模型.弱内存模型的一个经典的例子是DEC Alpha. 不过主流的处理器都不是弱有序的。

C11和C++11所描述的弱内存模型在很多方面都是收Alpha影响的,当我们在这些语言中使用底层原子操作时,即便你使用了 x86/64这一类强有序的硬件,你也应该保证正确的内存顺序来保证编译器正确处理编译期间的内存重排。

保证数据依赖性的弱有序模型

虽然Alpha现在已经不再流行了,我们仍然有若干的线代CPU模型继承了弱有序硬件模型的性质

  • ARM,实现中很多手机、平板的处理器,在多核环境下也越来越普及
  • PowerPC,以Xbox 360为典型,也在生活中普及
  • Itanium,现今已经不被Window支持维护,但是仍然被Linux支持,存在于一些HP服务器端。

这些类别对应的内存模型,在很多方面都和Alpha类似,但是他们抱着了数据依赖性(data dependency ordering)。具体来说,如果你在C/C++中写了A->B,那么你永远保证对于B的读取一定至少比A要新,这是Alpha所不能霸主的。对于数据依赖性,我不在这里深究了。

强内存模型

先让我们看看硬件内存模型,强内存模型和弱内存模型的区别是什么呢?对于这个问题,确实有一些争议。但是就我的感觉而言,对于80%的情况,大多数人都有共同的认识。归纳如下——

strong hardware memory model is one in which every machine instruction comes implicitly with acquire and release semantics. As a result, when one CPU core performs a sequence of writes, every other CPU core sees those values change in the same order that they were written.

强硬件内存模型是指,硬件的所有指令都保证了 acquire和release语义。这意味着,当处理器核心进行了一系列写操作,其他处理器核心看到值的改变的一定符合相同的顺序。

这不难通过版本控制的例子想象出来,所有的修改都向共享内存以指定顺序渗透(没有#StoreStore重排),而所有的读取也按照固定顺序(没有#LoadLoad重排),指令的处理也都按照顺序执行(没有#LoadStore重排),在此基础上#StoreLoad仍然是可能的。

在上述的定义下,x86/64系列处理器通常是强有序的,但是在一些特定情况下,这个强有序的保证是不存在的,不过对于应用编写者,我们完全可以忽视这些情况,处理器确实会乱序执行指令,但是这仅仅是处理器内部的问题,重要的是即使如此,所有的内存指令仍然是有序的,因此在多核环境中,我们仍然将其视为强有序的。

运行在TSO模式下的SPARC处理器是另一个强硬件有序的例子,TSO意思是储存全有序(total store order),换句话说,对于向内存的写操作,所有核心有一个唯一的全局的顺序,x86/64也保证了这个性质。从我知道的来看,TSO性质并不被程序员们关注,但是这确实是想顺序一致性又进了一步。

顺序一致性

在顺序一致性内存模型中,内存重排不复存在,整个程序多个线程的指令可以看做不在相交,这时,之前例子中r1 = r2 = 0的情况将不复存在。

现在,想要找到一个多核设备保证了顺序一致性并不容易,不过回顾历史,在1989年,386系列的 Compaq SystemPro 从Intel手册上来看,并没有足够“先进”以至于能够引入运行时内存重排。

顺序一致性一般而言都是作为一个软件内存模型存在的,在编写高级语言时,比如Java5以上你可以定义volatile,在C++11,你可以使用缺省的memory_order指示符,memory_order_seq_cst来实现顺序一致性。倘若你读过Herlihy & Shavit的 多核编程的艺术,注意他们的大多数例子都是基于顺序一致性的。

更多

关于内存模型,还有很多重要的细节,但是在我看来都在工程中不那么重要,比如control dependencies, causal consistency, and different memory types。而对他们的大部分研究都会回到我之前说过的四种组合。

如果你真的希望深入研究,你可以看看剑桥大学的admirably detailed work,以及Paul McKenney的accessible overview 。

 

原创文章地址:【无锁编程教程:强内存模型与弱内存模型】转载时请注明出处mhy12345.xyz

无锁编程教程:Acquire和Release语义

  • 这是无锁编程教程的第四篇文章。
  • 本文详细讲解了内存顺序中Acquire和Release的含义,包括了如何使用甚至屏障命令以及使用C++11的原子数据类型库实现屏障。
  • 如果你发现本文使用了一些没有解释的术语,那么很有可能我已经在本系列之前的几篇文章中有所涉及。
  • 原文地址:http://preshing.com/20120913/acquire-and-release-semantics/

在无锁编程中,线程有两种方法操纵他们的共享内存:他们既可以通过竞争的方式抢夺某一种资源,也可以借助共享内存传递信息来实现相互之间的合作。Acquire和Release对于后者来说是至关重要的:他们可以让信息的传递变得可靠,实际上,缺少或者不正确的Acquire/Release使用是无锁编程中的一个经典错误!

在这篇文章中,我将向大家介绍若干种通过C++实现Acquire/Release的方式。作为引入,我将以最快的速度过一遍C++11的原子类型库,因此,你并不一定需要立即读懂。同时,这篇文章仍然默认我们的编程都不满足顺序一致性。我们将直面存在内存重排问题的多核处理器环境。

不幸的是,倘若你尝试通过搜索网上来学习他们,你会发现Acquire和Release术语的定义过于混乱,根本不知道在说些什么。不过,Bruce Dawson在他的论文中给我们了一系列非常靠谱的定义,而我在这里,也将向大家介绍我自己归纳出的一些定义,尽可能的与现存的C++11原子数据类型相吻合。

Acquire semantics is a property that can only apply to operations that read from shared memory, whether they are read-modify-write operations or plain loads. The operation is then considered a read-acquire. Acquire semantics prevent memory reordering of the read-acquire with any read or write operation that follows it in program order.

Acquire语义修饰内存读操作(包括内存读取或者读-修改-写操作),倘若一个操作被该修饰符修饰(read-acquire),那么他就能够防止其后面的所有内存读/写操作重排到他的前面。

Release semantics is a property that can only apply to operations that write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation that precedes it in program order.

Release语义修饰内存写操作(包括内存修改或者读-修改-写操作),倘若一个操作被该修饰符修饰(write-release),那么他就能够防止其前面的所有内存读/写操作重排到他的后面。

一旦你仔细理解了上述定义,你就会发现acquire和release操作可以通过上一篇文章中说的内存屏障实现——将内存屏障通过某种方式放在read-acquire操作后,或者write-acquire操作前面,这样,内存屏障就能起到acquire/release相同的作用。不过,需要注意的是,从技术上来说还会复杂一些,不过并不影响我们理解。

一个很好的地方是,acquire和release都不需要使用#StoreLoad屏障,也就是说,他们总不会太低效。举一个例子,在PowerPC中,lwsync(全称”lightweight sync”,即轻量级同步)指令表现为#LoadLoad,#LoadStore和#StoreStore屏障的组合,在这种情况下仍然比sync要快很多,而sync就是一个#StoreLoad屏障。

直接使用平台的屏障指令

实现我们希望的内存屏障的一种方法是直接使用平台指定的屏障指令,让我们从一个简单的例子出发,假设我们在PowerPC上面编程,而 __lwsync() 是一个编译器的内部用于生成 lwsync 的函数。由于 lwsync 同时引入了多种屏障,因此,不论我们希望使用release语义还是acquire语义,我们都可以用同样的方式建立屏障——在线程1中,将对于 Ready 变量的储存转化为write-release,并在线程2中,将对于 Ready 变量的读取转化为read-acquire.

如果我们让两个线程执行结果为 r1==1 ,那么我们可以确信在第一个线程中,A的赋值操作成功的传递到了线程中,进而保证了 r2 == 42 。在我之前的文章中,我已经详细讲解了#LoadLoad和#StoreStore的原理,因此就不在这里赘述了。

用正规的术语表示,我们可以说:变量 Ready 与数据的读取是同步(synchronized-with)的。而对于同步的理解,可以参见这里。至少我们现在可以肯定这样的策略是可行的,但是他们必须作用于同一个变量上,比如这里的 Ready ,而且读取和储存必须是原子的。由于在这里,Ready是一个int类型,因此它的读写操作在PowerPC上面本身就是原子的。

在C++11中使用屏障指令

在之前的样例中,为了实现屏障代码,我们需要仔细了解编译器以及处理器的版本。并在此基础上设计代码。而假设我们希望写一个支持多处理器的代码,我们可以使用C++11重写我们的代码。在C++11中和原子操作有关的所有的数据类型都存在于std命名空间中,我们在之后的代码中,默认包含 using namespace std; 。

在C++原子库中定义了一个可移植的函数 atomic_thread_fence() ,这个函数接受一个参数来决定屏障的种类。当然,比如 memory_order_acquire 和 memory_order_acquire 就是一种选择,我们可以把这个函数放在之前我们放 __lwsync() 的地方。

不过,还有一点点小小的缺陷,那就是在PowerPC,我们可以保证 Ready 是一个原子变量,但是我们不能够假设这适合与所有的平台,因此我们应该将 int 改为 atomic<int> 。唔,这确实是一个挺愚蠢的改变,因为现在所有CPU对于int的读写都是原子的。不过我将在这里详细叙述这个问题,但是至少现在为止,我们使用这个愚蠢的修改来保证我们理论上100%的正确率吧。

在代码中,参数 memory_order_relaxed 意思是“保证这个操作是原子的,但是我并不指定一个特定的内存顺序限制。”

重新申明一些,所有之前的 atomic_thread_fence() 调用都能够(并很有可能确实是)用PowerPC上的  lwsync 替代的,他们都可以在ARM中生成 dmb 指令,在PowerPC上面, atomic_thread_fence() 也至少不比 lwsync 糟糕。在x86/64上面, atomic_thread_fence() 都被解析成了编译器屏障,因为所有的x86/64的读写操作都自动蕴含了acquire/release语义。这也是为什么x86/64是强顺序(strongly ordered)的。

在C++11中不使用屏障指令

在C++11中,我们实际上可以不显示指定内存屏障指令来实现屏障,我们只需要对于Ready的指令显示指定内存顺序要求就好了。

考虑将所有屏障指令包含在Ready的修改指令自身(注意,这种形式不完全和在外面定义屏障指令相同,前者是不那么严格的)。编译器会生成必要的指令来保证屏障的效果,比如在Itanium里面,所有操作可以被表示为单个指令 ld.acq 和 st.rel 。正如之前所说的,这样的操作保证了 r1 == 1 能够决定 r2 == 42 一定成立,也就是保证了同步(synchronizes-with)关系。

这也是C++11推荐的,表达acquire/release语义的方式,事实上, atomic_thread_fence() 的加入甚至比标准的指定还要晚。

Acquire 和 Release 和锁

正如你所看到的,上述所有的例子都没有使用acquire和release语义引出的#LoadStore屏障,只有#LoadLoad和#StoreStore是真正有用的,这是因为在这个文章中,我选择最简单的例子让大家理解API和语法。

一个#LoadStore比较重要的例子是我们使用acquire和release语义实现一个锁。实际上,这也是acquire和release两个词的来历——获取(acquire)一个锁,和释放(releaseing)一个锁。所有的内存操作内存操作都被这两个命令关在了一个小区域内,进保证锁的临界区的有效性。

在这里,acquire和release语义保证了在持有锁的时候的修改都在锁里面,所有锁的的实现(包括你自己实现的锁),都需要保证这些要求,而这些都是为了能够有效地在两个线程中传递信息,即使是在多核、多处理器环境中。

在之后的一系列文章中,我会展示一个用C++11实现的演示。他可以在真实的硬件上运行,而其中,acquire和release保证了其运行的稳定性。

原创文章地址:【无锁编程教程:Acquire和Release语义】转载时请注明出处mhy12345.xyz

浅析CapsNet的原理以及Pytorch实现

原文链接:Dynamic Routing Between Capsules

之前对于数字识别等算法,CNN已经取得了非常不错的算法,而作为一个新晋的算法,CapsNet并无法立即超越原来CNN的精确度。但是从另一方面来说,在传统网络中,由于参数过于密集,特征本身混杂在密集的全连接中,想要提取出来非常困难。CapsNet可以说是挑战这种传统网络缺点的一次成功的尝试,下面就来看看Hinton这篇论文讲了什么吧——


概述

在这篇文章中,Hinton提出了一种新颖的模型CapsNet来解决传统的手写数字识别MNIST问题,并取得了较好的效果。CapsNet相比于传统的卷积神经网络CNN有如下创新:

  • 对于特征向量(Channels),使用其模长表征该向量的重要程度。
  • 对于特征的层次传递,不再是使用传统方法——高层特征来源于底层特征的加权求和,而是引入一个Routing策略。

从CNN到CapsNet

与CapsNet相对应的是传统的卷积神经网络CNN,事实上,在CapsNet在构造上和CNN非常相似,其中很多部分甚至直接使用了卷积层,因此本文尝试通过对比的方式在回顾CNN的同时介绍CapsNet。

Capsule是什么?

在CNN中,一个特定的卷积核可以提取出原图中的某一个局部的特征信息。而多个卷积核的并列,等同于同时记录了多种不同的局部特征,为之后整合成一个更加复杂的特征做好了铺垫。

举一个例子,一个普通的MNIST图片(1个28*28维向量)经过一个[kernel_size=9*9,out_channels=10]的卷积核,可以得到10个20*20维的特征向量。这10个特征向量可以记录宽度、扭曲,粗细等不同细节。

再让我们看看CapsNet是怎么构造出来的——

Capsule,胶囊,在这里,可以理解为一个功能独立的小模块,他可以产生一个特征向量。比较而言,CNN中的一层,可以类比于CapsNet中的out_channels个Capsule。

与CNN相似,特征经过每一层的组合,从简单特征慢慢变得复杂,一个高层的Capsule的输入依赖于低层Capsule的输出。这种依赖关系不在是CNN中的加权求和,而是另外一种更加巧妙的方式,具体细节将在后面详述。

特征向量在Capsule间的传递已经讲解了,那么特征向量在Capsule内部干了什么呢?这就依赖于Capsule的设计者的想要解决什么问题了,至少在本文MNST识别中,Capsule内部执行了一次卷积操作。

特征向量的重要性权重

不论是CapsuleNet还是CNN,我们都通过卷积操作,提取出了特征向量。不同的特征向量重要性不尽相同。那如何处理每一个特征的重要性呢?

在CNN中,由于相邻的卷积层中,第i层的输入是第i-1层所有输出的加权和,因此,我们可以用了一个矩阵来表示第i-1层的第X个特征向量对于第i层的第Y个特征向量的重要性。这个矩阵恰好对应了一个线性全连接层,可以通过梯度下降算法学习。

而Capsule Net提出了一个全新的方法——将特征向量的重要性记录在向量的模长中!具体而言,倘若Capsule的内部计算出了一个特征向量s_j,我们希望通过一种名为squash的归一化方式,使得模长较大的s_j映射到接近1的特征向量v_j,而模长较小的s_j映射到接近0的特征向量v_j。映射方程如下:

    \[v_j = squash(s_j) =  \frac{\|s_j\|^2}{1+\|s_j\|^2} \frac{s_j}{\|s_j\|}\]

Routing策略

如果说在传统算法中,我们通常先用网络求解出一系列低级特征向量s_i,和一个表示该特征向量对于高一层特征j重要性的标量b_{i,j},则高一层特征的输入可以表示为

    \[s_j = f \left( \sum_j b_{i,j}*s_i \right)\]

实际上,相比于之后我们将介绍的Routing策略,原来的方式略显笨拙,因为b_{i,j}是一个于s_i无关的量。而我们希望的是b_{i,j}随着s_i而自适应调整。这也就是Routing策略的设计初衷。

在Routing策略中,b_{i,j}不再是通过梯度下降算法学习出来的,而是通过若干次迭代得到的——

每一次Routing初始时满足b_{i,j} = 0

对于b_{i,j}做一遍softmax归一化【注:论文是这样写的,不过我感觉softmax应该是第一维啊……不过实际上应该没有太大的差别】,

    \[c_{i,j} = \frac{exp(b_{i,j}) }{\sum_k exp(b_{i,k})}\]

归一化之后的数组c_{i,j}满足 \sum_k c_{i,k} = 1,换句话说,就是我们得到了低层s_i组合出高层s_j的加权系数c_{i,j}了。

    \[s_j = \sum_i c_{i,j} \hat{u}_{j|i} , \hat{u}_{j|i} = W_{ij} u_i\]

对于初始情况,我们的b_{i,j}=0,所有局部特征向量等权重得贡献到高一层特征中去(注意,即使是等权重,由于向量本身的模长不同,一次不同的低层次特征向量对于高层次特征向量的影响也不尽相同)。不过随着迭代的深入,b_{i,j}会发生改变,每次变化量a_{i,j}的定义如下:

    \[a_{i,j} = v_j \cdot \hat{u}_{j|i}\]

其中v_j = squash(s_j).

这个定义式的理解其实也很简单,我们相信如果一个输入向量和输出向量的方向相近,这个向量就是重要的,在下一次迭代中我们就会倾向于给这个输入向量更高的权重。

    \[b_{i,j} \rightarrow b_{i,j} + \hat{u}_{j|i} \cdot v_j\]

损失函数的设计

多层Capsule顺序链接,最后一层包含10个Capsules的特征向量v_k,这里的v_k里面包含了两个信息

  • v_k的模长包含了输入数据究竟像不像这个Capsule代表的数字。
  • v_k的向量方向包含了足以刻画原来图像的所有重要特征。

这两个信息我们分别可以设计一个Loss值来表示.

刻画相似度的Margin Loss

首先定义三个个超参数m^+ = 0.9, m^- = 0.1,以及\lambda = 0.5,并假设T_k = 1当且仅当输入图片属于第k类。

    \[L_k  = T_k max(0,m^+ -  \| v_k \| )^2 + \lambda (1-T_k) max(0, \|v_k \| - m^-)^2\]

这个式子的原理就是我们希望对于正确的那一类的向量的模长大于等于m^+,而其他分类错误的类别的向量模长小于等于m^-.

用于正则化的Reconstruction Loss

我们使用特征向量的模长能够构造出Margin Loss,这时,我们并没有使用特征向量本身,因此至少对于MNIST这个课题来说,我们可以利用最后的特征向量,来尝试恢复原来的输入数据,进而产生一个Reconstruction Loss,有利于模型的防止过拟合。

不过这里,论文中注明Reconstruction Loss仅仅用来作为一个正则项,并不能够主导模型的效果,因此在实际Loss中,Reconstruction Loss仅仅贡献一个很小的比例0.005.

使用CapsNet解决MNIST问题

整个模型包含一个CapsNet用于提取特征,和一个ReconstructNet用于尝试恢复最终提取出来的向量。其中CapsNet结构如下——

在这里我们只用了单层CapsNet,首先,对于原图进行一次卷积,得到一个256维向量,然后在进行卷积,得到32个8维向量组成的Capsules。通过之前介绍的Routing策略,我们可以对于这些低层次的Capsules合成10个代表数值的高层Capsules,每个特征向量16维。这些向量中,正确的那一个特征向量进而传到Reconstruct Net中,验证其是否真的表示了那个数字。

 

解码部分单纯由三层带激活函数的全连接层实现,最终的ReconstructionLoss决定于原图和解码后向量的距离。

 

Pytorch实现

我的实现代码参考了论文作者的实现,在这个实现中,几个常用的pytorch函数被多次用到,所以读者需要先确定你理解了这些pytorch函数。

  • view
  • unsqueeze
  • expand

其次,代码的分块清晰对应了流程图中的不同部分,包含了PrimaryCaps模块,处理处最底层的Capsule向量,以及通过一层AgreementRouting决定出的第二层Capsule向量(DigitCaps).

预处理

一个非常神奇的东西是,pytorch作为一个非常成熟的框架,竟然没有one_hot表示的内部实现,所以我们需要自己实现一个代码将标号转化为one_hot表示。

这个转换是网络上提供的经典转换方式,使用了_scatter函数。感兴趣的读者可以查阅文档了解这个函数的作用,这里就不细讲了。

Squash函数

squash函数的定义式是

    \[v_j = squash(s_j) =  \frac{\|s_j\|^2}{1+\|s_j\|^2} \frac{s_j}{\|s_j\|}\]

而函数只是无脑翻译成代码而已。

PrimaryCapsule模块

PrimaryCapsule通过卷积生成了最底层的向量,其卷积核大小都在论文中(也在流程图中)清晰指出了。

Routing模块

Routing模块本质上是通过三次迭代,得到每一个Capsule向量对于下一层的Capsule的贡献大小。

整体结构

将两个模块合并为1个模块即可得到如下结构

 

原创文章地址:【浅析CapsNet的原理以及Pytorch实现】转载时请注明出处mhy12345.xyz

无锁编程教程:通过版本控制理解内存屏障(Memory Barrier)

  • 这是无锁编程教程的第三篇文章。
  • 本文主要介绍了内存指令重排的另外一种情况:由于缓存的原因导致的线程间内存操作相互不可见的原理,并介绍了四种内存屏障模型#LoadLoad,#StoreStore,#LoadStore和#StoreLoad

如果你使用过版本控制系统,那么你也许能够更容易理解内存顺序,进而理解无锁代码的诸多特性。

理解内存顺序需要两步,第一步在我之前的文章编译期间的内存顺序 已经成功介绍了,而第二步,则是这篇文章我想讲的,来自于处理器本身的运行时的内存操作重排。和编译器的重排相似,处理器的重排也是对单线程程序不可见的,只有在无锁程序中,共享内存被多个不互斥的线程同时访问时才能够出现。不过,与编译重排不同的是,处理器重排只在多核/多处理器系统可见。

你可以通过强制一些指令表现为内存屏障来保证正确的内存顺序,从某种意义上来说,你只需要这些技巧就够了,因为这样,编译器顺序就已经自动维护了。这些指令包括但不限于:

  • 某些特定的汇编指令,例如PowerPC的 asm volatile("lwsync" ::: "memory")
  • 任何Win32的原子操作(Interlock operation),Xbox360除外
  • 大部分C++11原子类型的方法
  • 与POSIX锁相关的操作,如 pthread_mutex_lock

既然有很多的指令都能表现的如同一个内存屏障,那么内存屏障的种类就有很多种了。实际上,上述的这些指令所代表的内存屏障都并不相同。leading to another possible area of confusion when writing lock-free code。为了让读者能够更加清楚,我准备通过类比的方式介绍大部分内存屏障的种类。

首先,考虑经典的多核系统:双核,每个核有32KB的私有L1缓存,1MB的公有L2缓存,和512MB的公有主存。

 

一个多核系统有点像一组程序员合作完成一个工程,他们用了一个很奇怪的源码维护方式。比如一个双核系统意味着两个程序员,我们不妨称他们为Larry和Sergey

在我们的右边,我们有一个公有的,核心代码仓库,这一部分表示了主存和L2缓存。Larry与Sergey分别将将他们的相关代码拷贝到自己的私有电脑上,这个私有电脑代表了每一个核拥有的L1缓存,由于每一个机器都有一个暂存区域,默默地耿总寄存器以及局部变量。我们的两个程序员坐在电脑前,不停地改动他们自己暂存区中的代码拷贝,这里的改动指的是基于自己在内存中(自己的私有拷贝)看到的数据,进行一系列决策,并且更新内存中的数据,和线程的执行过程完全相同。

现在,我们再来看看代码控制的策略吧,在这个类比情形中,源码控制的策略非常奇怪。当Larry和Sergey修改了自己的私有代码仓库,他们的修改逐步的渗透到中心代码仓库,而且这种渗透是随机的。一旦Larry修改了本地代码X,修改一定会在通过渗透与中心代码仓库同步,但是我们无法保证渗透的时间。也许同步在修改后立即发生,也许在修改后很久很久才成功同步。甚至当Larry后续修改了代码Y和Z,后面的修改比前面的修改更早渗透也是有可能的。在这样的情形下,内存的写从主存的角度来看,是完全乱序的。

同样的,在Sergey的机器上,修改从公共代码仓库反向同步到私有代码仓库的时间也是不固定的,内存读的顺序因此也被打乱了。

现在,倘若一个程序员在这个代码仓库中工作,他既不会知道中心代码的渗透同步何时在发生,他甚至不能知道是否有其他程序员在和他一起工作!这样,程序员就可以和我们的线程联系到一起了。顺便一提,之前曾提到过的基本规则——单线程无法分辨内存的乱序仍然是满足的。

上述类比在程序员们开始处理代码仓库的同一个文件时,变得很有意思。首先,我们复习一下之前文章中提到的一个问题:X和Y都是初始值为0的全局变量:

考虑X和Y是存在于Larry的私有仓库的两个文件,同时X和Y也存在于公共代码仓库和Sergey的私有仓库。Larry在自己的私有仓库的X中写下了一个1,同时Sergey也在同时向自己的私有仓库Y写下了一个1。现在,由于他们写的太快了,双方都在自己修改还没有渗透到公共仓库的情况下查询另一个文件的值。他们会发现同时满足r1=0和r2=0。这个结果在原来是根本无法理解的,但是通过代码仓库的类比,我们发现这中情况的发生是显然的。

内存屏障的种类

幸运的是,对于这种无法预测的渗透同步操作,Larry和Sergey并没有束手无策。他们拥有一个特殊的指令,称之为“屏障(fence)”。屏障(fence)的表现和内存屏障(memory barrier)相似,且在我们的类比中,我们可以定义出四种不同的内存屏障(memory barrier),每一种屏障通过一种“屏障指令(fence instruction)”实现,且代表了一种为了避免的内存重排。举一个例子#StoreLoad是用来防止一个内存写后面一个内存读这样的指令的重排的。

正如Doug Lea指出的,这四个类别非常清楚地对应了真实CPU上的指令,但是也不近绝对。在大多数情况下,CPU的指令可能表现的向上述一些屏障类型的组合,甚至外加一些其他额外的效果。不过,只要通过类比你理解这四种屏障的含义,你就可以很轻松拓展到真实CPU上的情况了。

#LoadLoad

一个#LoadLoad屏障用于防止屏障前的Load操作和屏障后的Load操作的重排。

在我们的类比中,一个#LoadLoad屏障等价于从中心仓库pull一次。考虑 git pull , hg pull , p4 sync , svn update 或者 cvs update ,都是作用于整个代码仓库的,如果其中有任何合并冲突,那么就只有随机舍弃一边的修改了。

这里有一点需要注意的,#LoadLoad操作并没有保证pull的一定是最近的修改,他甚至可能pull到一个较早的修改,不过可以保证的是,屏障后的Load操作至少会比之前的Load操作更新。也就是说至少不会比最近渗透同步到私有仓库的那个文件早。

听起来,这是一个非常弱的保证,不过仍然能够有效防止读取到过时的信息。考虑一个经典操作,Sergey通过比较公共的标记(flag)来判断是否有一些数据被Larry更新了,如果flag是真,那么他就可以在读取数据之前使用#LoadLoad屏障来保证数据已经成功更新的值。

诚然,这个例子要求 IsPublished 标记自己渗透到Sergey的私有仓库,而这并没有确切发生时间,不过只要标记成功渗透过去,那么Sergey久一定可以通过#LoadLoad屏障防止读到的 Value 比标记老。

#StoreStore

一个#StoreStore屏障用于防止屏障前的Store操作和屏障后的Store操作的重排。

在我们的类比中,一个#StoreStore屏障等价于向中心仓库push一次。考虑 git push , hg push , p4 submit , svn commit 或者 cvs commit ,都是作用于整个代码仓库的。

同理,我们#StoreStore操作可能不会立即进行,而是存在一些延迟,类似于异步操作。因此,即使Larry执行了#StoreStore,我们并不能得出什么时候他的所有的Store操作在中心仓库可见。

相似的,虽然看起来#StoreStore屏障非常的弱,但仍然足够用来防止Sergey看到过时的数据。还是原来的例子,Larry只需要先讲数据放在储存下来,然后使用#StoreStore屏障,保证之后对flag的储存一定晚于数据就好了。

我们假设 IsPublished 自发渗透到了Larry的私有仓库,一旦Sergey发现了flag的变化,那么他可以肯定此时读到的Value是足够新的。有趣的是,这样的工作甚至不需要Value是一个原子数据类型,甚至一个复杂的大结构体也可以使用这种方式传递。

#LoadStore

不同于#LoadLoad和#StoreStore,我们不太好用版本系统的方式理解。最好的理解方式很简单,就是用从指令重排的角度理解。

考虑Larry有一系列操作,其中一部分让他从自己的私有仓库读取一些数据到寄存器,另一部分将寄存器的信息写回到私有仓库。在一些特殊的情况下,Larry有能力去打乱这些指令的顺序。一旦他遇到了load操作,他看看之后的所有store操作,如果这些store操作完全和当前的load无关,那么他允许这些store提前执行,并在之后执行load。在这种情况下,基本规则——单线程无法分辨出内存乱序是满足的。

在真实CPU上,如果在load操作时发生了cache miss,而在store操作时发生了cache hit,处理器可能会尝试上述的内存操作重排。不过,硬件的实现细节并不会有助于我们理解内存屏障。现在Larry有一个很无聊的工作,不过有些时候他被允许自行调整工作的顺序,这样的调整是不可预料的。幸运的是,存在这样的一个时间花销并不昂贵的指令,强制Larry不在这个地方随意调整读写的执行顺序。

在我们的类比中,即使存在了#LoadLoad屏障和#StoreStore屏障,Larry仍然可以在Load和Store中间进行重排。不过在真实CPU中,如果一个指令表现为#LoadStore屏障,那么这个指令一定可以以理解为#LoadLoad和#StoreStore的其中之一。

#StoreLoad

一个#StoreLoad屏障保证屏障前所有的Store在其他处理器可见后,屏障后的Load操作的结果一定比Store操作的结果更新。换句话说,这个屏障保证了屏障前的所有store操作不会发生在之后所有load操作之后。符合顺序一致性。

#StoreLoad非常特别,因为他是唯一一种可以防止前文例子中结果为r1=r2=0的情况的发生。看到这里,你一定会非常疑惑,为什么#StoreLoad操作就是如此的特别呢?毕竟#StoreStore等价于代码管理的push,#LoadLoad等价于代码管理的pull,而这两种内存屏障都是不够的。因为push操作可能被延迟若干时间,而这时pull并没有能力去获得最新的版本。这结识了为什么PowerPC的 lwsync 操作同时支持了#LoadLoad,#LoadStore和#StoreStore,但是仍然无法防止r1=r2=0的出现。

在类比中,#StoreLoad屏障push了所有的局部修改,等这些修改push完成后,再pull最近的远程库的HEAD。在大多数处理器中#StoreLoad屏障的时间花销远大于其他三种内存屏障。

如果我们使用了#LoadStore,我们就能够得到一个万能的内存屏障,同时支持了本文介绍的四种内存屏障。正如Doug Lea所说,所有支持#StoreLoad屏障的指令都是一个完整的内存屏障。

版本控制的类比告诉我们

之前曾说过,每一个处理器在处理内存重排的策略不尽相同。在x86/64系列中,内存模型是抢的,内存重排被降低到了最小。而在PowerPC和ARM中,内存模型是弱的,Alpha则自成一派。辛运的是,我们的类比是依赖于弱内存模型的,只要我们在类比中成功理解了屏障操作,那么我们就可以随心所欲解决主流CPU的无锁编程任务了。

这个类比在C++11下也非常实用,因此,如果我们这个类比来理解无锁代码,那么也可以在很多平台上正确编程。

在这个类比中,我曾假设所有程序员在不同的核上执行程序,而在实际的操作系统中,线程有时会在不同的核上交替运行,不过我们的假设依然成立。同时,我们的类比是以C++为载体,不过也可拓展到其他语言上。

至今为止,我并没有介绍完所有的内存屏障,比如,同时存在有数据依赖性的屏障,我在之后的文章中将深入讲解。不过本文的这四个算是最重要的了。

如果你好奇CPU工作的内部细节,比如内存写缓冲区, 缓存一致性协议和其他硬件实现细节。我推荐读者阅读资料。实际上,我相信只要你成功的实现了一些无锁的代码,你就已经非常熟悉有关的硬件细节了。

原创文章地址:【无锁编程教程:通过版本控制理解内存屏障(Memory Barrier)】转载时请注明出处mhy12345.xyz

无锁编程教程:编译期间的内存顺序(Memory Order)

  • 这是无锁编程教程的第二篇文章。
  • 本文主要介绍了内存指令重排的其中一种情况:编译器优化导致的内存重排。这种内存重排可以解释单核处理器下多线程程序的诸多表现。

当你写了一个C++程序,并让他在CPU上面运行,其中的内存指令顺序会产生重排,这样的重排是编译器优化与处理器优化共同导致的,其初衷都是让你的程序能跑的更快。

当然内存指令的重排也有一些普遍承认的规则,对于编译器以及处理器的开发者,都需要保证:

Thou shalt not modify the behavior of a single-threaded program.

你的修改不能够改变单线程程序的行为。

由于这样的规则,内存的重排对于单线程的开发者通常都不会被注意到。甚至在很多的多线程程序中,由于程序中使用了“锁(mutexes)”“信号量(semaphores)”和“事件(events)”这类用于在其所在位置防止内存重排的操作。内存重排仍然不会被注意到。然而,当我们来到“无锁编程”中,公共内存的访问没有了任何互斥的保护措施,内存顺序的灾难性后果才终于显现出来

不过,你仍然不需要在多核处理器上考虑内存重排的问题,正如我在无锁编程教程:简介 中提到过的,我们可以利用满足顺序一致性的类型(如Java中的 volatile  变量和C++中的原子变量),使用微小的时间开销代价来解决内存顺序的问题。不过我不准备在这里详述,我想在这里讲讲编译器对于非顺序一致性的内存指令重排的影响。

编译器的指令重拍

正如我们知道的,编译器的作用就是将人们可读的源代码转化成机器可读的机器代码,在翻译中,编译器可以自由做很多等价变换。

一旦编译器在保证单线程程序行为不变的基础上,产生了一系列指令重拍(通常情况下,这种重拍只会在编译器优化开关打开时进行)。考虑如下的代码片段:

如果我们使用了GCC 4.6.1并禁用编译优化开关,那么编译器生成的机器代码可以使用  -S 指令查看。全局变量 B 的内存写操作在全局变量 A 读操作的后方,和源代码顺序吻合。

对比一下打开编译器优化开关 -O2 之后的结果:

这时,编译器自作主张修改了内存读写的顺序,至少对于单线程程序完全不能区分这两种顺序。

然而,这样的编译器重排在无锁数据类型中却产生了问题,下面使用了一个常用的例子,这个例子中,我们使用一个公开的标记 isPublished 来表示某个公开变量的储存是否完毕:

考虑如果编译器将 IsPublished 的储存放在 Value 的储存之前会发生什么。甚至对于但处理器的程序,我们都会发现出了问题,首先,一个线程依次执行了 IsPublished 和 Value 的储存,在这期间,另外一个线程在监视到 IsPublished 值改变后,会认为 Value 已经更新了,而事实上没有。

当然,也有可能编译器并没有重排这些操作,在这个情况下,我们的程序也有可能和其他无锁程序一样正常结束。特别是如果我们的多核CPU拥有 强内存模型 ,例如在简介部分提到的x86/64结构,或者是在一个单处理器环境,程序都会表现的毫无问题。如果事情正式这样,我们只能说自己是太幸运了,换句话来说,我们还是应该从学习如何从原理上杜绝内存重排导致的程序行为异常。

显示定义编译屏障

最简单,也最直接的防止编译器重排的方式是编译器屏障(Complier Barrier),在之前的文章【英】中已经讲述过相关的问题。下面我们将介绍如何使用GCC实现一个编译器屏障,在Microsoft的Visual C++中, _ReadWriteBarrier 拥有同样的功能。

当加入了编译器屏障,在编译器优化开关打开的情况,内存写的指令仍然会按照我们希望的顺序生成。

同样的,如果我们试图通过引入编译器屏障,修改之前的 SendMessage 函数(这里只能在单处理器情况下正确,多处理器仍然存在问题)。实际上,不只是Sending操作需要编译器屏障,Receiving操作也需要编译器屏障限制。

诚然,编译器优化已经足够用来防止单处理器下的内存重排。但是现在已经2012年了,也就是说,在这个多核处理器普及的年代,如果我们仍然希望保证在任何处理器下,内存操作都按照我们想要的顺序进行,那么编译器屏障是不够的,我们需要引入CPU的屏障指令,或者其他的有内存屏障作用的操作。而这些操作将会出现在我的下一篇文章中。

Linux内核暴露了部分CPU的屏障指令,我们可以使用如 smb_rmb 等编译宏(preprocessor macros)来引入,这些操作在单核处理器系统中会退化为普通的编译屏障。

隐式定义编译屏障

有很多其他的防止编译器重排的方式,实际上,我们刚刚介绍过的CPU的屏障指令就可以表现的想一个编译屏障。下面是一个用PowerPC下的宏定义实现屏障指令的例子:

#define RELEASE_FENCE() asm volatile("lwsync" ::: "memory")

我们将宏 RELEASE_FENCE 放置在我们希望防止内存重排(包括编译器重排)的任意位置。比如可以让我们的 sendValue 函数变得更加安全。

在新的C++11的原子操作库中,所有的非relax的原子操作都表现的像一个编译器屏障。

顺便一提,所有包含了编译屏障的函数,自身一定能够表现为一个编译屏障(即使这个函数是内联函数)。

实际上,不论内部是否包含编译屏障,大部分的函数(出去内联函数和标记为pure的函数,以及链接时生成代码(link-time code generation))调用都可以看做是一个编译屏障。进一步说,对于一个外部函数的调用甚至比普通的编译屏障还要强,因为编译器完全不知道这些外部函数是什么,因此编译器必须要完全放弃尝试优化内存调用的顺序。

这其实是非常显然的,在之前的代码中,假设 sendValue 是定义在其他外部的库中的,编译器无从知晓是否 sendValue 依赖于 foo->bar 的值。也不知道 sendValue 是否会在内存中改变 foo->bar 的值。因此,为了满足内存乱序不改变单线程程序的行为这个规则,编译器一定不会进行任何的内存操作的重排。同样的,在函数调用之后,即使编译器开了O2优化,编译器还是会生成一些代码重新从内存中提取 foo->bar 的最新值,而非默认他的值为5。

正如读者看到的,在很多情况下,编译器的自动指令重排都是被禁止的,甚至在一些极端情况,编译器必须要理解从内存中读取并更新某个值。我相信这些规则就是为什么人们一致认为C++中的 volatile是没有存在意义的。

Out-Of-Thin-Air Stores

不知道读者是不是感觉到了指令重排让无锁编程非常的棘手呢?在C++11规范诞生之前,从技术上是没有任何方式来防止编译器对指令惊醒重拍。特别的,当一个内存区域什么东西也没有时,编译器可以按照自己的想法向共享内存写东西。这里给出一个小例子:

诚然,这种情况很少在实际中发生,但是没有东西可以组织编译器试图在与A比较前就将变量B储存在寄存器(register)中。优化后的代码如下:

同样,编译器的优化完全没有影响我们提到过的基本规则。一个单线程程序仍然会对我们所做的优化一无所知,但是在多线程环境中,我们得到了一个即使A的值是false,也可以擦除其他线程对于B的所有改变的操作 B=r 。这并不是我们代码的初衷!这种问题非常鲜为人知,而理论上并不是不可能发生,这就导致了人们认为C++并不能很好的支持多线程,即使事实上我们已经开开心心的写了一百年的C++多线程无锁程序!

我不知道有任何人被这种凭空而来的内存写坑过,也许这只是因为我们写的无锁代码并没有能够恰好优化到能够导致问题的组合。至少如果我遇到了这个问题,我会尝试去向编译器提交问题。如果你遇到了这个问题,可以在下文评论。

现在,由于这种情况会导致“数据竞争与冒险(data race)”新的C++11标准显式禁止编译器引入这种情况。你可以在 most recent C++11 working draft的$1.10.22看到:

Compiler transformations that introduce assignments to a potentially shared memory location that would not be modified by the abstract machine are generally precluded by this standard.

对于可能向潜在共享内存地址写数据的指令,在这个标准中,被禁止进行编译器的指令重排优化操作。

为什么会有指令重排

正如我一开始就已经说过的,编译器优化内存操作的顺序的动机和处理器相同——为了让代码运行的更快。这种优化直接导致了现代的CPU构造。

可能我比较天真,但是确实非常的质疑一些理论说编译器在八十年代就做了很多指令重拍的操作,那是的CPU至多只包含大约十万个晶体管。我不认我在这种情况编译器可以做到这一步。但是自从摩尔定律给CPU设计者提供的可以操作的晶体管数量翻了大于10000倍之后,这些晶体管于是乎被用来实现了类似于流水线(piplining)、内存预取(memory prefetching), 指令级并行(ILP)和最近的多核(multicore)。从结果上来看,这些操作使得指令重拍能够为程序实现较大的性能优化。

最初的Intel Pentium出现在在1993年,包含了所谓U pipe和V pipe。这是我第一次记得人们开始广泛讨论流水线和指令顺序的重要性的相关问题。近年来,当我开始使用VisualStudio的x86汇编,我甚至十分惊讶的在这里几乎没有内存指令重排。另一方面,在我多年来通过PlayStation3的反汇编,我发现编译器同样也到达了这一步。不过这仅仅是我的个人体验罢了,并不能改变我们需要在无锁代码中考虑内存顺序的必要性。

 

原创文章地址:【无锁编程教程:编译期间的内存顺序(Memory Order)】转载时请注明出处mhy12345.xyz

无锁编程教程:简介


无锁程序的设计非常复杂,一方面,需要读者对于并行计算涉及概念有较深的理解,另一方面,由于不同平台表现不一致,调试困难等客观原因,即使写出了程序也不容易检验。我的无锁编程始于Bruce Dawson的论文,十分幸运的是,我甚至有机会在工作中,借鉴Bruce的一些无锁数据结构编程技巧,并运用到Xbox 360等平台的编程与调试中。

从那以后,我写了一系列资料,从最基本的理论推导到最实际的代码编写,甚至最底层的硬件细节都有所涉及。然而不幸的是,这些资料甚至有些都是相互矛盾的,比如,有一些材料直接假定了顺序一致性(sequential consistency),并借此避免了任何有关于内存顺序细节的讨论,而在另一些材料中却没有做这些假设。随着C++11原子数据类型 的出现,本来就非常混乱的无锁编程变得更加复杂,让我们更难解释无锁算法的运行原理了。

在这篇文章中,我希望能够重新系统得介绍无锁编程,从对于每一个基本概念的定义开始。运用流程图,展示出这些概念如何互相关联,进而分析这些概念的一些细节。如果你准备继续读下去,我假设你已经理解最简单的多线程程序的编写,以及锁(mutex),信号量(semaphores)等同步机制。

无锁编程是什么?

大多数人对于无所编程的理解都停留在“不用锁来写多线程程序”。毋庸置疑,这样的定义是没有问题的,但是并不完整。对于无锁编程,被学术界认可的定义更加宽泛,学术界认为,“无锁(lockfree)”仅仅是一种代码的性质罢了。

简单的来说,如果程序的一部分满足接下来提到的这些条件,那么我们就可以认为他是“无锁”的,反之,如果不满足,则程序不是“无锁”的。

通过上图,我我们发现“无锁(lock-free)”这个词中的“锁(lock)”并不是指代码中的“锁(mutex)”,而是指的是能够通过某种方式“阻塞(locking up)”整个程序的可能性。这个可能性可能来源于经典的“死锁(deadlock)”,也可能由于很糟糕的内存调度顺序使得程序停滞不前(这可能变成一些恶意攻击者的突破口)。这听起来挺搞笑的,但是由于持有锁(mutex)的线程的调用顺序是任意的,因此最坏的情况是可能发生的,纵使有些时候,理论计算告诉我们“最坏情况”是一个不可能事件(概率为0),但是从概念上来说,只要“可能发生”阻塞,那么这个程序就不是无锁的。

举一个例子,对于下面的无锁程序,在初始 X=0 的情况下,什么样的调度顺序可以导致程序永远按无法退出循环?(这个问题留给读者自己思考)

没有人指望一个很大的工程是完全无锁的,通常来说,我们希望这个工程中某一个访问了公有内存的代码片段是无锁的。举一个例子,我们可能希望拥有一个“无锁队列”,这个无锁队列支持若干无锁的操作,诸如 push , pop , isEmpty 等等操作。

The Art of Multiprocessor Programming的作者Herlihy 和 Shavit倾向于将上述的操作描述成类的方法,进而对无锁(lock-free)有了一个更简单的定义:

在无限次执行中,可以完成无限次方法调用。

换句话来说,只要程序不停地调用这些“无锁”的方法,已完成的函数调用不停增加,则从算法上来看,系统是不可能发生死锁的。

从无锁编程的定义,我们可以引出一个很重要的结果:假如说我们停止了一个线程,这个操作是不会影响其他线程的执行的。正因为如此,在编写实际程序的时候,所有的线程都必须能够在有限的时间内完成,不论其他的线程干了什么。

顺带一提,如果一个操作被设计成阻塞操作,他有可能仍然是无锁的。比如无锁队列的删除会在队列为空的时候被阻塞,这并不影响他是无锁的。

无锁编程的技巧

当你尝试去实现一个无阻塞的无锁程序,这会引出一系列技巧,比如:原子操作(atomic operations),内存屏障(memory barriers), ABA问题等。从这里开始,问题就变得棘手起来。

这些技巧是如何关联起来的呢?我准备使用一个流程图来解释这个问题:

原子的“读-修改-写”操作

原子操作的定义为一系列可以访问内存,并且不可分割的操作。没有任何线程可以观测到进行了一半的原子操作。在现代的处理器中,很多的操作都是原子的,比如:基础数据类型的“对齐读取(aligned reads)”和“对齐写(aligned writes)”通常是原子的。

更近一步,我们有了 读-修改-写(Read-modify-write) (RMW)操作,这个操作使我们可以原子化更复杂的操作,特别的,当有多个写线程时,这个操作非常有用。原因在于,当多个线程试图去读-修改-写一个内存区域时,他们会自动被排成不想交的一列,并依次执行。在之前的博客中,我已经讲过读-修改-写操作了,比如在 轻量锁, a 自旋锁 和  轻量的日志系统.

RMW操作的例子有Win32编程中的  _InterlockedIncrement ,IOS编程中的 OSAtomicAdd32 ,和C++11中的 std::atomic<int>::fetch_add 。值得注意的是,C++11标准并不保证这个实现是无锁的,具体是不是通过无锁来实现依赖于你的平台。因此,你最好提前了解你的平台是否支持这些无锁操作,或者通过调用 std::atomic<>::is_lock_free 来查看。

不同的CPU系列使用不同的方式支持RMW操作。比如PowerPC和ARM等处理器使用load-link/store-conditional 指令,这种指令使你能够在底层自定义你自己的RMW操作,即使通常并没有人这么干,毕竟普通的RMW操作已经足够了。

正如流程图中所说,RMW十分重要,即使是在只有一个处理器的系统中。如果没有了原子性,一个线程可能被中途打断,并导致一些潜在的问题。

“比较并交换”循环

最常讨论的RMW操作是 比较并交换(compare-and-swap) (CAS)。在Win32里面,CAS通过一系列intrinsics函数实现的,比如 _InterlockedCompareExchange 。通常情况下,我们在循环中使用CAS操作来尝试提交一些操作。具体来说,我们首先拷贝一些公有变量到局部变量中,并进行一些操作来改动局部变量的值,最后,将这些改动借助CAS操作提交至公有可见。

这样的循环是无锁的,因为如果一个线程的if条件测试为false,这意味着他一定紧接着另一个线程执行完毕相同操作的线程之后。尽管在一些架构下,存在 弱化的CAS操作,在这些CAS操作中,上述不一定是if语句判断false的充要条件,但是这些弱化的CAS操作仍然能够有效避免ABA问题。

顺序一致性

顺序一致性(Sequential Consistency)意味着所有的线程都有共同的对于内存访问操作的顺序的判定。这个判定的内存访问操作的顺序恰好等同于在源代码中的内存访问定义的顺序。在线性一致性模型中,一些内存顺序有关的问题不会发生。

一个非常简单(但是显然不可能在实际中使用的)解决内存一致性的方式是禁用编译器优化,并且强制所有的线程在同一个处理器上面运行。这样,即使存在着线程的切换,处理器将永远无法发现自己的内存顺序出现了问题。

一些编程语言即使在优化了代码之后,在多核环境中,依然保证了顺序移植性。在C++11中,你可以定义拥有默认内存顺序(memory ordering)的公共的原子数据类型来实现内存访问的移植性。在Java中,你可以将公有变量标记为 volatile 已实现顺序移植性。下面是一个例子:

由于C++原子操作保证了顺序一致性,因此结果r1 = r2 = 0是不会发生的。从编译器层面来看,编译器添加了一些额外的指令(如内存屏障或RMW操作)来保证顺序一致性。这些额外的指令带来了更大的时间花销,但是让程序员能够以最直观的方式操作内存顺序。

内存顺序

正如流程图中所述,当你在多核计算机上运行无锁程序,且你的程序并没有保证内存顺序一致性的时候,你需要思考如何避免内存乱序的发生。

在线代的处理器结构中,这些试图矫正内存顺序的方法可以分为两类分别是矫正 编译器导致的内存乱序(compiler reordering)处理器导致的内存乱序(processor reordering) 具体而言有如下方式:

  • 一系列轻量级的同步以及屏障指令,这些我将在之后讨论
  • 一系列内存屏障的指令,我在之前已经展示过
  • 一些内存顺序的指令,提供了acquire和release语义

Acquire语义防止该语句后的语句内存乱序,而Release语义防止了该语句之前语句的错排,这些语义特别适合用于处理“生产者/消费者”关联的线程关系,一个线程生产并广播消息,而另一个线程接收消息,这些我也将在之后的文章中详述。

不同处理器有不同的内存模型

不同的处理器有不同的内存模型,在内存重拍的问题上,不同的CPU以来的规则是依赖于硬件的,比如PowerPC和ARM处理器可以修改内存写的执行顺序,而Inter和AMD的x86/64处理器则不行。因此,古老的处理器有更加弱的内存模型(relaxed memory model).

通过C++11,我们可以调用一些固有的模板来无视掉这些由于平台导致的问题。不过我认为程序员们需要知道不同平台的区别。其中比较重要的一点事,在x86/64的处理器层面,所有的读(load)操作都自带了acquire语义,而所有的写(store)操作都自带了release语义,至少对于非SSE指令集和非并行储存的内存模型而言是这样的。从结果上来看,一些在x86/64上运行正常的程序在其他处理器上崩溃就不是一件很奇怪的事情了。

如果你对于处理器如何将内存操作重排感兴趣的话,我推荐你阅读Is Parallel Programming Hard的附录C。并且时刻警醒内存重排有时候是来自于编译器而非处理器。

在这篇文章中,我们有过多的提及无锁编程的一些实际代码编写上的策略,比如什么时候我们应该用无锁编程,我们应该做到什么程度,以及验证你程序有效性的必要性。对于大多数读者,这个简介只是为了给你一些无锁编程的最基本的概念,让你在之后的阅读中不会因为一些简单的概念而困惑。与之前相似,如果你发现有任何的不准确的地方,请通过评论告诉我。

原创文章地址:【无锁编程教程:简介】转载时请注明出处mhy12345.xyz

vim简单教程及配置

vim是什么?

既然今天是向大家安利vim,那么先说说安利的原因吧:

通过官网链接下载vim并且安装后,我们可以看到vim的启动界面——

唔,请关注重点……

我是在安利读者为慈善事业做贡献呢!

这个逼装的,我给99分……剩下1分哪里去了呢?

——剩下一分是因为vim确实确实非常好用

言归正传,vim是一款编辑器,而编辑器是什么呢?

编辑器就是类似于notepad(记事本)这样的只能用来打字的工具,而当这种工具集成了编译运行调试等等功能后,就成了集成开发环境(Integrated Development Environment)也就是我们常说的IDE,比如DevC++和VC6.0。

IDE与编辑器的区别就在于由于IDE集成了所有功能,所以对初学者非常友好,但是开发效率通常来说比较糟糕,反之,编辑器一心只做编辑方面的优化,所以在编写代码方面效率完爆IDE。这些在之后都会提到。

Vim作为一个编辑器,作者亲身经历表示他至少能让你的代码编写速度提升一倍,而且和vim配套使用的g++,gdb还会使你的代码调试速度变成原来的三倍甚至更多。

为什么是vim

  1. 作者作为一个vim党,当然会推荐vim咯
  2. 帮助乌干达的可怜儿童
  3. 无视个人偏好,emacs,notepad++,sublime等“编辑器”都是很不错哒(换句话来说dev-c++,vc6.0,xcode等IDE就不符合这篇文章的核心思想了),当然,vim也属于这些编辑器中的一个
  4. 以后同学们编写代码不一定是在本机,有可能需要登录到其他电脑上,这时能够在终端里面使用的编辑器据我所知也就vim和emacs了,到时候即使你是一个资深IDE党也不得不去学习使用vim。
  5. 我曾在计算机系群里的调查,结果如下(大势所趋,不服不行啊……):
    1. 明确表示使用编辑器编程的同学们中,vim党最多
    2. 对于所有的被调查者vim也有相当大的优势

vim怎么用

不同平台的vim其实都是大同小异的

我们接下来就用mac下的终端vim举例了。

安装

不同平台vim的安装方式不同

  • Windows用户:在vim官网中搜索安装方法与安装文件,需要注意的是,windows下的vim是gvim,表示图形界面版本的vim。
  • Linux用户:可以使用该发行版自带的包管理器安装vim,比如Ubuntu使用 apt install vim
  • Mac用户: brew install vim

与此同时,倘若用vim写C++程序的话,我们还需要安装g++与gdb。

  • Mac用户: brew install g++ ,gdb最好就改成mac自带的lldb好了
  • Ubuntu用户: apt-get install g++ && apt-get install gdb
  • Windows用户:
    • 方法1:首先安装Dev-C++,在安装目录中找到g++,gdb所在的目录,将目录加入windows环境变量path中,至于环境变量该怎么用,有什么意义,不是本文探讨的范畴。
    • 方法2:安装MingW,然后使用mingw-get安装g++。

运行

Windows用户

windows用户在桌面打开图标就好了。

当你看到帮助乌干达的可怜儿童那句话就说明你成功打开vim了~

注意vim存在一个当前目录的概念,windows大家最好还是通过“用Vim打开”一个目录特定文件的方式进入vim以确保当前文件夹就是你想要储存文件的文件夹。否则,倘若直接打开vim的桌面快捷方式,你保存的文件会去一个奇奇怪怪的地方。

而检验gdb/g++是否安装成功,你只需要在CMD里面输入命令 g++ ,看是否报错说没有该命令。

MAC/LINUX用户

mac、linux用户在终端输入vim命令即可,在mac/linux终端里面,你在哪个文件夹下打开的vim,vim的当前目录就是哪个。

而检验gdb/g++是否安装成功,你只需要在终端输入命令 g++ ,看是否报错说没有该命令。

vim简易教程

首先,vim官方是有教程的,在开始界面输入 :help 就可以直接进去

其次,如果想要学习vim,最好拿着电脑跟着教程亲自试一试

最后,要有心理准备,你可能会经历一周左右生不如死的适应过程。

第一步:像用记事本一样用vim

先说个笑话:

问:如何生成随机字符串
答:让萌新退出vim

大家可以自己尝试一下(windows用户不允许使用窗口那个红叉叉)就会发现,进入vim后,不但不容易退出,甚至按键盘是无法直接开始编写程序的,因为vim分为不同模式,开始时进入的模式叫做“命令模式”,是专门输入命令的,而我们需要在“插入模式”中写程序。

模式切换

命令模式:输入命令的模式。之后没有特殊指名,所以命令都在命令模式下输入

插入模式:输入字符直接插入文本的模式

  • 命令模式->插入模式: i
  • 插入模式->命令模式: <esc>

基本操作

vim中,有很多操作以冒号开头,这些操作使用频率相对较低,但不影响其重要性:

退出vim:退出 :q 或强制退出 :q!

  • 查看帮助: :help
  • 运行命令: :!<command> ,例如 :!ls 列出当前文件夹下文件(命令的执行目录为当前vim打开的文件的目录)
  • 保存文件: :w 或 :w <filename>
  • 打开文件(若不存在新建): :e filename

保存与打开文件可以为绝对路径,也可以为一个文件名,此时默认在“当前目录”打开

快捷操作

在命令模式中,命令不一定以冒号开头。

  • 剪切/删除一行: dd
  • 粘贴: p
  • 撤销: u
  • 回退: <ctrl+r>
  • 光标移动:方向键或 h / j / k / l

第二步:像IDE一样用vim

先从一个特定目录进入vim,然后编写程序,并保存为a.cpp.

我们知道,倘若在终端下切换到了源文件所在目录,执行 g++ a.cpp o a 可以将当前文件下的a.cpp编译为可执行文件,同理,调用 gdb ./a 可以使用gdb调试程序(mac是lldb)。

我们还知道,vim中,我们可以使用 :!<command> 调用外部命令,所以我们在vim中输入 :!g++ % -o %< 就等同于从终端用g++命令编译源文件。(注意:命令中的 % 表示当前vim正在编辑的文件的文件名,而 %< 则表示他去了后缀的文件名。)

通过上面所述的手段,我们可以实现在vim中的编译运行:

  • 编译: :!g++ % -o %<
  • 调试: :!gdb %<
  • 运行: :!%< 
  • 查看空间: :!size %<

vim提供了键盘映射函数map,形如 :map A : B ,那么如果我们提前用了映射命令,就不用输入编译命令了。

  • 编译: :map <F9> : !g++ % -o %< <CR>
  • 运行: :map <F6> : !%< <CR>
  • 调试: :map <F5> : !gdb %< <CR>

其中, <CR> 表示回车,读者可以试试没有这个 <CR> 会变成什么。

通过了映射,我们可以直接按 <F9> 编译,按 <F5> 调试。

最后,由于这些map命令时预处理性质的,我们可以将它写入一个叫做vimrc的文件,每次打开vim的时候自动加载

  • 在mac/linux中该文件为 ~/.vimrc
  • 在windows中,可在菜单栏-编辑-启动设置中直接修改

比如我们可以在vimrc中加入

 

第三步:定义自己的vim

之前已经知道vimrc中可以定义编译运行快捷键,实际上还可以有更多的自定义属性,比如:

  • 左边显示行号: set number
  • 查找命令高亮: set hlsearch
  • 开启自动缩进:
    • set smartindent
    • filetype plugin indent on
  • 用鼠标拖拽分栏: set mouse=a
  • 设置折叠: set fdm=marker
  • 设置缩进:
    • set tabstop=2
    • set softtabstop=2
    • set shiftwidth=4
  • 设置代码高亮: syntax on
  • 令插入模式jj为退出: imap jj <esc>
  • 设置颜色: colors evening

其中,颜色我推荐大家使用

加上这些命令之后,界面美观度一下就上升了——

最后,读者可以在文末找到我的vimrc配置文件。

第四步:神一般的编辑器

了解完之前的只是,我们也只能把vim当做记事本来用,下面介绍一些快捷键,可以极大加快编写代码的速度。在开始了解快捷键前,你需要知道vim快捷键的设计初衷是让你可以不用鼠标,甚至手不离开主键盘就可以打字。

基本操作

vim中,有很多操作以冒号开头,这些操作使用频率相对较低,但不影响其重要性:

  • 退出Vim: :q
  • 强制退出Vim: :q!
  • 查看帮助: :help
  • 运行命令: :!<command> ,例如 :!ls 列出当前文件夹下文件(命令的执行目录为当前vim打开的文件的目录)
  • 保存文件: :w 或 :w <filename>
  • 强制保存: :w!
  • 保存并退出: :wq
  • 打开文件(若不存在新建): :e filename

撤销操作

  • 撤销: u
  • 回退: <ctrl+r>

分栏

  • 竖向分栏: :vsp
  • 横向分栏: :sp
  • 不同栏跨越: :<ctrl+w> <up>/<down>/<left>/<right> 或 :<ctrl+w> i/j/k/l

多文件

打开vim时用 vim a.cpp b.cpp 或 vim *.cpp 可以同时打开多个文件,不过第一个文件全屏显示,需要通过快捷键切换。

  • 下一个文件: :n
  • 上一个文件: :N

进入插入模式

  • 当前光标前: i
  • 当前光标后: a
  • 当前行首: I
  • 当前行末: A
  • 当前行后新建一行: o
  • 当前行前新建一行: O
  • 退出插入模式:
    • 默认:  <esc>
    • 在配置文件中加入 imap jj : <esc> 之后,可用 jj 退出插入模式

进入覆盖模式

  • 进入字符覆盖模式,并在覆盖后回到命令模式: r
  • 直接进入覆盖模式: R

复制粘贴与删除

  • 复制当前行: yy
  • 剪切当前行: dd
  • 删除光标位置字符: x
  • 复制之后的10行: 10yy
  • 剪切之后的10行: 10dd
  • 全文复制: :%y
  • 复制第3行到第5行: :3,5 y
  • 剪切第3行到第5行: :3,5 d
  • 粘贴: p
  • 粘贴10份: 10p

光标跳转

  • 行首: ^
  • 行末: $
  • 第5行: 5G 或 :5
  • 光标移动:方向键或 h / j / k / l
  • 文首: H
  • 文末: L

查找替换

  • 查找: /pattern
  • 全文替换: :%s/old_pattern/new_pattern/g
  • 全文替换(每行替换第一个匹配): :%s/old_pattern/new_pattern
  • 第5至10行替换: :5,10s/old_pattern/new_pattern/g
  • 跳到下一个: n
  • 跳到上一个: N
  • 替换所有int单词(正则表达式使用): :%s/\<int\>/long long/g

代码缩进

  • 自动缩进: yy=G 或 gg=G
  • 第五行到第十行向前缩进: 5,10 <
  • 第五行到第十行向后缩进: 5,10 >
  • 接下来五行向前缩进: 5<<
  • 压行: J

其他

  • 括号匹配: %
  • 宏定义(录制操作): q<name>
  • 宏定义调用: @<name> 或 @@
  • 调用make命令: :make

再论Vim的好处

效率高

  1. 使用了vim你的手甚至可以不动鼠标,不离主键盘
  2. 编程中存在的很多类似于复制特定行,粘贴若干遍的操作在vim下都是可以用命令解决的
  3. 查找替换功能强大,连不能查找替换的很多功能都可以用宏来解决,对于批量修改帮助极大
  4. 其配套的gdb让你永远告别肉眼查错,进入二分查错的行列,复杂度直接从O(N)降到了O(logN)

用途广

  1. 基本上所有平台都有vim,而其他IDE只能在特定平台用
  2. vim的操作不依赖于具体语言,不需要每学一门语言都重新学习一个新的IDE
  3. 有丰富的插件可以使用(但是插件方面Vim比起Emacs还是差远了)
  4. Vim模式在很多地方都有支持,比如Emacs和Sublime,所以你学了Vim还可以直接迁移到这些平台上

好玩

  1. 突然发现找到了除大括号换不换行(当然要换)之外新的战场:编辑器用Emacs还是Vim(当然是Vim),引战什么的最好玩了~
  2. 我这人还是非常支持慈善事业的

结语

愿世界和平,乌干达儿童幸福快乐~

 

原文为《【和平向】一波vim安利》,计62班级公众号

配置文件

总结下来,一个简单的windows版vimrc如下(其中1-33行是自带的内容,34行之后是自定义内容),这个版本适合OI党使用,可以现场手敲vimrc。

MAC版的vimrc如下(支持了更多文件的运行快捷键)

最后,可以在这里找到我的最新的vimrc

原创文章地址:【vim简单教程及配置】转载时请注明出处mhy12345.xyz

真实感图像渲染系列:小结

这是真实感图像渲染系列的第十篇文章。

这里写一写个人在编写过程中发现的一些坑,分享出来以免之后再踩吧。

  • CMake好啊,比Makefile好,可以很容易整合第三方库,但是……编译超级慢,别人的工程3s编译完成我的需要半分钟……
  • eps设多少确实是个坑,我设的是1e-7,但是得保证牛顿迭代的精度严格高于eps,否则焦点可能存在大于eps的误差,eps的设置就没有意义了
  • MAC的错误报告挺有用的 == 比如下面这个直接秒调

原创文章地址:【真实感图像渲染系列:小结】转载时请注明出处mhy12345.xyz

真实感图像渲染系列:相机(Camera)与景深效果(Field of Depth)

这是真实感图像渲染系列的第九篇文章。

普通相机模型

不同的相机模型中,有一个人眼位置和一个屏幕,对于屏幕中每一个像素,连接人眼和该像素位置得到一条射出光线。其2D示意图如下:

首先,一直屏幕像素坐标,以及屏幕本身在场景中的位置,我们可以计算出该像素的位置,如图中红点所述。接着,连接人眼和像素的光线就可以用于计算该光线的颜色。这一部分挺容易理解的。

带景深的相机模型

在普通相机模型的屏幕和人眼位置之外,带景深的相机模型额外存在一个焦平面。如下图所示

通过普通的相机模型,我们可以求得普通相机的光线的方向。

普通相机的光线一定会和焦平面在某个位置碰撞,为了达到景深效果,一方面,我们需要保证同一个像素对应的光线一定会击打到焦平面上的同一个点,另一方面,在焦平面之外的其他位置,同一个像素对应的光线应该击打到不同的点。

解决方案如下:我们求得在普通相机模型中,光线和焦平面的焦点,将该焦点景深相机模型的焦点。接下来,我们对光线的起始位置做一个微小扰动,并且修改光线方向使得光线恒定过焦平面上的点。这样,无论初始光线如何扰动,焦平面上的点都可以最清晰的表现出来。而不在焦平面上的点,会产生随机的模糊效果。

 

 

原创文章地址:【真实感图像渲染系列:相机(Camera)与景深效果(Field of Depth)】转载时请注明出处mhy12345.xyz