分类 计算机体系结构

统计一个数字二进制位1的个数

发布于
标签 Go
阅读数

最近一个需求需要使用golang实现一个兼容redis的无压缩的bitmap,需要提供一个bitcoun函数来统计这个bitmap中二进制位1的个数,查了一圈并没有找到类似的第三方库,因此决定自己实现一个.(利用一切机会造轮子

1. 问题简化

问题本质实际就是给定一个数字,比如一个二进制数10101101,计算出这个数字中二进制位1的个数,对于10101101这个数字来说它有5个位为1,即:10101101

对于这个问题,最简单的办法就是挨位数,不过这个办法太笨了,没有逼格。

那么有没有银弹呢?答案是肯定的,而且还不止一种。 退后 ,我要开始装逼了

2. 查表法

对于一个8位的数字来说,它只有256个值,因此完全可以预先计算好每个值的二进制位1个个数写入到映射表中,使用时直接查询这张映射表即可。

伪代码如下所示:

var count1map = map[uint8]uint8 {
    0b0000_0000: 0,
    0b0000_0001: 1,
    ...
    0b1111_1111: 8,
}

func bitcount(x uint8) uint8 {
    return count1map[x]
}

3. 移位法

查表法虽然可以应对8位这样值数量有限的数字,但是对于uint64 or int64这样64位的数字来说,它的值数量是非常多的,我们无法在内存中维护这样巨大的映射表,因此不能使用查表法来解决

Golang在bits包中提供一个OnesCount64(x uint64) int的函数,可以计算一个64位数字中二进制为1的个数,其源码如下:

const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff00ff00ff // etc.
const m4 = 0x0000ffff0000ffff

func OnesCount64(x uint64) int {
	const m = 1<<64 - 1
	x = x>>1&(m0&m) + x&(m0&m)
	x = x>>2&(m1&m) + x&(m1&m)
	x = (x>>4 + x) & (m2 & m)
	x += x >> 8
	x += x >> 16
	x += x >> 32
	return int(x) & (1<<7 - 1)
}

初看起来是有点懵逼的,一顿位运算操作怎么就能把1的个数算出来了呢?

这段代码注释中标明其来源于Hacker's Delight第5章

骚操作

别着急,我们还是采用自底向上的思想来拆解下。

3.1 2位数字二进制位1的个数

我们先想一下如何计算2位的数字二进制位1的个数,答案是非常简单的:

func OnesCount2(x uint2) int {
    return (x & 0b01) + ((x >> 1) & 0b01)
}

x & 0b01就是求第0位是不是1,((x >> 1) & 0b01)就是求第1位是不是1,加起来就是x这个2位数字二进制位1的个数。

3.2 4位数字二进制位1的个数

对于一个4位数字,如1011,我们先按照3.1中的算法分别求出第3位与第2位即10 和 第1位与第0位即11的二进制位1的个数,然后再加起来就得出这个4位数字的二进制位1的个数了。

伪代码如下所示:

func OnesCount4(x uint4) int {
    x = x & 0b0101 + x >> 1 & 0b0101
    return x & 0b0011 + x >> 2 & 0b0011
}

计算过程如图: image.png

3.3 8位数字二进制位1的个数

8位数字计算过程与4位计算过程本质是相同的,都是拆解组合,伪代码如下:

func OnesCount8(x uint8) int {
    x = x & 0b01010101 + x >> 1 & 0b01010101
    x = x & 0b00110011 + x >> 2 & 0b00110011
    return x & 0b00001111 + x >> 4 && 0b00001111
}

计算过程如下: image.png

64位数字重复这个过程即可,回头看golang的代码应该就可以看懂了,这里就不再详细解释了。

另外这个算法过程还可以进一步优化,详细可以参考下:计算汉明权重的SWAR(SIMD within a Register)算法 感兴趣的可以研究一下,这里就不赘述了。

4. POPCNT指令

一些较新的CPU上支持POPCNT指令,可以通过硬件直接进行计算,Golang代码示例如下:

main.go文件

package main

import (
    "fmt"
    "math/bits"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().Unix())
    for i := 0; i < 100; i++ {
        var num = rand.Uint64()
        if popcnt(num) != bits.OnesCount64(num) {

            panic(fmt.Sprintf("i: %d, popcnt(%b) = %d, bits.OnesCount64(%b) = %d", i, num, popcnt(num), num, bits.OnesCount64(num)))
        }
    }
    fmt.Println("ok")
}

func popcnt(x uint64) int

amd64.s 文件

#include "textflag.h"

TEXT main·popcnt(SB), NOSPLIT, $0-8
    MOVQ x+0(FP), AX // 将参数x移到AX寄存器
    BYTE $0xf3; BYTE $0x48; BYTE $0x0f; BYTE $0xb8; BYTE $0xc0  // 计算二进制X中1的个数,golang编译器不支持POPCNT指令,这行对应于POPCNT AX, AX
    MOVQ AX, ret+8(FP) // 将结果存入ret
    RET

...

阅读全文 »

brk与mmap

发布于
阅读数

1. 前言

glibc的malloc函数在申请大于128K的内存时使用mmap分配内存,mmap会从堆区和栈区中间的部分划分内存,而在申请小于128K的内存时使用brk从堆上划分内存。

2. brk/sbrk

brk是linux上一个系统调用,而sbrk是一个C库函数

2.1 brk函数原型

int brk(void *addr);

参数

|参数|解释| |----|----| |addr|要调整到的内存地址|

返回值

返回增加的大小

2.2 sbrk函数原型

void *sbrk(intptr_t increment);

参数

|参数|解释| |----|----| |increment|增加的内存大小|

返回值

返回增加之后的program break内存地址

2.3 brk的原理

brk实际是通过改变program break来实现的,这个program break可以理解为“堆顶指针”,意味着程序堆内存使用到了该位置。

image.png

而这种内存的分配方式有个问题,看下下图:

image.png

假设B已经被free了,但是由于上面有一个C对象,所以program break指针不能简单的向下移动来释放内存。那怎么办呢?

