Press "Enter" to skip to content

深入理解PHP7内核之HashTable

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

PHP5

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

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

#define UPDATE_DATA(ht, p, pData, nDataSize)                                            
    if (nDataSize == sizeof(void*)) {                                                   
        if ((p)->pData != &(p)->pDataPtr) {                                             
            pefree_rel((p)->pData, (ht)->persistent);                                   
        }                                                                               
        memcpy(&(p)->pDataPtr, pData, sizeof(void *));                                  
        (p)->pData = &(p)->pDataPtr;                                                    
    } else {                                                                            
        if ((p)->pData == &(p)->pDataPtr) {                                             
            (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);            
            (p)->pDataPtr=NULL;                                                         
        } else {                                                                        
            (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);   \
            /* (p)->pDataPtr is already NULL so no need to initialize it */             \
        }                                                                              
        memcpy((p)->pData, pData, nDataSize);                                           
    }

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

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

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

问题

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

  • 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的定义:

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    _unused,
                zend_uchar    nIteratorsCount,
                zend_uchar    _unused2)
        } 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;
};

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

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

#ifdef WORDS_BIGENDIAN
# define ZEND_ENDIAN_LOHI_4(a, b, c, d)    d; c; b; a;
#else
# define ZEND_ENDIAN_LOHI_4(a, b, c, d)    a; b; c; d;
#endif

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

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

再对比看下PHP5多Bucket:

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;

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

对比的看,

  • 现在的冲突拉链被bauck.zval->u2.next替代, 于是bucket->pNext, bucket->pLast可以去掉了。
  • zend_array->arData是一个数组,所以也就不再需要pListNext, pListLast来保持顺序了, 他们也可以去掉了。 现在数组中元素的先后顺序,完全根据它在arData中的index顺序决定,先加入的元素在低的index中。
  • 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的场景。

另外,对于原来一些扩展会使用HashTable来保存一些自己的内存,现在可以通过IS_PTR这种zval类型来实现。

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

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

ZEND_API zval* ZEND_FASTCALL zend_hash_find(const HashTable *ht, zend_string *key);
ZEND_API zval* ZEND_FASTCALL zend_hash_str_find(const HashTable *ht, const char *key, size_t len);
ZEND_API zval* ZEND_FASTCALL zend_hash_index_find(const HashTable *ht, zend_ulong h);
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的内存开销,也是很有用的。

另外,我们还做了不少进一步的优化:

Packed array

对于字符串key的数组来说, zend_array在arHash中保存了Hash值到arData的对应,有同学可能会好奇怎么没有在zend_array中看到arHash? 这是因为arHash和arData是一次分配的:

HashTable Data Layout
=====================

         +=============================+
pointer->| HT_HASH(ht, ht->nTableMask) |
         | ...                         |
         | HT_HASH(ht, -1)             |
         +-----------------------------+
arData ->| Bucket[0]                   |
         | ...                         |
         | Bucket[ht->nTableSize-1]    |
         +=============================+

如图,事实上arData是一块分配的内存的中间部分,分配的内存真正的起始位置其实是pointer,而arData是计算过的一处中间位置,这样就可以用一个指针来表达俩个位置,分别通过前后偏移来获取位置, 比如-1对应的是arHash[0], 这个技巧在PHP7的过程中我们也大量应用了,比如因为zend_object是变长的,所以不能在他后面有其他元素,为了实现一些自定义的object,那么我们会在zend_object前面分配自定义的元素等等。

而对于全部是数字key的数组,arHash就显得没那么必要了,所以此时我们就用了一种新的数组, packed array来优化这个场景。

对于HASH_FLAG_PACKED的数组(标志在zend_array->u.flags)中,它们是只有连续数字key的数组,它们不需要Hash值来映射,所以这样的数组读取的时候,就相当于你直接访问C数组,直接根据偏移来获取zval.

<?php
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();
$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";

如图所示的简单测试,在我的机器上输出如下(请注意,这个测试的部分结果可能会受你的机器,包括装了什么扩展相关,所以记得要-n):

$ /home/huixinchen/local/php74/bin/php -n /tmp/1.php
Packed array:
Memory: 528480 bytes
Memory Increased: 0 bytes
Time: 0.49519538879395 ms

