关于后端:PHP7内核实现原理数组的实现

27次阅读

共计 7235 个字符，预计需要花费 19 分钟才能阅读完成。

PHP 的数组是基于 HashTable 实现的，并且在其上减少了程序拜访的个性。这里分 PHP 5 和 PHP 7 两个版本看数组的演进。

PHP 5.6.31 源码：https://github.com/php/php-src/blob/php-5.6.31/Zend/zend_hash.h#L67

PHP 7.2.1 源码：https://github.com/php/php-src/blob/php-7.2.1/Zend/zend_types.h#L234

PHP 数组特点

PHP 中的数组有两个最突出的特点，也即 PHP 数组满足两个语义：

  • PHP 数组是一个字典，反对 key value 拜访，key 反对整型或字符串。
  • PHP 数组是有序的，即遍历数组时会依照增加程序遍历，不像传统意义上的字典是无序的。

传统 HashTable

一个传统的 HashTable 大抵构造如下：

首先一个 key 通过哈希函数计算，得出属于哪个 slot。key 值和 value 值应用 bucket 构造体保留，放在对应的 slot 下。如果不同 key 通过哈希计算后失去雷同 slot 值，即产生哈希抵触时，应用链表法接在 slot 的 bucket 链前面。这里提一句有的语言解决哈希抵触会应用红黑树。

PHP 中的 HashTable

PHP 中的 HashTable 在此基础上做了一些调整，减少了一个哈希函数，以及这个新增哈希函数对应的哈希值 h：

其中 key 通过 hash1 函数失去 h 值，h 值是一个无符号整型（ulong），之后 h 值再通过 hash2 函数计算失去 slot，调配时与之前一样。另外 bucket 中也减少了对 h 值的保留。

为什么的要减少这个 h 值，作用是什么？

  • PHP 要反对数字和字符串两种 key，当应用字符串 key 时，h 值就是其对应的数字值。而 应用数字 key 时，h 间接就等于这个 key 值。相当于将数字和字符串两种 key 归一为数字类型，对立放到 h 字段中。
  • 在比拟两个字符串 key 的 value 是否相等时，能够先通过判断对应的 h 值是否相等，且绝大部分状况下，字符串哈希抵触的概率也比拟小，所以如果不相等间接返回，放慢判断的速度。

PHP 5 的数组实现

先看源码：

https://github.com/php/php-src/blob/php-5.6.31/Zend/zend_hash.h#L67

PHP 5 的 bucket：

bucket 代码：

struct _hashtable;

typedef struct bucket {
    ulong h; /* Used for numeric indexing */
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey;
} Bucket;

bucket 图示：

各字段含意：

  • h：就是后面提到的 h 值
  • arKey：是以后 bucket 的 key 值
  • pListLast、pListNext、pLast、pNext：四个指针
  • nKeyLength：是 arKey 的长度，当这个值为 0 时，示意以后 key 是数字类型。
  • pDataPtr 和 pData：指向具体的 value。这里有个优化，如果 value 的大小等于一个指针，则将 value 间接存储在 pDataPtr 上，缩小内存占用

bucket 中为什么有 4 个指针？

因为要满足数组有序的语义，PHP 5 应用 pListNext 和 pListLast 别离示意 全局链表 上的下一个节点和上一个节点。在前面 HashTable 的实现中别离也有两个指针，指向全局链表的头部和尾部，实现正序和倒序拜访。

而 pNext 和 pLast 别离示意产生哈希抵触时的 部分链表。

PHP 5 的 HashTable 的构造：

HashTable 源码：

typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;    /* Used for element traversal */
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;
  • arBuckets：是一个指针，指向一段间断的数组内存，数组中每个元素指向一个 slot。通过这个指针就能够找到所有 slot 及 slot 下的 bucket。即 slot 的数组。
  • nTableSize：是 arBuckets 所指向的数组的大小，即 slot 的数量。取值始终是 2 的 n 次方。最小值 8，最大 2 的 31 次方。这个值的意义在于，当 bucket 的数量大于这个值时，示意曾经呈现了哈希抵触，当抵触重大时 PHP 会发动 rehash，从新平衡 slot 的散布。
  • nTableMask：掩码。始终等于 nTableSize – 1，所以他的每一位都是 1。HashTable 要通过两层 hash 函数，第二个 hash 函数就是 slot = h & nTableMask 以此来计算出 slot。相当于 取余操作。这里在 PHP 7 中会发生变化。
  • nNumOfElements：bucket 元素的个数。
  • pListHead 和 pListTail：为实现 HashTable 有序而保护的双向链表。这两个指针别离指向第一个 bucket 和最初一个 bucket。
  • pInternalPointer：指向 以后元素的指针，foreach 遍历时就是应用这个指针遍历的，这也是为什么 PHP 5 中 foreach 遍历数组比用索引遍历快的起因。