实际上free后不能立即归还内存,只是将这块内存标记为空闲,后续再申请内存时可以复用这块内存。并且两块连续的空闲内存可以合并为一块空闲内存,当最高地址空间的空闲内存大于128K时(可以通过M_TRIM_THRESHOLD选项调节),执行内存紧缩。对于上图来说,如果C也被free了,program break就可以指向A的结束地址了,就能释放一部分内存了。

难道这就是传说中的线性内存分配

3. mmap

3.1 mmap函数原型

void *mmap(void *addr, size_t len, int prot, int flags, int fd, off_t offset);

参数

|参数|解释| |----|----| |addr|映射的起始地址,通常设置为NULL,由内核来分配| |len|指定将文件映射到内存的部分的长度| |prot|映射区域的保护方式,通常是下面几个选项的组合| |flags|映射区的特性标志位,常用的有以下两个选项| |fd|要映射到内存中的文件描述符| |offset|文件映射的偏移量,必须是操作系统内存页大小的整数倍|

返回值

返回映射区的起始地址

3.2 munmap函数原型

// 解除映射
int munmap(void *start, size_t length);

参数

|参数|解释| |----|----| |start|mmap返回的映射区的起始地址| |length|映射区的大小|

返回值

解除成功返回0,失败返回-1

3.3 mmap原理

linxu内核使用vm_area_struct结构来表示一个独立的虚拟内存区域(比如堆、栈、bss段、代码段等),一个进程会有多个vm_area_struct结构体,各个vm_area_struct使用树结构或者链表连接。

vm_area_struct结构包含了该区域的起止地址和其他信息以及一个vm_ops指针,vm_ops指针内部引出所有针对这个区域可用的系统调用函数。

mmap就是创建一个新vm_area_struct结构,并将其与文件磁盘地址做映射。

image.png

mmap申请的内存可以通过munmap释放。

4. 总结

|方式|内存碎片|适用场景| |---|----|----| |brk|多,因为不可释放|申请小内存| |mmap|无,因为可以直接释放|申请大内存,如果用来申请小内存的话就会创建非常多的vm_area_struct结构体,不划算|

5. 参考资料

...

阅读全文 »

x64架构下Linux系统函数调用

发布于
标签 AT&T汇编
阅读数

一、 函数调用相关指令

关于栈可以看下我之前的这篇文章x86 CPU与IA-32架构

在开始函数调用约定之前我们需要先了解一下几个相关的指令

1.1 push

pushq 立即数 # q/l是后缀,表示操作对象的大小
pushl 寄存器

push指令将数据压栈。具体就是将esp(stack pointer)寄存器减去压栈数据的大小,再将数据存储到esp寄存器所指向的地址。

1.2 pop

popq 寄存器
popl 寄存器

pop指令将数据出栈并写入寄存器。具体就是将数据从esp寄存器所指向的地址加载到指令的目标寄存器中,再将esp寄存器加上出栈的数据的大小。

1.3 call

call 立即数
call 寄存器
call 内存

call指令会调用由操作数所代表的地址指向的函数,一般都是call一个符号。call指令会将当前指令寄存器中的内容(即这条call指令下一条指令的地址,也就是函数执行完的返回地址)入栈,然后跳到函数对应的地址开始执行。

1.4 ret

ret指令用于从子函数中返回,ret指令会先弹出当前栈顶的数据,这个数据就是先前调用这个函数的call指令压入的“下一条指令的地址”,然后跳转到这个地址执行。

1.5 leave

leave相当于执行了movq %rbp, %rsp; popq %rbp,即释放栈帧。

二、 函数调用约定

函数调用约定约定了caller如何传参即将实参放到何处,应该按照何种顺序保存,以及callee如何返回返回值即将返回值放到何处。

x86的32位机器之上C语言一般是通过栈来传递参数,且一般都是倒序push,即先push最后一个参数再push倒数第二个参数,并通过ax寄存器返回结果,这称为cdecl调用约定(C有三种调用约定,linux系统中使用cdecl),Go与之类似但是区别在于Go通过栈来返回结果,所以Go支持多个返回值。

x64架构中增加了8个通用寄存器,C语言采用了寄存器来传递参数,如果参数超过。在x64系统默认有System V AMD64Microsoft x64两种C语言函数调用约定,System V AMD64实际是System V AMD64 ABI文档的一部分,类UNIX系统多采用System V的调用约定。

System V AMD64 ABI文档地址https://software.intel.com/sites/default/files/article/402129/mpx-linux64-abi.pdf

本文主要讨论x64架构下Linux系统的函数调用约定即System V AMD64调用约定。

三、 x64架构下Linux系统函数调用

3.1 如何传递参数

System V AMD64调用约定规定了caller将第1-6个整型参数分别保存到rdirsirdxrcxr8r9寄存器中,第7个及之后的整型参数从右往左倒序的压入栈中。前8个浮点类型的参数放到xmm0-xmm7寄存器中,之后的浮点类型的参数从右往左倒序的压入栈中。

3.2 如何返回返回值

对于整型返回值要保存到rax寄存器中,浮点型返回值保存到xmm0寄存器中。

3.3 栈的对齐问题

System V AMD64要求栈必须按照16字节对齐,就是说在通过call指令调用目标函数之前栈顶指针即rsp指针必须是16的倍数。之所以要按照16字节对齐是因为x64架构引入了SSE和AVX指令,这些指令要求必须从16的整数倍地址取数,为了兼顾这些指令所以就要求了16字节对齐。

3.4 变长参数

这部分没看懂,待后续发掘。

四、 实际案例分析

4.1 案例1

看下下面这段C代码

unsigned long long foo(unsigned long long param1, unsigned long long param2) {
    unsigned long long sum = param1 + param2;
    return sum;
}

int main(void) {
    unsigned long long sum = foo(8589934593, 8589934597);
    return 0;
}

uname -a: Linux xxx 3.10.0-514.26.2.el7.x86_64 #1 SMP Tue Jul 4 15:04:05 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux gcc -v: gcc 版本 4.8.5 20150623 (Red Hat 4.8.5-39) (GCC)

