Earthson_Lu

Earthson_Lu 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

Earthson_Lu 收藏了文章 · 2014-01-08

并行视角下的硬件习性

大多数人根据直觉就知道,在系统间传递消息要比在单个系统上执行简单计算更加耗时。不过,在共享同一块内存的系统的线程间传递消息是不是也更加耗时,这点可就不一定了。本章主要关注共享内存系统中的同步和通信的开销,只涉及了一些共享内存并行硬件设计的皮毛,想了解更多信息的读者,可以翻看Hennessy和Patterson的经典教材最新版[HP95]。

小问题:为什么并行软件程序员需要如此痛苦地学习硬件的低级属性?如果只学习更高级些的抽象是不是更简单,更好,更通用?

概述

如果只是粗略地扫过计算机系统规范手册,很容易让人觉得CPU的性能就像在一条清晰跑道上的赛跑,如下图所示,总是最快的人赢得比赛。

CPU的最佳性能

虽然有一些只限于CPU的基准测试能够让CPU达到上图中显示的理想情况,但是典型的程序不像跑道,更像是一条带有障碍的道路。托摩尔定律的福,最近几十年间CPU的内部架构发生了急剧的变化。在后面的章节中将描述这些变化。

CPU流水线

在上世纪80年代初,典型的微处理器在处理下一条指令之前,至少需要取指,解码和执行3个时钟周期来完成本条指令。与之形成鲜然对比是,上世纪90年代末期和本世纪初的CPU可以同时处理多条指令,通过一条很长的“流水线”来控制CPU内部的指令流,图2.2显示了这种差异。

新CPU和旧CPU

带有长流水线的CPU想要达到最佳性能,需要程序给出高度可预测的控制流。代码主要在紧凑循环中执行的程序,可以提供恰当的控制流,比如大型矩阵或者向量中做算术计算的程序。此时CPU可以正确预测在大多数情况下,代码循环结束后的分支走向。在这种程序中,流水线可以一直保持在满状态,CPU高速运行。

另一方面,如果程序中带有许多循环,且循环计数都比较小;或者面向对象的程序中带有许多虚对象,每个虚对象都可以引用不同的实对象,而这些实对象都有频繁被调用的成员函数的不同实现,此时CPU很难或者完全不可能预测某个分支的走向。这样CPU要么等待控制流进行到足以知道分支走向的方向时,要么干脆猜测——由于此时程序的控制流不可预测——CPU常常猜错。在这两种情况中,流水线都是空的,CPU需要等待流水线被新指令填充,这将大幅降低CPU的性能,就像图中的画一样。

CPU遭遇pipeline flush

不幸的是,流水线冲刷并不是唯一影响现代CPU运行性能的的障碍。下一节将讲述内存引用带来的危害。

内存引用

在上世纪80年代,微处理器从内存读取一个值的时间比执行一条指令的时间短。在2006年,同样是读取内存的时间,微处理器可以在这段时间执行上百条甚至上千条指令。这个差异来源于摩尔定律使得CPU性能的增长速度大大超过内存性能的增长速度,也有部分是由于内存大小的增长速度。比如,70年代的微型计算机通常带有4KB主存(是的,是KB,不是MB,更别提GB了),访问需要一个周期。到2008年,CPU设计者仍然可以构造单周期访问的4KB内存,即使是在几GHz时钟频率的系统上。事实上这些设计者经常构造这样的内存,但他们现在称呼这种内存为“0级cache”。

虽然现代微型计算机上的大型缓存极大地减少了内存访问延迟,但是只有高度可预测的数据访问模式才能让缓存发挥最大效用。不幸的是,一般像遍历链表这样的操作的内存访问模式非常难以预测——毕竟如果这些模式是可预测的,我们也就不会被指针所困扰了,是吧?

CPU遭遇内存引用

因此,正如图中显示的,内存引用常常是影响现代CPU性能的重要因素。

到现在为止,我们只考虑了CPU在单线程代码中执行时会遭遇的性能障碍。多线程会为CPU带来额外的性能障碍,我们将在下面的章节中接着讲述。

原子操作

其中一种障碍是原子操作。原子操作的概念在某种意义上与CPU流水线上的一次执行一条的汇编操作冲突了。拜硬件设计者的精密设计所赐,现代CPU使用了很多非常聪明的手段让这些操作看起来是原子的,即使这些指令实际上不是原子的。不过即使如此,也还是有一些指令是流水线必须延迟甚至需要冲刷,以便一条原子操作成功完成。

CPU遭遇原子操作

原子指令对性能的影响见上图。

不幸的是,原子操作通常只用于数据的单个元素。由于许多并行算法都需要在更新多个数据元素时,保证正确的执行顺序,大多数CPU都提供了内存屏障。内存屏障也是影响性能的因素之一,下一节将对它进行描述。

小问题:什么样的机器会允许对多个数据元素进行原子操作?

内存屏障

下面是一个简单的基于锁的临界区。

spin_lock(&mylock);

a = a + 1;

spin_unlock(&mylock);

如果CPU没有按照上述语句的顺序执行,变量”a”会在没有得到“mylock”保护的情况下加一,这肯定和我们取”a”的值的目的不一致。为了防止这种有害的乱序执行,锁操作原语必须包含或显式或隐式的内存屏障。由于内存屏障的作用是防止CPU为了提升性能而进行的乱序执行,所以内存屏障几乎一定会降低CPU性能,如下图所示。

CPU遭遇内存屏障

Cache Miss

对多线程程序来说,还有个额外的障碍影响CPU性能提升——“Cache Miss”。正如前文提到的,现代CPU使用大容量的高速缓存来降低由于较低的内存访问速度带来的性能惩罚。但是,CPU高速缓存事实上对多CPU间频繁访问的变量起反效果。因为当某个CPU想去更改变量的值时,极有可能该变量的值刚被其他CPU修改过。在这种情况下,变量存在于其他CPU而不是当前CPU的缓存中,这将导致代价高昂的Cache Miss。如下图所示。

CPU遭遇Cache Miss

I/O操作

缓存未命中可以视为CPU之间的I/O操作,这应该是代价最低廉的I/O操作之一。I/O操作涉及网络、大容量存储器,或者(更糟的)人类本身,I/O操作对性能的影响远远大于之前几个章节提到的各种障碍,如下图所示。

CPU等待I/O完成

共享内存式的并行计算和分布式系统式的并行计算的其中一个不同点是,共享内存式并行计算的程序一般不会处理比缓存未命中更糟的情况,而分布式并行计算的程序则很可能遭遇网络通信延迟。这两种情况的延迟都可看作是通信的代价——在串行程序中所没有的代价。因此,通信的开销占执行的实际工作的比率是一项关键设计参数。并行设计的一个主要目标是尽可能的减少这一比率,以达到性能和可扩展性上的目的。

当然,说I/O操作属于性能障碍是一方面,说I/O操作对性能的影响非常明显则是另一方面。下面的章节将讨论两者的区别。

开销

本节将概述前一节列出的性能障碍的实际开销。不过在此之前,需要读者对硬件体系结构有一个粗略认识,下一小节将对该主题进行阐述。

硬件体系结构

系统硬件体系结构

上图是一个粗略的八核计算机系统概要图。每个管芯有两个CPU核,每个核带有自己的高速缓存,管芯内还带有一个互联模块,使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信,并且将管芯与主存连接起来。

数据以“缓存线”为单位在系统中传输,“缓存线”对应于内存中一个2的幂大小的字节块,大小通常为32到256字节之间。当CPU从内存中读取一个变量到它的寄存器中时,必须首先将包含了该变量的缓存线读取到CPU高速缓存。同样地,CPU将寄存器中的一个值存储到内存时,不仅必须将包含了该值的缓存线读到CPU高速缓存,还必须确保没有其他CPU拥有该缓存线的拷贝。

比如,如果CPU0在对一个变量执行“比较并交换”(CAS)操作,而该变量所在的缓存线在CPU7的高速缓存中,就会发生以下经过简化的事件序列:

​1. CPU0检查本地高速缓存,没有找到缓存线。

​2. 请求被转发到CPU0和CPU1的互联模块,检查CPU1的本地高速缓存,没有找到缓存线。

​3. 请求被转发到系统互联模块,检查其他三个管芯,得知缓存线被CPU6和CPU7所在的管芯持有。

​4. 请求被转发到CPU6和CPU7的互联模块,检查这两个CPU的高速缓存,在CPU7的高速缓存中找到缓存线。

​5. CPU7将缓存线发送给所属的互联模块,并且刷新自己高速缓存中的缓存线。

​6. CPU6和CPU7的互联模块将缓存线发送给系统互联模块。

​7. 系统互联模块将缓存线发送给CPU0和CPU1的互联模块。

​8. CPU0和CPU1的互联模块将缓存线发送给CPU0的高速缓存。

​9. CPU0现在可以对高速缓存中的变量执行CAS操作了。

小问题:这是一个简化后的事件序列吗?还有可能更复杂吗?

小问题:为什么必须刷新CPU7高速缓存中的缓存线?

操作的开销

一些在并行程序中很重要的常见操作开销如下所示。该系统的时钟周期为0.6ns。虽然在现代微处理器上每时钟周期retire多条指令并不常见,但是在表格的第三列,操作被标准化到了整个时钟周期,称作“比率”。关于这个表格,第一个需要注意的是比率的值都很大。

4-CPU 1.8GHz AMD Opteron 844系统

操作开销(ns)比率
Clock period0.1.0
Best-case CAS37.963.2
Best-case lock65.6109.3
Single cache miss139.5232.5
CAS cache miss306.0510.0
Comms fabric3,0005,000
Global Comms130,000,000216,000,000

最好情况下的CAS操作消耗大概40纳秒,超过60个时钟周期。这里的“最好情况”是指对某一个变量执行CAS操作的CPU正好是最后一个操作该变量的CPU,所以对应的缓存线已经在CPU的高速缓存中了,类似地,最好情况下的锁操作(一个“round trip对”包括获取锁和随后的释放锁)消耗超过60纳秒,超过100个时钟周期。这里的“最好情况”意味着用于表示锁的数据结构已经在获取和释放锁的CPU所属的高速缓存中了。锁操作比CAS操作更加耗时,是因为锁操作的数据结构中需要两个原子操作。

缓存未命中消耗大概140纳秒,超过200个时钟周期。需要在存储新值时查询变量的旧值的CAS操作,消耗大概300纳秒,超过500个时钟周期。想想这个,在执行一次CAS操作的时间里,CPU可以执行500条普通指令。这表明了细粒度锁的局限性。

小问题:硬件设计者肯定被要求过改进这种情况!为什么他们满足于这些单指令操作的糟糕性能呢?

I/O操作开销更大。一条高性能(也是高价的)光纤通信,比如Infiniand或者其他私有的 interconnects,它的通讯延迟大概有3微秒,在这期间CPU可以执行5000条指令。基于某种标准的通信网络一般需要一些协议的处理,这更进一步增加了延迟。当然,物理距离也会增加延迟,理论上光速绕地球一周需要大概130毫秒,这相当于2亿个时钟周期。

小问题:这些数字大的让人发疯!我怎么才能记住它们?

硬件的免费午餐

最近几年并行计算受到大量关注的主要原因是摩尔定律的终结,摩尔定律带来的单线程程序性能提升(或者叫“免费午餐”[Sut08])也结束了。本节简短地介绍一些硬件设计者可能采用的办法,这些办法可以带来某种形式上的“免费午餐”。

不过,前文中概述了一些影响并发性的硬件障碍。其中对硬件设计者来说最严重的一个限制莫过于有限的光速。在一个1.8GHz的时钟周期内,光只能在真空中传播大约8厘米远。在5GHz的时钟周期内,这个距离更是降到3厘米。这个距离对于一个现代计算机系统的体积来说,还是太小了点。

更糟糕的是,电子在硅中的移动速度比真空中的光慢3到30倍,比如,内存引用需要在将请求发送给系统的其他部分前,等待查找本地缓存操作结束。此外,相对低速和高耗电的驱动器需要将电信号从一个硅制管芯传输到另一个管芯,比如CPU和主存间的通信。

不过,以下(包括硬件和软件的)技术也许可以改善这一情况:

​1. 3D集成,

​2. 新材料和新工艺,

​3. 用光来替换电子,

​4. 专用加速器,

​5. 已有的并行计算软件。

在下面的小节中将会分别介绍这些技术。

3D集成

不过,由于时钟逻辑级别造成的延迟是无法通过3D集成的方式降低的,并且必须解决诸如生产、测试、电源和散热等3D集成中的重大问题。散热问题需要用基于钻石的半导体来解决,钻石是热的良好导体,但却是电的绝缘体。据说生成大型单晶体钻石仍然很困难,更别说将钻石切割成晶圆了。另外,看起来上述这些技术不大可能让性能出现指数级增长,如同某些人习惯的那样。

新材料和新工艺

据说斯蒂芬·霍金曾经声称半导体制造商面临两个基本问题:(1)有限的光速,(2)物质的原子本质。半导体制造商很有可能已经逼近这两个限制,不过有一些研究报告和开发过程关注于如何规避这两个基本闲置。

其中一个规避物质的原子本质的办法是一种称为“high-K”绝缘体材料,这种材料允许较大的设备模拟较小型设备的电气属性。这种材料存在一些严重的生产困难,但是能让研究的前沿再向前推进一步。另一个比较奇异的规避方法,根据电子可以存在于多个能级之上的事实,在电子中存储多个二进制位。不过这种方法还有待观察,确定能否在生产的半导体设备中稳定工作。

还有一种称为“量子点”的规避方法,使得可以制造体积小得多的半导体设备,不过该方法还处于研究阶段。

虽然光速是一个很难跨越的限制,但是半导体设备更多的是受限于电子移动的速度,而非光速,在半导体材料中移动的电子速度仅是真空中光速的3%到30%。在半导体设备间用铜来连接是一种提升电子移动速度的方法,并且出现其他技术让电子移动速度接近光速的可能性是很大的。另外,还有一些实验用微小的光纤作为芯片内和芯片间的传输通道,因为在玻璃中的光速能达到真空中光速的60%还多。这种方法存在的一个问题是光电/电光转换的效率,会产生电能消耗和散热问题。

这也就是说,除开在物理学领域的基础性进展以外,任何让数据流传输速度出现指数级增长的想法都受限于真空中的光速。

专用加速器

用通用CPU来处理某个专门问题,通常会将大量的时间和能源消耗在一些与当前问题无关的事项上。比如,当对一对向量进行点积操作时,通用CPU一般会使用一个带循环计数的循环(一般是展开的)。对指令解码、增加循环计数、测试计数和跳转回循环的开始处,这些操作在某种意义上来说都是无用功:真正的目标是计算两个向量对应元素的乘积。因此,在硬件上设计一个专用于向量乘法的部件会让这项工作做的既快速又节能。

这就是在很多商用微处理器上出现向量指令的原因。这些指令可以同时操作多个数据,能让点积计算减少解码指令消耗和循环开销。

类似的,专用硬件可以更有效地进行加密/解密、压缩/解压缩、编码/解码和许多其他的任务。不过不幸的是,这种效率提升不是免费的。包含特殊硬件的计算机系统需要更多的晶体管,即使在不用时也会带来能源消耗。软件也必须进行修改以利用专用硬件的长处,同时这种专门硬件又必须足够通用,这样高昂的up-front设计费用才能摊到足够多的用户身上,让专用硬件的价钱变得可以承受。部分由于以上经济考虑,专用硬件到目前为止只在几个领域出现,包括图形处理(GPU),矢量处理器(MMX、SSE和VMX指令),以及相对规模较小的加密领域。

不过,随着摩尔定律带来的单线程性能提升的结束,我们可以安全的预测:未来各种各样的专用硬件会大大增加。

