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

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位。

根据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.001和1.010，|1.001 011 - 1.001| = 0.000 011，|1.001 011 - 1.010| = 0.000 101，显然0.000 011 < 0.000 101，所以1.001比1.010更接近原值1.001 011，所以舍入到了1.001
2. 1.001 101 舍入后： 1.010 原因： 1.001 101舍入有两个选择：1.001和1.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.001和1.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查看反汇编结果： 可以看到a的值被存入了寄存器eax，在gdb中通过i r eax查看eax寄存器中的值： 可以看到eax寄存器中保存的值是0x400666666，转为二进制：01000000000001100110011001100110，套入IEEE754标准表示法： 0 10000000 00001100110011001100110，即符号位为0，M = 1.00001100110011001100110，E = 2^7^ - (2^7^ - 1) = 1

参考资料

• 深入理解计算机系统
• IEEE754规范的舍入方案怎么理解呢？

一、CPU 缓存架构

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

相较于访问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)组成。物理结构大概是下图这样：

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

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

这里的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
}

上面的程序中x与y占用了8 * 4 = 2 ^ 5 = 32个字节，假设x被加载到地址为0-31的内存之中，y被加载到32-63之中，sum存在于寄存器中，不占用内存地址。如下图所示 运行时，第一次循环中，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

这样的话再看下分布情况：

这样的话由于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=. 得到以下结果 可以看到我们只在结构体中加入了一个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上。

参考资料

• 深入理解计算机系统
• Numbers Everyone Should Know
• Go and CPU Caches
• 【译】CPU 高速缓存原理和应用

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

一、求一个结构体的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像是垂直叠在一起，物理上它们并不是连续的。 之所以这样设计是基于电路工作效率考虑，这样的设计可以并行取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
}

在不了解内存对齐前我们可能会简单以为结构体在内存中可能是这样排列的： 总共占用13个字节。我们可以看到 I64 这个字段的内存地址是1-8，而在64位平台上为了将这个字段加载到寄存器中，CPU需要两次内存IO。
但做内存对齐后： 总共占用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
}

再做内存对齐的话该结构体在内存中应该就是下面这个样子了： 这时总共占用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

现代计算机使用的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中主要寄存器如下图：