转为汇编代码,gcc -S call.c

    .file   "call.c"
    .text
    .globl  foo
    .type   foo, @function
foo:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movq    %rdi, -24(%rbp)
    movq    %rsi, -32(%rbp)
    movq    -32(%rbp), %rax
    movq    -24(%rbp), %rdx
    addq    %rdx, %rax
    movq    %rax, -8(%rbp)
    movq    -8(%rbp), %rax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   foo, .-foo
    .globl  main
    .type   main, @function
main:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $16, %rsp
    movabsq $8589934597, %rsi
    movabsq $8589934593, %rdi
    call    foo
    movq    %rax, -8(%rbp)
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE1:
    .size   main, .-main
    .ident  "GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-39)"
    .section    .note.GNU-stack,"",@progbits

我们先看main函数的汇编代码,main函数中首先执行了三条指令:

pushq   %rbp # 将当前栈基底地址压入栈中
movq    %rsp, %rbp # 将栈基底地址修改为栈顶地址
subq    $16, %rsp # 栈顶地址-16,栈扩容,这里没搞懂为什么要扩容,有懂的同学欢迎评论区指点下

这三条指令是用来分配栈帧的,执行完成后栈变成下方的样子: image.png 继续往下看:

movabsq $8589934597, %rsi # 先将第二个参数保存到rsi寄存器
movabsq $8589934593, %rdi # 再将第一个参数保存到rdi寄存器
call foo # 调用foo函数,这一步会将下一条指令的地址压到栈上

执行完call foo指令后,栈的情况如下: image.png

然后我们跳到foo函数中看下:

pushq   %rbp # 将当前栈基底地址压入栈中
movq    %rsp, %rbp # 将栈基底地址修改为栈顶地址

开头仍然是建立栈帧的指令,执行完成后,此时栈帧的样子如下: image.png

继续往下看:

movq    %rdi, -24(%rbp)
movq    %rsi, -32(%rbp)
movq    -32(%rbp), %rax # 将第二个参数保存到rax寄存器
movq    -24(%rbp), %rdx # 将第一个参数保存到rdx寄存器
addq    %rdx, %rax # 执行加法并将结果保存在rax寄存器
movq    %rax, -8(%rbp) 
movq    -8(%rbp), %rax # 将返回值保存到rax寄存器

这里没搞懂为什么需要先挪到内存中再保存到rax寄存器上,可能是编译器实现起来比较方便吧,有懂的同学欢迎评论区指点下

此时栈情况: image.png foo函数最后执行了以下两条指令:

popq    %rbp # 将栈顶值pop出来保存到rbp寄存器,即修改栈基底地址为当前栈顶值,同时栈顶指针-8
ret # 从子函数中返回到main函数中

最终结果如图: image.png

4.2 案例2

我们修改下函数foo,使它接收9个参数验证下上面的理论。

unsigned long long foo(unsigned long long param1, unsigned long long param2, unsigned long long param3, unsigned long long param4, unsigned long long param5, unsigned long long param6, unsigned long long param7, unsigned long long param8, unsigned long long param9) {
    unsigned long long sum = param1 + param2;
    return sum;
}

int main(void) {
    unsigned long long sum = foo(8589934593, 8589934597, 3, 4,5,6,7,8,9);
    return 0;
}

编译为汇编后:

foo:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movq    %rdi, -24(%rbp)
    movq    %rsi, -32(%rbp)
    movq    %rdx, -40(%rbp)
    movq    %rcx, -48(%rbp)
    movq    %r8, -56(%rbp)
    movq    %r9, -64(%rbp)
    movq    -32(%rbp), %rax
    movq    -24(%rbp), %rdx
    addq    %rdx, %rax
    movq    %rax, -8(%rbp)
    movq    -8(%rbp), %rax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   foo, .-foo
    .globl  main
    .type   main, @function
main:
.LFB1:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $40, %rsp
    movq    $9, 16(%rsp) # 后6个参数放到栈上
    movq    $8, 8(%rsp)
    movq    $7, (%rsp)
    movl    $6, %r9d # 前6个参数分别使用rdi rsi rdx ecx r8 r9寄存器
    movl    $5, %r8d
    movl    $4, %ecx
    movl    $3, %edx
    movabsq $8589934597, %rsi
    movabsq $8589934593, %rdi 
    call    foo
    movq    %rax, -8(%rbp)
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret

五、 参考资料

...

阅读全文 »

IEEE754标准浮点数表示与舍入

发布于
阅读数

友情提示:本文排版不太好,但内容简单,请耐心观看,总会搞懂的。

1. 定点数

对于一个无符号二进制小数,例如101.111,如果我们要用2个字节即16位来存储它,我们可以约定用高8位存储小数点前的数字,用低8位存储小数点后的数字,这样的话它在存储空间中就是这样的:00000101.11100000。这种存储方式中小数点的位置是固定的,这称为定点数。这种存储方式有个问题那就是存储的数值是有上限的即11111111.11111111 = 2^7^+2^6^+2^5^+2^4^+2^3^+2^2^+2^1^+2^0^+2^-1^+2^-2^+2^-3^+2^-4^+2^-5^+2^-6^+2^-7^+2^-8^。如果我们要存储1111111111111111.这个数的话,用这个存储方式是无法存储的,但是实际上对于这个数来说16位的存储空间是够用的,就是说定点数存在空间浪费的缺点。

基于这个缺点,计算机中通常用浮点数来表示一个小数。

2. 浮点数

IEEE754标准使用V = (-1)^s^ × M × 2^E^表示浮点数,符号位(sign)s 决定该数是正数(s=0)还是负数(s=1),尾数(significand)M是一个二进制小数,阶码(exponent) E。

单精度浮点数中,s占用1位,M占用23位,E占用8位,总共32位,双精度浮点数s占1位,M占52位,E占11位,总共64位,这两种分别对应C中的float和double,另外还有一个扩展双精度它占用80位。

image.png

根据E值,浮点数有三种情况,

2.1 规格化的:E所有位既不全为0也不全为1。

