PHP7 커널의 HashTable을 함께 배워볼까요?

이전 두 기사에서는 PHP7 커널의 zval에 대한 심층적인 이해와 PHP7 커널의 Reference에 대한 심층적인 이해를 바탕으로 zval과 참조의 변환에 대한 몇 가지 생각과 결과를 소개했습니다. 나중에 PHP7을 개발하다 보니 체력이 부족해서 계속 글을 쓰지 못했는데, 1년이 넘게 갑작스러운 전염병으로 인해 재택근무를 하게 되어서 드디어 PHP7의 변경 사항을 계속 소개할 시간이 생겼습니다. PHP7의 Hashtable과 당시 변경 이유.

PHP5

PHP 커널에 관심을 갖고 있는 학생들은 PHP5의 Hashtable에 익숙할 것이지만, 먼저 PHP5의 Hashtable을 간략하게 살펴보겠습니다.

PHP5의 구현 여러 위치에서 동일한 zval을 가리킬 수 있으므로 가장 일반적인 것은 COW 중에 zval*이 저장된 경우 변수를 새 zval을 가리켜야 할 때일 수 있습니다. 기호 테이블에서는 수정할 수 없으며 모든 소유자가 이를 알고 있으므로 zval**이어야 합니다. 이 디자인의 원래 시작점은 Hashtable이 모든 크기의 정보를 저장할 수 있도록 허용하는 것입니다. 포인터만 있으면 메모리 값을 저장할 수도 있습니다(물론 대부분의 경우 기호 테이블은 여전히 ​​zval 포인터를 저장합니다).

PHP5 코드는 또한 저장되는 내용을 결정하기 위해 해커 방법을 사용합니다.

#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);                                           
    }

저장된 크기는 포인터 크기이며, 저장된 콘텐츠를 업데이트하기 위해 다양한 방법을 사용합니다. 매우 해키적인 방법입니다.

PHP5의 Hashtable은 Bucket별로 별도로 릴리즈가 적용됩니다.

해시테이블에 저장된 데이터는 직접 탐색할 수 있는 pListNext 포인터를 통해 목록에 연결됩니다. 이에 대해서는 PHP 배열에 대한 심층적인 이해에 대한 초기 기사를 참조하세요.

Problems

저는 PHP7을 작성하고 있습니다. 그 당시 우리는 성능 관점에서 현재 구현의 다음 문제를 요약하는 것을 포함하여 여러 가지 가능한 최적화 지점에 대해 자세히 생각했습니다.

• Hashtable은 PHP에서 다양한 zval을 저장하기 위해 가장 일반적으로 사용되며, PHP5의 HashTable은 너무 일반적으로 설계되었으며 특히 zval 저장에 최적화되도록 설계하여 메모리 사용량을 줄일 수 있습니다.
• 2. zval을 포함한 PHP5의 Hashtable 버킷이 독립적으로 할당되고 List가 Hashtable의 모든 요소를 ​​문자열로 지정하는 데 사용되기 때문에 캐시 지역성 문제가 발생합니다. 이로 인해 배열을 순회하거나 순차적으로 액세스할 때 캐시가 실패하게 됩니다. .
  
  예를 들어, 그림에 표시된 것처럼 PHP 코드의 일반적인 foreach 배열은 여러 메모리 점프를 발생시킵니다.
• 3 1과 유사하게 PHP5의 Hashtable에서는 zval*이므로 액세스해야 합니다. * 포인터를 두 번 이상 풀어야 하는 방법은 한편으로는 캐시 친화적이지 않으며 다른 한편으로는 비효율적입니다.
  예를 들어 위 그림의 파란색 상자에서 배열에서 버킷을 찾은 후 실제 zval 콘텐츠를 읽으려면 먼저 zval**의 압축을 풀어야 합니다. 즉, 두 번의 메모리 읽기가 발생해야 합니다. 무능한.

물론 그 밖에도 많은 문제가 있지만 여기서는 자세히 다루지 않겠습니다. 솔직히 말해서 그 당시에 생각했던 것 중 일부는 지금은 기억나지 않습니다. 이제 PHP7을 살펴보겠습니다

PHP7

먼저 PHP7에서는 당시 우리가 고려한 부분은 아마도 Hashtable을 너무 많이 사용하게 될까 봐 새로 디자인한 구조로는 모든 것을 커버하지 못할 수도 있다는 생각이었습니다. 물론, 일련의 노력 끝에 zend_array가 Hashtable을 완전히 대체할 수 있다는 사실이 밝혀졌습니다. 결국 Hashtable과 zend_array라는 두 이름은 그대로 유지되었지만 Alias입니다.
다음 글에서는 PHP5에서 Hashtable을 구체적으로 참조하기 위해 HashTable을 사용하고, PHP7에서 Hashtable을 참조하기 위해 zend_array를 사용하겠습니다.

먼저 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에서는 1바이트에 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는 버킷 배열입니다.

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

PHP5 Multi를 비교해 보겠습니다. -버킷:

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;

PHP 프로세스의 수십만 개의 배열 요소를 생각하면 메모리 사용량이 72바이트에서 32바이트로 줄었습니다.

비교를 보면,

• 现在的冲突拉链被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%。

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读写操作基本都很临近，这个问题其实很难被实际代码触发，所以这个问题一直悬停着。

推荐教程：《php教程》

위 내용은 PHP7 커널의 HashTable을 함께 배워볼까요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!