PHP开源Hub
致力于开发者的提升

深入理解PHP7内核之HashTable

本文转自鸟哥博客  https://www.laruence.com/2020/02/25/3182.html

之前的俩篇文章深入理解PHP7内核之zval 深入理解PHP7内核之Reference, 我介绍了我们在开发PHP7的时候对zval和reference的一些改造思考和结果, 之后因为确实精力有限就没有继续往下写,时隔一年多以后,因为这场突如其来的疫情,在家办公的时间很多, 于是终于有了时间让我来继续介绍一下PHP7的中Hashtable的变化, 以及当时我们做这些变化背后的考量.

PHP5的Hashtable

对于PHP内核一直有关注的同学, 应该对PHP5的Hashtable会比较熟悉, 但我们还是先来简单回顾一下PHP5的Hashtable:

在PHP5的实现中, Hashtable的核心是存储了一个个指向zval指针的指针, 也就是zval**(我遇到不少的同学问为什么是zval**, 而不是zval*, 这个原因其实很简单, 因为Hashtable中的多个位置都可能指向同一个zval, 那么最常见的一个可能就是在COW的时候, 当我们需要把一个变量指向一个新的zval的时候, 如果在符号表中存的是zval*, 那们我们就做不到对一处修改, 所有的持有方都有感知, 所以必须是zval**), 这样的设计在最初的出发点是为了让Hashtable可以存储任何尺寸的任何信息, 不仅仅是指针, 还可以存储一段内存值(当然实际上大部分情况下,比如符号表还是存的zval的指针).
PHP5的代码中也用了比较Hack的方式来判断存储的是什么:

  1. #define UPDATE_DATA(ht, p, pData, nDataSize)
  2.     if (nDataSize == sizeof(void*)) {
  3.         if ((p)->pData != &(p)->pDataPtr) {
  4.             pefree_rel((p)->pData, (ht)->persistent);
  5.         }
  6.         memcpy(&(p)->pDataPtr, pData, sizeof(void *));
  7.         (p)->pData = &(p)->pDataPtr;
  8.     } else {
  9.         if ((p)->pData == &(p)->pDataPtr) {
  10.             (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
  11.             (p)->pDataPtr=NULL;
  12.         } else {
  13.             (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \
  14.             /* (p)->pDataPtr is already NULL so no need to initialize it */ \
  15.         }
  16.         memcpy((p)->pData, pData, nDataSize);
  17.     }

它来判断存储的size是不是一个指针大小, 从而采用不同的方式来更新存储的内容。非常Hack的方式。

PHP5的Hashtable对于每一个Bucket都是分开申请释放的。

而存储在Hashtable中的数据是也会通过pListNext指针串成一个list,可以直接遍历,关于这块可以参看我很早的一篇文章深入理解PHP之数组

问题

在写PHP7的时候,我们详细思考了几点可能优化的点,包括也从性能角度总结了以下目前这种实现的几个问题:

1. Hashtable在PHP中,应用最多的是保存各种zval, 而PHP5的HashTable设计的太通用,可以设计为专门为了存储zval而优化, 从而能减少内存占用。

2. 缓存局部性问题, 因为PHP5的Hashtable的Bucket,包括zval都是独立分配的,并且采用了List来串Hashtable中的所有元素,会导致在遍历或者顺序访问一个数组的时候,缓存不友好。

比如如图所示在PHP代码中常见的foreach一个数组, 就会发生多次的内存跳跃.

3. 和1类似,在PHP5的Hashtable中,要访问一个zval,因为是zval**, 那需要至少解指针俩次,一方面是缓存不友好,另外一方面也是效率低下。
比如上图中,蓝色框的部分,我们找到数组中的bucket以后,还需要解开zval**,才可以读取到实际的zval的内容。 也就是需要发生俩次内存读取。效率低下。

当然还有很多的其他的问题,此处不再赘述,说实在的毕竟俩年多了,当时怎么想的,现在有些也想不起来了, 现在我们来看看PHP7的

PHP7

首先在PHP7中,我们当时的考虑是可能因为担心Hashtable用的太多,我们新设计的结构体可能不一定能Cover所有的场景,于是我们新定义了一个结构体叫做zend_array, 当然最后经过一系列的努力,发现zend_array可以完全替代Hashtable, 最后还是保留了Hashtable和zend_array俩个名字,只不过互为Alias.
再下面的文章中,我会用HashTable来特指PHP5中的Hashtable,而用zend_array来指代PHP7中的Hashtable.

我们先来看看zend_array的定义:

  1. struct _zend_array {
  2.     zend_refcounted_h gc;
  3.     union {
  4.         struct {
  5.             ZEND_ENDIAN_LOHI_4(
  6.                 zend_uchar flags,
  7.                 zend_uchar _unused,
  8.                 zend_uchar nIteratorsCount,
  9.                 zend_uchar _unused2)
  10.         } v;
  11.         uint32_t flags;
  12.     } u;
  13.     uint32_t nTableMask;
  14.     Bucket *arData;
  15.     uint32_t nNumUsed;
  16.     uint32_t nNumOfElements;
  17.     uint32_t nTableSize;
  18.     uint32_t nInternalPointer;
  19.     zend_long nNextFreeElement;
  20.     dtor_func_t pDestructor;
  21. };

相比PHP5时代的Hashtable,zend_array的内存占用从PHP5点72个字节,降低到了56个字节,想想一个PHP生命进程中成千上万的数组,内存降低明显。

此处特别说明下ZEND_ENDIAN_LOHT_4这个作用,这个是为了解决大小端问题,在大端小端上都能让其中的元素保证同样的内存存储顺序,可以方便我们写出通用的位操作。 在PHP7种,位操作应用的很多,因为这样一来一个字节就可以保存8个状态位, 很节省内存:)

而数据会核心保存在arData中,arData是一个Bucket数组,Bucket定义:

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

再对比看下PHP5多Bucket:

  1. typedef struct bucket {
  2.     ulong h; /* Used for numeric indexing */
  3.     uint nKeyLength;
  4.     void *pData;
  5.     void *pDataPtr;
  6.     struct bucket *pListNext;
  7.     struct bucket *pListLast;
  8.     struct bucket *pNext;
  9.     struct bucket *pLast;
  10.     const char *arKey;
  11. } Bucket;

内存占用从72字节,降低到了32个字节,想想一个PHP进程中几十万的数组元素,这个内存降低就更明显了.

对比的看,相比HashTable的拉链法,zend_array采用了double Hash来解决Hash冲突,于是bucket->pNext, bucket->pLast可以去掉了。

现在zend_array->arData是一个数组,所以也就不再需要pListNext, pListLast来保持顺序了, 他们也可以去掉了。

最明显的就是PHP7中的Bucket现在直接保存一个zval, 取代了PHP5时代bucket中的pData和pDataPtr。

最后就是PHP7中现在使用zend_string作为数组的字符串key,取代了PHP5时代bucket的*key, nKeylength.

现在我们来整体看下zend_array的组织图:

回顾下深入理解PHP7内核之ZVAL, 现在的zend_array就可以应付各种场景下的HashTable的作用了。
特别说明对是除了一个问题就是之前提到过的IS_INDIRECT, 不知道大家是否还记得. 上一篇我说过原来HashTable为什么要设计保存zval**, 那么现在因为_Bucket直接保存的是zval了,那怎么解决COW的时候一处修改多处可见的需求呢? IS_INDIRECT就应用而生了,IS_INDIRECT类型其实可以理解为就是一个zval*的结构体。它被广泛应用在GLOBALS,Properties等多个需要俩个HashTable指向同于一个ZVAL的场景。

然后现在arData因为是一个连续的数组了,那么当foreach的时候,就可以顺序访问一块连续的内存,而现在zval直接保存在bucket中,那么在绝大部分情况下(不需要外部指针的内容,比如long,bool之类的)就可以不需要任何额外的zval指针解引用了,缓存局部性友好,性能提升非常明显。

还有就是PHP5的时代,查找数组元素的时候,因为传递进来的是char *key,所有需要每次查找都计算key的Hash值,而现在查找的时候传递进来的key是zend_string, Hash值不需要重新计算,此处也有部分性能提升。

  1. ZEND_API zval* ZEND_FASTCALL zend_hash_find(const HashTable *ht, zend_string *key);
  2. ZEND_API zval* ZEND_FASTCALL zend_hash_str_find(const HashTable *ht, const char *key, size_t len);
  3. ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h);
  4. ZEND_API zval* ZEND_FASTCALL _zend_hash_index_find(const HashTable *ht, zend_ulong h);

当然,PHP7也保留了直接通过char* 查找的zend_hash_str_find API,这对于一些只有char*的场景,可以避免生成zend_string的内存开销,也是很有用的。

赞(0) 打赏
未经允许不得转载PHP开源Hub » 深入理解PHP7内核之HashTable

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    支持一下

    违章代办1个月前 (02-29)回复

PHP开源Hub-致力于互联网开发者的成长

技术群聊软文发表

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