阅读视图

发现新文章，点击刷新页面。

Go 源码阅读：内存分配前的溢出判断

忘归

Jalan.江佳扬

2021年7月11日 19:01

今天在看切片内存分配的源码，makeslice 函数在内存分配前先使用 MaxUintptr 函数来判断内存分配是否越界：

func makeslice(et *_type, len, cap int) unsafe.Pointer {
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
if overflow || mem > maxAlloc || len < 0 || len > cap {
// 先判断是否越界
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}

    // 内存分配
return mallocgc(mem, et, true)
}

出于好奇看了一下 MaxUintptr 的源码：

// Copyright 2018 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package math

import "runtime/internal/sys"

const MaxUintptr = ^uintptr(0)

// MulUintptr returns a * b and whether the multiplication overflowed.
// On supported platforms this is an intrinsic lowered by the compiler.
func MulUintptr(a, b uintptr) (uintptr, bool) {
if a|b < 1<<(4*sys.PtrSize) || a == 0 {
return a * b, false
}
overflow := b > MaxUintptr/a
return a * b, overflow
}

由源码可知，MulUintptr 接收两个参数，分别是要分配的类型大小 a 和要分配的数量 b，计算后返回要分配的内存空间以及是否溢出。

位运算表达式的含义

a|b < 1<<(4*sys.PtrSize) 这个位运算表达式看起来非常复杂，我们来剖析一下。

sys.PtrSize 表示系统指针大小，在 32 位机器中，sys.PtrSize = 4，64 位机器中，sys.PtrSize = 8。<< 是左移运算符，我们知道在运算中左移 1 位就是一次乘 2 操作，因此 1<<(4*sys.PtrSize) 表示的其实就是 2^(4*sys.PtrSize)。

综上，我们可以把表达式变形一下：

在 32 位机器中，4*sys.PtrSize = 4 * 4 = 16 表达式可以写作 a|b < 2^16，可证明 a 与 b 均小于 2^16，a * b 必然小于 2^32
在 64 位机器中，4*sys.PtrSize = 4 * 8 = 32 表达式可以写作 a|b < 2^32，可证明 a 与 b 均小于 2^32，a * b 必然小于 2^64

那么 2^32 与 2^64 又代表着什么呢？

何为溢出？

我们常说的 64 位系统或 32 位系统，其中的「位数」决定了计算机的寻址空间，即 CPU 对于内存的寻址能力。通俗地讲，就是 CPU 最多能够使用的内存。32 位系统的寻址空间为 2^32，64 位系统的寻址空间为 2^64。

因此，a|b < 1<<(4*sys.PtrSize) 的含义是：要分配的内存是否小于寻址空间。若小于寻址空间，即不存在溢出，此时函数返回 overflow = false。

`^uintptr(0)` 是什么？

unintptr 是 Go 中的自定义整型：

#ifdef _64BIT
typedef    uint64        uintptr;
#else
typedef    uint32        uintptr;
#endif

32 位系统中，unitptr 代表 uint32，占 4 字节，^uintptr(0) 等于 ^uint32(0)，即 2^32 - 1
64 位系统中，unitptr 代表 uint64，占 8 字节，^uintptr(0) 等于 ^uint64(0)，即 2^64 - 1

因此，overflow := b > MaxUintptr/a 可以变形为：

在 32 位机器中：overflow := b > (2^32 - 1)/a
在 64 位机器中：overflow := b > (2^64 - 1)/a

这样就很好理解啦。

代码逻辑思考

如果由我来写这段代码，我无法想到这样的写法，大概率会使用 a * b < MaxUintptr 来暴力解决问题。然而计算机中乘法与除法并不意味着更快的计算过程，他们的本质还是使用累加器，而位运算才意味着高效。因此，先使用 a|b < 1<<(4*sys.PtrSize) 作为判断是非常巧妙的做法。

存在的疑问

if a|b < 1<<(4*sys.PtrSize) || a == 0 {
return a * b, false
}

我对以上这句逻辑判断存在疑问，根据短路求值，把 a == 0 写在前面是否更好呢？以及是否需要把 b == 0 也补上？准备提个 issue 问问开发者吧。

