Chaofan's

Bonvenon al la malpura mondo.

标签: Power

  • 快速了解SIMD

    SIMD即Single Instruction Multiple Data缩写,单指令多数据,表示CPU设计中一种提高程序并行度的技术。和它对应的SISD、MISD和MIMD三个概念已很少有人提及,倒是GPU又引入了个新概念叫SIMT (Single Instruction Multiple Threads)。

    换种理解方式或许更实在些:SIMD和SIMT表示逻辑上有多个执行的实体,但只有一个执行的状态。至于其他三种:

    • 一个执行实体,一个执行状态,属于单线程
    • 一个执行实体,多个执行状态,属于协程
    • 多个执行实体,多个执行状态,属于多线程

    更实用地说,编程用途上的SIMD就是一组指令集扩展,能用一条指令同时完成若干个数据的相同操作。由于大量计算程序最耗费时间的代码都是核心的若干循环,如果能有SIMD指令的帮助,虽然复杂度还是没有改变,但相当于耗时除以一个不小的系数,不算免费午餐也是廉价午餐了。

    快速上手SIMD指令

    这里用C语言举例,看下面的代码。

    #include <stdio.h>
    
    typedef unsigned vecu32 __attribute__((vector_size(16)));
    
    extern unsigned data0[];
    extern unsigned data1[];
    extern unsigned datalen;
    
    int main(void) {
      for (int i = 0; i < 100000; ++i) {
        int j = 0;
        for (; j + 4 <= datalen; j += 4) {
          vecu32 a = *(vecu32*)(&data0[j]);
          vecu32 b = *(vecu32*)(&data1[j]);
          *(vecu32*)(&data0[j]) = a + b;
        }
        for (; j < datalen; ++j)
          data0[j] += data1[j];
      }
    }

    为阻止编译器做常量优化,这里把两个数组的定义放置在另一个文件里,长度都为65536个unsigned。在Apple M1上,使用Apple Clang 16搭配-O选项,运行时间是0.87秒。而如果不使用vecu32,即注释掉中间用到vecu32的for循环,运行时间会来到2.40秒。这里一个vecu32是16字节,即能容纳4个unsigned。虽然没有完全达到4倍性能差距,但2.8倍也是非常明显的性能提升,奥秘就在这里声明的vecu32类型。

    如果你稍微熟悉GCC或Clang,就能发现这里的__attribute__是GCC风格属性扩展,而vector_size属性就是为向量类型准备的。在编译器语境,SIMD容器就被称作向量 (vector),实际上确实比C++的std::vector更接近数学上向量的原始定义。这里一个vecu32能容纳4个unsigned变量,那我能否定义一个32字节的vecu32来进一步加速呢?

    先看当前版本的汇编。在ARM上用clang -S可以发现输出中有一条add.4s v0, v0, v1指令,查询文档可得知这条指令的意思就是向量整数加。再把源码中的16改成32,for循环头上的4改成8编译一遍,会发现执行时间几乎没有变化,而汇编里有了两条 add.4s而没有想象中的add.8s存在。失落之余先别着急,在输出汇编的编译命令中加入-arch x86_64 -mavx,能惊喜地发现X86平台是有32字节SIMD指令的,叫vpaddd。甚至,甚至可以更进一步,把上面代码的向量尺寸改为64字节,循环步长改为8,然后加上-mavx512f选项,会发现X86版本还能有对应的单条指令 (尽管名字还叫vpaddd,但寄存器类型变了,实质上是和前面的vpaddd算不同的指令)。

    这告诉我们一个道理,SIMD指令的支持范围和CPU架构有关,和编译器选项也有关。

    SIMD和CPU架构

    不同CPU架构支持的SIMD长度和类型各有不同,但主流指令集都有面向SIMD的扩展。

    x86

    最早的x86 SIMD扩展指令集叫MMX,来自1996年的Intel,以加速多媒体程序。但它仅支持64位长度,并且只能加速8位到32位的整数操作。因为早期x86 CPU的古怪设计,这个MMX指令不光短,还会占用浮点数的寄存器,用今天的目光看实在鸡肋。AMD也看不下去,推出了名叫3DNow!的扩展,支持浮点SIMD。为了应对,Intel很快推出了新的SIMD扩展,也就是今天有名的SSE (Streaming SIMD Extensions)。

    SSE支持128位长度的向量,且可容纳如4xfloat、2xdouble、4xint、8xshort或16xchar等不同类型。更重要的是,因为过去X86对浮点的支持过于奇葩 (x87指令集),SSE对标量(即单个)浮点数的操作也做了延伸,float和double的操作终于可以对应到和整数相似的指令了。SSE经历了多次扩展,涵盖了整数和浮点数从算术到重排和加密等各种操作。对今天的x86 CPU来说,SSE可以视作默认支持。

    十年后,Intel又发布了新的SIMD扩展,称作AVX (Advanced Vector eXtensions),总体和SSE相似,不过长度又扩展了一倍,支持256位向量。AVX还有更变态的延伸版本叫做AVX-512,顾名思义就是512位向量,8个double或者64个char同时操作。

    ARM

    ARMv7引入了高级SIMD扩展,通常也被称作NEON。和x86的MMX/SSE类似,NEON支持64位和128位两种向量。虽然ARM处理器家族比x86更复杂多样,但今天也基本可以假定,主流ARM芯片都支持NEON指令集。

    一部分面向服务器的ARM处理器,为了支持更长的向量,走了和x86不同的道路,推出了称作SVE (Scalable Vector Extension) 的动态向量扩展。和AVX固定256位、AVX512固定512位不同,SVE没有固定向量长度,而是在向量操作之外,又引入了一组谓词指令和寄存器,这就可以在汇编层面体现上层的循环逻辑,从而在运行时确定向量长度(也就代表着循环次数)。这样做的好处是:一个为SVE编译的二进制程序,在不同向量长度的CPU上都可不经改动执行,自动获得硬件向量变长带来的性能提升。

    SVE支持128到2048位的向量,ARMv9引入的SVE2又加入了若干新指令。本文不计划深入讨论SVE的使用。普通桌面级的ARM CPU (如Apple M1),并不支持SVE。

    RISC-V

    RISC-V把除最基本整数指令外的所有指令都归类为扩展,并以单独的字母标记,如扩展F和D分别表示单精度和双精度浮点数。RISC-V曾经有个叫做P (Packed SIMD) 的扩展,但今天更主流的是扩展V。RISC-V的创造者之一David Patterson (《计算机体系结构:量化研究方法》的作者之一),曾经写过一篇文章批评传统的SIMD指令设计不够灵活,增加了复杂度。

    也因此,RISC-V的扩展V (经常称作RVV) 指令设计更类似ARM SVE。而细节上更加灵活。比如说,向量长度存储在一个特殊寄存器中,计算指令也并不包含元素长度,具体元素多长会由特别指令设置。一条vfadd.vv可能是f32也可能是f64。

    在RISC-V语境中,SIMD向量两个词有明显区分:SIMD指x86风格的定长定类指令,向量指可动态扩展的多数据指令。但在本文其他部分,不作严格区分。

    POWER

    在Mac电脑还在使用PowerPC CPU的年代,苹果、IBM和摩托罗拉组建过所谓的AIM联盟。90年代末还没有今天的GPU概念,多媒体相关的加速都由CPU完成。为了和x86 SSE竞争,AIM在PowerPC指令集上推出了Vector Media eXtension (VMX) 扩展。该扩展引入了一种128位向量类型,支持整数和部分单精度浮点指令。

    PowerPC Mac的绝唱,PowerMac G5,支持该指令集。而后续IBM服务器上的POWER指令集依然包括这个扩展。VMX更出名的名称叫AltiVec,但2004年摩托罗拉半导体部门分拆为飞思卡尔公司,AltiVec商标由飞思卡尔持有。为避免商标纠纷,IBM用到的场合继续称之为VMX。在GCC和Clang等编译器眼中,这个指令集依然叫AltiVec。

    从POWER指令集2.06版开始(即POWER 7),POWER在VMX基础上引入了新的VSX (Vector Scalar eXtension) 指令集。在传统的POWER浮点指令外,VSX加入了一组新的和IEEE-754完全兼容的标量和向量浮点指令,类似SSE。浮点和向量寄存器也统一起来,VSX共64个128位寄存器,传统的32个浮点寄存器成为了前32个VSX寄存器前64位的别名,32个VMX寄存器则对应到后32个VSX寄存器。

    WebAssembly

    虽然WebAssembly不是真实的CPU指令集,但因为设计上考虑性能,加入SIMD指令也有助于模拟和JIT执行。Wasm的SIMD类型相对简单,固定128位,配合不同类型的计算指令,和SSE、NEON、VMX/VSX都能对上。

    编译器与SIMD

    虽然SIMD能给计算密集的程序带来提升,但我们并不是每次都要手写这堆奇怪的语法才能用上SIMD。在开优化的情景下,编译器会努力地将代码中的标量操作组合成向量指令,这部分功能在编译器中称作Vectorizer。LLVM中有循环Vectorizer和SLP Vectorizer两类,前者针对循环而后者针对非循环。其实,开头那个程序如果用O3编译,即使不手工使用向量扩展,Clang也可以生成出向量指令。

    像开头例子中这样简单的循环,循环体内只出现了一次加法,为了「凑」出四个加法构成SIMD,编译器需要像我们手写的代码一样把循环体扩充为原来的4倍,然后让循环次数除以4,并且还要处理剩下几个余数的情况,所以汇编容易变得非常大。这种优化叫做循环展开 (Loop Unrolling)。有关其他自动向量化中可能涉及到的优化,可以查阅LLVM向量化的官方文档

    如果还是有要手写向量化代码的情况,除开头提到的__attribute__((vector_size()))外,每个平台都提供了自己的C语言扩展:

  • 理解Big-endian和Little-endian

    Big-endianLittle-endian,你也许听说过这两个概念,可能也大概知道是什么意思,但未必清楚更深入的细节。这不奇怪,因为不直接和内存打交道的程序员不会对Endian有多少实践层面的理解,而即使写过相关的程序,因为抽象泄露的魔咒,也说不清底层原理。本文试图解释big-endian和little-endian的由来,在执行层面的原理,以及主流高级语言中如何处理Endian相关问题。

    在继续之前,先解释前文提及的概念「抽象泄露」。计算机科学本身可以理解为有关抽象的学问,C语言尽管今天看来相当底层,但也是建立在CPU指令上的抽象,人们用C写的程序,实际上是被编译器转写到机器指令执行。这也意味着,机器指令层面的一些概念,并不能在C语言的模型里体现,即C语言程序的某些问题无法用C语言本身的模型解释,必须依赖更底层的原理。此种情况下,C语言的抽象显得不完备了,这就是抽象泄露。

    典型的抽象泄露例子就是a=a+1语句中,如果变量a不是一个原子(atomic)变量,那么多线程环境中这个语句可能会造成数据不一致。这个问题很难用C语言本身的逻辑理解,我们只知道机器会给a的值加上1(C语言甚至不考虑有符号整数的溢出情况!),但具体CPU是如何计算的,我们不知道。只有当我们知道这个表达式在汇编层面是通过读取内存、执行加法,再写回内存之后能理解数据竞争的起因。这也是我认为编程初学者可以从汇编入门的原因——尽管汇编也有抽象泄露(如预测执行),但总归是比C的模型完备多了,对人也不难理解,C系语言的执行模型实在有点两头不占(另一头是函数式模型)的意思。

    回到正题。来解释big-endian和little-endian的区别。

    什么是Big-endian和Little-endian

    考虑如下一段C程序。

    #include <stdio.h>
    #include <stdint.h>
    uint8_t u8s[4] = { 0x12, 0x34, 0x56, 0x78 };
    uint32_t conv(void) { return *((uint32_t*)u8s); }
    int main(void) { printf("%x\n", conv()); }

    程序把一个4字节数组当作4字节整数读取,输出的内容会是多少呢?按照通常思路,uint32_t占内存中4字节的空间,4个uint8_t也是占4字节空间,那么这个指针强转的结果自然也是16进制的12345678。但实际上,在你的电脑上通常结果是78563412。是的,不是12345678,不是87654321,也不是1e6a2c48。而且这不是什么随机行为,而是基于某种逻辑的固定倒转。

    简单来说,对该程序输出78563412的CPU,就是Little-endian的;而输出12345678,则是Big-endian的。

    这两块内存不都是4字节吗,为什么会有这个区别?一个不精确但通俗的解释是:CPU对聚合类型(数组、结构体)和基本类型的变量有不同的处理方式。

    u8s[0]u8s[1]u8s[2]u8s[3]
    0x120x340x560x78

    以上是u8s这个数组的内存布局,从低地址到高地址排列。对于Big-endian的CPU,从内存读取一个int类型也按照这个顺序。但对Little-endian来说,就要反过来了。

    int[3]int[2]int[1]int[0]
    0x120x340x560x78

    顺序是倒过来的。把以上程序的4字节调整为8字节或2字节,也会得到类似的效果。但注意,这只针对各种内置类型有效,struct {int l; int r;}int[2]有一样的顺序。

    Endian名称的由来

    中文技术资料基本把Endian统一译作「字节序」。在英文语境里,Endian倒是个有典故的词,它来自《格列佛游记》第一卷第四章:

    我下面就要告诉你的是,这两大强国过去三十六个月以来一直在苦战。战争开始是由于以下的原因:我们大家都认为,吃鸡蛋前,原始的方法是打破鸡蛋较大的一端。可是当今皇帝的祖父小时候吃鸡蛋,一次按古法打鸡蛋时碰巧将一个手指弄破了,因此他的父亲,当时的皇帝,就下了一道敕令,命全体臣民吃鸡蛋时打破鸡蛋较小的一端,违者重罚。人民对此法极为反感。历史告诉我们,由此曾发生过六次叛乱,其中一个皇帝送了命,另一个丢了王位。这些内乱常常是由不来夫斯库国的君王们煽动起来的。骚乱平息后,流亡的人总是逃到那个帝国去寻求避难。据估计,先后几次有一万一千人情愿受死也不肯去打破鸡蛋较小的一端。

    所以你吃鸡蛋时先打哪边?

    代码中的字节序

    C/C++

    由于C和C++支持对变量取地址和任意指针类型的互转,我们很容易在C或C++中遇到字节序问题。结合上面使用C语言的例子,要在C语言里检测当前CPU是little-endian还是big-endian也可以用类似的做法:

    bool is_little_endian(void) {
      uint32_t test = 0x12345678U;
      return ((uint8_t*)&test)[0] == 0x78;
    }

    在Little-endian平台上,编译器会聪明地把这个函数优化成return 1。但这对我们来说并不够,因为我们可能需要在不同字节序的机器上编译不同的代码,运行时判断显然不够。好在,主流编译器都有宏用来判断:

    #ifdef __GNUC__
    #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    #define LITTLE_ENDIAN 1
    #else
    #define LITTLE_ENDIAN 0
    #elif _MSC_VER || __INTEL_COMPILER
    #define LITTLE_ENDIAN 1
    #end

    Clang会伪装自己是GCC,二者都支持通过__BYTE_ORDER__宏判断字节序。实际上,除了__ORDER_LITTLE_ENDIAN____ORDER_BIG_ENDIAN__外,实际上GCC中还有一种可能取值是__ORDER_PDP_ENDIAN__。PDP是Unix诞生时的CPU架构,其对16位整数采用Little-endian,而对32位整数使用一种奇怪的字节序,即把0x12345678表示为0x34, 0x12, 0x78, 0x56。技术上,现在已不需要考虑这种字节序。

    对于Intel编译器(ICC)和Visual Studio (MSVC),它们只存在于little-endian平台上,所以发现编译器是它们就可以放心地确认字节序。早期版本的Windows NT支持过PowerPC和MIPS这类以big-endian为主的架构,但即使是这些版本的Windows,也是运行little-endian模式的。

    如果要在所有平台上以big-endian字节序读取整数,请使用位运算:

    uint32_t read32be(uint8_t input[]) {
      return ((uint32_t)input[0] << 24) |
             ((uint32_t)input[1] << 16) |
             ((uint32_t)input[2] << 8) |
             (uint32_t)input[3];
    }

    以Little-endian方式读取,请将数组下标倒过来。

    Rust

    Rust中,可使用target_endian指令在编译期判断字节序:

    #[cfg(target_endian = "little")]
    // Code for little endian
    
    #[cfg(target_endian = "big")]
    // Code for big endian

    要以某种字节序读取数据,可使用byteorder crate。

    Java

    尽管主流CPU都是little-endian,但Java大概因为靠近网络字节序(见下文)的原因,统一使用big-endian。通过java.nio.ByteOrder类的nativeOrder方法,Java程序可以得知当前系统硬件上使用哪种字节序:BIG_ENDIAN或者LITTLE_ENDIAN

    DataInputStream采用Big-endian,如果要以Little-endian方式读取数据,可采用同前面C语言相似的位拼接做法。

    JavaScript

    JavaScript这样的脚本语言通常不太会考虑字节序问题,因为我们无法对一个对象取地址,或者查看它的内存布局。但现代JavaScript依然提供了和字节流打交道的API,这里涉及到三个概念:TypedArrayArrayBufferDataView

    简单来说,TypedArray表示某种固定类型作为元素的数组(可以是8种整数和2种浮点其中之一),ArrayBuffer表示无类型的一串字节,DataView是在前者之上读写的适配器:

    let array = new Uint32Array(1)
    array[0] = 0x12345678
    let view = new DataView(array.buffer)
    view.getUint8(0) // => 120 (0x78)
    view.getUint8(3) // => 18  (0x12)
    view.setUint32(0, 0x12345678, true)  // set data as little-endian
    view.setUint32(0, 0x12345678, false) // set data as big-endian
    view.getUint8(0) // => 18  (0x12)

    在JavaScript中,对TypedArray元素的赋值,字节序由CPU的字节序决定,所以在little-endian机器上自然得到little-endian布局的ArrayBuffer。但DataView的set方法有第三个参数表示是否使用little-endian顺序写入,要注意的是,这个参数的默认值是false,也就是big-endian,这意味着在大多数平台上setUint32及其他类似函数的行为,同一般赋值是相反的。

    Ruby

    Ruby也同理,大部分情况下用不着和二进制表示直接打交道。但Ruby中数组类型有将对象转换为二进制字节的pack方法,字符串类型有把字节串解析回对象的unpack方法。这两个方法利用字符串参数指定要读取的类型,除了类型和长度外,不同记号还代表着不同字节序:

    [100].pack 'L' # => 32-bit int in native endian
    [100].pack 'V' # => 32-bit int in little-endian
    [100].pack 'N' # => 32-bit int in big-endian
    
    # double (1.1) in native endian
    "\x9A\x99\x99\x99\x99\x99\xF1?".unpack 'D'
    # double (1.1) in little endian
    "\x9A\x99\x99\x99\x99\x99\xF1?".unpack 'E'
    # double (1.1) in big endian
    "\x9A\x99\x99\x99\x99\x99\xF1?".reverse.unpack 'G'

    自然可以用同样的方法测试当前系统字节序:

    def is_little_endian?
      [1].pack('L') == [1].pack('V')
    end

    不同硬件架构的字节序

    x86

    主流的32位和64位x86都是little-endian字节序。64位x86指令集有时又被称作amd64,因为它最早是AMD发明的。曾经的Intel提出过支持两种字节序切换的IA-64架构作为x86的64位继承者,后来因为不向前兼容而陨落在历史之中。

    x86一直是little-endian,这意味着从最早最简单的ADD指令,到今天复杂的AVX512或者AMX,只要指令的某个操作数是内存地址,那指令就一定会按照低位在前高位在后的逻辑读取数据。

    ARM

    ARM在指令集层面对没有对字节序作强制要求,也就是说,一块ARM CPU可能是little-endian,可能是big-endian,也可能二者皆支持。可以从目标Triple区分:以aarch64_bearm64_bearmeb开头的,即为big-endian,其他不带be或者eb缩写的,则是little-endian。

    为了和x86兼容,主流ARM基本都是little-endian模式。

    RISC-V

    RISC-V是little-endian,尽管有说法曰作者更喜欢big-endian,但因为主流的ARM和x86都是little-endian,因此也选择了little-endian。

    POWER

    POWER诞生在90年代,那时候RISC工作站还不是个历史概念,各大厂商都在制造自家的RISC CPU和UNIX分支,x86还是穷小子,所以大家依然倾向于big-endian。不过为了便于移植x86 PC程序,Windows NT支持的PowerPC 610还的确支持过little-endian模式,然而PowerPC和Windows的合作并没有持续几代,这个开关也被移除,直到POWER 7。

    但POWER 7的little-endian支持并不完整,例如硬件虚拟化就没法支持little-endian模式。从POWER 8开始,POWER CPU开始完整支持little-endian字节序。也就是说,POWER 8及以上的CPU支持两种字节序,由一个特权寄存器控制。甚至理论上,POWER CPU可以在运行时切换字节序。(但显然没人愿意这么做)

    在POWER支持little-endian前,Linux已经支持32位和64位的big-endian POWER CPU。而在little-endian加入以后,因为两种字节序的程序几乎没法相互兼容,所以它们在Triple上被看作两种不同的架构:ppc64指big-endian,而little-endian常用ppc64le或ppc64el表示。

    长远来看,同样是出于兼容目的,Linux将逐渐去除对64位POWER big-endian模式的支持,little-endian才是未来。不过这个故事仅限于Linux和BSD等开源社区,传统的AIX依然只会支持big-endian模式,且在可见的未来还没有改变的迹象。

    一些应用场景的字节序

    Unicode

    UTF-16和UTF-32这两种格式都会采用多个字节表示单个码点(通俗点说就是字符,尽管并不准确),这就引出little-endian和big-endian两种格式。在多数编辑器或处理字符编码的程序里,UTF-16 LE和UTF-16 BE被看作两种编码。但根据Unicode标准,使用UTF-16和UTF-32的文件都需要在开头用2字节标记文件是big-endian还是little-endian:0xFE 0xFF表示big-endian,0xFF 0xFE表示little-endian。

    对于一个内容为「Test」的文件,以下是三种编码的字节内容:

    feff 0054 0065 0073 0074 (UTF-16 BE)
    fffe 5400 6500 7300 7400 (UTF-16 LE)
    6554 7473 (UTF-8)

    开头的这两个字节被称作BOM(Byte-order mark),显然UTF-8因为基本单位是字节,所以并不需要BOM。但一些Windows程序依然会给UTF-8文件加上0xEF 0xBB 0xBF作为BOM以标记这个文件使用UTF-8。

    网络字节序

    根据RFC 1700,socket通信中的数据都使用big-endian格式传输,因此使用socket的C API时,需要用htonl/htons/ntohl/ntohs系列函数将数据在big-endian和原生字节序之间作转换,比如要绑定的端口号。一些上层库可能已经封装了这个行为,但这一点仍需牢记在心。

    WebAssembly

    WebAssembly采用little-endian,但这指的是内存读写指令采用的字节序,WebAssembly字节码中的整数都用LEB128格式表示。

    字节序不是什么

    • 数组在内存中永远是从前向后排的,和字节序无关
    • C/C++中的结构体也永远是从前向后排的,其他高级语言可能会重排对象的内存布局,但这同样和字节序无关
    • 整数或浮点数在CPU寄存器中使用何种字节顺序或位顺序,和字节序无关,实际上这对程序员也不可见,概念上我们都完全可以认为寄存器都是从前向后,类似big-endian般排列
    • 字节序只和数据从内存被加载到寄存器这一过程有关,且单位是字节而不是位

    意义何在

    字节序是一个习惯远比实际好处重要的领域。如果一定要为两种字节序列出一些好处的话:

    • Big-endian更加直观,读取一个4字节整数和4字节数组采用同样的顺序,由于网络通信使用big-endian,因此big-endian的程序在处理网络数据时还能省去字节反转的开销
    • Little-endian环境下,长度不同的数据能够保证低位重合,也就是说32位的0x1234用16位指令去读取依然是0x1234,这节省了类型强制转换时的开销

    但站在今天的角度,这些优缺点都无伤大雅。最重要的原因,不过是x86活下来成了主流,因此little-endian碰巧也成了主流,一如Windows和C语言。计算机领域各个层次都充满了抽象,如果有什么东西能穿越潮起潮落流传至今,原因几乎就是兼容性而已。