在这种情况中,阶码被解释为以偏置(biased)形式表示的有符号整数,这时E的值表示为E=e-Bias,其中e为E所占位所表示的无符号整数,Bias=2^E所占位数^-1。举个单精度浮点数的🌰,假设当前E为00001010那么E = (00001010所对应的无符号整数) - (2^8^ - 1) = 10 - 127 = -117。

这种情况中M用来表示小数,其二进制表示为1.f~-1~f~-2~f~-3~……f~n~。举个单精度的例子,假设当前M为01100000000000000000100,那么M=1 + (2^-2^ + 2^-3^ + 2^-21^)。

2.2 非规格化的:E所有位都为0

在这种情况中,阶码值E=1-Bias,而尾数M二进制表示为0.f~-1~f~-2~f~-3~……f~n~,没有规格化值前面的1。
非规格化值有两个用途。首先规格化值M始终>1,所以没法表示0,所以+0.0的浮点表示的位模式为全0:符号位0,阶码字段全为0(表明是一个非规格化值),尾数都是0就得到M=0.0。如果符号位为1,我们就得到了-0.0。其次非规格值的另外一个用途是表示那些非常接近0.0的数。

2.3 特殊值:E所有位都为1,这时又有两种以下两种情况

  1. 无穷大:M所有位全为0,当符号位为0是就是正无穷,当符号位为1时就表示负无穷。当我们把两个特别大的数相乘或者除0的时候无穷能表示溢出的结果。
  2. NaN(Not a Number):M不全为0,如果一些运算的结果不能是实数或者无穷,比如对-1开平方根时就会返回NaN。

经过上面的讲解后我们思考下十进制数15.3203125使用单精度浮点数来表示的话其二进制形式应该是什么呢?我们首先将它转为二进制数,即:1111.0101001 = 1.1110101001 × 2^3^,即M=1.1110101001,E=3。

3. 浮点数舍入

浮点数并不能表示所有的实数,比如十进制的2.1没有完全对应的二进制数,浮点数只能近似的表示一些实数,为了尽量精确的表示这个实数就只能尽量增加二进制的位数,但是数据类型的位数是有限的,比如C中float只有32位。

关于十进制小数如何转二进制不清楚的同学可以自行搜索下相关文章,很简单,这里就不详述了。

这里举个例子:将十进制的2.1用单精度浮点数表示。首先小数点前的2转为二进制是10,然后我们将小数点后的0.1转为2进制,它是这个样子的:0.000110011001100110011001100110011001100110011001100110011...(后面是0011无限循环)所以2.1转为二进制就是:10.000110011001100110011001100110011001100110011001100110011...,转为IEEE标准表达方式就是 1.0000110011001100110011001100110011001100110011001100110011... × 2^1^,即M=0.0000110011001100110011001100110011001100110011001100110011... + 1,但单精度浮点数位数只有23位,这样就面临一个问题00001100110011001100110(这里是23)01100110011001100110011001100110011...这一长串23位之后的数字怎么办?直接舍去后面的位的话意味着计算机中所有小数都小于等于它的实际值,进1的话意味着计算机中所有小数都大于等于它的实际值,四舍五入看起来不错,但是由于中间的5会进位,所以仍然会使计算系统中的小数整体偏大。在进行一些大量数据的统计时,这三种方式都回累计一个相当大的误差。

IEEE浮点格式定义了四种不同的舍入方式,下面以十进制的小数舍入只保留小数点后0位为例:

| 方式 | 1.40 | 1.60 |1.50 | 2.50 | -1.50 | | ------ | ------ | ------ | ------ | ------ | ------ | | 向偶数舍入|1| 2| 2 | 2 | -2 | | 向零舍入|1|1|1|2|-1 | | 向下舍入|1|1|1|2|-2 | | 向上舍入|2|2|2|2|-1 |

向偶数舍入这个方式乍看可能没看懂,它其实是使舍入后的值的最低有效数字是偶数。1.5舍入有两个选择:1和2,但由于2是偶数所以就舍入到2,同样2.5舍入有两个选择:2和3,但由于3是奇数,所以还是舍入到2。

向偶数舍入的方式使得在大多数情况下,5舍去还是进位的概率是差不多的,在进行一些大量数据的统计时产生的偏差相较其他方式小一些。

4. 二进制舍入的🌰与规则总结

好多中文资料一般到这里就戛然而止了,CSAPP书中讲到这也没有给到一个二进制的例子,相信大部分读者看完了上面也不知道二进制里是怎么处理的,所以下面给个二进制舍入的例子。

假设我们要求只保留小数点后三位,有以下例子:

  1. 1.001 011 舍入后: 1.001 原因: 1.001 011舍入有两个选择:1.0011.010|1.001 011 - 1.001| = 0.000 011|1.001 011 - 1.010| = 0.000 101,显然0.000 011 < 0.000 101,所以1.0011.010更接近原值1.001 011,所以舍入到了1.001
  2. 1.001 101 舍入后: 1.010 原因: 1.001 101舍入有两个选择:1.0011.010|1.001 101 - 1.001| = 0.000 101|1.001 101 - 1.010| = 0.000 011,显然0.000 101 > 0.000 011所以舍入到后者。
  3. 1.001 100 舍入后: 1.010 原因: 1.001 100舍入有两个选择:1.0011.010|1.001 100 - 1.001| = 0.000 100|1.001 100 - 1.010| = 0.000 100,两种选择的差值是相同的,这时使用向偶数舍入的方式,1.010是偶数(0偶1奇),所以舍入到1.010

根据上面的例子我们总结出以下规律: 我们用RR...RDD...D来表示一个二进制小数,R表示保留位,D表示舍去位,那么有以下规则:

  1. DD...D < 10...0 直接舍去
  2. DD...D > 10...0 向上舍入
  3. DD...D = 10...0 向偶数舍入,细则:
    1. RR...R = XX...0,直接舍去
    2. RR...R = XX...1,向上舍入

5. 代码验证下

最后,我们写一段C代码,看下到底是不是按照IEEE754标准存的浮点数,代码如下:

int main(void) {
    float a = 2.1;
    float b = a + 3;
    return 0;
}