通用寄存器 (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寄存器。

栈

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

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

栈的操作

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

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

栈帧

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

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

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

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

指令指针

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

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

标志寄存器

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

标志有以下三类：

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个字节数据的二进制表现形式如下：

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

一、背景

公司当前有一个用户群的系统，核心功能是根据不同的条件组去不同的业务线中get符合条件的uid列表，然后存到redis中的bitmap中。

举个🌰，如果一个用户群中有两个用户: 3和7，即[3,7]，用bitmap表示那就是：00010001

最后利用redis提供的bitOp命令: bitOp AND \ bitOp XOR \ bitOp OR对各个条件组对应的uid列表bitmap做交并差集计算，得出最终的用户群并存储到redis bitmap中。

二、问题

对于上面描述的系统，如果用户群人数较多的那我们就需要执行较多次的setBit {uid} 1命令，而且如果用户群中的第一个uid是一个特别大的值比如10亿的话，就可能会一次malloc 1000000000/1024/1024/8 ~= 120M的内存，这可能会导致redis卡住一段时间，在高并发的redis实例上执行这个操作是相当危险的。而且可以预想到对于两个较大的bitmap key执行bitOp也是非常消耗CPU的，应该尽量避免在存储型的redis实例中做这种十分消耗CPU的计算操作。

实际上内存最少只能申请一个字节，即8位，所以上面的计算方式稍有出入，但相差并不大。

三、解决方案

针对上述的问题，可以将bitmap的计算挪到应用程序中来，只将最终统计出来的bitmap存储到redis中即可。
如果最终结果用户群中的第一个uid是一个特别大的值的话，可以先set 1K再设置2K..3K...这样缓存的增加bitmap的大小避免redis卡住。

四、PHP实现Bitmap

由于该系统目前是使用的PHP，所以下面记录下PHP实现Bitmap的”心路历程“。

由于要操作PHP变量的某一位，所以就要借助位运算来实现，但是又由于PHP的位运算只能作用在整型数上，所以我们无法使用字符串或者浮点数来实现，所以最先考虑的就是使用整型数组来实现。

为什么是数组呢？因为在64位机器上一个整型变量最多只能使用64位，又由于PHP的整型是有符号的，所以最高位无法供我们使用，所以一个整型变量能存储的最大的uid就是63，这真是太鸡肋了-_-||，所以只能搞个用多个整型变量了实现了。

OK，到此为止貌似找到一个看起来不错的解决方案。但是我们再思考这样一个问题：假设我们系统中最大的uid是63x100万=3.6千万（对主流互联网公司来说这很正常吧😸），那为了存储所有uid，我们需要1百万个整数才行，即我们需要一个拥有1百万个元素的数组，那么如果我在进程中制造了一个这样的数组会占用多少内存呢？会是64 * 1百万 / 1024 / 1024 / 8 ~= 7.6M吗？答案是否定的，因为php数组是由HashTable实现的，这是一个复杂的结构体，除了数组元素占用的内存外，还有其他的占用。（这里先不做展开，有兴趣可以自行查看下php数组的实现） 眼见为实：

<?php
ini_set('memory_limit','4G');
$arr = [];
for ($i = 0; $i < 64 * 1000000; $i++)
{
    $arr[] = PHP_INT_MAX;
}

echo "done\n";
while(1){
}

查看内存占用

可以看到大概是1.5G，比我们上面预计的大的多,这太可怕了，必须优化下我们的内存占用，才能真正在生产环境中使用。

这里需要提一句，我的机器只有8G，所以程序可能会用到swap分区，而ps命令结果中的RSS不统计swap分区的占用，在我实际实现中发现ps结果中RSS一列显示占用的内存会随着时间慢慢减少，但是我的程序中arr变量占用的内存是不可能被回收的，所以推测是物理内存中占用的部分内存被置换到了swap分区中。如果你要进行这个实验的话建议关闭swap分区，这样你能得到一个更准确的结果。

五、继续优化

基于上面的经验，如果我们要占用尽可能小的内存，那我们必须能够操作一段近乎无限长的内存且不能产生其他额外占用才可以。幸运的是PHP给我们提供了这样一个扩展：GMP，这个扩展可以让我们使用一个任意长度的整数。OK现在我们拥有了获得一块连续的内存而不会产生其他额外占用的手段，再写一段代码使用下并验证下内存占用情况：

<?php

$gmp = gmp_init(0);
gmp_setbit($gmp, 64 * 1000000, true);
echo "done\n";
while(1){}

Awesome，这次只使用了15M的内存。更加兴奋的是这个扩展提供了诸如：gmp_and、gmp_or、gmp_xor这样进行位运算的函数，极大的方便了我们的使用。

到此为止我们似乎找到了一个完美的解决方案，但是真的完美吗？No！其实还可以再优化一下，想象下如果我们有一个用户群，里面只有一个uid：64000000（表示为数组的话就是：[64000000]），为了存储这个用户我们需要占用7.6M内存，而这个用户群中仅仅只有一个元素，这真是极大的浪费啊！

为了优化这个问题可以拥抱上面被我们唾弃的数组😸，一个大的bitmap拆分为一个个小bitmap的数组，这一个个小的bitmap我们限制大小为1Kw位。

回到上面的问题，如果我们要存储[64000000]这个用户群的话只需要在数组的第6个元素中设置一个little bitmap: 1即可。这样我们就由一开始的占用7.6M内存优化为了占用1位内存。

OK，到此为止我们找到一个还不错的解决方案😸。

后言

为了在Mac中安装GMP扩展又耗费了很多时间，当然，这又是另外一个故事了。有时间我会分享Mac中安装GMP扩展的过程中我遇到的问题。

参考资料

1. GNU Multiple Precision
2. Process Memory Management in Linux
3. 从源码看 PHP 7 数组的实现

此篇文章要求读者对编译原理前端部分有一定了解 此篇文章中，我们以大写英文作为非终结符，小写英文作为终结符

1. LR(0)分析法简述

LR分析法从左至右移进输入的终结符（词法分析器的输出实际是token，但在语法分析阶段会代表是一个终结符），并将终结符压入到堆栈，称为shift。如果当前栈上的符号恰好符合某个非终结符的生成式，则此时进行归约操作：将这些符号弹出栈，然后将规约后的非终结符压入堆栈，这一步就称为reduce。然后继续上面的步骤，直到没有输入。
如果最终栈上只有一个非终结符，且该非终结符就是目标符号，那证明识别成功，否则识别失败。
名称LR得名于：从左(Left)到右扫描（L）,反向（Reverse）最右推导（R）。

2. LR(0)分析法的不足

上面描述的算法存在一个问题，我们以下面的语法为例说明：

// 例1
B : A c
A : b d
  | b

对于上面的语法，当语法分析器遇到终结符b时，面临着两个选择，一个是继续移进下一个终结符，一个是使用生成式A : b进行归约。这种情况称为shift/reduce冲突。
继续看下面一个例子：

// 例2
A : b
C : b
D : A a
E : C d

对于上面的语法，当语法分析器遇到终结符b时，面临着两个选择，一个是根据A : b，归约为A，另一个选择是使用生成式C : b进行归约。这种情况称为reduce/reduce冲突。

因为这两种冲突的存在导致了LR(0)分析法在实际语法分析中基本不可用，必须找到解决这两种冲突的方案才行，那么如何这两种冲突呢？

3. SLR(1)

对于这两种冲突，我们首先先看一种简单的解决方案：SLR(1) (Simple LR)分析法。
SLR(1)分析法首先求出所有非终结符的Follow Set，即 跟在非终结符之后的所有终结符的集合，然后前瞻一个符号（即从词法分析器中预先读入下一个终结符），如果该前瞻符号在一个非终结符的Follow Set中，就根据此非终结符的生成式进行归约。

我们以上面的例2为例，SLR(1)分析器先求出A的Follow Set为{a},C的Follow Set为{b}，假设当前输入为b a，输入b之后，语法分析器面临选择：归约到A or 归约到C，此时分析器前瞻一个符号即c，由于c属于A的Follow Set，所以分析器选择归约到A。

上面的例1也可以通过此算法解决shift/reduce冲突。

遗憾的是SLR(1)依然存在问题，这里举个例子就清楚了：

// 例3
T : S
S : aAd
S : bAc
S : aec
S : bed
A : e

首先求出各个非终结符的Follow Set:

Follow(T) = {}
Follow(S) = {}
Follow(A) = {d, c}

我们假设当前的输入为a e c, 当输入e时，SLR(1)分析器面临两个选择：继续移进下一个符号 or 根据A : e归约到A，此时SLR(1)分析器前瞻符号c，c存在于Follow(A)中，但此时又可以选择移进c，所以SLR(1)此时又面临着冲突了。

SLR(1)不足之处在于Follow Set太宽泛，处于Follow Set中的前瞻符号不一定能合法的跟在非终结符之后。实际上SLR(1)忽略了分析的上下文，针对SLR(1)的不足由提出了LR(1)分析法。

4. LR(1)

LR(1)的基本原理就是只要前瞻符号能合法跟在归约的非终结符之后就可以进行归约，LR(1)会为每个生成式绑定一个** LookAhead Set**，只有前瞻符号处于这个集合之中才进行归约，它是Follow Set的子集。那么LookAhead Set如何生成呢？

4.1 LookAhead Set生成

我们将生成式一般化为下面的样子：

s -> α .x β， C 
x -> . r

其中 s,x都是非终结符，α β r可以是终结符也可以是非终结符，C 为生成式的LookAhead Set。

x的LookAhead Set = First(β C)，即β的FirstSet与C串起来之后的First集

First Set可以理解为非终结符所有生成式中第一个终结符的集合

5. Merak

我将LR(1)分析算法封装成了一个Golang Parser库：Merak，并且用它实现了一个面向对象语言的Parser: Mizar。对此有兴趣的同学可以试用下，它将为你省略手写语法分析器的过程，节省宝贵的时间投入到更加有趣的编译器后端工作中。

前言

上一篇《我的第一个面向需求的Haskell程序》文章中的Haskell程序还存在一个问题： 程序只打印出了文件中有没有重复的元素但是并没有告知是哪一个元素重复了，重复了几次也没有打印出来。 所以我继续优化下上篇文章中的Haskell程序，现在这段程序变成了下面这样

代码

module Main where

import Data.List.Split
import Data.List
import System.IO
import System.Environment

main = do
    args <- getArgs
    check args

check::[String] -> IO ()
check [filename] = do
    contents <- readFile filename
    mapM_ printRepeat $ fmap (\(x:xs) -> (x, 1 + length xs)) $ group $ splitOn "\r\n" contents
    putStrLn "check done"

check x = do
    putStrLn "请输入文件名"

printRepeat::(String, Int) -> IO()
printRepeat (word, num)
    | num > 1 = putStrLn $ word ++ " repeated " ++ (show num) ++ " times."
    | otherwise = return ()

使用

$ cabal build
$ ./dist-newstyle/build/x86_64-osx/ghc-8.8.4/repeat-0.1.0.0/x/repeat/build/repeat/repeat test.txt
joM2qWfjOJc repeated 2 times.
check done

解释

首先我们使用split包提供的splitOn 函数按照换行符将文件内容切分为[String]，现在我们有了：

["abc", "abc", "def", "ghi", "def"]

然后使用group函数聚合下这个List，得到：

[["abc", "abc", "abc"], ["def", "def"], ["ghi"]]

再通过fmap (\(x:xs) -> (x, 1 + length xs))即map一个lambda表达式到这个List上，将这个List中的每个元素转为元组，得到：

[("abc", 3), ("def", 2), ("ghi", 1)]

至此我们实际做了一个WordCount程序...

接下来调用printRepeat函数打印出来结果就OK了

学习汇编语法的目的

为什么要学习汇编语法呢？原因是我最近在做一个面向对象语言的编译器（地址：https://github.com/Orlion/Mizar），目前已经完成了parser部分，即已经生成了AST，下一步要做的就是语义分析了，而语义分析之后要做的就是生成AT&T汇编代码了，所以有必要提前了解下汇编语法看在语义分析的实现阶段能否有所指导。

先看一段代码

首先我们有这样一段c语言代码：

#include <stdio.h>

char msg[14] = "Hello,world!\n";
 
int main(void)
{
    puts(msg);
    return 0;
}

运行 gcc -S -Os hello.c

    .file   "hello.c"
    .section    .text.startup,"ax",@progbits
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rax
    .cfi_def_cfa_offset 16
    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax
    popq    %rdx
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .globl  msg
    .data
    .align 8
    .type   msg, @object
    .size   msg, 14
msg:
    .string "Hello,world!\n"
    .ident  "GCC: (GNU) 4.8.5 20150623 (Red Hat 4.8.5-39)"
    .section    .note.GNU-stack,"",@progbits

接下来解释下AT&T汇编的语法

指令

指令是直接由CPU负责处理的命令，不以.开头的行首缩进的行都是指令行。

    movl    $msg, %edi
    call    puts
    xorl    %eax, %eax

指令由操作符和作为参数的操作数组成，以 movl $msg, %edi 为例，movl 为操作符， $msg 和 %edi 为操作数，操作数以逗号来间隔。

汇编伪操作

以 . 开头末尾没有:的行都是汇编伪操作。例如，.file "hello.c", .globl main。汇编伪操作是由汇编器而非CPU处理的指令。一般用于在目标文件中记录元数据（meta data）或者设定指定的属性等。例如 .string 是用来定义字符串常量的汇编伪操作。

标签(labal)

以冒号: 结尾的行都是标签行，例如：.LFB0:,main:。 标签具有为汇编伪操作生成的数据或者指令命名(标上符号)的功能，这样就可以在其他地方调用通过标签定义的符号。 标签可以以.开头

注释

支持两种注释：

# xxx

/* xxx
xxx */

助记符后缀

刚才提到的movl和subl为助记符，更准确的说mov和sub为助记符，末尾的l是后缀，l是long的缩写，表示操作对象的数据大小。类似这样的后缀还有b,w,l。

|后缀|操作对象的大小|缩写| |-|-|-| |b|8位|byte| |w|16位|word| |l|32位|long|

操作数

操作数有四种：

1. 立即数
2. 寄存器
3. 直接内存引用
4. 间接内存引用

1. 立即数

立即数就是C语言中的字面量，机器语言中立即数以整数的形式出现，能高速访问。像$27这样，立即数用$来标识，如果漏掉了$就成了直接内存引用了。立即数有8位，16位，32位。

2. 寄存器

GUN汇编器规定寄存器以%开头，例如eax寄存器写作%eax

3. 直接内存引用

直接访问固定内存地址的方式。GNC汇编器会将任何整数解释为内存地址并访问。比起使用数字，更常用符号(symbol)直接访问内存。例如.LFE0就是访问符号.LFE0所指向的地址。符号在汇编和链接的过程中会被置换为实际内存地址。

4. 间接内存引用

是将寄存器的值作为内存地址访问的方式。间接内存引用中最通用的就是下方的形式：

disp(base, index, scale)

其中任何一者都可以省略。

上述指令访问disp + (base + index * scale)的地址。 下面详细讲解，首先最简单的间接引用的形式如下：

(%eax)

即只指定基地址(base)的形式。上述表达式将eax寄存器中的值作为内存地址访问。 接着带有disp的形式如下。disp是displacement(偏移)的简称。

4(%eax)

上述就是访问 4 + (eax寄存器中值) 这个内存地址。在C语言中用来访问如下结构体中成员y的情况：

struct point {
    int x; // x占4个字节，即4个内存地址
    int y;
}

最后使用index和scale的情况如下所示：

(%ebx, %eax, 4)

上面访问的就是(ebx寄存器中的值 + eax寄存器中的值 * 4)内存地址。在C语言中用来访问数组，例如访问元素大小为4字节（例如int）的数组中元素的第%ebx个元素时就可以用这种方式。当并非所有的数组访问都可以只靠间接内存引用来表示，因为scale只能是1、2、4、8之一。

2020-09-22更

突然意识到如果要将一个复杂工程的AST编译为汇编代码必须具备能够用汇编实现这个复杂工程的能力才行，这太难了... 所以暂时放弃吧，先编译到了LLVM IR再说，嗯。

2020-10-07更

不如趁此机会学习下汇编以及后续的链接装载，有助于建立宏观的了解。所以还是继续学习吧。 😸

未完待续...

全文均为伪代码，没有验证，只可意会

doIf::Bool -> a -> Maybe a
doIf cond action = if cond then (Maybe action) else Nothing

我们声明了一个doIf函数，它接收两个参数：cond与action，它干一件事：如果cond == true 就调用action,并包在Maybe中返回。 如果是strict的语言的话，在调用doIf函数的之时action就会被执行了，而Haskell默认是non-strict的，所以在调用doIf时，action无需求值，只有在cond为true时才需要对action求值，如果cond为false的话action根本不会被执行，这就是non-strict与strict的区别。

背景

上周五（20年8月28日）的时候，公司测试同学需要测试我的一个提测需求，其中有个测试用例是需要检查下下后台导出的兑换口令列表文件中是否有重复的口令。

由于导出的口令有数百万之多，肯定是不能用眼去看了，原本是打算用excel来检查的，但是我一想：ei(二声)~，最近不是正好在搞Haskell吗？正好拿来练练手，用Haskell写个检测程序。

Why is Haskell

因为这个程序写出来是要交给测试同学使用的，如果用java或者php这种解释型语言来写，还需要测试同学先去安装个java/php的解释器才行，显然是有点扯的，所以用编译型语言写完后直接build出一个可执行文件才比较方便。

当然可以将java/php的程序打包成一个可执行文件，但是又要花费我一些不必要的时间了。

编译型语言中我常用的有golang和Haskell。不可否认Go面对这个需求写起来可能更快，但是我其实还是想用Haskell练练手。

那? 开始吧！

首先，使用cabal创建一个项目

$ mkdir repeat && cd repeat
$ cabal init

导出的口令文件是以\r\n换行的，haskell的lines函数无法切分，所以需要通过cabal引入一个包:split，我的repeat.cabal文件就变成了下面这样了：

cabal-version:       >=1.10
-- Initial package description 'repeat.cabal' generated by 'cabal init'.
-- For further documentation, see http://haskell.org/cabal/users-guide/

name:                repeat
version:             0.1.0.0
-- synopsis:
-- description:
-- bug-reports:
-- license:
license-file:        LICENSE
author:              wangdongdong
maintainer:          wangdongdong@smzdm.com
-- copyright:
-- category:
build-type:          Simple
extra-source-files:  CHANGELOG.md

executable repeat
  main-is:             Main.hs
  -- other-modules:
  -- other-extensions:
  build-depends:       base >=4.13 && <4.14, split
  -- hs-source-dirs:
  default-language:    Haskell2010

编辑Main.hs

module Main where

import Data.List.Split
import Data.List
import System.IO
import System.Environment

main = do
    args <- getArgs
    check args

-- 通过模式匹配获取命令行参数中的文件名
check::[String] -> IO ()
check [filename] = do
    contents <- readFile filename
    -- 暴力通过去重后的list length对比来判重，不可取
    if (length $ mylines contents) /= (length $ nub $ mylines contents)
        then putStrLn "有重复元素" 
        else putStrLn "没有重复元素"

check x = putStrLn "请输入文件名"

-- 通过split库的splitOn函数以\r\n为切割符将文件内容切分为list
mylines contents = splitOn "\r\n" contents

最后编译为可执行文件

$ cabal build

编译结果在dist-newstype文件夹之中

交付使用

$ ./repeat keywords.txt

能够满足需求！

后续优化请看

《我的第一个面向需求的Haskell程序》续