Yuerer's Blog

钰儿的Blog


  • 首页

  • 标签

  • 分类

  • 归档

  • 关于

Python3-源码剖析(三)-GC垃圾回收

发表于 2022-05-01 | 更新于 2022-05-02 | 分类于 Python3 | 评论数: | 阅读次数:

趁着五一难得有自己的时间,就来剖析一下 CPython 的自动垃圾回收机制,并尝试提出改进的思路。

引用计数

相信有过计算机基础的人,哪怕对垃圾回收不那么熟悉,也肯定知道引用计数这个玩意。引用计数诞生于上个世纪,其主要思想是通过给每个对象增加计数,当计数为0时,则肯定没人使用该对象,可以放心将其删除。

虽然这个方法看起来有点糙,但在实际项目中,它的优点在于可以更实时的释放内存,释放内存的时机更精确,这也是为什么有的项目会尝试给 Lua 增添一个引用计数的垃圾回收,避免内存上涨过快。

凡事都有利弊,它的缺点也很明显,无法处理循环引用。

以下用 Python 举一个非常普遍的例子。

1
2
3
4
5
6
7
8
9
10
11
12
class A:  
pass

class B:
pass

a = A()
b = B()
a.b = b
b.a = a
del a
del b

在上面中,我们手动删除了 a 和 b ,理应进行释放,但由于 a 和 b 互相构成了循环引用,导致其引用计数总是不为0,进而造成内存泄漏,而 CPython 对其解决方法也极其简单,就是将所有可能造成循环引用的对象,构成一个双向链表进行扫描,从 root object 出发进行扫描 - 清除,无法到达的对象就是可释放的对象,普通的对象直接采用引用计数去释放,简单快捷。

怎么去验证以上结论呢?我们可以用反证法,当 del a 和 del b 后,再调用 gc.collect() 查看其是否能被回收到,如果能回收到,说明在此时引用计数已经失效。

1
2
3
4
5
6
7
8
# 设置 debug 标签,使得垃圾回收后的对象 存放至 gc.garbage 列表中
gc.set_debug(gc.DEBUG_SAVEALL)

# 回收第0代垃圾对象
gc.collect(0)

# 打印出回收的垃圾对象
print(gc.garbage)

可以看出引用计数确实失效了,因为通过 扫描-清除 回收能回收到这两个对象。

阅读全文 »

Python3-源码剖析(二)-指令特化

发表于 2022-04-09 | 更新于 2022-04-17 | 分类于 Python3 | 评论数: | 阅读次数:

在上一篇关于 Python3 源码剖析中,剖析 float 的实现主要是阅读的 Python 3.10 的源码,但是在我看到 PEP-659 这篇关于指令特化(Specializing Adaptive Interpreter)的提案时,我就被它吸引了,因为这就是我之前想给 Lua 提速加的功能之一,冲着对它的热情,我决定将阅读的 CPython 版本提升到 3.11 ,这一篇就来剖析一下指令特化的实现,我们将通过两个对象做加法进行分析。

对象相加

首先通过 Python 自带的 dis 工具进行分析,分析两个对象相加的流程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from dis import *
def test():
a = 1.5
c = a + 1.3
print(dis(test))

3 0 RESUME 0

4 2 LOAD_CONST 1 (1.5)
4 STORE_FAST 0 (a)

5 6 LOAD_FAST 0 (a)
8 LOAD_CONST 2 (1.3)
10 BINARY_OP 5 (*)
14 POP_TOP
16 LOAD_CONST 0 (None)
18 RETURN_VALUE

可以看到两个对象相乘的指令码为 BINARY_OP ,我们跟踪到 CPython 中,可以确定会调用到 PyNumber_Add 函数中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static const binaryfunc binary_ops[] = {
[NB_ADD] = PyNumber_Add,
[NB_AND] = PyNumber_And,
.....
};
TARGET(BINARY_OP) {
PREDICTED(BINARY_OP);
PyObject *rhs = POP();
PyObject *lhs = TOP();
PyObject *res = binary_ops[oparg](lhs, rhs);
Py_DECREF(lhs);
Py_DECREF(rhs);
SET_TOP(res);
if (res == NULL) {
goto error;
}
JUMPBY(INLINE_CACHE_ENTRIES_BINARY_OP);
DISPATCH();
}

