ConcurrentHashMap源码解析
ConcurrentMap接口说明
1 | public interface ConcurrentMap<K, V> extends Map<K, V> { |
select， poll， epoll， 信号驱动 IO细讲
63章 其他备选的 IO 模型
整体概览
实际上 I/O 多路复用，信号驱动 I/O 以及 epool 都是用来实现同一个目标的技术——同时检查多个文件描述符，看它们是否准备好了执行 I/O 操作（准确地说，是看 I/O 系统调用是否可以非阻塞地执行）。文件描述符就绪状态的转化是通过一些 I/O 事件来触发的，比如输入数据到达，套接字连接建立完成，或者是之前满载的套接字发送缓冲区在 TCP 将队列中的数据传送到对端之后由了剩余空间。同时检查多个文件描述符在类似网络服务器的应用中很有用处，或者是那么必须同事检查终端以及管道或套接字输入的应用程序。
需要注意的是这些技术都不会执行实际的 I/O 操作。它们只是告诉我们某个文件描述符已经处于就绪状态了，这时需要调用其他的系统调用来完成实际的 I/O 操作。
HashMap源码解析
1 |
|
yield与yield from备忘录
对于 yield与yield from的语法，官方给出的解释Link
分析一波 Java 线程池
Executors.executeCase
1 | public class FixedThreadPool { |
Python整型对象创建
整数类型
Python3 中无论整数还是长整数统统使用 PyLongObject 类型来代替
1 | typedef struct _longobject PyLongObject; /* Revealed in longintrepr.h */ |
由于Py_TRACE_REFS在release状态下是不会定义的，所以整个数据结构就会特别简单:
1 | typedef struct _object { |
小数优化
1 |
|
创建函数
1 | PyLongObject * |
其中 PyObject_MALLOC是与 WITH_PYMALLOC定义相关
Pymalloc, a specialized object allocator written by Vladimir Marangozov, was a feature added to Python 2.1. Pymalloc is intended to be faster than the system malloc() and to have less memory overhead for allocation patterns typical of Python programs. The allocator uses C’s malloc() function to get large pools of memory and then fulfills smaller memory requests from these pools.
In 2.1 and 2.2, pymalloc was an experimental feature and wasn’t enabled by default; you had to explicitly enable it when compiling Python by providing the –with-pymalloc option to the configure script. In 2.3, pymalloc has had further enhancements and is now enabled by default; you’ll have to supply**–without-pymalloc** to disable it.
可以看出这东西是默认开启的，所以从代码可知调用的是_PyObject_Malloc方法，再追踪源码发现其最终调用的是如下方法：
1 | void * |
1 | /* Allocate a new arena. If we run out of memory, return NULL. Else |
具体可以参考以上注释，以上。
参考资料
https://docs.python.org/2.3/whatsnew/section-pymalloc.html
《Python 源码解析》
Python内存管理机制——内存模型
Python 中所有的内存管理机制都有两套实现，这两套实现由编译符号PYMALLOC_DEBUG 控制，当该符号被定义时，使用的是 debug 模式下的内存管理机制，这套机制在正常的内存管理动作之外，还会记录许多关于内存的信息，以方便 Python 在开发时进行调试；而当该符号未被定义时，Python 的内存管理机制只进行正常的内存管理动作。
1 | // /include/Python.h |
内存管理架构
在 Python 中，内存管理机制被抽象成下图这样的层次似结果。
Layer 0：
操作系统提供的内存管理接口，比如 C 运行时所提供的 malloc 和 free 接口。这层由操作系统实现并管理，Python 不能干涉这一层的行为。
Layer 1：
Python 基于第 0 层操作系统的内存管理接口包装而成的，这一层并没有在第 0 层加入太多的冻灾，其目的仅仅是为 Python 提供一层同意的 raw memory 的管理接口。防止操作系统的差异。第一次实现就是一组以PyMem_为前缀的函数族。
1 | // Include/pymem.h |
在第一层中，Python 还提供了面向 Python 中类型的内存分配器
1 | // Include/pymem.h |
在 PyMem_New 中，只要提供类型和数量，Python 会自动侦测其所需的内存空间大小。
Layer 2：
以 PyObje_为前缀的函数族，主要提供了创建 Python 对象的接口。这一套函数族又被唤作 Pymalloc 机制。
在第二层内存管理机制之上，对于 Python 中的一些常用对象，比如整数对象、字符串对象等，Python 又构建了更高抽象层次的内存管理策略。
真正在 Python 中发挥巨大作用、同时也是 GC 的藏身之处的内存管理机制所在层次。
Layer 3:
第三层的内存管理策略，主要就是对象缓冲池机制。（参加书中第一部分，或者下篇博客）。
小块空间的内存池
在 Python 中，许多时候申请的内存都是小块的内存，这些小块内存在申请后，很快又会被释放，由于这些内存的申请并不是为了创建对象，所以并没有对象一级的内存池机制。这就意味着 Python 在运行期间会大量地执行 malloc 和 free 操作，导致操作系统频繁地在用户态和核心态之间进行切换，这将严重影响 Python 的执行效率。为了提高 Python 的执行效率，Python 引入了一个内存池机制，用于管理对小块内存的申请和释放。这也就是之前提到的 Pymalloc 机制。
在 Python 中，整个小块内存池可以视为一个层次结构，在这个层次结构中，一共分为4层，从下至上分别是：block、pool、arena 和内存池。需要说明的是，block、pool 和 arena 都是 Python 代码中可以找到的实体，而最顶层的『内存池』只是一个概念上的东西，表示 Python 对于整个小块内存分配和释放行为的内存管理机制。
Block
在最底层，block 是一个确定大小的内存块。在 Python 中，有多种 block，不同种类的 block 都有不同的内存大小，这个内存大小的值被称为 size class。为了在当前主流的平台都能获得最佳性能，所有的 block 的长度都是8字节对齐的。
1 | // Object/obmalloc.c |
block 上限，当申请的内存大小小于这个上限时，Python 可以使用不同种类的 block 来满足对内存的需求；当神奇的内存大小超过这个上限，Python 就会对内存的请求转交给第一层的内存管理机制，即 PyMem 函数族，来处理。
1 | // Object/obmalloc.c |
现在，需要指出一个相当关键的点，虽然我们这里谈论了很多block，但是在Python中，block只是一个概念，在Python源码中没有与之对应的实体存在。之前我们说对象，对象在Python源码中有对应的PyObject；我们说列表，列表在Python源码中对应PyListObject、PyType_List。这里的block就很奇怪了，它仅仅是概念上的东西，我们知道它是具有一定大小的内存，但它不与Python源码里的某个东西对应。然而，Python却提供了一个管理block的东西，这就是下面要剖析的pool。
Pool
一组 block 的集合称为一个 pool，换句话说，一个 pool 管理着一堆有固定大小的内存块。事实上，pool 管理着一大块内存，它由一定的策略，将这块大的内存划分为多个小的内存块。在 Python 中，一个 pool 的大小通常为一个系统内存页，由于当前大多数 Python 支持的系统的内存页都是4KB，所以 Python 内部也将一个 pool 的大小定义为4KB。
1 | // Object/obmalloc.c |
1 | // Object/obmalloc.c |
4KB 中除去 pool_header，还有一大块内存就是 pool 中维护的 block 的集合占用的内存。
前面提到block 是有固定大小的内存块，因此，pool 也携带了大量这样的信息。一个 pool 管理的所有 block，它们的大小都是一样的。也就是说，一个 pool 可能管理了100个32个字节的 block，也可能管理了100个64个字节的 block，但是绝不会有一个管理了50个32字节的 block 和50个64字节的 block 的 pool 存在。每一个 pool 都和一个 size 联系在一起，更确切地说，都和一个 size class index 联系在一起。这就是 pool_header 中的 szindex 的意义。
假设我们手上现在有一块 4KB 的内存，来看看 Python 是如何将这块内存改造为一个管理32字节 block 的 pool，并从 pool 中取出第一块 block 的。
1 | // [obmalloc.c]-[convert 4k raw memory to pool] |
注意其中的实线箭头是指针，但是虚线箭头不是代表指针，是偏移位置的形象表示。在nextoffset和maxnextoffset中存储的是相对于poo头部的偏移位置。
1 | // [obmalloc.c]-[allocate block] |
原来freeblock指向的是下一个可用的block的起始地址，这一点在上图中也可以看得出。当再次申请32字节的block时，只需返回freeblock指向的地址就可以了，很显然，这时freeblock需要向前进，指向下一个可用的block。这时，nextoffset现身了。
在pool header中，nextoffset和maxoffset是两个用于对pool中的block集合进行迭代的变量：从初始化pool的结果及图16-2中可以看到，它所指示的偏移位置正好指向了freeblock之后的下一个可用的block的地址。从这里分配block的动作也可以看到，在分配了block之后，freeblock和nextoffset都会向前移动一个block的距离，如此反复，就可对所有的block进行一次遍历。而maxnextoffset指名了该pool中最后一个可用的block距pool开始位置的便移，它界定了pool的边界，当nextoffset > maxnextoff 时，也就意味着已经遍历完了pool中所有的block了。
可以想像，一旦Python运转起来，内存的释放动作将会导致pool中出现大量的离散的自由block，Python必须建立一种机制，将这些离散的自由block组织起来，再次使用。这个机制就是所谓的自由block链表。这个链表的关键就着落在pool_header中的那个freeblock身上。
1 | // [obmalloc.c] |
arena
在 Python 中，多个 pool 聚合的结果就是一个 arena。
1 | // Object/obmalloc.c |
『未使用』的 arena 和『可用』的 arena
实际上，在Python中，确实会存在多个arena_object构成的集合，但是这个集合并不构成链表，而是构成了一个arena的数组。数组的首地址由arenas维护，这个数组就是Python中的通用小块内存的内存池；另一方面，nextarea和prevarea也确实是用来连接arena_object组成链表的。
pool_header管理的内存与pool_header自身是一块连续的内存，而areana_object与其管理的内存则是分离的。这后面隐藏着这样一个事实：当pool_header被申请时，它所管理的block集合的内存一定也被申请了；但是当aerna_object被申请时，它所管理的pool集合的内存则没有被申请。换句话说，arena_object和pool集合在某一时刻需要建立联系。注意，这个建立联系的时刻是一个关键的时刻，Python从这个时刻一刀切下，将一个arena_object切分为两种状态。
当一个arena的area_object没有与pool集合建立联系时，这时的arena处于“未使用”状态；一旦建立了联系，这时arena就转换到了“可用”状态。对于每一种状态，都有一个arena的链表。“未使用”的arena的链表表头是unused_arena_objects、arena与arena之间通过nextarena连接，是一个单向链表；而“可用”的arena的链表表头是usable_arenas、arena与arena之间通过nextarena和prevarena连接，是一个双向链表。
申请 arena
1 | // [obmalloc.c] |
内存池
可用 pool 缓冲池——usedpools
Python 内部默认的小块内存与大块内存的分界点定在512个字节，这个分界点由前面我们看到的名为SMALL_REQUEST_THRESHOLD 的符号控制。也就是说，当申请的内存小于512字节时，PyObject_Malloc 会在内存池中申请内存；当申请的内存大于512字节时，PyObject_Malloc 的行为将退化为 malloc 的行为。
在Python中，pool是一个有size概念的内存管理抽象体，一个pool中的block总是有确定的大小，这个pool总是和某个size class index对应，还记得pool_head中的那个szidx么？而arena是没有size概念的内存管理抽象体，这就意味着，同一个arena，在某个时刻，其内的pool集合可能都是管理的32字节的block；而到了另一时刻，由于系统需要，这个arena可能被重新划分，其中的pool集合可能改为管理64字节的block了，甚至pool集合中一半管理32字节，一半管理64字节。这就决定了在进行内存分配和销毁时，所有的动作都是在pool上完成的。
内存池中的pool，不仅是一个有size概念的内存管理抽象体，而且，更进一步的，它还是一个有状态的内存管理抽象体。一个pool在Python运行的任何一个时刻，总是处于以下三种状态的一种：
- used状态：pool中至少有一个block已经被使用，并且至少有一个block还未被使用。这种状态的pool受控于Python内部维护的usedpools数组；
- full状态：pool中所有的block都已经被使用，这种状态的pool在arena中，但不在arena的freepools链表中；
- empty状态：pool中所有的block都未被使用，处于这个状态的pool的集合通过其pool_header中的nextpool构成一个链表，这个链表的表头就是arena_object中的freepools；
Python内部维护的usedpools数组是一个非常巧妙的实现，维护着所有的处于used状态的pool。当申请内存时，Python就会通过usedpools寻找到一块可用的（处于used状态的）pool，从中分配一个block。一定有一个与usedpools相关联的机制，完成从申请的内存的大小到size class index之间的转换，否则Python也就无法寻找到最合适的pool了。这种机制与usedpools的结构有密切的关系，我们来看一看usedpools的结构。
一定有一个与usedpools相关联的机制，完成从申请的内存的大小到size class index之间的转换，否则Python也就无法寻找到最合适的pool了。这种机制与usedpools的结构有密切的关系，我们来看一看usedpools的结构。
1 | // [obmalloc.c] |
其中的NB_SMALL_SIZE_CLASSES指明了在当前的配置之下，一共有多少个size class。
1 | // [obmalloc.c] |
Python会首先获得 size class index，通过 size = (uint )(nbytes - 1) >> ALIGNMENT_SHIFT，得到 size class index 为3。在usedpools 中，寻找第3+3=6个元素，发现 usedpools[6] 的值是指向 usedpools[4] 的地址。有些迷惑了，对吧？好了，现在对照 pool_header 的定义来看一看 usedpools[6] -> nextpool 这个指针指向哪里了呢？是从 usedpools[6]（即usedpools+4）开始向后偏移8个字节（一个ref的大小加上一个freeblock的大小）后的内存，不正是 usedpools[6] 的地址（即usedpools+6）吗？这是Python内部使用的一个 trick。
想象一下，当我们手中有一个size class为32字节的pool，想要将其放入这个usedpools中时，需要怎么做呢？从上面的描述可以看到，只需要进行usedpools[i+i]->nextpool = pool即可，其中i为size class index，对应于32字节，这个i为3。当下次需要访问size class为32字节（size class index为3）的pool时，只需要简单地访问usedpool[3+3]就可以得到了。Python正是使用这个usedpools快速地从众多的pool中快速地寻找到一个最适合当前内存需求的pool，从中分配一块block。
1 | // [obmalloc.c] |
Pool 的初始化
当 Python 启动之后，在 usedpools 这个小块空间内存池中，并不存在任何可用的内存，准确地说，不存在任何可用的pool。在这里，Python 采用了延迟分配的策略，即当我们确实开始申请小块内存时，Python 才开始建立这个内存池。
考虑一下这样的情况，当申请32字节内存时，从“可用的” arena 中取出其中一个 pool 用作32字节的 pool 。当下一次内存分配请求分配64字节的内存时，Python 可以直接使用当前“可用的” arena 的另一个 pool 即可。这正如我们前面所说， arena 没有 size class 的属性，而 pool 才有（见下面代码）。
1 | // [obmalloc.c] |
初始化之一
好了，现在我们手里有了一块用于32字节内存分配的pool，为了以后提高内存分配的效率，我们需要将这个pool放入到usedpools中。这一步，叫做init pool。
1 | // [obmalloc.c] |
在什么样的情况下才会发生一个 pool 从 empty 状态转换为 used 状态呢？假设申请的内存的 size class index 为 i，且 usedpools[i+i] 处没有处于 used 状态的 pool ，同时在 Python 维护的全局变量 freepools 中还有处于 empty 的 pool ，那么位于 freepools 所维护的 pool 链表头部的 pool 将被取出来，放入 usedpools 中，并从其内部分配一块 block 。同时，这个 pool 也就从 empty 状态转换到了 used 状态。下面我们看一看这个行为在代码中是如何体现的。
1 | // [obmalloc.c] |
初始化之二
我们现在可以来看看，当PyObject_Malloc从new_arena中得到一个新的arena后，是怎么样来初始化其中的pool集合，并最终完成PyObject_Malloc函数的分配一个block这个终极任务的。
1 | // [obmalloc.c] |
block 的释放
pool 的状态变更最为常见的还是之前是 used 之后也是 used：
在pool的状态保持used状态这种情况下，Python仅仅将block重新放入到自由block链表中，并调整了pool中的ref.count这个引用计数。
1 | // [obmalloc.c] |
当我们释放一个 block 后，可能会引起 pool 的状态的转变，这种转变可分为两种情况：
full状态转变为used状态
仅仅是将 pool 重新链回到 usedpools 中即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26[obmalloc.c]
void PyObject_Free(void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
pool = POOL_ADDR(p);
if (Py_ADDRESS_IN_RANGE(p, pool)) {
……
//当前pool处于full状态，在释放一块block后，需将其转换为used状态，并重新
//链入usedpools的头部
--pool->ref.count;
size = pool->szidx;
next = usedpools[size + size];
prev = next->prevpool;
/* insert pool before next: prev <-> pool <-> next */
pool->nextpool = next;
pool->prevpool = prev;
next->prevpool = pool;
prev->nextpool = pool;
return;
}
……
}used状态转变为empty状态
首先 Python 要做的是将empty状态的 pool 链入到 freepools 中去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30// [obmalloc.c]
void PyObject_Free(void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
pool = POOL_ADDR(p);
if (Py_ADDRESS_IN_RANGE(p, pool)) {
*(block **)p = lastfree = pool->freeblock;
pool->freeblock = (block *)p;
if (lastfree) {
struct arena_object* ao;
uint nf; //ao->nfreepools
if (--pool->ref.count != 0) {
return;
}
// 将pool放入freepools维护的链表中
// 这里隐藏着一个类似于内存泄露的问题：arena 从来不释放 pool
ao = &arenas[pool->arenaindex];
pool->nextpool = ao->freepools;
ao->freepools = pool;
nf = ++ao->nfreepools;
……
}
……
}
……
}现在开始处理 arena，分为四种情况：
如果arena中所有的pool都是empty的，释放pool集合占用的内存。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40// [obmalloc.c]
void PyObject_Free(void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
pool = POOL_ADDR(p);
struct arena_object* ao;
uint nf; //ao->nfreepools
……
//将pool放入freepools维护的链表中
ao = &arenas[pool->arenaindex];
pool->nextpool = ao->freepools;
ao->freepools = pool;
nf = ++ao->nfreepools;
if (nf == ao->ntotalpools) {
//调整usable_arenas链表
if (ao->prevarena == NULL) {
usable_arenas = ao->nextarena;
}
else {
ao->prevarena->nextarena = ao->nextarena;
}
if (ao->nextarena != NULL) {
ao->nextarena->prevarena = ao->prevarena;
}
//调整unused_arena_objects链表
ao->nextarena = unused_arena_objects;
unused_arena_objects = ao;
//释放内存
free((void *)ao->address);
//设置address，将arena的状态转为“未使用”
ao->address = 0;
--narenas_currently_allocated;
}
……
}如果之前arena中没有了empty的pool，那么在usable_arenas链表中就找不到该arena，由于现在arena中有了一个pool，所以需要将这个aerna链入到usable_arenas链表的表头。
若arena中的empty的pool个数为n，则从usable_arenas开始寻找arena可以插入的位置，将arena插入到usable_arenas。这个操作的原因是由于usable_arenas实际上是一个有序的链表，从表头开始往后，每一个arena中的empty的pool的个数，即nfreepools，都不能大于前面的arena，也不能小于前面的arena。保持这种有序性的原因是分配block时，是从usable_arenas的表头开始寻找可用的arena的，这样，就能保证如果一个arena的empty pool数量越多，它被使用的机会就越少。因此，它最终释放其维护的pool集合的内存的机会就越大，这样就能保证多余的内存会被归还给系统。
其他情况，不进行任何对arena的处理。
内存池全景
参考资料
《Python 源码解析》
Redis与消息队列
背景知识
Pub/Sub
Redis中使用SUBSCRIBE, UNSUBSCRIBE 和 PUBLISH 方法将可以实现生产者/消费者模式，所谓的生产者其实就是使用PUBLISH将message(这里需要说明，message只能是String，不过我们可以序列化一个对象为Json再进行推送)推送到指定的队列中，再由SUBSCRIBE监听到消息并取出。UNSUBSCRIBE是取消监听。