bucket 和 HashTable 联动图示：

按程序插入四个 key a、b、c、d，假如 a 被映射到了 slot1，而 b、c、d 被映射到了 slot0 中：

其中 HashTable 上的 pListHead 作为全局链表头指向了第一个 bucket a，pListTail 作为全局链表尾指向最初一个 bucket d。通过 pListHead 和 pListTail 就可实现数组的正序和倒序遍历。

可见 PHP 的数组有序指的是插入的程序，例如鸟哥的博客也讲到这一点，提了一个问题：

https://www.laruence.com/2009/08/23/1065.html

$arr['laruence'] = 'huixinchen';
$arr['yahoo']    = 2007;
$arr['baidu']    = 2008;
foreach ($arr as $key => $val) {// 后果是什么?}

$arr[2] = 'huixinchen';
$arr[1]  = 2007;
$arr[0]  = 2008;
foreach ($arr as $key => $val) {// 当初后果又是什么?}

答案是一样的，即插入的程序。

PHP 5 数组的有余

整体来说，有两处能够优化：

  • 应用的字段是比拟多的，而且每个 bucket 都要有四个指针，占用空间大。
  • 其次 bucket 的调配地位是随机的，不间断的，导致无奈利用到 CPU 的局部性原理，无奈利用 cache。

PHP 7 的数组实现

PHP 7 次要针对下面提到的两个不足之处做了改良。首先精简了字段，且不再应用指针保护节点间的程序，改为了间断内存。这样既缩小了空间占用，又应用程序读写利用了 CPU 的局部性原理，进步了数据读取速度。

PHP 7 数组的源码：https://github.com/php/php-src/blob/php-7.2.1/Zend/zend_types.h#L234

bucket 构造：

typedef struct _Bucket {
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

首先因为不再应用指针保护程序，bucket 的构造精简了很多。

  • val：指向具体的变量，zval 构造体
  • h：跟以前一样的 h 值，无符号数字类型
  • key：字符串 key，不再应用 char *，而是间接用了 zend_string 构造体

之后 bucket 引入了状态的概念，分为：未应用、无效、有效。无效和有效 bucket 始终排列在未应用 bucket 后面：

状态机：

HashTable 构造：

typedef struct _zend_array HashTable;

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

图示：

各字段含意：

  • gc：援用计数
  • arData：一块间断的内存空间，寄存 bucket 数组。
  • nTableSize：arData 指向的 bucket 数组的大小，即所有 bucket 的数量。该字段取值始终是 2 的 n 次方，最小值是 8
  • nNumUsed：指所有 已应用 bucket 的数量，包含无效 bucket 和有效 bucket。
  • nNumOfElements：无效 bucket 的数量。该值总是小于或等于 nNumUsed。

  • nTableSize、nNumUsed、nNumOfElements 三者的关系：

  • nTableMask：掩码。个别为 -nTableSize。
  • nInternalPointer：游标指针，因为当初 bucket 都是间断存储的，所以不再应用指针而改用无符号整数存储索引值即可。
  • nNextFreeElement：下一个天然索引值，默认是 0。即如果应用 $arr[] = 1 的形式插入元素，相当于插入到索引 0 的地位。

基于以上前提，如何实现 key 对应到 slot 再到 bucket 链表呢？

这里就谈到为什么 nTableMask 是负值的起因了。实际上在调配 bucket 数组内存的时候，即 arData，在这个数组最后面额定多申请了一些内存，这段内存的作用是充当索引，也叫索引表或 arHash。索引表外面的每个元素代表一个 slot，其值为其下第一个 bucket 在 arData 中的下标。如果以后 slot 没有任何 bucket 元素，那么其值为 -1。到此就实现了 key 到 slot 再到 bucket 的映射。

从而 PHP 7 中的第二个哈希函数，即应用 h 值获得 slot 值，变成了：slot = h | nTableMask。

如，当 nTableSize=8，则 nTableMask=-8，二进制即：11111111111111111111111111111000。那么任何数与之做或运算，只能是 000 – 111 这 8 种值，即 -1 到 -8，这 8 个 slot 在别离存一个具体的 bucket 索引值。就实现了 key → h → slot → bucket 的查找了。

对于 -8 的二进制示意，须要回顾下计算机组成原理二进制示意：

正数 = 其正值的补码 -8 正值就是 8

8 的原码示意为 00001000

8 的反码示意为 11110111，即按位取反

8 的补码示意为 11111000，即反码 + 1

这样一来扩大到 32 位时就可知 -8 的二进制为 11111111111111111111111111111000

参考：https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/compute…

PHP 7 数组几种初始化过程：

packed array 和 hash array

留神后面提到 nTableMask = – nTableSize，但这个不相对，当数组是 packed array 类型时其实是用不到索引表的，所以个别初始化数组时，在未确定数组类型时，nTableSize 个别只调配 2 个。

初始化数组时，数组的内存调配状态：

什么是 packed array 和 hash array

$a = array(1,2,3); // packed array
$b = array('a' => 1, 'b' => 2, 'c' => 3); // hash array

当 HashTable 的 u.v.flags 的 HASH_FLAG_PACKED 位 > 0 时示意 packed array，否则是 hash array。

packed array 具备以下束缚和个性。

  • key 全是数字类型的。
  • key 按插入顺序排列，依然是递增的。
  • 每一个 key-value 对的存储地位都是确定的，都存储在 bucket 数组的第 key 个元素上。
  • packed array 不须要索引数组。

packed array 不须要索引表，间接用 key 作为 arData 的索引，节俭了后面一段索引表的空间。

packed array 示意图：

hash array 示意图：

如：

其中最初一个非凡，也是数字 key，也是递增，为什么不是 packed array？因为用 1 和 8 做索引，数组太过于稠密，利用率不高，在工夫效率和空间效率的均衡下，应用了 hash array。

来自鸟哥博客的一段代码，这段代码展现了从 packed array 切换到 hash array 的内存占用状况：

echo "Packed array:\n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory:", memory_get_usage() - $begin, "bytes\n";
$begin = memory_get_usage();

// 这里新增一个元素
$array[10001] = 1;
// 内存简直无变动
echo "Memory Increased:", memory_get_usage() - $begin, "bytes\n";
 
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {$array[$i];
}
echo "Time:", (microtime(true) - $start) * 1000 , "ms\n";
 
unset($array);
 
echo "\nMixed array:\n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory:", memory_get_usage() - $begin, "bytes\n";
$begin = memory_get_usage();

// 这里插入一个字符串 key，使数组变成了 hash array
$array["foo"] = 1;
// 内存占用变动显著
echo "Memory Increased:", memory_get_usage() - $begin, "bytes\n";
 
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {$array[$i];
}
echo "Time:", (microtime(true) - $start) * 1000 ,"ms\n";

打印后果：

Packed array:
Memory: 528440 bytes
Memory Increased: 0 bytes
Time: 0.19598007202148 ms

Mixed array:
Memory: 528440 bytes
Memory Increased: 126976 bytes
Time: 0.18215179443359 ms

鸟哥代码地址：https://www.laruence.com/2020/02/25/3182.html

packed array 转换成 hash array

从 packed array 到 hash array 转换须要调用 zend_hash_packed_to_hash 函数。首先将 u.flags 中设置标记位 HASH_FLAG_PACKED，之后新生成一个 arData，再调用 memcpy 拷贝过来，最初开释掉老的 arData。

PHP 7 数组的 CRUD

根本步骤：

  • 先查找 key 存不存在
  • 插入时分为字符串 key 插入，数字 key 插入，nextIndex 插入

如何解决哈希抵触

发生冲突时，把新的元素放在 nextFreeIndex 处，而后新 zval 的 next 指针指向老元素在 arData 中的索引，之后在 arHash 索引表中，指向新元素的地位。即索引表永远指向新元素，新元素的 next 再指向老元素，串起来。

扩容 resize 和重建索引 rehash

扩容 resize 看书：zend_hash_do_resize

重建索引 rehash 函数：zend_hash_rehash，因为扩容导致数组容量变动，须要重新分配索引

在插入元素时判断是否要 resize 和 rehash，根本步骤是：

  • 判断数组空间是否够用

  • 不够用时，看是不是有效 bucket 太多

    • 太多就真删除一波，之后 rehash
    • 不是很多，阐明真的没中央了，那就先扩容 resize，再真删除，再 rehash

比拟 PHP 5 和 PHP 7 的数组实现：

  • 精简了 bucket 的字段
  • 应用 bucket.zval.u2.next 取代旧的部分抵触链表
  • 将 bucket 存储在间断的 arData 数组中，勾销了全局链表。并且因为内存间断，利用局部性原理，进步读取性能。
  • packed array 节俭了索引表 arHash 的空间。

本文由 mdnice 多平台公布

正文完
后端
发表至： 后端
2023-09-09
 0
关于后端:什么情况下使用-ArrayList-或者-LinkedList
关于后端:801-使序列递增的最小交换次数-状态机-DP-运用题
关于后端:个人珍藏的80道多线程并发面试题1120答案解析
关于后端:SpringBoot-配置文件这样加密才足够安全