现有的并行软件

虽然多核CPU曾经让计算机行业惊讶了一把,但是事实上基于共享内存的并行计算机已经商用了超过半个世纪了。这段时间足以让一些重要的并行软件登上舞台,事实也确实如此。并行操作系统已经非常常见了,比如并行线程库,并行关系数据库管理系统和并行数值计算软件。这些现有的并行软件在解决我们可能遇见的并行难题上已经走了很长一段路。

也许最常见的例子是并行关系数据库管理系统。它和单线程程序不同,并行关系数据库管理系统一般用高级脚本语言书写,并发地访问位于中心的关系数据库。在现在的高度并行化系统中,只有数据库是真正需要直接处理并行化的。因此它运用了许多非常好的技术。

软件设计

操作的开销表格中的比率值至关重要,因为它们限制了并行计算程序的效率。为了弄清这点,我们假设一款并行计算程序使用了CAS操作来进行线程间通信。假设进行通信的线程不是与自身而主要是与其他线程通信,那么CAS操作一般会涉及到缓存未命中。进一步假设对应每个CAS通信操作的工作需要消耗300纳秒,这足够执行几个浮点transendental函数了。其中一半的执行时间消耗在CAS通信操作上!这也意味着有两个CPU的系统运行这样一个并行程序的速度,并不比单CPU系统运行一个串行执行程序的速度快。

在分布式系统中结果还会更糟糕,因为单次通信操作的延迟时间可能和几千条甚至上百万条浮点操作的时间一样长。这就说明了会产生大量工作量的通信操作应该尽可能减少。

小问题:既然分布式系统的通信操作代价如此昂贵,为什么人们还要使用它?

总结

并行算法必须将每个线程设计成尽可能独立运行的线程。越少使用线程间通信手段,比如原子操作、锁或者其它消息传递方法,应用程序的性能和可扩展性就会更好。简而言之,想要达到优秀的并行性能和可扩展性,就意味着在并行算法和实现中挣扎,小心的选择数据结构和算法,使用现有的并行软件和环境,或者将并行问题转换成已经有并行解决方案存在的问题。


原文 Hardware and its habits 
作者 Paul E. McKenney
译者 谢宝友,鲁阳,陈渝
修订 SegmentFault
许可 Creative Commons Attribution-Share Alike 3.0 United States license

查看原文

Earthson_Lu 赞了文章 · 2014-01-08

并行视角下的硬件习性

大多数人根据直觉就知道,在系统间传递消息要比在单个系统上执行简单计算更加耗时。不过,在共享同一块内存的系统的线程间传递消息是不是也更加耗时,这点可就不一定了。本章主要关注共享内存系统中的同步和通信的开销,只涉及了一些共享内存并行硬件设计的皮毛,想了解更多信息的读者,可以翻看Hennessy和Patterson的经典教材最新版[HP95]。

小问题:为什么并行软件程序员需要如此痛苦地学习硬件的低级属性?如果只学习更高级些的抽象是不是更简单,更好,更通用?

概述

如果只是粗略地扫过计算机系统规范手册,很容易让人觉得CPU的性能就像在一条清晰跑道上的赛跑,如下图所示,总是最快的人赢得比赛。

CPU的最佳性能

虽然有一些只限于CPU的基准测试能够让CPU达到上图中显示的理想情况,但是典型的程序不像跑道,更像是一条带有障碍的道路。托摩尔定律的福,最近几十年间CPU的内部架构发生了急剧的变化。在后面的章节中将描述这些变化。

CPU流水线

在上世纪80年代初,典型的微处理器在处理下一条指令之前,至少需要取指,解码和执行3个时钟周期来完成本条指令。与之形成鲜然对比是,上世纪90年代末期和本世纪初的CPU可以同时处理多条指令,通过一条很长的“流水线”来控制CPU内部的指令流,图2.2显示了这种差异。

新CPU和旧CPU

带有长流水线的CPU想要达到最佳性能,需要程序给出高度可预测的控制流。代码主要在紧凑循环中执行的程序,可以提供恰当的控制流,比如大型矩阵或者向量中做算术计算的程序。此时CPU可以正确预测在大多数情况下,代码循环结束后的分支走向。在这种程序中,流水线可以一直保持在满状态,CPU高速运行。

另一方面,如果程序中带有许多循环,且循环计数都比较小;或者面向对象的程序中带有许多虚对象,每个虚对象都可以引用不同的实对象,而这些实对象都有频繁被调用的成员函数的不同实现,此时CPU很难或者完全不可能预测某个分支的走向。这样CPU要么等待控制流进行到足以知道分支走向的方向时,要么干脆猜测——由于此时程序的控制流不可预测——CPU常常猜错。在这两种情况中,流水线都是空的,CPU需要等待流水线被新指令填充,这将大幅降低CPU的性能,就像图中的画一样。

CPU遭遇pipeline flush

不幸的是,流水线冲刷并不是唯一影响现代CPU运行性能的的障碍。下一节将讲述内存引用带来的危害。

内存引用

在上世纪80年代,微处理器从内存读取一个值的时间比执行一条指令的时间短。在2006年,同样是读取内存的时间,微处理器可以在这段时间执行上百条甚至上千条指令。这个差异来源于摩尔定律使得CPU性能的增长速度大大超过内存性能的增长速度,也有部分是由于内存大小的增长速度。比如,70年代的微型计算机通常带有4KB主存(是的,是KB,不是MB,更别提GB了),访问需要一个周期。到2008年,CPU设计者仍然可以构造单周期访问的4KB内存,即使是在几GHz时钟频率的系统上。事实上这些设计者经常构造这样的内存,但他们现在称呼这种内存为“0级cache”。

虽然现代微型计算机上的大型缓存极大地减少了内存访问延迟,但是只有高度可预测的数据访问模式才能让缓存发挥最大效用。不幸的是,一般像遍历链表这样的操作的内存访问模式非常难以预测——毕竟如果这些模式是可预测的,我们也就不会被指针所困扰了,是吧?

CPU遭遇内存引用

因此,正如图中显示的,内存引用常常是影响现代CPU性能的重要因素。

到现在为止,我们只考虑了CPU在单线程代码中执行时会遭遇的性能障碍。多线程会为CPU带来额外的性能障碍,我们将在下面的章节中接着讲述。

原子操作

其中一种障碍是原子操作。原子操作的概念在某种意义上与CPU流水线上的一次执行一条的汇编操作冲突了。拜硬件设计者的精密设计所赐,现代CPU使用了很多非常聪明的手段让这些操作看起来是原子的,即使这些指令实际上不是原子的。不过即使如此,也还是有一些指令是流水线必须延迟甚至需要冲刷,以便一条原子操作成功完成。

CPU遭遇原子操作

原子指令对性能的影响见上图。

不幸的是,原子操作通常只用于数据的单个元素。由于许多并行算法都需要在更新多个数据元素时,保证正确的执行顺序,大多数CPU都提供了内存屏障。内存屏障也是影响性能的因素之一,下一节将对它进行描述。

小问题:什么样的机器会允许对多个数据元素进行原子操作?

内存屏障

下面是一个简单的基于锁的临界区。

spin_lock(&mylock);

a = a + 1;

spin_unlock(&mylock);

如果CPU没有按照上述语句的顺序执行,变量”a”会在没有得到“mylock”保护的情况下加一,这肯定和我们取”a”的值的目的不一致。为了防止这种有害的乱序执行,锁操作原语必须包含或显式或隐式的内存屏障。由于内存屏障的作用是防止CPU为了提升性能而进行的乱序执行,所以内存屏障几乎一定会降低CPU性能,如下图所示。

CPU遭遇内存屏障

Cache Miss