gcc编译下:

$ gcc -O0 -g float.c // -O0禁用优化,-g以下面使用gdb调试

gdb调试下:

$ gdb ./a.out

进入gdb后,输入start再输入layout asm查看反汇编结果: image.png 可以看到a的值被存入了寄存器eax,在gdb中通过i r eax查看eax寄存器中的值: image.png 可以看到eax寄存器中保存的值是0x400666666,转为二进制:01000000000001100110011001100110,套入IEEE754标准表示法: 0 10000000 00001100110011001100110,即符号位为0,M = 1.00001100110011001100110,E = 2^7^ - (2^7^ - 1) = 1

参考资料

...

阅读全文 »

CPU Cache与False Sharing

发布于
标签 Go
阅读数

一、CPU 缓存架构

现代多核CPU会在每个核心上加上一个较小的SRAM高速缓存存储器称为:L1高速缓存,其中L1缓存由分为dcache数据缓存,icache指令缓存。在L1缓存的下级加一个较大的L2高速缓存, 然后会再L2之下加一个多核共享的L3高速缓存。它们之间的逻辑结构大概是这样的: image.png

相较于访问CPU高速缓存来说访问主存简直太慢了,Jeff Dean曾给出过这样一组数字:

  • L1缓存访问时间 0.5ns
  • 分支预测错误 5ns
  • L2缓存访问时间 7ns
  • 主存访问 100ns

https://colin-scott.github.io/personal_website/research/interactive_latency.html 给出了不同年份这些指标的数字,

1.1 通用的高速缓存存储器结构

告诉缓存被划分为S = 2 ^ s高速缓存组(cache set),每个组含有E个高速缓存行(cache line),每个行又由B = 2 ^ b个字节的数据块(block)和有一个标识该行是否有效(即是否已过期或者已修改)的有效位(valid bit),以及t标记位(tag bit)组成。物理结构大概是下图这样: image.png

高速缓存的大小指的是所有数据块的大小的和,即:B * E * S。

假设当前CPU地址总线有m位,从而主存有M=2^m个地址,所以每个内存地址会有m位。当CPU需要从主存加载地址为A的内存块上的字节时,会先从CPU高速缓存中获取,这时候问题来了,应该到高速缓存的什么位置去拿呢?实际上会将m位地址A划分为以下几段:

image.png

这里的m、t、b、s都是二进制数,不要想成十进制数哦

从而有m = t + b + s CPU会根据A地址中间的s位定位主存地址A映射到了哪个组中,然后根据开头的t位与组内的E个行的标记位挨个比对以确认地址A映射到了哪一行(这里有文章说是并行查询),这时会检查该行的有效位标识该行是否有效,如果有效的话最后根据后b位就直接定位主存地址A映射到了数据块中的哪个字节上了。如果通过以上的步骤没有找到对应的高速缓存地址的话,高速缓存会向主存请求包含A地址的数据块的一个拷贝,CPU必须等待,当被请求的块到达高速缓存中时高速缓存会将这个块放到对应的位置上,然后从数据块中抽取出A地址上的字节返回给CPU。注意:高速缓存从主存中一次请求的是一个数据块而非具体地址上的一个字节,这非常关键!

CSAPP书中提到了为什么选择中间位作为组索引位,其大概意思是选择中间位能够使连续内存映射到不同的组上,提高高速缓存利用率并且减小冲突覆盖的问题,但是个人感觉其解释是按照特定平台来描述的,并没有普适所有平台,这里就不以我昏昏使你昭昭了,待后续查阅更加合理的解释再说。

根据E的不同我们将高速缓存划分为以下三类:

  • 直接映射高速缓存
  • 组相连高速缓存
  • 全相连高速缓存

1.2 直接映射高速缓存

每组只有一行即E=1的高速缓存称为直接映射高速缓存。这种缓存一旦定位到了组后就无需查询对应行了。

1.2.1 直接映射高速缓存的冲突不命中

假设当前计算机b=16即数据块为16个字节,高速缓存中有两个组,s=5即内存地址的第5位决定内存地址映射到哪个组上,有下面的一段golang代码

func foo(x [8]int32, y [8]int32) int32 {
	var sum int32 = 0
	for i := 0; i < 8; i++ {
		sum += x[i] * y[i]
	}

	return sum
}

上面的程序中xy占用了8 * 4 = 2 ^ 5 = 32个字节,假设x被加载到地址为0-31的内存之中,y被加载到32-63之中,sum存在于寄存器中,不占用内存地址。如下图所示 image.png 运行时,第一次循环中,CPU需要先加载x[0],由于高速缓存中一开始并没有,所以会从主存中加载x[0]-x[3]共16个字节(数据块的大小)的数据到高速缓存的组0中再返回给CPU,接下来同样的道理会将y[0]-y[3]加载到高速缓存的组0中。这时候由于每组只有一个行就导致了上一步加载进来的x[0]-x[3]被覆盖了,下一次循环中要加载x[1]时,x[1]就不在高速缓存中了,所以又必须去内存中加载一次,结果从内存中加载会的数据又把第二次加载进来的y[0]-y[3]给覆盖了,之后的每次循环都存在这个问题,导致每次都回冲突不命中。这种高速缓存反复地加载和驱逐相同的高速缓存块的组的情况称为抖动(thrash)

为了解决这个问题我们可以将x和y两个数组的长度定为12,即:

func foo(x [12]int32, y [12]int32) int32

这样的话再看下分布情况: image.png

这样的话由于y[0]-y[3]与x[0]-x[3]不在一个组上就不会出现抖动问题了。

1.3 组相联高速缓存

组相联高速缓存每组中有多个行。

1.4 全相联高速缓存

全相联高速缓存只有一个组。

1.5 写的问题

如果CPU要写一个已经缓存了的字时,有两种方法将该数据写到下层缓存中:

  1. 直写,最简单的一种方法,直接将数据写入到下层缓存。但是这种方案每次写都回引起总线流量
  2. 写回,为每个行单独维护一个修改位dirty bit,标识这个缓存块被修改过,只有当替换算法要驱逐更新过的块时才将它写入到下一层缓存中。