参考资料

MySQL 覆盖索引与延迟关联

忘归

Jalan.江佳扬

2020年9月1日 20:35

在了解覆盖索引与延迟关联前，我们先简单建立一个订单表 Orders 用于举例说明。表中共包含 3 个字段：

id：订单 ID，int 类型，主键自增长
product_id：商品 ID，在此列上建立索引
name：订单名称

CREATE TABLE `orders` (
  `id` int(10) NOT NULL COMMENT '订单 ID',
  `product_id` int(10) DEFAULT NULL COMMENT '商品 ID',
  `name` varchar(255) CHARACTER SET utf8 COLLATE utf8_unicode_ci DEFAULT NULL COMMENT '订单名称',
  PRIMARY KEY (`id`),
  KEY `product_idx` (`product_id`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

覆盖索引

什么是覆盖索引？

我们知道，如果 MySQL 根据索引查找到数据，但索引的叶子结点中并不包含我们所需要的数据字段，那么仍然需要进行回表查询。

如果一个索引包含（覆盖）我们所需要查询的所有字段值，我们就称之为「覆盖索引」。

MyISAM

当使用 MyISAM 存储引擎时，由于我们在 product_id 建立了索引，所以 SELECT product_id FROM orders 将使用覆盖索引：

mysql> EXPLAIN SELECT product_id FROM orders;
+----+-------------+--------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+
| id | select_type | table  | partitions | type  | possible_keys | key         | key_len | ref  | rows | filtered | Extra       |
+----+-------------+--------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | orders | NULL       | index | NULL          | product_idx | 5       | NULL |    2 |   100.00 | Using index |
+----+-------------+--------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+
1 row in set (0.00 sec)

如果我们在查询字段中加入 id 列，即执行 SELECT id, product_id FROM orders WHERE product_id = 1，查询轨迹如下：

在 product_id 索引树中找到 product_id = 1 子结点
通过该子结点指针读取磁盘上的数据行
取出数据行中的 id 字段

由于 MyISAM 的叶子结点存储着指向数据行的指针，该查询多了一步回表操作，无法使用覆盖索引。

mysql> EXPLAIN SELECT id, product_id FROM orders WHERE product_id = 1;
+----+-------------+--------+------------+------+---------------+-------------+---------+-------+------+----------+-------+
| id | select_type | table  | partitions | type | possible_keys | key         | key_len | ref   | rows | filtered | Extra |
+----+-------------+--------+------------+------+---------------+-------------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | orders | NULL       | ref  | product_idx   | product_idx | 5       | const |    1 |   100.00 | NULL  |
+----+-------------+--------+------------+------+---------------+-------------+---------+-------+------+----------+-------+
1 row in set (0.00 sec)

MyISAM 索引结构

InnoDB

InnoDB 与 MyISAM 的不同之处在于，InnoDB 的主键使用聚簇索引，而其二级索引的叶子结点保存着行的主键值。也就是说，二级索引不仅能覆盖其本身，也能覆盖到该行的主键值。

InnoDB 二级索引的叶子结点包含行主键值

由于 InnoDB 不同的数据存储方式，若使用 InnoDB 作为存储引擎，我们执行 SELECT id, product_id FROM orders WHERE product_id = 1 将得到如下结果：

mysql> EXPLAIN SELECT id, product_id FROM orders WHERE product_id = 1;
+----+-------------+--------+------------+------+---------------+-------------+---------+-------+------+----------+-------------+
| id | select_type | table  | partitions | type | possible_keys | key         | key_len | ref   | rows | filtered | Extra       |
+----+-------------+--------+------------+------+---------------+-------------+---------+-------+------+----------+-------------+
|  1 | SIMPLE      | orders | NULL       | ref  | product_idx   | product_idx | 5       | const |    1 |   100.00 | Using index |
+----+-------------+--------+------------+------+---------------+-------------+---------+-------+------+----------+-------------+
1 row in set (0.01 sec)

可以看到 Extra 显示 Using index，表示该查询使用了覆盖索引。该查询语句的查询轨迹如下：

在二级索引 product_id 的索引树中找到 product_id = 1 的叶子结点
取出该叶子结点的行主键值 id 一并返回

查询轨迹并未进行回表取值。

覆盖索引的好处

延迟关联

延迟关联（deferred join）指「延迟了对列的访问」，不直接获取所有需要的列。

在查询的第一阶段 MySQL 使用覆盖索引，再通过该覆盖索引查询到的结果到外层查询匹配锁需要的所有列值。

这样说有些抽象，我们来看看下面的例子。

用延迟关联优化分页（LIMIT）

当使用 LIMIT 碰上较大偏移量时，例如 LIMIT 10000, 20 这样的查询，MySQL 需要查询 10020 条记录然后再返回最后的 20 条。前面的 10000 最终都会被抛弃，这样的代价非常高。

mysql> EXPLAIN SELECT * FROM orders LIMIT 10000, 20;
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------+
| id | select_type | table  | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------+
|  1 | SIMPLE      | orders | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    2 |   100.00 | NULL  |
+----+-------------+--------+------------+------+---------------+------+---------+------+------+----------+-------+

优化此类分页查询的一个最简单的办法就是尽可能使用索引覆盖扫描，而不是查询所有列。然后根据需要再做一次关联，返回所需要的列。

mysql> EXPLAIN SELECT * FROM orders AS o1 JOIN (SELECT id FROM orders LIMIT 10000, 20) AS o2 ON o1.id = o2.id;
+----+-------------+------------+------------+-------+---------------+-------------+---------+------------+------+----------+-------------+
| id | select_type | table      | partitions | type  | possible_keys | key         | key_len | ref        | rows | filtered | Extra       |
+----+-------------+------------+------------+-------+---------------+-------------+---------+------------+------+----------+-------------+
|  1 | PRIMARY     | o1         | NULL       | ALL   | PRIMARY       | NULL        | NULL    | NULL       |    2 |   100.00 | NULL        |
|  1 | PRIMARY     | <derived2> | NULL       | ref   | <auto_key0>   | <auto_key0> | 4       | test.o1.id |    2 |   100.00 | Using index |
|  2 | DERIVED     | orders     | NULL       | index | NULL          | PRIMARY     | 4       | NULL       |    2 |   100.00 | Using index |
+----+-------------+------------+------------+-------+---------------+-------------+---------+------------+------+----------+-------------+

这样一来，MySQL 在 SQL 语句的「内层」进行扫描时使用了覆盖索引，「外层」再通过索引树找到相关的数据行，直接减少了扫描的数据量。

参考资料

《高性能 MySQL》

聊聊 Go 语言中的字符表示与字符串遍历

忘归

Jalan.江佳扬

2019年11月16日 23:57

和其他语言不同，在 Go 语言中没有字符类型，字符只是整数的特殊用例。

为什么说字符只是整数的特殊用例呢？因为在 Go 中，用于表示字符的 byte 和 rune 类型都是整型的别名。在 Go 的源码中我们可以看到：

// byte is an alias for uint8 and is equivalent to uint8 in all ways. It is
// used, by convention, to distinguish byte values from 8-bit unsigned
// integer values.
type byte = uint8

// rune is an alias for int32 and is equivalent to int32 in all ways. It is
// used, by convention, to distinguish character values from integer values.
type rune = int32

byte 是 uint8 的别名，长度为 1 个字节，用于表示 ASCII 字符
rune 是 int32 的别名，长度为 4 个字节，用于表示以 UTF-8 编码的 Unicode 码点

Tips：Unicode 从 0 开始，为每个符号指定一个编号，这叫做「码点」（code point）。

字符的表示

那么，如何在 Go 语言中表示字符呢？

在 Go 语言中使用单引号包围来表示字符，例如 'j'。

byte

如果要表示 byte 类型的字符，可以使用 byte 关键字来指明字符变量的类型：

var byteC byte = 'j'

又因为 byte 实质上是整型 uint8，所以可以直接转成整型值。在格式化说明符中我们使用 %c 表示字符，%d 表示整型：

// 声明 byte 类型字符
var byteC byte = 'j'
fmt.Printf("字符 %c 对应的整型为 %d\n", byteC, byteC)
// Output: 字符 j 对应的整型为 106

rune

与 byte 相同，想要声明 rune 类型的字符可以使用 rune 关键字指明：

var runeC rune = 'J'

但如果在声明一个字符变量时没有指明类型，Go 会默认它是 rune 类型：

runeC := 'J'
fmt.Printf("字符 %c 的类型为 %T\n", runeC, runeC)
// Output: 字符 J 的类型为 int32

为什么需要两种类型？

看到这里你可能会问了，既然都用于表示字符，为什么还需要两种类型呢？

我们知道，byte 占用一个字节，因此它可以用于表示 ASCII 字符。而 UTF-8 是一种变长的编码方法，字符长度从 1 个字节到 4 个字节不等。byte 显然不擅长这样的表示，就算你想要使用多个 byte 进行表示，你也无从知晓你要处理的 UTF-8 字符究竟占了几个字节。

因此，如果你在中文字符串上狂妄地进行截取，一定会输出乱码：

testString := "你好，世界"
fmt.Println(testString[:2]) // 输出乱码，因为截取了前两个字节
fmt.Println(testString[:3]) // 输出「你」，一个中文字符由三个字节表示

此时就需要 rune 的帮助了。利用 []rune() 将字符串转为 Unicode 码点再进行截取，这样就无需考虑字符串中含有 UTF-8 字符的情况了：

testString := "你好，世界"
fmt.Println(string([]rune(testString)[:2])) // 输出：「你好」

Tips：Unicode 和 ASCII 一样，是一种字符集，UTF-8 则是一种编码方式。

遍历字符串

字符串遍历有两种方式，一种是下标遍历，一种是使用 range。

下标遍历

由于在 Go 语言中，字符串以 UTF-8 编码方式存储，使用 len() 函数获取字符串长度时，获取到的是该 UTF-8 编码字符串的字节长度，通过下标索引字符串将会产生一个字节。因此，如果字符串中含有 UTF-8 编码字符，就会出现乱码：

testString := "Hello，世界"

for i := 0; i < len(testString); i++ {
c := testString[i]
fmt.Printf("%c 的类型是 %s\n", c, reflect.TypeOf(c))
}

/* Output:
H 的类型是 uint8（ASCII 字符返回正常）
e 的类型是 uint8
l 的类型是 uint8
l 的类型是 uint8
o 的类型是 uint8
ï 的类型是 uint8（从这里开始出现了奇怪的乱码）
¼ 的类型是 uint8
 的类型是 uint8
ä 的类型是 uint8
¸ 的类型是 uint8
 的类型是 uint8
ç 的类型是 uint8
 的类型是 uint8
 的类型是 uint8
*/

range

range 遍历则会得到 rune 类型的字符：

testString := "Hello，世界"

for _, c := range testString {
fmt.Printf("%c 的类型是 %s\n", c, reflect.TypeOf(c))
}

/* Output:
H 的类型是 int32
e 的类型是 int32
l 的类型是 int32
l 的类型是 int32
o 的类型是 int32
， 的类型是 int32
世 的类型是 int32
界 的类型是 int32
*/

总结

Go 语言中没有字符的概念，一个字符就是一堆字节，它可能是单个字节（ASCII 字符集），也有可能是多个字节（Unicode 字符集）
byte 是 uint8 的别名，长度为 1 个字节，用于表示 ASCII 字符
rune 则是 int32 的别名，长度为 4 个字节，用于表示以 UTF-8 编码的 Unicode 码点
字符串的截取是以字节为单位的
使用下标索引字符串会产生字节
想要遍历 rune 类型的字符则使用 range 方法进行遍历

阅读视图

位运算表达式的含义

何为溢出？

^uintptr(0) 是什么？

代码逻辑思考

存在的疑问

参考资料

覆盖索引

什么是覆盖索引？

MyISAM

InnoDB

覆盖索引的好处

延迟关联

用延迟关联优化分页（LIMIT）

参考资料

字符的表示

byte

rune

为什么需要两种类型？

遍历字符串

下标遍历

range

总结

参考资料

`^uintptr(0)` 是什么？