PHP7カーネルのHashTableを一緒に学びましょう

前の 2 つの記事では、PHP7 カーネルの zval と PHP7 カーネルの Reference について深く理解し、いくつかの考えと結果を紹介しました。 PHP7 開発時の zval と参照の変換について書いていましたが、エネルギーが本当に限られていたので書くのをやめましたが、1 年以上経ち、突然の疫病のせいで在宅勤務に多くの時間を費やしたため、ようやく書くことができました。 PHP7 の Hashtable の変更点と、その時点で行った変更の背後にある考慮事項を引き続き紹介します。

PHP5

##PHP カーネルについて常に関心を持っている学生の皆さんは、PHP5 の Hashtable についてはよく知っているはずですが、PHP5 の Hashtable について簡単に復習してみましょう:

PHP5 の実装において、Hashtable の核となるのはzval ポインタへのポインタ、つまり zval** (なぜ zval* ではなく zval** なのかと尋ねる多くの学生に会いました。その理由は実際には非常に簡単です。ハッシュテーブル内の複数の位置が同じ zval を指す可能性があるため、最も一般的なものは、COW で、変数を新しい zval にポイントする必要がある場合、zval* がシンボル テーブルに格納されている場合、1 つの場所を変更することはできず、すべての所有者がそれを認識することになるため、次のようにする必要があります。 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 のハッシュテーブルは、バケットごとに個別にリリースが適用されます。

ハッシュテーブルに格納されたデータは、pListNext ポインタを介してリストに結合され、直接移動することができます。これに関しては、PHP の配列を詳しく理解するために私の非常に初期の記事を参照してください

Question

PHP7 を作成する際、パフォーマンスの観点から現在の実装に関する次の問題を要約するなど、考えられるいくつかの最適化ポイントを詳細に検討しました。

Hashtable はPHP ではさまざまな zval を保存するために最も一般的に使用されますが、PHP5 の HashTable は多用途であり、zval の保存に特化して最適化するように設計できるため、メモリ使用量が削減されます。
• 2. キャッシュの局所性の問題。zval を含む PHP5 のハッシュテーブルのバケットが独立して割り当てられ、ハッシュテーブル内のすべての要素を文字列化するためにリストが使用されるため、配列を走査したり連続してアクセスしたりするときに問題が発生します。 . 場合によっては、キャッシュが適切ではないことがあります。
• 
  たとえば、図に示すように、PHP コード内の一般的な foreach 配列は複数のメモリ ジャンプを引き起こします。
  
3. 1 と同様に、PHP5 のハッシュテーブルでは、A zval にアクセスします。は zval** であるため、ポインタを少なくとも 2 回解決する必要があり、キャッシュに優しくない一方で非効率的です。
• たとえば、上の図の青いボックスでは、配列内でバケットを見つけた後、実際の zval の内容を読み取る前に zval** を解凍する必要があります。つまり、2 回のメモリ読み取りが発生する必要があります。効率が低い。
  

もちろん、他にもたくさんの問題があるので、ここでは詳しく述べませんが、正直に言うと、もう2年以上も経っています。 PHP7

PHP7

まず第一に、当時私たちが PHP7 で検討したのは、おそらく Hashtable が使いすぎると、新しく設計された構造が必ずしもすべてのシナリオをカバーできるとは限りません。そこで、zend_array という新しい構造を定義しました。もちろん、一連の努力の結果、zend_array が Hashtable を完全に置き換えることができることがわかりました。最終的には、 Hashtable と zend_array という名前は引き続き使用していますが、これらは互いにエイリアスです。

次の記事では、特に PHP5 のハッシュテーブルを参照するために HashTable を使用し、PHP7 のハッシュテーブルを参照するために 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 に保存されます:

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

PHP5 の複数のバケットを比較してみましょう:

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%。

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 中国語 Web サイトの他の関連記事を参照してください。