写不命中通常有两种方法:

  1. 写分配,加载低一层的缓存到高速缓存中,然后更新这个数据块。缺点是每次不命中都会导致一个块从低一层传送到高速缓存。
  2. 非写分配,避开高速缓存,直接把这个数据写入到低一层中。

直写通常是非写分配的,写会通常是写分配的。

二、伪共享False Sharing

通过上文了解CPU的缓存结构后我们做一个实验来引出伪共享的问题,实验前我们先看下实验机器的一些信息。Mac上通过sysctl -a查看机器信息,这里我过滤了下只拿出来与此实验相关的一些机器指标:

hw.cachelinesize: 64 // Cacheline 64字节
hw.l1icachesize: 32768
hw.l1dcachesize: 32768 // L1数据缓存32K
hw.l2cachesize: 262144 // L2缓存256K
hw.l3cachesize: 6291456 // L3缓存6M
machdep.cpu.core_count: 4 // 4核
machdep.cpu.thread_count: 8

现在我们定义一个程序,有2个线程,两个变量a和b,线程1循环n次执行a++操作,线程2执行n次b++操作,我们用Go来描述:

type SimpleStruct struct {
	n int32
}

type PaddedStruct struct {
	n int32
	_ CacheLinePad
}

type CacheLinePad struct {
	_ [CacheLinePadSize]byte
}

const CacheLinePadSize = 64

const Num = 10000000

