HashTable在PHP7中的應用

這篇文章將為大家詳細講解有關HashTable在PHP7中的應用，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

先來簡單回顧一下PHP5的Hashtable:

PHP5的實現中, Hashtable的核心是存儲了一個個指向zval指針的指針, 也就是zval**(我遇到不少的同學問為什么是zval**, 而不是zval*, 這個原因其實很簡單, 因為Hashtable中的多個位置都可能指向同一個zval, 那么最常見的一個可能就是在COW的時候, 當我們需要把一個變量指向一個新的zval的時候, 如果在符號表中存的是zval*, 那們我們就做不到對一處修改, 所有的持有方都有感知, 所以必須是zval**), 這樣的設計在最初的出發點是為了讓Hashtable可以存儲任何尺寸的任何信息, 不僅僅是指針, 還可以存儲一段內存值(當然實際上大部分情況下，比如符號表還是存的zval的指針).

PHP5的代碼中也用了比較Hack的方式來判斷存儲的是什么:

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

它來判斷存儲的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

首先在PHP7中，我們當時的考慮是可能因為擔心Hashtable用的太多，我們新設計的結構體可能不一定能Cover所有的場景，于是我們新定義了一個結構體叫做zend_array, 當然最后經過一系列的努力，發現zend_array可以完全替代Hashtable， 最后還是保留了Hashtable和zend_array倆個名字，只不過互為Alias.
再下面的文章中，我會用HashTable來特指PHP5中的Hashtable，而用zend_array來指代PHP7中的Hashtable.

我們先來看看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中，位操作應用的很多，因為這樣一來一個字節就可以保存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是一個Bucket數組，Bucket定義:

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

再對比看下PHP5多Bucket:

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讀寫操作基本都很臨近，這個問題其實很難被實際代碼觸發，所以這個問題一直懸停著。

關于HashTable在PHP7中的應用就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。