5

深入理解PHP7内核之HashTable

 3 years ago
source link: https://www.laruence.com/2020/02/25/3182.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

深入理解PHP7内核之HashTable

之前的俩篇文章深入理解PHP7内核之zval 和深入理解PHP7内核之Reference, 我介绍了当时在开发PHP7的时候对zval和reference的一些改造思考和结果, 之后因为确实精力有限就没有继续往下写，时隔一年多以后，因为这场突如其来的疫情，在家办公的时间很多， 于是终于有了时间让我来继续介绍一下PHP7的中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.         memcpy(&(p)->pDataPtr, pData, sizeof(void *));
  6.         (p)->pData = &(p)->pDataPtr;
  7.     } else {
  8.         if ((p)->pData == &(p)->pDataPtr) {
  9.             (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);
  10.             (p)->pDataPtr=NULL;
  11.         } else {
  12.             (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent); \
  13.             /* (p)->pDataPtr is already NULL so no need to initialize it */ \
  14.         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中，我们当时的考虑是可能因为担心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.         uint32_t flags;
  11.     uint32_t nTableMask;
  12.     Bucket *arData;
  13.     uint32_t nNumUsed;
  14.     uint32_t nNumOfElements;
  15.     uint32_t nTableSize;
  16.     uint32_t nInternalPointer;
  17.     zend_long nNextFreeElement;
  18.     dtor_func_t pDestructor;

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

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

  1. #ifdef WORDS_BIGENDIAN
  2. # define ZEND_ENDIAN_LOHI_4(a, b, c, d) d; c; b; a;
  3. #else
  4. # define ZEND_ENDIAN_LOHI_4(a, b, c, d) a; b; c; d;
  5. #endif

而数据会核心保存在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进程中几十万的数组元素，这个内存降低就更明显了.

对比的看，

  • 现在的冲突拉链被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值不需要重新计算，此处也有部分性能提升。

  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的内存开销，也是很有用的。

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

Packed array

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

  1. HashTable Data Layout
  2. =====================
  3.          +=============================+
  4. pointer->| HT_HASH(ht, ht->nTableMask) |
  5.          | ... |
  6.          | HT_HASH(ht, -1) |
  7.          +-----------------------------+
  8. arData ->| Bucket[0] |
  9.          | ... |
  10.          | Bucket[ht->nTableSize-1] |
  11.          +=============================+

如图，事实上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.

  1. <?php
  2. echo "Packed array:\n";
  3. $begin = memory_get_usage();
  4. $array = range(0, 10000);
  5. echo "Memory: ", memory_get_usage() - $begin, " bytes\n";
  6. $begin = memory_get_usage();
  7. $array[10001] = 1;
  8. echo "Memory Increased: ", memory_get_usage() - $begin, " bytes\n";
  9. $start = microtime(true);
  10. for ($i = 0; $i < 10000; $i++) {
  11.     $array[$i];
  12. echo "Time: ", (microtime(true) - $start) * 1000 , " ms\n";
  13. unset($array);
  14. echo "\nMixed array:\n";
  15. $begin = memory_get_usage();
  16. $array = range(0, 10000);
  17. echo "Memory: ", memory_get_usage() - $begin, " bytes\n";
  18. $begin = memory_get_usage();
  19. $array["foo"] = 1;
  20. echo "Memory Increased: ", memory_get_usage() - $begin, " bytes\n";
  21. $start = microtime(true);
  22. for ($i = 0; $i < 10000; $i++) {
  23.     $array[$i];
  24. echo "Time: ", (microtime(true) - $start) * 1000 ," ms\n";

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

  1. $ /home/huixinchen/local/php74/bin/php -n /tmp/1.php
  2. Packed array:
  3. Memory: 528480 bytes
  4. Memory Increased: 0 bytes
  5. Time: 0.49519538879395 ms
  6. Mixed array:
  7. Memory: 528480 bytes
  8. Memory Increased: 131072 bytes
  9. Time: 0.63300132751465 ms

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

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

  1. $arr[2] = 1;
  2. $arr[1] = 2;
  3. $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中也大量应用了这种数据特性。

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

  1. ifdef __SSE2__
  2.             __m128i xmm0 = _mm_setzero_si128();
  3.             xmm0 = _mm_cmpeq_epi8(xmm0, xmm0);
  4.             _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 0), xmm0);
  5.             _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 4), xmm0);
  6.             _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 8), xmm0);
  7.             _mm_storeu_si128((__m128i*)&HT_HASH_EX(data, 12), xmm0);
  8.         } while (0);
  9. #else
  10.         HT_HASH_EX(data, 0) = -1;
  11.         HT_HASH_EX(data, 1) = -1;
  12.         HT_HASH_EX(data, 2) = -1;
  13.         HT_HASH_EX(data, 3) = -1;
  14.         HT_HASH_EX(data, 4) = -1;
  15.         HT_HASH_EX(data, 5) = -1;
  16.         HT_HASH_EX(data, 6) = -1;
  17.         HT_HASH_EX(data, 7) = -1;
  18.         HT_HASH_EX(data, 8) = -1;
  19.         HT_HASH_EX(data, 9) = -1;
  20.         HT_HASH_EX(data, 10) = -1;
  21.         HT_HASH_EX(data, 11) = -1;
  22.         HT_HASH_EX(data, 12) = -1;
  23.         HT_HASH_EX(data, 13) = -1;
  24.         HT_HASH_EX(data, 14) = -1;
  25.         HT_HASH_EX(data, 15) = -1;
  26. #endif

存在的问题

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

  1. <?php
  2. $array = range(0, 7);
  3. set_error_handler(function($err, $msg) {
  4.     global $array;
  5.     $array[] = 1; //force resize;
  6. function crash() {
  7.     global $array;
  8.     $array[0] += $var; //undefined notice
  9. 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 中找到。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK