Apprenons ensemble la HashTable du noyau PHP7

Dans les deux articles précédents, j'ai une compréhension approfondie de zval dans le noyau PHP7 et une compréhension approfondie de Reference dans le noyau PHP7. sur la transformation de zval et de référence lors du développement de PHP7 , puis j'ai arrêté d'écrire parce que j'avais vraiment une énergie limitée. Après plus d'un an, à cause de cette soudaine épidémie, j'ai passé beaucoup de temps à travailler à domicile, donc j'ai enfin. il est temps de continuer à introduire les changements dans Hashtable dans PHP7 et les considérations derrière les changements que nous avons apportés à ce moment-là.

PHP5

<.>

Étudiants qui ont toujours été préoccupés par le noyau PHP, vous devriez être familiers avec la table de hachage de PHP5, mais passons brièvement en revue la table de hachage de PHP5 :

Dans l'implémentation de PHP5, le cœur de Hashtable est de stocker des pointeurs vers des pointeurs zval, c'est-à-dire zval** (j'ai rencontré de nombreux étudiants qui se demandaient pourquoi il s'agissait de zval** au lieu de zval*. La raison est en fait très simple, car plusieurs positions dans la table de hachage peuvent pointer vers le même zval, donc le le plus courant peut être Dans COW, lorsque nous devons pointer une variable vers un nouveau zval, si zval* est stocké dans la table des symboles, alors nous ne pouvons pas modifier un endroit et tous les détenteurs en seront conscients, donc cela doit être le cas. zval**), le point de départ original de cette conception est de permettre à Hashtable de stocker n'importe quelle information de n'importe quelle taille, pas seulement des pointeurs, mais aussi une valeur mémoire (bien sûr dans la plupart des cas, comme des symboles). La table stocke toujours le pointeur zval ).

Le code PHP5 utilise également une méthode de comparaison Hack pour déterminer ce qui est stocké :

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

Il détermine si la taille stockée est une taille de pointeur, utilisant ainsi différentes manières de mettre à jour le contenu stocké. . Manière très hacky.

La table de hachage de PHP5 demande une publication séparément pour chaque compartiment.

Les données stockées dans la Hashtable seront également regroupées dans une liste via le pointeur pListNext, qui peut être parcouru directement. À ce sujet, vous pouvez vous référer à mon tout premier article pour acquérir une compréhension approfondie de PHP. arrays

Problèmes

Lors de l'écriture de PHP7, nous avons examiné en détail plusieurs points d'optimisation possibles, notamment en résumant les problèmes suivants avec l'implémentation actuelle du point de vue des performances :

Hashtable est le plus couramment utilisé en PHP pour enregistrer divers zvals. Cependant, HashTable de PHP5 est trop polyvalent et peut être conçu pour être optimisé spécifiquement pour le stockage de zvals, réduisant ainsi l'utilisation de la mémoire.
• 2. Problème de localité du cache, car le bucket de la table de hachage de PHP5, y compris zval, est alloué indépendamment et une liste est utilisée pour chaîner tous les éléments de la table de hachage, ce qui entraînera des problèmes lors de la traversée ou de l'accès séquentiel à un tableau. . Parfois, le cache n'est pas convivial.
• 
  Par exemple, comme le montre la figure, un tableau foreach commun dans le code PHP provoquera plusieurs sauts de mémoire
  
Semblable à 1, dans la table de hachage de PHP5, pour accéder à A zval, car. c'est zval**, il faut résoudre le pointeur au moins deux fois. D'une part, il n'est pas respectueux du cache et, d'autre part, il est également inefficace.
• Par exemple, dans la case bleue de l'image ci-dessus, après avoir trouvé le bucket dans le tableau, nous devons décompresser zval** avant de pouvoir lire le contenu réel de zval. Autrement dit, deux lectures de mémoire doivent avoir lieu. Inefficace.
  

Bien sûr, il y a bien d'autres problèmes, que je n'entrerai pas dans les détails ici. Pour être honnête, cela fait plus de deux ans. Ce que je pensais à l'époque, je ne m'en souviens pas. certains d'entre eux maintenant. Regardons cela maintenant. Regardez PHP7

PHP7

Tout d'abord, en PHP7, notre réflexion à l'époque était peut-être parce que nous craignions que Hashtable le soit. trop utilisée, notre nouvelle structure ne sera peut-être pas nécessairement capable de couvrir tous les scénarios. Nous avons donc nouvellement défini une structure appelée zend_array. Bien sûr, après une série d'efforts, nous avons découvert que zend_array pouvait complètement remplacer Hashtable. a toujours conservé les noms Hashtable et zend_array, mais ils sont des alias l'un pour l'autre.

Dans l'article suivant, j'utiliserai HashTable pour faire référence spécifiquement à la Hashtable en PHP5, et zend_array pour faire référence à la Hashtable en PHP7.

Jetons d'abord un coup d'œil à la définition de 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;
};

Par rapport à Hashtable à l'ère PHP5, l'utilisation de la mémoire de zend_array a été réduite de 72 octets en PHP5 à 56 octets. Si l'on considère des milliers de tableaux dans un processus de vie PHP, la réduction de la mémoire est évidente.

Ici encore, le rôle de ZEND_ENDIAN_LOHT_4 dans la définition de zend_array ci-dessus est expliqué. Il s'agit de résoudre le problème du big et small endian. Sur big endian et little endian, les éléments peuvent être garantis d'être dans le. même ordre de stockage en mémoire, ce qui est pratique. Nous écrivons des opérations générales sur les bits. En PHP7, les opérations sur les bits sont largement utilisées, car un octet peut enregistrer 8 bits d'état, ce qui économise de la mémoire :)

#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

Les données seront stockées dans arData, qui est un Bucket Array, définition du Bucket :

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

Comparons les multiples buckets de 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;

L'utilisation de la mémoire a été réduite de 72 octets à 32 octets. Pensez aux centaines de milliers d'éléments de tableau PHP, la réduction de mémoire est encore plus. évident.

En comparaison,

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!