PyNumber_Add 实现也很简单,先看看这两个对象支不支持该二元运算符,不支持,则看看支不支持 concat 操作。

阅读全文 »

Python3 源码剖析(一)-float诞生

发表于 2022-04-05 | 更新于 2022-04-17 | 分类于 Python3 | 评论数: | 阅读次数:

去年 2021 年的时候,我的工作主要集中在改进 Lua虚拟机 ,后来由于工作变动,现在主要的工作语言已经切换为了 Python ,因此打算阅读下 Python 3.10 的源码,学习一下它的设计,对比 Lua 的优势。

希望在接下来的阅读过程中,能够体会到一种 回家 的畅快感。

本篇将以 float 作为起点,了解如何创建出一个浮点对象,深入剖析 float 其内部实现。

一切皆对象

一切皆对象 这句话都要被讲烂了,但是还要讲多一次。

Python 是一门面向对象的强类型动态语言,里面的任何东西都是对象,以浮点数为例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# a 是一个浮点实例对象,类型是 float
>>> a = 3.14159
>>> type(a)
<class 'float'>

# float 也是个对象,但它是 类型对象
>>> float
<class 'float'>
>>> float()
0.0

# float这个类型对象的类型是 type
>>> type(float)
<class 'type'>

以上我们可以确定,Python 中类型也是对象。

此外所有对象的类型都是 type ,可以称其为元类。而所有对象都继承自 object 。

阅读全文 »

LuaJIT 5.3.6 方案

发表于 2021-07-04 | 更新于 2022-04-04 | 分类于 Lua | 评论数: | 阅读次数:

截止至上一次发博文已经过了接近三个月时间,这么长的一段时间我主要是去做了以下几件事情,一个是实现 Lua 多线程的垃圾回收 方案,另一个则是 LuaJIT 5.3.6 实现。其实也没用到三个月,实现代码加上测试一共花了一个月,至于剩下的两个月,主要是响应号召,去打了一下疫苗,腹泻,发烧,休息😓。

Lua 多线程垃圾回收

这一块的思路主要是从 Redis 通过子线程释放内存这块学来的,通过这个小优化,使得我们游戏服务器在大量玩家下线时,不再出现大规模的掉帧,效果还是非常显著的。

LuaJIT 5.3.6

之所以实现这个 Lua 5.3.6 JIT,其实是因为 LuaJIT 2.0 不支持 5.3的新扩展,而项目已经进行到了中后期,没有时间去调整代码了,最后花了半个月的时间去实现了一个小版本,通过了 Lua 的官方测试用例,也在项目用上了。性能方面提高了2-5倍,接入成本为0,不需要修改任何逻辑代码。

至于解释器部分,借鉴了 Lua 5.4 的一个小优化点,将 switch case 修改为了 computed goto ,提升了约 5% 的性能,之后可能会学习 Lua 5.4 扩展字节码。如果这个项目还做下去的话(我有时间的话),我会想尝试解释器执行脚本时记录各个操作数的类型,实现动态替换字节码,减少不必要的类型判断,从而提升一定的解释器速度。不过这个方案风险太大,暂时先搁置。

在实现 LuaJIT 5.3.6 的过程中,顺带复习了一下编译原理的前端部分,实现了一些官方不支持的语法,比如 ‘+=’,自增表达式(当然没有提交),还是非常有趣的。

结语

以上的代码实现已经开源,合并之前的 NOGC 优化思路,LuaJIT-5.3.6,欢迎 Star ,这对我很重要。

阅读全文 »

Redis 6 剖析(二) 主从同步

发表于 2021-04-03 | 分类于 Redis | 评论数: | 阅读次数:

本篇是 Redis 6 剖析的第二篇,主要探讨 Redis 是怎么做主从同步的,对代码会有所删减。

SLAVE

通常启用主从同步,只要在从服务器执行 SLAVEOF HOST PORT 即可,这个时候就会执行到 replicaofCommand 。由于主从同步是从服务器发起的,因此我们先从 Slave 开始进行剖析。

Redis6-Replication

阅读全文 »

Redis 6 剖析(一) 异步机制

发表于 2021-03-26 | 更新于 2021-07-04 | 分类于 Redis | 评论数: | 阅读次数:

一直觉得关系型数据库非常难用,在使用之前要先定好表的结构,中途修改存储结构,改动就会非常繁杂,特别是 外键 这玩意离开了学校就再也没见过。好在在 游戏领域 中,用的最多的都是 NoSQL 。

熟悉我风格的人,可以看出这个系列的标题,不再是 源码剖析,而是只有 剖析 两字,主要是考虑到 Redis 6.0 的代码量已经挺大了,同时网络中又有大量关于 Redis 数据结构的源码剖析,没必要再炒冷饭了。

出于以上的原因,我将 Redis 分为几个部分进行剖析和讨论。

  1. 异步机制
  2. 主从同步
  3. 集群
  4. 数据结构

本篇主要是来剖析 Redis 为了避免 阻塞 ,是如何运用 多进程 与 多线程,这两种异步机制的。

阻塞点

Redis 一般有以下几种阻塞的点。

从网络交互来看有

  • 网络 I/O (多线程)
  • 客户端交互 (部分删除用多线程 BIO)
  • 传输 RDB 快照 (多进程)

从磁盘交互又分

  • 关闭文件 (多线程 BIO)
  • 记录 AOF 日志 (多线程 BIO)
  • AOF 日志重写 (多进程)
  • RDB 快照生成 (多进程)
阅读全文 »

Raft 共识算法解析

发表于 2021-03-14 | 分类于 分布式 | 评论数: | 阅读次数:

前篇解析了 Gossip 协议,这篇主要看看 Raft 是如何实现的。

本文主要分为两个部分,首先是粗略讲解一遍 Raft 的设计思想,在这一部分不会将 RPC 的各种字段(因为没有意义,只会徒增心智负担),而在第二部分则是通过解析一份优质的 Raft 源码实现,在这个部分再深入到 RPC 各个字段。

如果看了一遍看不懂也没关系,建议多去看看 Raft 的论文,笔者也是反复看了两周才大致理解其指导思想。

Raft

一提到共识算法,相信大部分人都能马上想到 Paxos,但是我认为它不是算法,它的论文里面顶多算是一个指导思想,很少有人能够读完它就实现出一个可靠的共识算法(关键是要验证其的正确性),但是 Raft 不一样,它的一些设计非常巧妙,能够令人非常好的理解其指导思想,同时比较容易的实现(因为 Raft 从诞生那一刻就是为了弥补 Paxos 的可理解性,看看人家的论文名字 In Search of an Understandable Consensus Algorithm 可理解的分布式共识算法)。

用过 Zookeeper 的可能知道其内部的协议就是根据 Paxos 的指导实现的一个 Zab 算法,之所以不用 Raft 是因为 Raft 那时候还没出世呢。

阅读全文 »

Gossip 协议解析

发表于 2021-03-09 | 更新于 2021-03-14 | 分类于 分布式 | 评论数: | 阅读次数:

一直都对分布式协议比较感兴趣,选择了 Gossip 和 Raft 作为起点,之所以这么选择有两个原因。

  1. 它们足够简单。
  2. 一个基于 AP ,一个基于 CP ,分别是可用性优先和一致性优先的代表。

Gossip

Gossip 协议主要通过谣言传播的形式,传播给其他节点。

我这里称 Gossip 为 协议 而不是算法是因为这只是个思想,基于这个思想有很多的变种。

Gossip 能够正常运作需要以下三种实现组合。

  1. 广播
  2. 反熵(Anti-entropy)
  3. 谣言传播
