Lassen Sie uns gemeinsam HashTable des PHP7-Kernels lernen

In den beiden vorherigen Artikeln habe ich ein tiefes Verständnis von zval im PHP7-Kernel und ein tiefes Verständnis von Reference im PHP7-Kernel vorgestellt über die Transformation von zval und Referenz bei der Entwicklung von PHP7, und dann habe ich aufgehört zu schreiben, weil ich aufgrund dieser plötzlichen Epidemie viel Zeit damit verbracht habe, von zu Hause aus zu arbeiten Zeit, die Änderungen in Hashtable in PHP7 und die Überlegungen hinter den Änderungen, die wir damals vorgenommen haben, fortzusetzen.

PHP5

Studenten, die sich schon immer Gedanken über den PHP-Kernel gemacht haben, sollten mit PHP5s Hashtable vertraut sein, aber lassen Sie uns einen kurzen Blick auf PHP5s Hashtable werfen:

Bei der Implementierung von PHP5 besteht der Kern von Hashtable darin, zu speichern Zeiger auf zval-Zeiger, also zval** (Ich traf viele Studenten und fragte, warum es zval** statt zval* sei. Der Grund ist eigentlich sehr einfach, da mehrere Positionen in der Hashtable auf dasselbe zval verweisen können, also das Die gebräuchlichste Variante dürfte sein: Wenn wir in COW eine Variable auf einen neuen zval verweisen müssen und zval* in der Symboltabelle gespeichert ist, können wir eine Stelle nicht ändern und alle Inhaber werden sich dessen bewusst sein, also muss es so sein zval**), der ursprüngliche Ausgangspunkt dieses Entwurfs besteht darin, Hashtable das Speichern beliebiger Informationen beliebiger Größe zu ermöglichen, nicht nur Zeiger, sondern auch einen Speicherwert (natürlich in den meisten Fällen, z. B. Symbole). Die Tabelle speichert weiterhin den zval-Zeiger ).

Der PHP5-Code verwendet auch eine Vergleichs-Hack-Methode, um zu bestimmen, was gespeichert wird:

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

Es bestimmt, ob die gespeicherte Größe eine Zeigergröße ist, und verwendet dabei verschiedene Möglichkeiten, den gespeicherten Inhalt zu aktualisieren . Sehr hackige Art.

PHP5s Hashtable beantragt die Veröffentlichung separat für jeden Bucket.

Die in der Hashtable gespeicherten Daten werden auch über den pListNext-Zeiger in eine Liste eingefügt, die direkt durchlaufen werden kann. In diesem Zusammenhang können Sie auf meinen sehr frühen Artikel verweisen, um ein tieferes Verständnis von PHP zu erlangen Arrays

Probleme

Beim Schreiben von PHP7 haben wir mehrere mögliche Optimierungspunkte im Detail betrachtet, einschließlich der Zusammenfassung der folgenden Probleme mit der aktuellen Implementierung aus Leistungssicht:

• Hashtable wird in PHP am häufigsten zum Speichern verschiedener Zvals verwendet. HashTable von PHP5 ist jedoch zu vielseitig und kann speziell für die Speicherung von Zvals optimiert werden, wodurch der Speicherverbrauch reduziert wird.
• 2. Cache-Lokalitätsproblem, da der Bucket der Hashtable von PHP5, einschließlich zval, unabhängig zugewiesen wird und eine Liste zum Aneinanderreihen aller Elemente in der Hashtable verwendet wird, was beim Durchlaufen oder sequentiellen Zugriff auf ein Array zu Problemen führt . Manchmal ist der Cache nicht freundlich.
  
  Wie in der Abbildung gezeigt, führt ein gemeinsames foreach-Array im PHP-Code zu mehreren Speichersprüngen.
• 3 Ähnlich wie 1, in PHP5s Hashtable, um auf A zval zuzugreifen Es ist zval** und muss den Zeiger mindestens zweimal auflösen. Einerseits ist es nicht Cache-freundlich und andererseits auch ineffizient.
  Zum Beispiel müssen wir im blauen Feld im Bild oben, nachdem wir den Bucket im Array gefunden haben, zval** entpacken, bevor wir den tatsächlichen Zval-Inhalt lesen können. Das heißt, es müssen zwei Speicherlesevorgänge durchgeführt werden. Ineffizient.

Natürlich gibt es noch viele andere Themen, auf die ich hier nicht näher eingehen werde. Ehrlich gesagt kann ich mich nicht mehr daran erinnern, was ich damals dachte Einige davon jetzt. Schauen wir uns jetzt PHP7 an Wenn wir es zu oft verwenden, kann unsere neu entworfene Struktur möglicherweise nicht alle Szenarien abdecken. Daher haben wir nach einer Reihe von Bemühungen festgestellt, dass zend_array Hashtable vollständig ersetzen kann Die Namen Hashtable und zend_array wurden immer noch beibehalten, aber sie sind Alias ​​zueinander.

Im folgenden Artikel werde ich HashTable verwenden, um speziell auf Hashtable in PHP5 zu verweisen, und zend_array, um auf Hashtable in PHP7 zu verweisen.

Werfen wir zunächst einen Blick auf die Definition von 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;
};

Im Vergleich zu Hashtable in der PHP5-Ära wurde die Speichernutzung von zend_array von 72 Byte in PHP5 auf 56 Byte reduziert. Wenn man an Tausende von Arrays in einem PHP-Lebensprozess denkt, ist die Speicherreduzierung offensichtlich.

Hier wird noch einmal die Rolle von ZEND_ENDIAN_LOHT_4 in der Definition von zend_array erläutert. Dies dient dazu, das Problem von Big-Endian und Little-Endian zu lösen gleiche Speicherreihenfolge, was praktisch ist. In PHP7 werden Bitoperationen häufig verwendet, da ein Byte 8 Statusbits speichern kann, was Speicher spart:)

#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

Die Daten werden in arData gespeichert, einem Bucket-Array, Bucket-Definition:

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

Vergleichen wir die mehreren Buckets von 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;

Die Speichernutzung wurde von 72 Byte auf 32 Byte reduziert. Denken Sie an Hunderttausende in einem PHP-Prozess-Array-Element, die Speicherreduzierung ist noch deutlicher.

Im Vergleich

• 现在的冲突拉链被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教程》

Das obige ist der detaillierte Inhalt vonLassen Sie uns gemeinsam HashTable des PHP7-Kernels lernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!