Mixed array:
Memory: 528480 bytes
Memory Increased: 131072 bytes
Time: 0.63300132751465 ms

可以看到, 当我们使用$array[“foo”]=1, 强迫一个数组从PACKED ARRAY变成一个Mixed Array以后,内存增长很明显,这部分是因为需要为10000个arHash分配内存。
而通过Index遍历的耗时,Packed Array仅仅是Mixed Array的78%。

但是这里还是要特别说明一些, packed array一定是按照数字键自然增长顺序添加的数组,比如对于如下的这种数组就不是packed array:

$arr[2] = 1;
$arr[1] = 2;
$arr[0] = 3;

虽然这个数组的索引值是自然增长的,但是添加顺序并不是按照索引值的增长来的,这里也是为了保证PHP数组的foreach的遍历顺序是按照添加顺序这个特性来的。

比如如果你foreach上面的数组,你会发现依旧是顺序的获得1,2,3数组的值。

对于这样的数组,还是依照arHash来记录添加循序。

总的来说,arData中的值是按照添加顺序来自然增长使用的,而索引的顺序则记录在arHash中。

Static key array

对于字符串array来说, destructor的时候是需要释放字符串key的, 数组copy的时候也要增加key的计数,但是如果所有的key都是INTERNED字符串,那事实上我们不需要管这些了。于是就有了这个HASH_FLAG_STATIC_KEYS。

Empty array

我们分析发现,在实际使用中,有大量的空数组,针对这些, 我们在初始化数组的时候,如果不特殊申明,默认是不会分配arData的,此时会把数组标志为HASH_FLAG_UNINITIALIZED, 只有当发生实际的写入的时候,才会分配arData。

Immutable array

类似于INTERNED STRING,PHP7中我们也引入了一种Imuutable array, 标志在array->gc.flags中的IS_ARRAY_IMMUTABLE, 大家可以理解为不可更改的数组,对于这种数组,不会发生COW,不需要计数,这个也会极大的提高这种数据的操作性能,我的Yaconf中也大量应用了这种数据特性。

SIMD

后来的PHP7的版本中,我实现了一套SIMD指令集优化的框架,比如SIMD的base64_encode, 而在HashTable的初始化中,我们也应用了部分这样的指令集(此处应用虽然很微小,但有必要提一下):

ifdef __SSE2__
        do {
            __m128i xmm0 = _mm_setzero_si128();
            xmm0 = _mm_cmpeq_epi8(xmm0, xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  0), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  4), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data,  8), xmm0);
            _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 12), xmm0);
        } while (0);
#else
        HT_HASH_EX(data,  0) = -1;
        HT_HASH_EX(data,  1) = -1;
        HT_HASH_EX(data,  2) = -1;
        HT_HASH_EX(data,  3) = -1;
        HT_HASH_EX(data,  4) = -1;
        HT_HASH_EX(data,  5) = -1;
        HT_HASH_EX(data,  6) = -1;
        HT_HASH_EX(data,  7) = -1;
        HT_HASH_EX(data,  8) = -1;
        HT_HASH_EX(data,  9) = -1;
        HT_HASH_EX(data, 10) = -1;
        HT_HASH_EX(data, 11) = -1;
        HT_HASH_EX(data, 12) = -1;
        HT_HASH_EX(data, 13) = -1;
        HT_HASH_EX(data, 14) = -1;
        HT_HASH_EX(data, 15) = -1;
#endif

存在的问题

在实现zend_array替换HashTable中我们遇到了很多的问题,绝大部份它们都被解决了,但遗留了一个问题,因为现在arData是连续分配的,那么当数组增长大小到需要扩容到时候,我们只能重新realloc内存,但系统并不保证你realloc以后,地址不会发生变化,那么就有可能:

<?php
$array = range(0, 7);

set_error_handler(function($err, $msg) {
    global $array;
    $array[] = 1; //force resize;
});

function crash() {
    global $array;
    $array[0] += $var; //undefined notice
}

crash();

比如上面的例子, 首先是一个全局数组,然后在函数crash中, 在+= opcode handler中,zend vm会首先获取array[0]的内容,然后+$var, 但var是undefined variable, 所以此时会触发一个未定义变量的notice,而同时我们设置了error_handler, 在其中我们给这个数组增加了一个元素, 因为PHP中的数组按照2^n的空间预先申请,此时数组满了,需要resize,于是发生了realloc,从error_handler返回以后,array[0]指向的内存就可能发生了变化,此时会出现内存读写错误,甚至segfault,有兴趣的同学,可以尝试用valgrind跑这个例子看看。