对多线程程序来说,还有个额外的障碍影响CPU性能提升——“Cache Miss”。正如前文提到的,现代CPU使用大容量的高速缓存来降低由于较低的内存访问速度带来的性能惩罚。但是,CPU高速缓存事实上对多CPU间频繁访问的变量起反效果。因为当某个CPU想去更改变量的值时,极有可能该变量的值刚被其他CPU修改过。在这种情况下,变量存在于其他CPU而不是当前CPU的缓存中,这将导致代价高昂的Cache Miss。如下图所示。

CPU遭遇Cache Miss

I/O操作

缓存未命中可以视为CPU之间的I/O操作,这应该是代价最低廉的I/O操作之一。I/O操作涉及网络、大容量存储器,或者(更糟的)人类本身,I/O操作对性能的影响远远大于之前几个章节提到的各种障碍,如下图所示。

CPU等待I/O完成

共享内存式的并行计算和分布式系统式的并行计算的其中一个不同点是,共享内存式并行计算的程序一般不会处理比缓存未命中更糟的情况,而分布式并行计算的程序则很可能遭遇网络通信延迟。这两种情况的延迟都可看作是通信的代价——在串行程序中所没有的代价。因此,通信的开销占执行的实际工作的比率是一项关键设计参数。并行设计的一个主要目标是尽可能的减少这一比率,以达到性能和可扩展性上的目的。

当然,说I/O操作属于性能障碍是一方面,说I/O操作对性能的影响非常明显则是另一方面。下面的章节将讨论两者的区别。

开销

本节将概述前一节列出的性能障碍的实际开销。不过在此之前,需要读者对硬件体系结构有一个粗略认识,下一小节将对该主题进行阐述。

硬件体系结构

系统硬件体系结构

上图是一个粗略的八核计算机系统概要图。每个管芯有两个CPU核,每个核带有自己的高速缓存,管芯内还带有一个互联模块,使管芯内的两个核可以互相通信。在图中央的系统互联模块可以让四个管芯相互通信,并且将管芯与主存连接起来。

数据以“缓存线”为单位在系统中传输,“缓存线”对应于内存中一个2的幂大小的字节块,大小通常为32到256字节之间。当CPU从内存中读取一个变量到它的寄存器中时,必须首先将包含了该变量的缓存线读取到CPU高速缓存。同样地,CPU将寄存器中的一个值存储到内存时,不仅必须将包含了该值的缓存线读到CPU高速缓存,还必须确保没有其他CPU拥有该缓存线的拷贝。

比如,如果CPU0在对一个变量执行“比较并交换”(CAS)操作,而该变量所在的缓存线在CPU7的高速缓存中,就会发生以下经过简化的事件序列:

​1. CPU0检查本地高速缓存,没有找到缓存线。

​2. 请求被转发到CPU0和CPU1的互联模块,检查CPU1的本地高速缓存,没有找到缓存线。

​3. 请求被转发到系统互联模块,检查其他三个管芯,得知缓存线被CPU6和CPU7所在的管芯持有。

​4. 请求被转发到CPU6和CPU7的互联模块,检查这两个CPU的高速缓存,在CPU7的高速缓存中找到缓存线。

​5. CPU7将缓存线发送给所属的互联模块,并且刷新自己高速缓存中的缓存线。

​6. CPU6和CPU7的互联模块将缓存线发送给系统互联模块。

​7. 系统互联模块将缓存线发送给CPU0和CPU1的互联模块。

​8. CPU0和CPU1的互联模块将缓存线发送给CPU0的高速缓存。

​9. CPU0现在可以对高速缓存中的变量执行CAS操作了。

小问题:这是一个简化后的事件序列吗?还有可能更复杂吗?

小问题:为什么必须刷新CPU7高速缓存中的缓存线?

操作的开销

一些在并行程序中很重要的常见操作开销如下所示。该系统的时钟周期为0.6ns。虽然在现代微处理器上每时钟周期retire多条指令并不常见,但是在表格的第三列,操作被标准化到了整个时钟周期,称作“比率”。关于这个表格,第一个需要注意的是比率的值都很大。

4-CPU 1.8GHz AMD Opteron 844系统

操作开销(ns)比率
Clock period0.1.0
Best-case CAS37.963.2
Best-case lock65.6109.3
Single cache miss139.5232.5
CAS cache miss306.0510.0
Comms fabric3,0005,000
Global Comms130,000,000216,000,000

最好情况下的CAS操作消耗大概40纳秒,超过60个时钟周期。这里的“最好情况”是指对某一个变量执行CAS操作的CPU正好是最后一个操作该变量的CPU,所以对应的缓存线已经在CPU的高速缓存中了,类似地,最好情况下的锁操作(一个“round trip对”包括获取锁和随后的释放锁)消耗超过60纳秒,超过100个时钟周期。这里的“最好情况”意味着用于表示锁的数据结构已经在获取和释放锁的CPU所属的高速缓存中了。锁操作比CAS操作更加耗时,是因为锁操作的数据结构中需要两个原子操作。

缓存未命中消耗大概140纳秒,超过200个时钟周期。需要在存储新值时查询变量的旧值的CAS操作,消耗大概300纳秒,超过500个时钟周期。想想这个,在执行一次CAS操作的时间里,CPU可以执行500条普通指令。这表明了细粒度锁的局限性。

小问题:硬件设计者肯定被要求过改进这种情况!为什么他们满足于这些单指令操作的糟糕性能呢?

I/O操作开销更大。一条高性能(也是高价的)光纤通信,比如Infiniand或者其他私有的 interconnects,它的通讯延迟大概有3微秒,在这期间CPU可以执行5000条指令。基于某种标准的通信网络一般需要一些协议的处理,这更进一步增加了延迟。当然,物理距离也会增加延迟,理论上光速绕地球一周需要大概130毫秒,这相当于2亿个时钟周期。

小问题:这些数字大的让人发疯!我怎么才能记住它们?

硬件的免费午餐

最近几年并行计算受到大量关注的主要原因是摩尔定律的终结,摩尔定律带来的单线程程序性能提升(或者叫“免费午餐”[Sut08])也结束了。本节简短地介绍一些硬件设计者可能采用的办法,这些办法可以带来某种形式上的“免费午餐”。

不过,前文中概述了一些影响并发性的硬件障碍。其中对硬件设计者来说最严重的一个限制莫过于有限的光速。在一个1.8GHz的时钟周期内,光只能在真空中传播大约8厘米远。在5GHz的时钟周期内,这个距离更是降到3厘米。这个距离对于一个现代计算机系统的体积来说,还是太小了点。

更糟糕的是,电子在硅中的移动速度比真空中的光慢3到30倍,比如,内存引用需要在将请求发送给系统的其他部分前,等待查找本地缓存操作结束。此外,相对低速和高耗电的驱动器需要将电信号从一个硅制管芯传输到另一个管芯,比如CPU和主存间的通信。

不过,以下(包括硬件和软件的)技术也许可以改善这一情况:

​1. 3D集成,

​2. 新材料和新工艺,

​3. 用光来替换电子,

​4. 专用加速器,

​5. 已有的并行计算软件。

在下面的小节中将会分别介绍这些技术。

3D集成

不过,由于时钟逻辑级别造成的延迟是无法通过3D集成的方式降低的,并且必须解决诸如生产、测试、电源和散热等3D集成中的重大问题。散热问题需要用基于钻石的半导体来解决,钻石是热的良好导体,但却是电的绝缘体。据说生成大型单晶体钻石仍然很困难,更别说将钻石切割成晶圆了。另外,看起来上述这些技术不大可能让性能出现指数级增长,如同某些人习惯的那样。

新材料和新工艺

据说斯蒂芬·霍金曾经声称半导体制造商面临两个基本问题:(1)有限的光速,(2)物质的原子本质。半导体制造商很有可能已经逼近这两个限制,不过有一些研究报告和开发过程关注于如何规避这两个基本闲置。

其中一个规避物质的原子本质的办法是一种称为“high-K”绝缘体材料,这种材料允许较大的设备模拟较小型设备的电气属性。这种材料存在一些严重的生产困难,但是能让研究的前沿再向前推进一步。另一个比较奇异的规避方法,根据电子可以存在于多个能级之上的事实,在电子中存储多个二进制位。不过这种方法还有待观察,确定能否在生产的半导体设备中稳定工作。