func BenchmarkSimple(b *testing.B) {
	structA := SimpleStruct{}
	structB := SimpleStruct{}
	wg := sync.WaitGroup{}

	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() { // 为方便下文描述这个线程称为structA线程
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() { // 为方便下文描述这个线程称为structB线程
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

func BenchmarkSimplePad(b *testing.B) {
	structB := SimpleStruct{}
	structA := PaddedStruct{}
	wg := sync.WaitGroup{}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() {
			var j int32
			for j = 0; j < Num; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

运行benchmark go test -bench=. 得到以下结果 image.png 可以看到我们只在结构体中加入了一个64字节的元素性能就得到了极大的提高,这是为什么呢?

我们看下Simple这个函数的代码,假设structA线程运行在core1上,structB线程运行在core2s上,假设structA线程先执行,它会将structA这个变量与structB一起加载到core1的L1的同一cacheline中,structB线程也会将structA这个变量与structB一起加载到core2的L1的同一cacheline,structA线程修改了structA的值,它会将这个事件同步到core2上,导致core2上cacheline失效,这时就需要从低一层存储中加载最新数据,然后structB又修改了structB,又导致了cacheline失效,循环往复导致了运行效率极低。

而SimplePad这个函数中structA中加入了cachelinesize个字节,使得structA和structB处于不同的cacheline上,也就避免了上面的问题。

2.1 题外话

  1. 关于多核间同步缓存我没有查到特别好的文章,所以我就不妄加解释了,如果你想深入研究的话可以搜索这个关键词:MESI协议
  2. 上面的实验代码来自于【译】CPU 高速缓存原理和应用。最初在我在做这个实验时,写的实验代码是这样的:
var a int32
var pad [64]byte{}
var b int32
...

运行benchmark后发现运行时间并没有缩短,后来获取了a、pad、b的地址后才发现go将pad这个变量分配到了堆上,a和b两个变量在内存上还是紧挨着的,你做实验的话可以吸收这个经验:如果加上pad后发现运行时间没有缩短的话确认下a和b是不是真的被分隔到了两个cacheline上。

参考资料

...

阅读全文 »

理解内存对齐

发布于
标签 Go
标签 编译器
阅读数

相信大家都听说过内存对齐的概念,不过这里还是通过一个现象来引出本篇话题。

一、求一个结构体的size

猜下下面这个结构体会占用多少字节

type S struct {
    B byte  // Go中一个byte占1字节,int32占4个字节,int64占8个字节
    I64 int64
    I32 int32
}

是不是以为是1+8+4 = 13个字节?写段代码验证下:

type S struct {
	B   byte
	I64 int64
	I32 int32
}

func main() {
	s := S{}
	fmt.Printf("s size:%d\n", unsafe.Sizeof(s))
}

输出:

s size:24

与预想显然不同,这是为什么呢?答案是编译器替我们做了内存对齐。

二、什么是内存对齐

要理解这个问题需要先了解一下字长的概念以及内存的物理结构

2.1 字长

在计算器领域,对于某种特定的计算机设计而言,字(word)是用于表示其自然的数据单位的术语。在这个特定计算机中,字是其用来一次性处理事务的一个固定长度的位(bit)组。一个字的位数即为字长

字长在计算机结构和操作的多个方面均有体现,计算机中大多数寄存器(这里应该是指通用寄存器)的大小是一个字长

上面这段话可能太过于概念化不太好理解,那么请看下面的这段64位机器上的GUN汇编器语法的汇编代码:

movq (%ecx) %eax

这段汇编代码是将eax这个寄存器中的数据作为地址访问内存,并将内存中的数据加载到eax寄存器中。

我们可以看到mov指令的后缀是q,意味着该指令将加载一个64位的数据到eax寄存器中,这样一条指令可以操作一个64位的数据,说明该机器的字长为64位,同时这段代码能够执行则说明我们机器上的CPU中的eax寄存器必定是64位的,而一条指令能够从内存中加载一个64位的数据也说明了数据总线的位宽也为64位,说明了我们的CPU可以一次从内存中加载8个字节的数据。

2.2 64位内存物理结构

内存是由若干个黑色颗粒组成的,每个内存颗粒叫做一个chip,每个chip是由8个bank组成,每个bank是二维平面上的矩阵,矩阵中的每个元素保存1个字节也就是8个bit。

对于内存中连续的8个字节比如0x0000-0x0007,并非位于一个bank上,而是位于8个bank上,每个bank保存一个字节,8个bank像是垂直叠在一起,物理上它们并不是连续的。 image.png 之所以这样设计是基于电路工作效率考虑,这样的设计可以并行取8个字节的数据,如果想取址0x0000-0x0007,每个bank只需要工作一次就可以取到,IO效率比较高,如果这8个字节在同一个bank上则需要串行读取该bank8次才能取到。

结合上面的结构图可以看到0x0000-0x0007是一列,0x0008-0x000F是另外一列,如果从内存中取8-15字节的数据也可以一次取出来,但如果我们要取1-9的数据就需要先取0-7的数据,再取8-15的数据然后拼起来,这样的话就会产生两次内存IO。所以基于性能的考虑某些CPU会强制只能读取8的倍数的内存,而这也导致了编译器再此类平台上编译时必须做内存对齐。

2.3 Cacheline

CPU通常会将Cacheline size个字节一次加载到高速缓存中(即L1、L2、L3缓存)。 这部分内容我后续会写一篇博客专门介绍下CPU高速缓存结构。

2.4 再来看结构体size的问题

以下均以64位平台,即:64位宽内存以及64位cpu(数据总线64位,寄存器64位)、cacheline size=64byte为前提

type S struct {
    B byte
    I64 int64
    I32 int32
}

在不了解内存对齐前我们可能会简单以为结构体在内存中可能是这样排列的: image.png 总共占用13个字节。我们可以看到 I64 这个字段的内存地址是1-8,而在64位平台上为了将这个字段加载到寄存器中,CPU需要两次内存IO。
但做内存对齐后: image.png 总共占用20个字节,I64这个字段的内存地址是8-15,为了将这个字段加载到寄存器中,只需要一次内存IO即可。 我们写段代码验证下是否真的占用了20个字节:

type S struct {
	B   byte
	I64 int64
	I32 int32
}

func main() {
	s := S{}
	fmt.Printf("s size: %d, align: %d\n", unsafe.Sizeof(s), unsafe.Alignof(s))
}

输出:

s size: 24, align: 8

程序输出了24,而非上面我们以为的20,这是怎么回事呢?原因是结构体本身也必须要做对齐,它必须在后面再额外占用4个字节以使自己的size为8的倍数。

上面的结构体如果后面跟一个4字节的变量的话理论上说不用对齐也能保证一次内存IO就可加载,所以结构体对齐的根本原因目前我还不是特别能理解,可能为编译器做的优化,了解的同学欢迎在评论区指点一下

我们再调整下结构体的声明:

type S struct {
    B byte
    I32 int32
    I64 int64
}

再做内存对齐的话该结构体在内存中应该就是下面这个样子了: image.png 这时总共占用16个字节,相比较上面我们节省了8个字节。 写段代码验证下:

type S struct {
	B   byte
	I32 int32
	I64 int64
}
func main() {
	s := S{}
	fmt.Printf("s size:%v, s.B地址:%v, s.I32地址:%v, s.I64地址:%v\n", unsafe.Sizeof(s), &s.B, &s.I32, &s.I64)
}

输出结果:

s size:16, s.B地址:0xc0000b4010, s.I32地址:0xc0000b4014, s.I64地址:0xc0000b4018

确实占用了16字节,但貌似I32这个字段跟我们预想的不太一样,它被对齐到了4的倍数地址上,而非紧跟在B后边,这大概是编译器编译一套代码可以运行在32位又可以运行在64位平台上吧,目前没有查到相关资料姑且这么认为吧。

参考资料

字 (计算机)

带你深入理解内存对齐最底层原理

...

阅读全文 »

x86 CPU与IA-32架构

发布于
标签 AT&T汇编
阅读数

x86 CPU

现代计算机使用的CPU大部分都是x86CPU,包括现在牙膏厂的酷睿。x86系列CPU的原型是Intel 1978年推出的8086 CPU

32位CPU

368是x86系列第一款32位CPU,Pentium4是Intel第一款64位CPU。"xx位CPU"的定位比较模糊,但一般要满足以下两个条件:

  1. 具备n位宽的通用寄存器
  2. 具备n位以上的地址空间

“通用寄存器”是寄存器中用于整数运算等的通用的寄存器,地址空间是指进程虚拟地址的全体范围。

指令集

多种多样的CPU有着不同的架构和速度,存在很大的差异,但尽管有这些差异一般386和Core 2都可以统称为x86CPU,这是因为386和Core 2能够执行相同的机器语言的指令。如果只是使用386指令编写的程序,在386和Core 2上都是可以跑的。像这样不同的CPU都能解释的机器语言的体系称为 指令集架构(ISA, Instruction Set Architecture) ,简称 指令集 。 Intel将x86系列CPU之中的32位CPU的指令集架构称为IA-32。IA是“Intel Architecture”。

IA-32的变迁

随着CPU技术的不同发展,CPU支持的指令越来越多,IA-32中指令增加的非常多。 首先486中增加了非常重要的指令。从486的486DX型号开始加入了 浮点数运算单元(FPU,Floating Point number Processing Unit) 支持浮点数计算。486DX所支持的浮点数运算指令称为 x87FPU指令(x87 FPU instuctions)。 386也能够支持浮点数运算,但必须添加名为387的FPU。也就是说配置有387的机器与没有配置387的机器支持的指令是不同的。 所添加的其他重要的指令还有 MMX和SSE(Streaming SIMD Extensions) 。两者都是为了支持并行处理多条数据的扩展指令。例如用通常的IA-32指令进行加法运算时一次只能执行一次加法运算,但使用MMX和SSE的加法指令可以同时执行多个运算。

IA-32的64位扩展: AMD64

AMD曾先于Intel提出x86系列的64位扩展,并推出了相应的产品。由AMD设计的x86位指令集架构称为AMD64。
Intel随后在自己的CPU中加入了和AMD64几乎相同的名为Intel64的指令集。Pentium4后期的版本和Core 2的后续产品都是基于Intel64指令集架构的。
要统称AMD64和Intel64时可以试用独立于公司名称的用语:x86-64。另外,Windows中将AMD64对应的架构称为x64。
Intel曾与HP一起开发名为IA-64的指令集架构,IA-64与IA-32架构完全不兼容。Intel推出的Itanium处理器是基于IA-64架构的。

IA-32的概要

IA-32中主要寄存器如下图:

image.png

通用寄存器 (generic register)是编程时使用频率最高的寄存器,宽度为32位的通用寄存器有eax、ebx、ecx、edx、esi、esp、ebp共8个,用于整数运算和指针处理。

指令指针 (instruction pointer) 是存放下一条要执行的代码的地址的寄存器,IA-32的指令指针为32位,称为eip。

标志寄存器 (flag register) 用于保存CPU的运行模式及表示运算状态等的标志的寄存器。 浮点数寄存器 (floating point number register) 是存放浮点数的寄存器,用于浮点数的计算。IA-32中从st0到st7有8个宽度为80位的浮点数寄存器。

MMX寄存器 (MMX register) 是MMX指令用的寄存器。MMX Pentium以及Pentiunm Ⅱ之后的CPU中有从mm0到mm7共8个64位的寄存器。但实际上MMX寄存器和浮点数寄存器是共用的,即无法同时使用浮点数寄存器和MMX寄存器。

XMM寄存器 (XMM register) 是SSE指令指令用的寄存器。Pentium Ⅲ以及之后的CPU中提供了xmm0到xmm7共8个128位宽的XMM寄存器。XMM寄存器和MMX寄存器不同,是独立的寄存器不和浮点数寄存器共用。另外 mxcsr寄存器 是表示SSE指令的运算状态的寄存器。

除上述寄存器外还有写OS内核时用到的 系统寄存器 和debug时用到的 debug寄存器 以及32位环境下用不到的段寄存器。

通用寄存器

名称由来

| 寄存器 | 名称的由来 | 翻译 | | ------ | ------ | ------ | | eax | accumulator | 累加器,很多加法乘法指令的缺省寄存器 | | ebx | base regiter | 基底寄存器,在内存寻址时存放基地址 | | ecx | count register | 计数寄存器,是重复(REP)前缀指令和LOOP指令的内定计数器 | | edx | data register | 数据暂存寄存器,总是被用来放整数除法产生的余数 | | esi | source index | 源索引寄存器 | | edi | destination index | 目标索引寄存器 | | ebp | base point | 基址指针,经常被用作高级语言函数调用的frame pointer | | esp | stack pointer | 用作堆栈指针,称为栈顶指针 |

ebp和esp寄存器一般用来实现机器栈,其他寄存器原则上可以随便用。

通用寄存器的宽度都为32位,它们的一部分可以当做16位/8位寄存器使用。例如可以当eax寄存器中的低16位当做16位寄存器ax来访问,还可以将ax寄存器的高8位当做ah寄存器,低8位当做al寄存器。 image.png

IA-32中各进程的一部分地址空间被当做栈来使用,主要用于保存函数的临时变量和参数。栈的位置因OS而已,IA-32 Linux平台上,栈位于各进程地址空间中靠近3GB位置。即栈是从高地址向低地址进行延伸image.png

IA-32中用栈指针(stack pointer)来表示栈,栈指针(esp寄存器)是存放栈顶地址的寄存器

栈的操作

举个例子如果我们要向栈中压一个4字节的整数17,整个操作步骤就是先将esp寄存器-4(栈从高地址向低地址进行延伸的),然后将整数保存到esp寄存器指向的内存地址中。 image.png

出栈则正好相反,首先从esp寄存器指向的内存地址中将数据加载出来,并将esp寄存器+4。 image.png

栈帧

栈并不是连续的一整块,栈是根据每一个函数分开管理的,我们将管理单个函数数据的栈的领域称为栈帧(stack frame)。如果有这样一个程序:main函数调用函数f,f调用函数g,那么这个程序在执行g时的栈就会是下图这样:

image.png

ebp寄存器总是指向当前函数栈的栈底,栈帧的顶部与当前进程的栈顶是相同的,esp寄存器总是指向栈帧的顶部。其他架构中一般将具有和基址指针相同功能的指针称为帧指针(frame pointer)。

一个栈帧中通常保存一下信息:

  • 临时变量
  • 源函数执行中的代码地址(返回地址)
  • 函数的参数 在每个栈帧上存储上述信息的具体步骤是由函数的调用约定(calling convention)决定的,各个CPU、操作系统的函数调用约定是不同的。

指令指针

指令指针(instruction pointer)是存放下一条要执行的指令的地址的寄存器。CPU从该寄存器所指向的内存地址中获取下一条指令并执行,同时将指令指针推到下一条指令,可以通过跳转指令来改变指令指针的值。

根据架构的不同,有时将指令指针称为程序计数器(program counter, pc)。

标志寄存器

eflags是32位寄存器,CPU的运行模式以及运算相关的信息等都以1个bit的形式存在该寄存器中。 image.png

标志有以下三类:

  1. 表示运算结果的状态标志(status flag)
  2. 用于运算控制的控制标志(control flag)
  3. 用于控制计算器整体运行的系统标志(system flag)

一般程序中可用的只有状态标志和控制标志,系统标志再写OS时会用到,用户模式的进程不能修改系统标志,否则会报没有权限的错误。

状态标志的具体含义如下: 简称 | 标志的正式名称 | 含义 -- | -- | -- CF | carry flag | 运算结果中发生进位或借位 PF | parity flag | 运算结果中的奇偶标志位 AF | auxiliary carry flag | 运算结果中低4位向高4位发生进位或借位 ZF | zero flag | 比较结果为0的时候被置为1 SF | sign flag | 运算结果为负数时被置为1 OF | overflow flag | 运算结果越过了正/负的界限

这些标志位一般与跳转指令配合使用。

字节序

32位即4个字节数据的二进制表现形式如下: image.png

MSB(Most Significant Bit)指向最高位,LSB(Least Significant Bit)指向最低位。而在内存中先放MSB所在的字节还是先放LSB所在的字节是由CPU的类型决定的,先放MSB所在字节的架构称为大端(big endian),先放LSB所在字节的架构称为小端(little endian)。通过网络传输超过2个字节数据时一般使用大端的方式,所以大端也被称为网络字节序(network byte order)

本文摘自

How to develop a compiler

...

阅读全文 »