阅读全文 »

ptmalloc2 内存管理

发表于 2021-02-28 | 分类于 内存分配 | 评论数: | 阅读次数:

近期在压测服务器的过程中发现内存随着用户数增加而暴涨,用户数减少内存却没有释放回内核,一开始怀疑是内存泄漏,后面上了工具排查,最终定位到是 glibc 的内存管理并没有将内存释放给OS,为了解决这个问题,对 ptmalloc2 进行了剖析。

本篇中,不谈论 brk 和 mmap 系统调用的使用方法,默认环境为 Linux-x86-64,讨论的 ptmalloc2 的版本为 glibc 2.17 的版本。

chunk

ptmalloc2 分配给用户的内存都以 chunk 来表示,可以理解为 chunk 为分配释放内存的载体。

chunk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size */
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))

struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
// -----------------------------------------------------------------------
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};

chunk 由以上几部分组成, INTERNAL_SIZE_T 为 size_t 为了屏蔽平台之间的差异,这里只谈论64位平台,为8字节。

  1. prev_size 代表着上一个 chunk 的大小,是否有效取决于 size 的属性位 P。
  2. size 代表当前 chunk 的大小和属性,其中低3位为属性位 [A|M|P]。
  3. 当这个 chunk 为空闲时,则会使用 fd, bk 将其加入链表中管理。
  4. 同上, fd_nextsize bk_nextsize 只用在 large bin 中,表示 上/下一个大小的指针,加快链表遍历。
阅读全文 »

Lua GC垃圾回收优化方案

发表于 2020-12-19 | 更新于 2022-02-27 | 分类于 Lua | 评论数: | 阅读次数:

最近接手的一个游戏项目是重 Lua 的结构(网络模块在 C++,其余逻辑全在 Lua)。和许多用 Lua 的游戏项目一样,遇到了 Lua 的垃圾回收的性能问题,经常跑着跑着就会掉帧,因此花了一周的时间,给 Lua 虚拟机写了个模块,把 Lua 垃圾回收的速度提高了一个量级。

思路

这个思路其实在之前的一篇博客中也有提到,想要 垃圾回收快,无非就那么几种思路。

  1. 使用内存池
  2. 减少对象生成
  3. 垃圾回收提速

使用内存池

第一种思路,我觉得不合理,因为现代的内存分配器早就有内存池的设计了,手写一个内存池的收益并不大。

减少对象生成

第二种思路,是比较合理的。因为我在项目的代码中发现很多处地方有动态生成 Closure 的情况。

1
2
3
4
5
6
7
function test()
local fn = function()
print("test")
end
fn()
fn()
end

上面那个例子,每次调用到 test 函数的时候,都会动态根据 fn 的 函数原型,生成一个 Closure

可能有人会问,Proto 不是有一个 cache 指向 Closure 吗?按道理这里 没有 UpValue(即代表UpValue 完全相同),应该会复用啊,但是很可惜,执行完这个函数以后,因为没有对象指向 Closure 用完再不久的将来又会被回收。

因此,少写这种代码就可以减少对象的生成。

垃圾回收提速

第三种思路,我的想法是,让垃圾回收所要遍历的对象大幅减少,就可以为垃圾回收提速了,由于我们是重 Lua 的框架,因此我们的所有配置都存在于 Lua 的 table中,而这一部分肯定是不需要被回收的,但是每次垃圾回收的时候,又会不停的扫描递归遍历,不合理。同时代码中的很多全局函数,也是根本不需要被回收的,也会被扫描到,于是就想到一个想法,给这些对象打上标记,让他们不被遍历不被清理,就可以大幅度的提速了。

原理简单,但是做起来确实挺难受的,要注意要手动关闭 UpValue 将其保留下来。

目前已经开源,LuaJIT-5.3.6源码。

阅读全文 »
12…6>
Yuerer

Yuerer

钰儿的Blog

53 日志
14 分类
73 标签
RSS
GitHub E-Mail
© 2018 – 2022 Yuerer