还有一种称为“量子点”的规避方法,使得可以制造体积小得多的半导体设备,不过该方法还处于研究阶段。

虽然光速是一个很难跨越的限制,但是半导体设备更多的是受限于电子移动的速度,而非光速,在半导体材料中移动的电子速度仅是真空中光速的3%到30%。在半导体设备间用铜来连接是一种提升电子移动速度的方法,并且出现其他技术让电子移动速度接近光速的可能性是很大的。另外,还有一些实验用微小的光纤作为芯片内和芯片间的传输通道,因为在玻璃中的光速能达到真空中光速的60%还多。这种方法存在的一个问题是光电/电光转换的效率,会产生电能消耗和散热问题。

这也就是说,除开在物理学领域的基础性进展以外,任何让数据流传输速度出现指数级增长的想法都受限于真空中的光速。

专用加速器

用通用CPU来处理某个专门问题,通常会将大量的时间和能源消耗在一些与当前问题无关的事项上。比如,当对一对向量进行点积操作时,通用CPU一般会使用一个带循环计数的循环(一般是展开的)。对指令解码、增加循环计数、测试计数和跳转回循环的开始处,这些操作在某种意义上来说都是无用功:真正的目标是计算两个向量对应元素的乘积。因此,在硬件上设计一个专用于向量乘法的部件会让这项工作做的既快速又节能。

这就是在很多商用微处理器上出现向量指令的原因。这些指令可以同时操作多个数据,能让点积计算减少解码指令消耗和循环开销。

类似的,专用硬件可以更有效地进行加密/解密、压缩/解压缩、编码/解码和许多其他的任务。不过不幸的是,这种效率提升不是免费的。包含特殊硬件的计算机系统需要更多的晶体管,即使在不用时也会带来能源消耗。软件也必须进行修改以利用专用硬件的长处,同时这种专门硬件又必须足够通用,这样高昂的up-front设计费用才能摊到足够多的用户身上,让专用硬件的价钱变得可以承受。部分由于以上经济考虑,专用硬件到目前为止只在几个领域出现,包括图形处理(GPU),矢量处理器(MMX、SSE和VMX指令),以及相对规模较小的加密领域。

不过,随着摩尔定律带来的单线程性能提升的结束,我们可以安全的预测:未来各种各样的专用硬件会大大增加。

现有的并行软件

虽然多核CPU曾经让计算机行业惊讶了一把,但是事实上基于共享内存的并行计算机已经商用了超过半个世纪了。这段时间足以让一些重要的并行软件登上舞台,事实也确实如此。并行操作系统已经非常常见了,比如并行线程库,并行关系数据库管理系统和并行数值计算软件。这些现有的并行软件在解决我们可能遇见的并行难题上已经走了很长一段路。

也许最常见的例子是并行关系数据库管理系统。它和单线程程序不同,并行关系数据库管理系统一般用高级脚本语言书写,并发地访问位于中心的关系数据库。在现在的高度并行化系统中,只有数据库是真正需要直接处理并行化的。因此它运用了许多非常好的技术。

软件设计

操作的开销表格中的比率值至关重要,因为它们限制了并行计算程序的效率。为了弄清这点,我们假设一款并行计算程序使用了CAS操作来进行线程间通信。假设进行通信的线程不是与自身而主要是与其他线程通信,那么CAS操作一般会涉及到缓存未命中。进一步假设对应每个CAS通信操作的工作需要消耗300纳秒,这足够执行几个浮点transendental函数了。其中一半的执行时间消耗在CAS通信操作上!这也意味着有两个CPU的系统运行这样一个并行程序的速度,并不比单CPU系统运行一个串行执行程序的速度快。

在分布式系统中结果还会更糟糕,因为单次通信操作的延迟时间可能和几千条甚至上百万条浮点操作的时间一样长。这就说明了会产生大量工作量的通信操作应该尽可能减少。

小问题:既然分布式系统的通信操作代价如此昂贵,为什么人们还要使用它?

总结

并行算法必须将每个线程设计成尽可能独立运行的线程。越少使用线程间通信手段,比如原子操作、锁或者其它消息传递方法,应用程序的性能和可扩展性就会更好。简而言之,想要达到优秀的并行性能和可扩展性,就意味着在并行算法和实现中挣扎,小心的选择数据结构和算法,使用现有的并行软件和环境,或者将并行问题转换成已经有并行解决方案存在的问题。


原文 Hardware and its habits 
作者 Paul E. McKenney
译者 谢宝友,鲁阳,陈渝
修订 SegmentFault
许可 Creative Commons Attribution-Share Alike 3.0 United States license

查看原文

赞 3 收藏 3 评论 4

Earthson_Lu 赞了文章 · 2014-01-03

七个用于数据科学(Data Science)的命令行工具

数据科学是OSEMN(和 awesome 相同发音),它包括获取(Obtaining)、整理(Scrubbing)、探索(Exploring)、建模(Modeling)和翻译(iNterpreting)数据。作为一名数据科学家,我用命令行的时间非常长,尤其是要获取、整理和探索数据的时候。而且我也不是唯一一个这样做的人。最近,Greg Reda 介绍了可用于数据科学的经典命令行工具。在这之前,Seth Brown介绍了如何在Unix下进行探索性的数据分析

下面我将介绍在我的日常工作中发现很有用的七个命令行工具。包括:jqjson2csvcsvkit、scrape、 xml2json、 sample 和 Rio。(我自己做的scrapesampleRio可以在这里拿到)。任何建议意见、问题甚至git上的拉取请求都非常欢迎(其他人建议的工具可以在最后找到)。好的,下面我们首先介绍 jq

1. jq – sed for JSON

JSON现在越来越流行,尤其当API盛行了以后。我还记得处理JSON时,用 grepsed 写着丑陋的代码。谢谢 jq,终于可以不用写的这么丑了。

假设我们对2008总统大选的所有候选人感兴趣。纽约时报有一个关于竞选财务的API。让我们用 curl 取一些JSON:

curl -s 'http://api.nytimes.com/svc/elections/us/v3/finances/2008/president/totals.json?api-key=super-secret' > nyt.json

-s 表示静默模式。然后我们用 jq 最简单的格式 jq ‘.’,可以把得到的丑陋的代码

