一起學習PHP7核心之HashTable
之前的倆篇文章深入理解PHP7核心之zval 和深入理解PHP7核心之Reference, 我介紹了當時在開發PHP7的時候對zval和reference的一些改造思考和結果, 之後因為確實精力有限就沒有繼續往下寫，時隔一年多以後，因為這場突如其來的疫情，在家辦公的時間很多， 於是終於有了時間讓我來繼續介紹一下PHP7的中Hashtable的變化, 以及當時我們做這些變化背後的考量.
PHP5
對於PHP核心一直有關注的同學, 應該對PHP5的Hashtable會比較熟悉, 但我們還是先來簡單回顧一下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, " bytesn";
$begin = memory_get_usage();
$array[10001] = 1;
echo "Memory Increased: ", memory_get_usage() - $begin, " bytesn";
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
$array[$i];
}
echo "Time: ", (microtime(true) - $start) * 1000 , " msn";
unset($array);
echo "nMixed array:n";
$begin = memory_get_usage();
$array = range(0, 10000);
echo "Memory: ", memory_get_usage() - $begin, " bytesn";
$begin = memory_get_usage();
$array["foo"] = 1;
echo "Memory Increased: ", memory_get_usage() - $begin, " bytesn";
$start = microtime(true);
for ($i = 0; $i < 10000; $i++) {
$array[$i];
}
echo "Time: ", (microtime(true) - $start) * 1000 ," msn";如圖所示的簡單測試，在我的機器上輸出如下(請注意，這個測試的部分結果可能會受你的機器，包括裝了什麼擴充套件相關，所以記得要-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讀寫操作基本都很臨近，這個問題其實很難被實際程式碼觸發，所以這個問題一直懸停著。
以上就是一起學習PHP7核心之HashTable的詳細內容，更多請關注TW511.COM其它相關文章！