但这个问题的触发条件比较多,修复需要额外对数据结构,或者需要拆分add_assign对性能会有影响,另外绝大部分情况下因为数组的预先分配策略存在,以及其他大部分多opcode handler读写操作基本都很临近,这个问题其实很难被实际代码触发,所以这个问题一直悬停着。

最后,就暂时写到这里吧,以后想到再补充吧。 另外这里的大部分的内容,你也可以从我4年前的一个演讲ppt: The Secret of PHP7’s Performance 中找到。

18 Comments

  1. harshing
    harshing May 16, 2021

    static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht)
    {
    void *data;

    if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) {
    data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), 1);
    } else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) {
    data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
    } else {
    data = emalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK));
    }
    HT_SET_DATA_ADDR(ht, data);
    /* Don’t overwrite iterator count. */
    ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
    HT_HASH_RESET_PACKED(ht);
    }

    源码中数组初始化的这个条件判断看起来完全是多余的
    else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) {
    data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
    }

  2. liang neng
    liang neng December 24, 2020

    鸟哥,作为一个工作4年的PHPER 感觉没什么进步。想问问您 接下来如果想往资深或架构进发的话,大概要一个怎样的学习路线比较好呢?

  3. ksana
    ksana April 23, 2020

    鸟哥,想请问一下如果有hash冲突,数组怎么保证顺序遍历呢?

    • laruence
      laruence April 24, 2020

      zval.u2.next 这个字段会记录冲突的拉链“遍历顺序”

      • ksana
        ksana April 27, 2020

        了解了,谢谢鸟哥

      • gaotao
        gaotao May 31, 2020

        鸟哥,进行遍历不是直接遍历Bucket数组吗?

        • wanghui
          wanghui July 21, 2020

          应该是鸟哥理解错了 即使冲突也是直接遍历Bucker数组,zval.u2.next 只有在寻值的时候才会用的到

          • laruence
            laruence August 3, 2020

            噢,对,误会了他的问题,冲突的时候用u2.next来记录hash冲突的下一个顺序的值,如果是单纯的遍历的话,是根据插入顺序来的,遍历buckets。

  4. xiaotian044500
    xiaotian044500 March 30, 2020

    学习了

  5. adskyfly
    adskyfly March 30, 2020

    鸟哥,文章里面“而通过Index遍历的速度,Packed Array仅仅是Mixed Array的78%。”这句话感觉有问题,应该是Packed Array的时间仅仅是Mixed Array的78%吧。

    • laruence
      laruence March 30, 2020

      嗯,你说的对,我修改一下

  6. hzhu
    hzhu February 25, 2020

    想问下代码高亮方案是哪套

    • laruence
      laruence February 25, 2020

      SHJSSyntaxHiliter

  7. Demon
    Demon February 25, 2020

    这一刻感觉重返青春!爱过!

  8. ben
    ben February 25, 2020

    鸟哥,未来是大数据云计算ai的天下,我希望最好用的php不能缺席,我会java但是非常喜欢php,php8的jit我非常支持,高瞻远瞩的一部,现在php缺什么,我觉得他缺乏swoole东西,fpm已经使过去了,放下过去吧,应该同时保留fpm,增加多线程,内存常驻,让用户想用什么就有解决方案,确实需要多线程,这个是致命的,如果没有多线程,在后时代php估计会被抛弃,应用是种子,多线程是土壤,没有多线程的php永远的痛,加了多线程,再加上一些好的gc解决方案,php真的就活了,还是就是多出一些在大数据时代,更多分布式解决方案,和非常好的数据处理工具函数包之类的,希望php能赶上最后一趟车,数据时代,致敬php每一个辛勤工作的人,在我心里php是最棒的语言

  9. 章鱼
    章鱼 February 25, 2020

    Laruence,你好,文章中“关于这块可以参看我很早的一篇文章深入理解PHP之数组”,其中的链接出错了,跳转的url变成了这样:https://www.laruence.com/2020/02/25/%E2%80%9C/www.laruence.com/2009/08/23/1065.html

Comments are closed.