Python 虚拟机字典dict内存优化方法解析
作者:一无是处的研究僧 发布时间:2022-03-04 08:20:56
引言
在前面的文章当中我们讨论的是 python3 当中早期的内嵌数据结构字典的实现,在本篇文章当中主要介绍在后续对于字典的内存优化。
字典优化
在前面的文章当中我们介绍的字典的数据结构主要如下所示:
typedef struct {
PyObject_HEAD
Py_ssize_t ma_used;
PyDictKeysObject *ma_keys;
PyObject **ma_values;
} PyDictObject;
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
Py_ssize_t dk_size;
dict_lookup_func dk_lookup;
Py_ssize_t dk_usable;
PyDictKeyEntry dk_entries[1];
};
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
用图示的方式表示如下图所示:
所有的键值对都存储在 dk_entries 数组当中,比如对于 "Hello" "World" 这个键值对存储过程如下所示,如果 "Hello" 的哈希值等于 8 ,那么计算出来对象在 dk_entries 数组当中的下标位 0 。
在前面的文章当中我们谈到了,在 cpython 当中 dk_entries 数组当中的一个对象占用 24 字节的内存空间,在 cpython 当中的负载因子是 23\frac{2}{3}32 。而一个 entry 的大小是 24 个字节,如果 dk_entries 的长度是 1024 的话,那么大概有 1024 / 3 * 24 = 8K 的内存空间是浪费的。为了解决这个问题,在新版的 cpython 当中采取了一个策略用于减少内存的使用。具体的设计如下图所示:
在新的字典当中 cpython 对于 dk_entries 来说如果正常的哈希表的长度为 8 的话,因为负载因子是 23\frac{2}{3}32 真正给 dk_entries 分配的长度是 5 = 8 / 3,那么现在有一个问题就是如何根据不同的哈希值进行对象的存储。dk_indices 就是这个作用的,他的长度和真正的哈希表的长度是一样的,dk_indices 是一个整型数组这个数组保存的是要保存对象在 dk_entries 当中的下标,比如在上面的例子当中 dk_indices[7] = 0,就表示哈希值求余数之后的值等于 7,0 表示对象在 dk_entries 当中的下标。
现在我们再插入一个数据 "World" "Hello" 键值对,假设 "World" 的哈希值等于 8,那么对哈希值求余数之后等于 0 ,那么 dk_indices[0] 就是保存对象在 dk_entries 数组当中的下标的,图中对应的下标为 1 (因为 dk_entries 数组当中的每个数据都要使用,因此直接递增即可,下一个对象来的话就保存在 dk_entries 数组的第 3 个(下标为 2)位置)。
内存分析
首先我们先来分析一下数组 dk_indices 的数据类型,在 cpython 的内部实现当中并没有一刀切的直接将这个数组当中的数据类型设置成 int 类型。
dk_indices 数组主要有以下几个类型:
当哈希表长度小于 0xff 时,dk_indices 的数据类型为 int8_t ,即一个元素值占一个字节。
当哈希表长度小于 0xffff 时,dk_indices 的数据类型为 int16_t ,即一个元素值占 2 一个字节。
当哈希表长度小于 0xffffffff 时,dk_indices 的数据类型为 int32_t ,即一个元素值占 4 个字节。
当哈希表长度大于 0xffffffff 时,dk_indices 的数据类型为 int64_t ,即一个元素值占 8 个字节。
与这个相关的代码如下所示:
/* lookup indices. returns DKIX_EMPTY, DKIX_DUMMY, or ix >=0 */
static inline Py_ssize_t
dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i)
{
Py_ssize_t s = DK_SIZE(keys);
Py_ssize_t ix;
if (s <= 0xff) {
const int8_t *indices = (const int8_t*)(keys->dk_indices);
ix = indices[i];
}
else if (s <= 0xffff) {
const int16_t *indices = (const int16_t*)(keys->dk_indices);
ix = indices[i];
}
#if SIZEOF_VOID_P > 4
else if (s > 0xffffffff) {
const int64_t *indices = (const int64_t*)(keys->dk_indices);
ix = indices[i];
}
#endif
else {
const int32_t *indices = (const int32_t*)(keys->dk_indices);
ix = indices[i];
}
assert(ix >= DKIX_DUMMY);
return ix;
}
现在来分析一下相关的内存使用情况:
哈希表长度 | 能够保存的键值对数目 | 老版本 | 新版本 | 节约内存量(字节) |
---|---|---|---|---|
256 | 256 * 2 / 3 = 170 | 24 * 256 = 6144 | 1 * 256 + 24 * 170 = 4336 | 1808 |
65536 | 65536 * 2 / 3 = 43690 | 24 * 65536 = 1572864 | 2 * 65536 + 24 * 43690 = 1179632 | 393232 |
从上面的表格我们可以看到哈希表的长度越大我们节约的内存就越大,优化的效果就越明显。
来源:https://juejin.cn/post/7214489453399343160
猜你喜欢
- [asp] 献一函数:ASP获取ACCESS数据库的表名以及表名对应的字段名和字段类型<%showtable "../dat
- 一个简单的for语句就能循环字典的所有键,就像处理序列一样:In [1]: d = {'x':1, 'y':
- 1.sort()方法sort()是列表的方法,修改原列表使得它按照大小排序,没有返回值,返回NoneIn [90]: x = [4, 6,
- python 如何实现Excel 的Vlookup功能1、Excel 中VLOOKUP具体步骤Excel 中的VLOOKUP使用说明采用下面
- 通常来说,一个Python程序可以从键盘读取输入,也可以从文件读取输入;而程序的结果可以输出到屏幕上,也可以保存到文件中便于以后使用。本文就
- 代码如下:<% function GetBot() '查询蜘蛛 dim s_
- 一、设计目的1、教学目的本课程设计是学生学习完《Python程序设计》课程后,进行的一次全面的综合训练,通过课程设计,更好地掌握使用Pyth
- 导语:排版是一门艺术,也是一门技巧。我们每天都能在报纸,书籍等各种媒介上看到排版,或精美,或丑陋。如何能在准确传递信息的同时,又能排出精美的
- 在正文前,先简短介绍自己。我任职于广州的某个网站服务公司的系统开发员,主要任务是以.Net编写各种web系统,例如CMS.EIP。大家都知道
- 一、概述spark 有三大引擎,spark core、sparkSQL、sparkStreaming,spark core 的关键抽象是 S
- 这个分页使用的是0游标,也就是Rs.Open Sql,Conn,0,1。但是感觉也快不了多少,10万条数据的分页时间300多豪秒之间。风格A
- 用ASP代码实现对access数据库的在线压缩处理,注意压缩前请备份数据库。我们知道每个一段时间压缩一下access数据库,可以减少数据库的
- 做过主页的朋友,几乎没有一个人没用到它,它使我们排版更加轻松。有人说DW的表格没有Fp的好用,我认为不
- 即text-overflow:ellipsis,需要配合white-space:nowrap使用。运行代码:<div style=&q
- 什么是错误页面?是指链接指向的网页现在失效了,原因可能是用户输错了地址,也可能是网站结构调整,内容删除,或者地址变更都有可能出现这种情况。那
- <html><head><title>不刷新页面查询的方法</title><meta
- 当很多人发现在DW4中定义CSS很方便的时候,开始报怨FP2000不能定义CSS,甚至就此抨击FP2000如何的不好。事实上,在FP2000
- 主要利用了XMLHTTP的一些方法和属性来获取服务器的信息。 以下是全部源代码: &
- [Hack] 意为”劈”、”砍”。 [Hacker] 意为”黑客”CSS Hack 是指针对不同的浏览器写不同的CSS code的过程,简单
- 这篇文章主要介绍了Python hashlib加密模块常用方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价