{"status":"OK","base_uri":"http://api.nytimes.com/svc/elections/us/v3/finances/2008/","cycle":2008,"copyright":"Copyright (c) 2013 The New York Times Company. All Rights Reserved.","results":[{"candidate_name":"Obama, Barack","name":"Barack Obama","party":"D",

转换成漂亮的格式:

< nyt.json jq '.' | head { "results": [ { "candidate_id": "P80003338", "date_coverage_from": "2007-01-01", "date_coverage_to": "2008-11-24", "candidate_name": "Obama, Barack", "name": "Barack Obama", "party": "D",

同时,jq还可以选取和过滤JSON数据:

< nyt.json jq -c '.results[] | {name, party, cash: .cash_on_hand} | select(.cash | tonumber > 1000000)'
{"cash":"29911984.0","party":"D","name":"Barack Obama"}
{"cash":"32812513.75","party":"R","name":"John McCain"}
{"cash":"4428347.5","party":"D","name":"John Edwards"}

更多使用方法参见手册,但是不要指望jq能做所有事。Unix的哲学是写能做一件事并且做得好的程序,但是jq功能强大!下面就来介绍json2csv。

2. json2csv – 把JSON转换成CSV

虽然JSON适合交换数据,但是它不适合很多命令行工具。但是不用担心,用json2csv我们可以轻松把JSON转换成CSV。现在假设我们把数据存在million.json 里,仅仅调用

< million.json json2csv -k name,party,cash

就可以把数据转换成:

Barack Obama,D,29911984.0
John McCain,R,32812513.75
John Edwards,D,4428347.5

有了CSV格式我们就可以用传统的如 cut -dawk -F 一类的工具了。grepsed 没有这样的功能。因为 CSV 是以表格形式存储的,所以csvkit的作者开发了 csvkit

3. csvkit – 转换和使用CSV的套装

csvkit 不只是一个程序,而是一套程序。因为大多数这类工具“期望” CSV 数据有一个表头,所以我们在这里加一个。

echo name,party,cash | cat - million.csv > million-header.csv

我们可以用 csvsort 给候选人按竞选资金排序并展示:

< million-header.csv csvsort -rc cash | csvlook

|---------------+-------+--------------|
|  name         | party | cash         |
|---------------+-------+--------------|
|  John McCain  | R     | 32812513.75  |
|  Barack Obama | D     | 29911984.0   |
|  John Edwards | D     | 4428347.5    |
|---------------+-------+--------------|

看起来好像MySQL哈?说到数据库,我们可以把CSV写到sqlite数据库(很多其他的数据库也支持)里,用下列命令:

csvsql --db sqlite:///myfirst.db --insert million-header.csv
sqlite3 myfirst.db
sqlite> .schema million-header
CREATE TABLE "million-header" (
    name VARCHAR(12) NOT NULL, 
    party VARCHAR(1) NOT NULL, 
    cash FLOAT NOT NULL
);

插入后数据都会正确因为CSV里也有格式。此外,这个套装里还有其他有趣工具,如 in2csvcsvgrepcsvjoin。通过 csvjson,数据甚至可以从csv转换会json。总之,你值得一看。

4. scrape – 用XPath和CSS选择器进行HTML信息提取的工具

JSON虽然很好,但是同时也有很多资源依然需要从HTML中获取。scrape就是一个Python脚本,包含了 lxmlcssselect 包,从而能选取特定HTML元素。维基百科上有个网页列出了所有国家的边界线语国土面积的比率,下面我们来把比率信息提取出来吧

curl -s 'http://en.wikipedia.org/wiki/List_of_countries_and_territories_by_border/area_ratio' | scrape -b -e 'table.wikitable > tr:not(:first-child)' | head
<!DOCTYPE html>
<html>
<body>
<tr>
<td>1</td>
<td>Vatican City</td>
<td>3.2</td>
<td>0.44</td>
<td>7.2727273</td>
</tr>

-b命令让 scrape 包含和标签,因为有时 xml2json 会需要它把 HTML 转换成 JSON。

5. xml2json – 把XML转换成JSON

如名字所说,这工具就是把XML(HTML也是一种XML)转换成JSON的输出格式。因此,xml2json是连接 scrape 和 jq 之间的很好的桥梁。

curl -s 'http://en.wikipedia.org/wiki/List_of_countries_and_territories_by_border/area_ratio' | scrape -be 'table.wikitable > tr:not(:first-child)' | xml2json | jq -c '.html.body.tr[] | {country: .td[1][], border: .td[2][], surface: .td[3][], ratio: .td[4][]}' | head
{"ratio":"7.2727273","surface":"0.44","border":"3.2","country":"Vatican City"}
{"ratio":"2.2000000","surface":"2","border":"4.4","country":"Monaco"}
{"ratio":"0.6393443","surface":"61","border":"39","country":"San Marino"}
{"ratio":"0.4750000","surface":"160","border":"76","country":"Liechtenstein"}
{"ratio":"0.3000000","surface":"34","border":"10.2","country":"Sint Maarten (Netherlands)"}
{"ratio":"0.2570513","surface":"468","border":"120.3","country":"Andorra"}
{"ratio":"0.2000000","surface":"6","border":"1.2","country":"Gibraltar (United Kingdom)"}
{"ratio":"0.1888889","surface":"54","border":"10.2","country":"Saint Martin (France)"}
{"ratio":"0.1388244","surface":"2586","border":"359","country":"Luxembourg"}
{"ratio":"0.0749196","surface":"6220","border":"466","country":"Palestinian territories"}

当然JSON数据之后可以输入给json2csv

6. sample – 用来debug

我写的第二个工具是 sample。(它是依据 bitly 的 [data_hacks](https://github.com/bitly/data_hacks)写的,bitly还有好多其他工具值得一看。)当你处理大量数据时,debug管道非常尴尬。这时,sample就会很有用。这个工具有三个用处:

逐行展示数据的一部分。
给在输出时加入一些延时,当你的数据进来的时候有些延时,或者你输出太快看不清楚时用这个很方便。
限制程序运行的时间。
下面的例子展现了这三个功能:

seq 10000 | sample -r 20% -d 1000 -s 5 | jq '{number: .}'

这表示,每一行有20%的机会被给到jq,没两行之间有1000毫秒的延迟,5秒过后,sample会停止。这些选项都是可选的。为了避免不必要的计算,请尽早sample。当你debug玩之后你就可以把它移除了。

7. Rio – 在处理中加入R

这篇文章没有R就不完整。将R/Rscript加入处理不是很好理解,因为他们并没有标准化输入输出,因此,我加入了一个命令行工具脚本,这样就好理解了。

Rio这样工作:首先,给标准输入的CSV被转移到一个临时文件中,然后让R把它读进df中。之后,在-e中的命令被执行。最后,最后一个命令的输出被重定向到标准输出中。让我用一行命令展现这三个用法,对每个部分展现5个数字的总结:

curl -s 'https://raw.github.com/pydata/pandas/master/pandas/tests/data/iris.csv' > iris.csv
< iris.csv Rio -e 'summary(df)'
  SepalLength      SepalWidth     PetalLength      PetalWidth   
 Min.   :4.300   Min.   :2.000   Min.   :1.000   Min.   :0.100 
 1st Qu.:5.100   1st Qu.:2.800   1st Qu.:1.600   1st Qu.:0.300 
 Median :5.800   Median :3.000   Median :4.350   Median :1.300 
 Mean   :5.843   Mean   :3.054   Mean   :3.759   Mean   :1.199 
 3rd Qu.:6.400   3rd Qu.:3.300   3rd Qu.:5.100   3rd Qu.:1.800 
 Max.   :7.900   Max.   :4.400   Max.   :6.900   Max.   :2.500 
     Name          
 Length:150       
 Class :character  
 Mode  :character

如果加入了-s 选项,sqldf包会被引入,这样CSV格式就会被输出,这可以让你之后用别的工具处理数据。

< iris.csv Rio -se 'sqldf("select * from df where df.SepalLength > 7.5")' | csvlook
|--------------+------------+-------------+------------+-----------------|
|  SepalLength | SepalWidth | PetalLength | PetalWidth | Name            |
|--------------+------------+-------------+------------+-----------------|
|  7.6         | 3          | 6.6         | 2.1        | Iris-virginica  |
|  7.7         | 3.8        | 6.7         | 2.2        | Iris-virginica  |
|  7.7         | 2.6        | 6.9         | 2.3        | Iris-virginica  |
|  7.7         | 2.8        | 6.7         | 2          | Iris-virginica  |
|  7.9         | 3.8        | 6.4         | 2          | Iris-virginica  |
|  7.7         | 3          | 6.1         | 2.3        | Iris-virginica  |
|--------------+------------+-------------+------------+-----------------|

如果你用-g选项,ggplot2会被引用,一个叫g得带有df的ggplot对象会被声明。如果最终输出是个ggplot对象,一个PNG将会被写到标准输出里。

< iris.csv Rio -ge 'g+geom_point(aes(x=SepalLength,y=SepalWidth,colour=Name))' > iris.png
iris

请输入图片描述

我制作了这个工具,为了可以在命令行中充分利用R的力量。当然它有很多缺陷,但至少我们不需要再学习gnuplot了。

别人建议的命令行工具

下面是其他朋友通过 twitter 和 hacker news 推荐的工具,谢谢大家。

结论

我介绍了七个我日常用来处理数据的命令行工具。虽然每个工具各有所长,我经常是将它们与传统工具(如grep, sed, 和awk)一起使用。将小工具结合起来使用组成一个大的流水线,这就是其用处所在。

不知你们对这个列表有什么想法,你们平时喜欢用什么工具呢。如果你们也做了什么好玩的工具,欢迎将其加入数据科学工具包data science toolbox

如果你不认为自己能制作工具,也不用担心,下次当你写一个异乎寻常的命令行流水线时,记得将它放到一个文件里,加一个#!,加一些参数,改成可执行文件,你就做成一个工具啦~

虽然命令行工具的强大在获取、处理和探索数据时不容小觑,在真正的探索、建模和理解翻译数据时,你还是最好在科学计算环境下进行。比如R或者IPython notebook+[pandas](http://pandas.pydata.org/)。

如果感兴趣,欢迎follow me on Twitter


原文:7 command-line tools for data science
转载自:伯乐在线 - 大飞

查看原文

赞 5 收藏 7 评论 1

Earthson_Lu 收藏了文章 · 2014-01-03

七个用于数据科学(Data Science)的命令行工具

数据科学是OSEMN(和 awesome 相同发音),它包括获取(Obtaining)、整理(Scrubbing)、探索(Exploring)、建模(Modeling)和翻译(iNterpreting)数据。作为一名数据科学家,我用命令行的时间非常长,尤其是要获取、整理和探索数据的时候。而且我也不是唯一一个这样做的人。最近,Greg Reda 介绍了可用于数据科学的经典命令行工具。在这之前,Seth Brown介绍了如何在Unix下进行探索性的数据分析

下面我将介绍在我的日常工作中发现很有用的七个命令行工具。包括:jqjson2csvcsvkit、scrape、 xml2json、 sample 和 Rio。(我自己做的scrapesampleRio可以在这里拿到)。任何建议意见、问题甚至git上的拉取请求都非常欢迎(其他人建议的工具可以在最后找到)。好的,下面我们首先介绍 jq

1. jq – sed for JSON

JSON现在越来越流行,尤其当API盛行了以后。我还记得处理JSON时,用 grepsed 写着丑陋的代码。谢谢 jq,终于可以不用写的这么丑了。

假设我们对2008总统大选的所有候选人感兴趣。纽约时报有一个关于竞选财务的API。让我们用 curl 取一些JSON:

curl -s 'http://api.nytimes.com/svc/elections/us/v3/finances/2008/president/totals.json?api-key=super-secret' > nyt.json

-s 表示静默模式。然后我们用 jq 最简单的格式 jq ‘.’,可以把得到的丑陋的代码

{"status":"OK","base_uri":"http://api.nytimes.com/svc/elections/us/v3/finances/2008/","cycle":2008,"copyright":"Copyright (c) 2013 The New York Times Company. All Rights Reserved.","results":[{"candidate_name":"Obama, Barack","name":"Barack Obama","party":"D",

转换成漂亮的格式:

< nyt.json jq '.' | head { "results": [ { "candidate_id": "P80003338", "date_coverage_from": "2007-01-01", "date_coverage_to": "2008-11-24", "candidate_name": "Obama, Barack", "name": "Barack Obama", "party": "D",

同时,jq还可以选取和过滤JSON数据:

< nyt.json jq -c '.results[] | {name, party, cash: .cash_on_hand} | select(.cash | tonumber > 1000000)'
{"cash":"29911984.0","party":"D","name":"Barack Obama"}
{"cash":"32812513.75","party":"R","name":"John McCain"}
{"cash":"4428347.5","party":"D","name":"John Edwards"}

更多使用方法参见手册,但是不要指望jq能做所有事。Unix的哲学是写能做一件事并且做得好的程序,但是jq功能强大!下面就来介绍json2csv。

2. json2csv – 把JSON转换成CSV

虽然JSON适合交换数据,但是它不适合很多命令行工具。但是不用担心,用json2csv我们可以轻松把JSON转换成CSV。现在假设我们把数据存在million.json 里,仅仅调用

< million.json json2csv -k name,party,cash

就可以把数据转换成:

Barack Obama,D,29911984.0
John McCain,R,32812513.75
John Edwards,D,4428347.5

有了CSV格式我们就可以用传统的如 cut -dawk -F 一类的工具了。grepsed 没有这样的功能。因为 CSV 是以表格形式存储的,所以csvkit的作者开发了 csvkit

3. csvkit – 转换和使用CSV的套装

csvkit 不只是一个程序,而是一套程序。因为大多数这类工具“期望” CSV 数据有一个表头,所以我们在这里加一个。

echo name,party,cash | cat - million.csv > million-header.csv

我们可以用 csvsort 给候选人按竞选资金排序并展示:

< million-header.csv csvsort -rc cash | csvlook

|---------------+-------+--------------|
|  name         | party | cash         |
|---------------+-------+--------------|
|  John McCain  | R     | 32812513.75  |
|  Barack Obama | D     | 29911984.0   |
|  John Edwards | D     | 4428347.5    |
|---------------+-------+--------------|

看起来好像MySQL哈?说到数据库,我们可以把CSV写到sqlite数据库(很多其他的数据库也支持)里,用下列命令:

csvsql --db sqlite:///myfirst.db --insert million-header.csv
sqlite3 myfirst.db
sqlite> .schema million-header
CREATE TABLE "million-header" (
    name VARCHAR(12) NOT NULL, 
    party VARCHAR(1) NOT NULL, 
    cash FLOAT NOT NULL
);

插入后数据都会正确因为CSV里也有格式。此外,这个套装里还有其他有趣工具,如 in2csvcsvgrepcsvjoin。通过 csvjson,数据甚至可以从csv转换会json。总之,你值得一看。

4. scrape – 用XPath和CSS选择器进行HTML信息提取的工具

JSON虽然很好,但是同时也有很多资源依然需要从HTML中获取。scrape就是一个Python脚本,包含了 lxmlcssselect 包,从而能选取特定HTML元素。维基百科上有个网页列出了所有国家的边界线语国土面积的比率,下面我们来把比率信息提取出来吧

curl -s 'http://en.wikipedia.org/wiki/List_of_countries_and_territories_by_border/area_ratio' | scrape -b -e 'table.wikitable > tr:not(:first-child)' | head
<!DOCTYPE html>
<html>
<body>
<tr>
<td>1</td>
<td>Vatican City</td>
<td>3.2</td>
<td>0.44</td>
<td>7.2727273</td>
</tr>

-b命令让 scrape 包含和标签,因为有时 xml2json 会需要它把 HTML 转换成 JSON。

5. xml2json – 把XML转换成JSON

如名字所说,这工具就是把XML(HTML也是一种XML)转换成JSON的输出格式。因此,xml2json是连接 scrape 和 jq 之间的很好的桥梁。

curl -s 'http://en.wikipedia.org/wiki/List_of_countries_and_territories_by_border/area_ratio' | scrape -be 'table.wikitable > tr:not(:first-child)' | xml2json | jq -c '.html.body.tr[] | {country: .td[1][], border: .td[2][], surface: .td[3][], ratio: .td[4][]}' | head
{"ratio":"7.2727273","surface":"0.44","border":"3.2","country":"Vatican City"}
{"ratio":"2.2000000","surface":"2","border":"4.4","country":"Monaco"}
{"ratio":"0.6393443","surface":"61","border":"39","country":"San Marino"}
{"ratio":"0.4750000","surface":"160","border":"76","country":"Liechtenstein"}
{"ratio":"0.3000000","surface":"34","border":"10.2","country":"Sint Maarten (Netherlands)"}
{"ratio":"0.2570513","surface":"468","border":"120.3","country":"Andorra"}
{"ratio":"0.2000000","surface":"6","border":"1.2","country":"Gibraltar (United Kingdom)"}
{"ratio":"0.1888889","surface":"54","border":"10.2","country":"Saint Martin (France)"}
{"ratio":"0.1388244","surface":"2586","border":"359","country":"Luxembourg"}
{"ratio":"0.0749196","surface":"6220","border":"466","country":"Palestinian territories"}

当然JSON数据之后可以输入给json2csv

6. sample – 用来debug

我写的第二个工具是 sample。(它是依据 bitly 的 [data_hacks](https://github.com/bitly/data_hacks)写的,bitly还有好多其他工具值得一看。)当你处理大量数据时,debug管道非常尴尬。这时,sample就会很有用。这个工具有三个用处:

逐行展示数据的一部分。
给在输出时加入一些延时,当你的数据进来的时候有些延时,或者你输出太快看不清楚时用这个很方便。
限制程序运行的时间。
下面的例子展现了这三个功能:

seq 10000 | sample -r 20% -d 1000 -s 5 | jq '{number: .}'

这表示,每一行有20%的机会被给到jq,没两行之间有1000毫秒的延迟,5秒过后,sample会停止。这些选项都是可选的。为了避免不必要的计算,请尽早sample。当你debug玩之后你就可以把它移除了。

7. Rio – 在处理中加入R

这篇文章没有R就不完整。将R/Rscript加入处理不是很好理解,因为他们并没有标准化输入输出,因此,我加入了一个命令行工具脚本,这样就好理解了。

Rio这样工作:首先,给标准输入的CSV被转移到一个临时文件中,然后让R把它读进df中。之后,在-e中的命令被执行。最后,最后一个命令的输出被重定向到标准输出中。让我用一行命令展现这三个用法,对每个部分展现5个数字的总结:

curl -s 'https://raw.github.com/pydata/pandas/master/pandas/tests/data/iris.csv' > iris.csv
< iris.csv Rio -e 'summary(df)'
  SepalLength      SepalWidth     PetalLength      PetalWidth   
 Min.   :4.300   Min.   :2.000   Min.   :1.000   Min.   :0.100 
 1st Qu.:5.100   1st Qu.:2.800   1st Qu.:1.600   1st Qu.:0.300 
 Median :5.800   Median :3.000   Median :4.350   Median :1.300 
 Mean   :5.843   Mean   :3.054   Mean   :3.759   Mean   :1.199 
 3rd Qu.:6.400   3rd Qu.:3.300   3rd Qu.:5.100   3rd Qu.:1.800 
 Max.   :7.900   Max.   :4.400   Max.   :6.900   Max.   :2.500 
     Name          
 Length:150       
 Class :character  
 Mode  :character

如果加入了-s 选项,sqldf包会被引入,这样CSV格式就会被输出,这可以让你之后用别的工具处理数据。

< iris.csv Rio -se 'sqldf("select * from df where df.SepalLength > 7.5")' | csvlook
|--------------+------------+-------------+------------+-----------------|
|  SepalLength | SepalWidth | PetalLength | PetalWidth | Name            |
|--------------+------------+-------------+------------+-----------------|
|  7.6         | 3          | 6.6         | 2.1        | Iris-virginica  |
|  7.7         | 3.8        | 6.7         | 2.2        | Iris-virginica  |
|  7.7         | 2.6        | 6.9         | 2.3        | Iris-virginica  |
|  7.7         | 2.8        | 6.7         | 2          | Iris-virginica  |
|  7.9         | 3.8        | 6.4         | 2          | Iris-virginica  |
|  7.7         | 3          | 6.1         | 2.3        | Iris-virginica  |
|--------------+------------+-------------+------------+-----------------|

如果你用-g选项,ggplot2会被引用,一个叫g得带有df的ggplot对象会被声明。如果最终输出是个ggplot对象,一个PNG将会被写到标准输出里。

< iris.csv Rio -ge 'g+geom_point(aes(x=SepalLength,y=SepalWidth,colour=Name))' > iris.png
iris

请输入图片描述

我制作了这个工具,为了可以在命令行中充分利用R的力量。当然它有很多缺陷,但至少我们不需要再学习gnuplot了。

别人建议的命令行工具

下面是其他朋友通过 twitter 和 hacker news 推荐的工具,谢谢大家。

结论

我介绍了七个我日常用来处理数据的命令行工具。虽然每个工具各有所长,我经常是将它们与传统工具(如grep, sed, 和awk)一起使用。将小工具结合起来使用组成一个大的流水线,这就是其用处所在。

不知你们对这个列表有什么想法,你们平时喜欢用什么工具呢。如果你们也做了什么好玩的工具,欢迎将其加入数据科学工具包data science toolbox

如果你不认为自己能制作工具,也不用担心,下次当你写一个异乎寻常的命令行流水线时,记得将它放到一个文件里,加一个#!,加一些参数,改成可执行文件,你就做成一个工具啦~

虽然命令行工具的强大在获取、处理和探索数据时不容小觑,在真正的探索、建模和理解翻译数据时,你还是最好在科学计算环境下进行。比如R或者IPython notebook+[pandas](http://pandas.pydata.org/)。

如果感兴趣,欢迎follow me on Twitter


原文:7 command-line tools for data science
转载自:伯乐在线 - 大飞

查看原文

Earthson_Lu 回答了问题 · 2013-12-10

长度为 2^k + k - 1 的 binary string,使其任意一个长度为 k 的 substring 都是唯一的

2^k + k -1长度的串,共有2^k个substring。长度为k的string也就是2^k个,所以每个string都要出现有且仅有一次。

假设串的k-1前缀是s,串就是sx。我们有如下的顺序满足。sx->ys!x->!ys,其中!x表示x取反,!y同理。->表示中间可能存在其它字符(不能有包含s前缀或者后缀的子串)。

待续。。。

关注 0 回答 4

Earthson_Lu 评论了回答 · 2013-11-23

Python编程:筛法求两个数之间的素数

Earthson_Lu 回答了问题 · 2013-11-23

怎么设置VPN允许访问服务器的内网?

让VPN servr把需要的路由表记录push过来(也就是你内网所在的网段),或者你自己设置这个vpn的路由表。当然,这种情况如果你使用的是NAT的话,会出现些问题:就是你能访问那边的机器,但是那边的机器不能直接访问你。

个人建议你做个网桥。你可以在A和自己机器上开一个tunnel(可能需要tap设备,不想自己开的话,可以用openvpn的桥接模式)。然后把A上的那个虚拟接口,桥接到物理接口上。这样你就完全在那边的局域网上了。

关注 1 回答 4

Earthson_Lu 回答了问题 · 2013-11-23

解决一个函数在setTimeout里调用自身会造成递归吗?

这个分逻辑上和实现上。

  • 逻辑上来说,它和递归是等价的。
  • 但是实现上,它是异步执行的,不会导致栈在使用上的无限增加,因为之前的函数执行完就销毁了。

lz可以这么认为,这种异步形式的递归,不会导致栈空间的溢出。但是作为副作用,这种递归不能依靠异步调用的返回值执行操作(当然,后面可以有操作,但是无法利用到返回值)。和尾递归很像呢,至少在逻辑上两者也确实非常接近。

关注 2 回答 8

Earthson_Lu 回答了问题 · 2013-11-23

解决如何高效的判断一段文本中是否包含一个字典中的某个词?

如果字典非常大,遍历字典匹配是不行的,hashset花费的空间也非常大。

  1. 字典保存上,lz可以选择用trie树。这是建立在分词的基础上的,分完词之后,看词是否在trie树中即可(和hashset类似的方法)。

  2. 直接用AC自动机之类的算法做多串匹配。这样的缺陷是某些不是词的相邻字会被匹配上呢。

trie一般只是对前缀作了压缩。如果lz要求高的话,可以尝试最小化该自动机(trie是一个无环自动机)。

关注 0 回答 3

Earthson_Lu 回答了问题 · 2013-11-23

最近点对距离计算问题

个人建议lz自己调试。治愈卡在了哪里,lz可以在可能卡主的地方(附近)添加printf(打印上下文,或者只是标记都行)。这样lz就可以确定程序到底跑到哪里的时候出问题了。

关注 0 回答 3

认证与成就

  • 获得 4 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 2013-11-21
个人主页被 180 人浏览