關於PHP5和PHP7中數組實現方式的比較總結

從 PHP 5 到 PHP 7 ,PHP 通過對 hashtable 數據結構和實現方式的修改,使得數組在內存占用和性能上有瞭很大的提升。

⒈ 數據結構

// PHP 5 中 hashtable 的數據結構定義
typedef struct bucket {
    ulong h;  /*對於索引數組,存儲 key 的原始值;對於關聯數組,存儲 key 的 hash 之後的值*/
    uint nKeyLength; /*關聯數組時存儲 key 的長度,索引數組此值為 0*/
    void *pData; /*指向數組 value 的地址*/
    void *pDataPtr; /*如果 value 為指針,則由 pDataPtr 記錄 vlaue,pData 則指向 pDataPtr*/
    // PHP 5 中數組元素的順序是固定的,無論什麼時候遍歷,數組元素總是與插入時的順序一致
    // PHP 5 中使用雙向鏈表來保證數組元素的順序,pListNext 和 pListLast 分別按照
    // 元素插入順序記錄當前 bucket 的下一個和上一個 bucket
    struct bucket *pListNext;
    struct bucket *pListLast;
    // PHP 5 使用拉鏈法解決 hash 碰撞,pNext 和 pLast 分別存儲當前 bucket
    // 在沖突的雙向鏈表中的下一個和上一個相鄰的 bucket
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey; /*關聯數組是存儲 key 的原始值*/
} Bucket;

typedef struct _hashtable {
    uint nTableSize; /*當前 ht 所分配的 bucket 的總數,2^n*/
    uint nTableMask; /*nTableSize - 1,用於計算索引*/
    uint nNumOfElements; /*實際存儲的元素的數量*/
    ulong nNextFreeElement; /*下一個可以被使用的整數 key*/
    Bucket *pInternalPointer; /*數組遍歷時,記錄當前 bucket 的地址*/
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets; /*記錄 bucket 的 C 語言數組*/
    dtor_func_t pDestructor; /*刪除數組元素時內部調用的函數*/
    zend_bool persistent; /*標識 ht 是否永久有效*/
    unsigned char nApplyCount; /*ht 允許的最大遞歸深度*/
    zend_bool bApplyProtection; /*是否啟用遞歸保護*/
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

// PHP 7 中 hashtable 的數據結構
// PHP 7 中個子版本以及階段版本中對 hashtable 的數據結構的定義會有微小的差別,這裡使用的是 PHP 7.4.0 中的定義 
struct _zend_string { 
    zend_refcounted_h gc;
    zend_ulong        h;  /*字符串 key 的 hash 值*/
    size_t            len;  /*字符串 key 的長度*/
    char              val[1]; /*存儲字符串的值,利用瞭 struct hack*/
};

typedef struct _Bucket {
    zval              val;  /*內嵌 zval 結構,存儲數組的 value 值*/
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

typedef struct _zend_array HashTable;

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; /*作用與 PHP 5 中 hashtable 中 nTableMask 作用相同,但實現邏輯稍有變化*/
    Bucket           *arData; /*存儲 bucket 相關的信息*/
    uint32_t          nNumUsed; /*ht 中已經使用的 bucket 的數量,在 nNumOfElements 的基礎上加上刪除的 key*/
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

  不考慮其他開銷,單從 Bucket 所占用的空間來看:在 PHP 5 中,考慮到內存對齊,一個 Bucket 占用的空間為 72 字節;在 PHP 7 中,一個 zend_value 占 8 字節,一個 zval 占 16 字節,一個 Bucket 占 32 字節。相比之下,PHP 7 中 Bucket 的內存空間消耗比 PHP 5 低瞭一半以上。

具體 PHP 5 數組的內存消耗情況,之前的文章已有講解,這裡不再贅述

  現在來談談 Bucket 的存儲:在 PHP 5 中,arBucket 是一個 C 語言數組,長度為 nTableSize,存儲的是指向 Bucket 的指針,發生 hash 碰撞的 Bucket 以雙向鏈表的方式連接。

  在 PHP 7 中,Bucket 按照數組元素寫入的順序依次存儲,其索引值為 idx,該值存儲在 *arData 左側的映射區域中。idx 在映射區域中的索引為 nIndex,nIndex 值為負數,由數組 key 的 hash 值與 nTableMask 進行或運算得到。

// nTableMask 為 -2 倍的 nTableSize 的無符號表示
#define HT_SIZE_TO_MASK(nTableSize) \
    ((uint32_t)(-((nTableSize) + (nTableSize))))

// 在通過 idx 查找 Bucket 時,data 默認為 Bucket 類型,加 idx 表示向右偏移 idx 個 Bucket 位置
# define HT_HASH_TO_BUCKET_EX(data, idx) \
    ((data) + (idx))

// 在通過 nIndex 查找 idx 時,
// (uint32_t*)(data) 首先將 data 轉換成瞭 uint32_t* 類型的數組
// 然後將 nIndex 轉換成有符號數(負數),然後以數組的方式查找 idx 的值
#define HT_HASH_EX(data, idx) \
    ((uint32_t*)(data))[(int32_t)(idx)]

nIndex = h | ht->nTableMask;
idx = HT_HASH_EX(arData, nIndex);
p = HT_HASH_TO_BUCKET_EX(arData, idx);

  這裡需要指出,nTableMask 之所以設置為 nTableSize 的兩倍,是這樣在計算 nIndex 時可以減小 hash 碰撞的概率。

⒉ 添加/修改元素

PHP 5

  先來談談 PHP 5 中數組元素的添加和修改,由於 PHP 5 中數組元素的插入順序以及 hash 碰撞都是通過雙向鏈表的方式來維護,所以雖然實現起來有些復雜,但理解起來相對容易一些。

// hash 碰撞雙向鏈表的維護
#define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
    (element)->pNext = (list_head);                         \
    (element)->pLast = NULL;                                \
    if ((element)->pNext) {                                 \
        (element)->pNext->pLast = (element);                \
    }

#define CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, last, next)\
    (element)->pListLast = (last);                          \
    (element)->pListNext = (next);                          \
    if ((last) != NULL) {                                   \
        (last)->pListNext = (element);                      \
    } else {                                                \
        (ht)->pListHead = (element);                        \
    }                                                       \
    if ((next) != NULL) {                                   \
        (next)->pListLast = (element);                      \
    } else {                                                \
        (ht)->pListTail = (element);                        \
    }                                                       \
// 數組元素插入順序雙向鏈表的維護
#define CONNECT_TO_GLOBAL_DLLIST(element, ht)                                   \
    CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, (ht)->pListTail, (Bucket *) NULL); \
    if ((ht)->pInternalPointer == NULL) {                                       \
        (ht)->pInternalPointer = (element);                                     \
    }
// 數組元素的更新
#define UPDATE_DATA(ht, p, pData, nDataSize)                                            \
    if (nDataSize == sizeof(void*)) {                                                   \
        // 值為指針類型的元素的更新                                                         \
        if ((p)->pData != &(p)->pDataPtr) {                                             \
            pefree_rel((p)->pData, (ht)->persistent);                                   \
        }                                                                               \
        // pDataPtr 存儲元素值的地址,pData 存儲 pDataPtr 的地址                             \
        memcpy(&(p)->pDataPtr, pData, sizeof(void *));                                  \
        (p)->pData = &(p)->pDataPtr;                                                    \
    } else {                                                                            \
        // 如果數組元素為值類型,則存入 pData,此時 pDataPtr 為 Null                          \
        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);                                           \
    }
// 數組元素的初始化
#define INIT_DATA(ht, p, _pData, nDataSize);                                \
    if (nDataSize == sizeof(void*)) {                                   \
        // 指針類型元素的初始化                                            \
        memcpy(&(p)->pDataPtr, (_pData), sizeof(void *));                   \
        (p)->pData = &(p)->pDataPtr;                                    \
    } else {                                                            \
        // 值類型元素的初始化                                                \
        (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
        memcpy((p)->pData, (_pData), nDataSize);                            \
        (p)->pDataPtr=NULL;                                             \
    }
// hashtable 初始化校驗,如果沒有初始化,則初始化 hashtable
#define CHECK_INIT(ht) do {                                             \
    if (UNEXPECTED((ht)->nTableMask == 0)) {                                \
        (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);   \
        (ht)->nTableMask = (ht)->nTableSize - 1;                        \
    }                                                                   \
} while (0)
// 數組元素的新增或更新(精簡掉瞭一些宏調用和代碼片段)
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
    ulong h;
    uint nIndex;
    Bucket *p;

    CHECK_INIT(ht);
    
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if (p->arKey == arKey ||
            ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
                // 數組元素更新邏輯
                if (flag & HASH_ADD) {
                    return FAILURE;
                }
                ZEND_ASSERT(p->pData != pData);
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                    *pDest = p->pData;
                }
                return SUCCESS;
        }
        p = p->pNext;
    }    
    // 數組元素新增邏輯
    if (IS_INTERNED(arKey)) {
        p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
        p->arKey = arKey;
    } else {
        p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
        p->arKey = (const char*)(p + 1);
        memcpy((char*)p->arKey, arKey, nKeyLength);
    }    
    p->nKeyLength = nKeyLength;
    INIT_DATA(ht, p, pData, nDataSize);
    p->h = h; 
    // hash 碰撞鏈表維護
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
    if (pDest) {
        *pDest = p->pData;
    }
    // 數組元素寫入順序維護
    CONNECT_TO_GLOBAL_DLLIST(p, ht);
    ht->arBuckets[nIndex] = p;

    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
    return SUCCESS;
}

  PHP 5 中的數組在新增或修改元素時,首先會根據給定的 key 計算得到相應的 hash 值,然後據此得到 arBuckets 的索引 nIndex,最終得到鏈表中第一個 Bucket( hash 碰撞鏈表的表頭),即p。

  如果是更新數組中已有的項,那麼會從 p 開始遍歷 hash 碰撞鏈表,直到找到 arkey 與給定的 key 相同的 Bucket,然後更新 pData。

  如果是向數組中新增項,首先會判斷給定的 key 是否為 interned string 類型,如果是,那麼隻需要為 Bucket 申請內存,然後將 p->arKey 指向給定的 key 的地址即可,否則在為新的 Bucket 申請內存的同時還需要為給定的 key 申請內存,然後將 p->arKey 指向為 key 申請的內存的地址。之後會對新申請的 Bucket 進行初始化,最後要做的兩件事:維護 hash 碰撞鏈表和數組元素寫入順序鏈表。在維護 hash 碰撞的鏈表時,新增的 Bucket 是放在鏈表頭的位置;維護數組元素寫入順序的鏈表時,新增的 Bucket 是放在鏈表的末尾,同時將 hashtable 的 pListTail 指向新增的 Bucket。

關於 PHP 中的 interned string,之前在講解 PHP 7 對字符串處理邏輯優化的時候已經說明,這裡不再贅述

PHP 7

  PHP 7 在 hashtable 的數據結構上做瞭比較大的改動,同時放棄瞭使用雙向鏈表的方式來維護 hash 碰撞和數組元素的寫入順序,在內存管理以及性能上得到瞭提升,但理解起來卻不如 PHP 5 中的實現方式直觀。

#define Z_NEXT(zval)                (zval).u2.next
#define HT_HASH_EX(data, idx) \
    ((uint32_t*)(data))[(int32_t)(idx)]
# define HT_IDX_TO_HASH(idx) \
    ((idx) * sizeof(Bucket))

// PHP 7 中數組添加/修改元素(精簡瞭部分代碼)
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag)
{
	zend_ulong h;
	uint32_t nIndex;
	uint32_t idx;
	Bucket *p, *arData;

	/*... ...*/

	ZEND_HASH_IF_FULL_DO_RESIZE(ht);		/* If the Hash table is full, resize it */

add_to_hash:
	idx = ht->nNumUsed++;
	ht->nNumOfElements++;
	arData = ht->arData;
	p = arData + idx;
	p->key = key;
	p->h = h = ZSTR_H(key);
	nIndex = h | ht->nTableMask;
	Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
	HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
	ZVAL_COPY_VALUE(&p->val, pData);

	return &p->val;
}

  這裡需要先說明一下 nNumUsed 和 nNumOfElements 的區別:

  按圖中示例,此時 nNumUsed 的值應該為 5,但 nNumOfElements 的值則應該為 3。在 PHP 7 中,數組元素按照寫入順序依次存儲,而 nNumUsed 正好可以用來充當數組元素存儲位置索引的功能。

  另外就是 p = arData + idx ,前面已經講過 arData 為 Bucket 類型,這裡 +idx 意為指針從 arData 的位置開始向右偏移 idx 個 Bucket 的位置。宏調用 HT_HASH_EX 也是同樣的道理。

  最後就是 Z_NEXT(p->val),PHP 7 中的 Bucket 結構都內嵌瞭一個 zval,zval 中的聯合體 u2 中有一項 next 用來記錄hash 碰撞的信息。nIndex 用來標識 idx 在映射表中的位置,在往 hashtable 中新增元素時,如果根據給定的 key 計算得到的 nIndex 的位置已經有值(即發生瞭 hash 碰撞),那麼此時需要將 nIndex 所指向的位置的原值記錄到新增的元素所對應的 Bucket 下的 val.u2.next 中。宏調用 HT_IDX_TO_HASH 的作用是根據 idx 計算得到 Bucket 的以字節為單位的偏移量。

⒊ 刪除元素

PHP 5

  在 PHP 5 中,數組元素的刪除過程中的主要工作是維護 hash 碰撞鏈表和數組元素寫入順序的鏈表。

// 刪除 Bucket 的代碼(精簡瞭部分代碼片段)
static zend_always_inline void i_zend_hash_bucket_delete(HashTable *ht, Bucket *p)
{
    if (p->pLast) {
        p->pLast->pNext = p->pNext;
    } else {
        ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
    }
    if (p->pNext) {
        p->pNext->pLast = p->pLast;
    }
    if (p->pListLast != NULL) {
        p->pListLast->pListNext = p->pListNext;
    } else {
        /* Deleting the head of the list */
        ht->pListHead = p->pListNext;
    }
    if (p->pListNext != NULL) {
        p->pListNext->pListLast = p->pListLast;
    } else {
        /* Deleting the tail of the list */
        ht->pListTail = p->pListLast;
    }
    if (ht->pInternalPointer == p) {
        ht->pInternalPointer = p->pListNext;
    }
    ht->nNumOfElements--;
    if (ht->pDestructor) {
        ht->pDestructor(p->pData);
    }
    if (p->pData != &p->pDataPtr) {
        pefree(p->pData, ht->persistent);
    }
    pefree(p, ht->persistent);
}
// 元素刪除
ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
{
    uint nIndex;
    Bucket *p;

    if (flag == HASH_DEL_KEY) {
        h = zend_inline_hash_func(arKey, nKeyLength);
    }
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if ((p->h == h)
             && (p->nKeyLength == nKeyLength)
             && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
                 || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
            i_zend_hash_bucket_delete(ht, p);
            return SUCCESS;
        }
        p = p->pNext;
    }
    return FAILURE;
}

  PHP 5 中數組在刪除元素時,仍然是先根據給定的 key 計算 hash,然後找到 arBucket 的 nIndex,最終找到需要刪除的 Bucket 所在的 hash 碰撞的鏈表,通過遍歷鏈表,找到最終需要刪除的 Bucket。

  在實際刪除 Bucket 的過程中,主要做的就是維護兩個鏈表:hash 碰撞鏈表和數組元素寫入順序鏈表。再就是釋放內存。

PHP 7

  由於 PHP 7 記錄 hash 碰撞信息的方式發生瞭變化,所以在刪除元素時處理 hash 碰撞鏈表的邏輯也會有所不同。另外,在刪除元素時,還有可能會遇到空間回收的情況。

#define IS_UNDEF                    0
#define Z_TYPE_INFO(zval)           (zval).u1.type_info
#define Z_TYPE_INFO_P(zval_p)       Z_TYPE_INFO(*(zval_p))
#define ZVAL_UNDEF(z) do {              \
        Z_TYPE_INFO_P(z) = IS_UNDEF;    \
    } while (0)
    
static zend_always_inline void _zend_hash_del_el_ex(HashTable *ht, uint32_t idx, Bucket *p, Bucket *prev)
{
    // 從 hash 碰撞鏈表中刪除指定的 Bucket
    if (!(HT_FLAGS(ht) & HASH_FLAG_PACKED)) {
        if (prev) {
            Z_NEXT(prev->val) = Z_NEXT(p->val);
        } else {
            HT_HASH(ht, p->h | ht->nTableMask) = Z_NEXT(p->val);
        }
    }
    idx = HT_HASH_TO_IDX(idx);
    ht->nNumOfElements--;
    if (ht->nInternalPointer == idx || UNEXPECTED(HT_HAS_ITERATORS(ht))) {
        // 如果當前 hashtable 的內部指針指向瞭要刪除的 Bucket 或當前 hashtable 有遍歷
        // 操作,那麼需要避開當前正在被刪除的 Bucket
        uint32_t new_idx;
        
        new_idx = idx;
        while (1) {
            new_idx++;
            if (new_idx >= ht->nNumUsed) {
                break;
            } else if (Z_TYPE(ht->arData[new_idx].val) != IS_UNDEF) {
                break;
            }
        }
        if (ht->nInternalPointer == idx) {
            ht->nInternalPointer = new_idx;
        }
        zend_hash_iterators_update(ht, idx, new_idx);
    }
    if (ht->nNumUsed - 1 == idx) {
        //如果被刪除的 Bucket 在數組的末尾,則同時回收與 Bucket 相鄰的已經被刪除的 Bucket 的空間
        do {
            ht->nNumUsed--;
        } while (ht->nNumUsed > 0 && (UNEXPECTED(Z_TYPE(ht->arData[ht->nNumUsed-1].val) == IS_UNDEF)));
        ht->nInternalPointer = MIN(ht->nInternalPointer, ht->nNumUsed);
    }
    if (p->key) {
        // 刪除 string 類型的索引
        zend_string_release(p->key);
    }
    // 刪除 Bucket
    if (ht->pDestructor) {
        zval tmp;
        ZVAL_COPY_VALUE(&tmp, &p->val);
        ZVAL_UNDEF(&p->val);
        ht->pDestructor(&tmp);
    } else {
        ZVAL_UNDEF(&p->val);
    }
}

static zend_always_inline void _zend_hash_del_el(HashTable *ht, uint32_t idx, Bucket *p)
{
    Bucket *prev = NULL;

    if (!(HT_FLAGS(ht) & HASH_FLAG_PACKED)) {
        // 如果被刪除的 Bucket 存在 hash 碰撞的情況,那麼需要找出其在 hash 碰撞鏈表中的位置
        uint32_t nIndex = p->h | ht->nTableMask;
        uint32_t i = HT_HASH(ht, nIndex);

        if (i != idx) {
            prev = HT_HASH_TO_BUCKET(ht, i);
            while (Z_NEXT(prev->val) != idx) {
                i = Z_NEXT(prev->val);
                prev = HT_HASH_TO_BUCKET(ht, i);
            }
        }
    }

    _zend_hash_del_el_ex(ht, idx, p, prev);
}

ZEND_API void ZEND_FASTCALL zend_hash_del_bucket(HashTable *ht, Bucket *p)
{
    IS_CONSISTENT(ht);
    HT_ASSERT_RC1(ht);
    _zend_hash_del_el(ht, HT_IDX_TO_HASH(p - ht->arData), p);
}

  PHP 7 中數組元素的刪除,其最終目的是刪除指定的 Bucket。在刪除 Bucket 時還需要處理好 hash 碰撞鏈表維護的問題。由於 PHP 7 中 hash 碰撞隻維護瞭一個單向鏈表(通過 Bucket.val.u2.next 來維護),所以在刪除 Bucket 時還需要找出 hash 碰撞鏈表中的前一項 prev。最後,在刪除 Bucket 時如果當前的 hashtable 的內部指針(nInternalPointer)正好指向瞭要刪除的 Bucket 或存在遍歷操作,那麼需要改變內部指針的指向,同時在遍歷時跳過要刪除的 Bucket。另外需要指出的是,並不是每一次刪除 Bucket 的操作都會回收相應的內存空間,通常刪除 Bucket 隻是將其中 val 的類型標記為 IS_UNDEF,隻有在擴容或要刪除的 Bucket 為最後一項並且相鄰的 Bucket 為 IS_UNDEF 時才會回收其內存空間。

⒋ 數組遍歷

PHP 5

  由於 PHP 5 中有專門用來記錄數組元素寫入順序的雙向鏈表,所以數組的遍歷邏輯相對比較簡單。

// 數組的正向遍歷
ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos)
{
    HashPosition *current = pos ? pos : &ht->pInternalPointer;

    IS_CONSISTENT(ht);

    if (*current) {
        *current = (*current)->pListNext;
        return SUCCESS;
    } else
        return FAILURE;
}
// 數組的反向遍歷
ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos)
{
    HashPosition *current = pos ? pos : &ht->pInternalPointer;

    IS_CONSISTENT(ht);

    if (*current) {
        *current = (*current)->pListLast;
        return SUCCESS;
    } else
        return FAILURE;
}

  PHP 5 中 hashtable 的數據結構中有三個字段:pInternalPointer 用來記錄數組遍歷過程中指針指向的當前 Bucket 的地址;pListHead 用來記錄保存數組元素寫入順序的雙向鏈表的表頭;pListTail 用來記錄保存數組元素寫入順序的雙向鏈表的表尾。數組的正向遍歷從 pListHead 的位置開始,通過不斷更新 pInternalPointer 來實現;反向遍歷從 pListTail 開始,通過不斷更新 pInternalPointer 來實現。

PHP 7

  由於 PHP 7 中數組的元素是按照寫入的順序存儲,所以遍歷的邏輯相對簡單,隻是在遍歷過程中需要跳過被標記為 IS_UNDEF 的項。

⒌ hash 碰撞

PHP 5

  前面在談論數組元素添加/修改的時候已有提及,每次在數組新增元素時,都會檢查並處理 hash 碰撞,即 CONNECT_TO_BUCKET_DLLIST,代碼如下

CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);

#define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
    (element)->pNext = (list_head);                         \
    (element)->pLast = NULL;                                \
    if ((element)->pNext) {                                 \
        (element)->pNext->pLast = (element);                \
    }

  在新增元素時,如果當前 arBuckets 的位置沒有其他元素,那麼隻需要直接寫入新增的 Bucket 即可,否則新增的 Bucket 會被寫入 hash 碰撞雙向鏈表的表頭位置。

PHP 7

  前面已經講過,PHP 7 中的 hashtable 是通過 Bucket 中的 val.u2.next 項來維護 hash 碰撞的單向鏈表的。所以,在往 hashtable 中添加新的元素時,最後需要先將 nIndex 位置的值寫入新增的 Bucket 的 val.u2.next 中。而在刪除 Bucket 時,需要同時找出要刪除的 Bucket 所在的 hash 碰撞鏈表中的前一項,以便後續的 hash 碰撞鏈表的維護。

⒍ 擴容

PHP 5

  在數組元素新增/修改的 API 中的最後有一行代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht) 來判斷當前 hashtable 是否需要擴容,如果需要則對其進行擴容。

// 判斷當前 hashtable 是否需要擴容
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht)             \
    if ((ht)->nNumOfElements > (ht)->nTableSize) {  \
        zend_hash_do_resize(ht);                    \
    }
// hashtable 擴容(精簡部分代碼)
ZEND_API int zend_hash_do_resize(HashTable *ht)
{
    Bucket **t;

    if ((ht->nTableSize << 1) > 0) {    /* Let's double the table size */
        t = (Bucket **) perealloc(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
        ht->arBuckets = t;
        ht->nTableSize = (ht->nTableSize << 1);
        ht->nTableMask = ht->nTableSize - 1;
        zend_hash_rehash(ht);
    }
}
// 擴容後對 hashtable 中的元素進行 rehash(精簡部分代碼)
ZEND_API int zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint nIndex;

    if (UNEXPECTED(ht->nNumOfElements == 0)) {
        return SUCCESS;
    }

    memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
    for (p = ht->pListHead; p != NULL; p = p->pListNext) {
        nIndex = p->h & ht->nTableMask;
        CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
        ht->arBuckets[nIndex] = p;
    }
    return SUCCESS;
}

  首先,PHP 5 hashtable 擴容的前提條件:數組中元素的數量超過 hashtable 的 nTableSize 的值。之後,hashtable 的 nTableSize 會翻倍,然後重新為 arBuckets 分配內存空間並且更新 nTableMask 的值。最後,由於 nTableMask 發生變化,需要根據數組元素的索引重新計算 nIndex,然後將之前的 Bucket 關聯到新分配的 arBuckets 中新的位置。

PHP 7

  在 PHP 7 的新增/修改 hashtable 的 API 中也有判斷是否需要擴容的代碼 ZEND_HASH_IF_FULL_DO_RESIZE(ht),當滿足條件時則會執行擴容操作。

#define HT_SIZE_TO_MASK(nTableSize) \
    ((uint32_t)(-((nTableSize) + (nTableSize))))
#define HT_HASH_SIZE(nTableMask) \
    (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t))
#define HT_DATA_SIZE(nTableSize) \
    ((size_t)(nTableSize) * sizeof(Bucket))
#define HT_SIZE_EX(nTableSize, nTableMask) \
    (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask)))

#define HT_SET_DATA_ADDR(ht, ptr) do { \
        (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); \
    } while (0)
#define HT_GET_DATA_ADDR(ht) \
    ((char*)((ht)->arData) - HT_HASH_SIZE((ht)->nTableMask))
// 當 hashtable 的 nNumUsed 大於或等於 nTableSize 時則執行擴容操作
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht)             \
    if ((ht)->nNumUsed >= (ht)->nTableSize) {       \
        zend_hash_do_resize(ht);                    \
    }
    
# define HT_HASH_RESET(ht) \
    memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))

#define HT_IS_WITHOUT_HOLES(ht) \
    ((ht)->nNumUsed == (ht)->nNumOfElements)
// 擴容(精簡部分代碼)
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
    if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
        zend_hash_rehash(ht);
    } else if (ht->nTableSize < HT_MAX_SIZE) {  /* Let's double the table size */
        void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
        uint32_t nSize = ht->nTableSize + ht->nTableSize;
        Bucket *old_buckets = ht->arData;

        ht->nTableSize = nSize;
        new_data = pemalloc(HT_SIZE_EX(nSize, HT_SIZE_TO_MASK(nSize)), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
        ht->nTableMask = HT_SIZE_TO_MASK(ht->nTableSize);
        HT_SET_DATA_ADDR(ht, new_data);
        memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
        pefree(old_data, GC_FLAGS(ht) & IS_ARRAY_PERSISTENT);
        zend_hash_rehash(ht);
    } else {
        zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
    }
}
// rehash(精簡部分代碼)
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint32_t nIndex, i;

    if (UNEXPECTED(ht->nNumOfElements == 0)) {
        if (!(HT_FLAGS(ht) & HASH_FLAG_UNINITIALIZED)) {
            ht->nNumUsed = 0;
            HT_HASH_RESET(ht);
        }
        return SUCCESS;
    }

    HT_HASH_RESET(ht);
    i = 0;
    p = ht->arData;
    if (HT_IS_WITHOUT_HOLES(ht)) {
    // Bucket 中沒有被標記為 IS_UNDEF 的項
        do {
            nIndex = p->h | ht->nTableMask;
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        } while (++i < ht->nNumUsed);
    } else {
    // Bucket 中有被標記為 IS_UNDEF 的項
        uint32_t old_num_used = ht->nNumUsed;
        do {
            if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
            // Bucket 中第一項被標記為 IS_UNDEF
                uint32_t j = i;
                Bucket *q = p;

                if (EXPECTED(!HT_HAS_ITERATORS(ht))) {
                // hashtable 沒有遍歷操作
                    while (++i < ht->nNumUsed) {
                        p++;
                        if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                            ZVAL_COPY_VALUE(&q->val, &p->val);
                            q->h = p->h;
                            nIndex = q->h | ht->nTableMask;
                            q->key = p->key;
                            Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                            if (UNEXPECTED(ht->nInternalPointer == i)) {
                                ht->nInternalPointer = j;
                            }
                            q++;
                            j++;
                        }
                    }
                } else {
                // hashtable 存在遍歷操作
                    uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0);

                    while (++i < ht->nNumUsed) {
                        p++;
                        if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                            ZVAL_COPY_VALUE(&q->val, &p->val);
                            q->h = p->h;
                            nIndex = q->h | ht->nTableMask;
                            q->key = p->key;
                            Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                            if (UNEXPECTED(ht->nInternalPointer == i)) {
                                ht->nInternalPointer = j;
                            }
                            if (UNEXPECTED(i >= iter_pos)) {
                                do {
                                    zend_hash_iterators_update(ht, iter_pos, j);
                                    iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
                                } while (iter_pos < i);
                            }
                            q++;
                            j++;
                        }
                    }
                }
                ht->nNumUsed = j;
                break;
            }
            nIndex = p->h | ht->nTableMask;
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        } while (++i < ht->nNumUsed);

        /* Migrate pointer to one past the end of the array to the new one past the end, so that
         * newly inserted elements are picked up correctly. */
        if (UNEXPECTED(HT_HAS_ITERATORS(ht))) {
            _zend_hash_iterators_update(ht, old_num_used, ht->nNumUsed);
        }
    }
    return SUCCESS;
}

  PHP 7 中 hashtable 在擴容時也是將 nTableSize 翻倍,然後進行 rehash。在進行 rehash 操作時,如果 Bucket 中沒有標記為刪除的項(IS_UNDEF),那麼 rehash 操作之後 Bucket 的存儲順序不會發生任何變化,隻是 idx 索引存儲的位置會因為 nTableMask 的變化而變化,最終導致 hash 碰撞鏈表的變化。如果 Bucket 中存在被標記為刪除的項,那麼在 rehash 的過程中會跳過這些 Bucket 項,隻保留那些沒有被刪除的項。同時,由於這樣會導致 Bucket 的索引相較於原來發生變化,所以在 rehash 的過程中需要同時更新 hashtable 內部指針的信息以及與遍歷操作相關的信息。

⒎ PHP 7 中的 packed hashtable

  在 PHP 7 中,如果一個數組為索引數組,並且數組中的索引為升序排列,那麼此時由於 hashtable 中 Bucket 按照寫入順序排列,而數組索引也是升序的,所以映射表已經沒有必要。PHP 7 針對這種特殊的情況對 hashtable 做瞭一些優化 packed hashtable。

#define HT_MIN_MASK ((uint32_t) -2)
#define HT_MIN_SIZE 8

#define HT_HASH_RESET_PACKED(ht) do { \
        HT_HASH(ht, -2) = HT_INVALID_IDX; \
        HT_HASH(ht, -1) = HT_INVALID_IDX; \
    } while (0)


static zend_always_inline void zend_hash_real_init_packed_ex(HashTable *ht)
{
    void *data;

    if (UNEXPECTED(GC_FLAGS(ht) & IS_ARRAY_PERSISTENT)) {
        data = pemalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), 1);
    } else if (EXPECTED(ht->nTableSize == HT_MIN_SIZE)) {
        data = emalloc(HT_SIZE_EX(HT_MIN_SIZE, HT_MIN_MASK));
    } else {
        data = emalloc(HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK));
    }
    HT_SET_DATA_ADDR(ht, data);
    /* Don't overwrite iterator count. */
    ht->u.v.flags = HASH_FLAG_PACKED | HASH_FLAG_STATIC_KEYS;
    HT_HASH_RESET_PACKED(ht);
}

  packed hashtable 在初始化時,nTableMask 的值默認為 -2,同時在 hashtable 的 flags 中會進行相應的標記。如果此時 packed hashtable 中沒有任何元素,那麼 nTableSize 會設為 0。

static void ZEND_FASTCALL zend_hash_packed_grow(HashTable *ht)
{
    HT_ASSERT_RC1(ht);
    if (ht->nTableSize >= HT_MAX_SIZE) {
        zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket), sizeof(Bucket));
    }
    ht->nTableSize += ht->nTableSize;
    HT_SET_DATA_ADDR(ht, perealloc2(HT_GET_DATA_ADDR(ht), HT_SIZE_EX(ht->nTableSize, HT_MIN_MASK), HT_USED_SIZE(ht), GC_FLAGS(ht) & IS_ARRAY_PERSISTENT));
}

  另外,packed hashtable 在擴容時,隻需要將 nTableSize 翻倍,同時由於索引是升序排列的,所以 Bucket 的順序不需要做任何調整,隻需要重新分配內存空間即可。

需要強調的是,packed hashtable 隻適用於索引為升序排列的索引數組(索引不一定要連續,中間可以有間隔)。如果索引數組的索引順序被破壞,或索引中加入瞭字符串索引,那麼此時 packed hashtable 會被轉換為普通的 hashtable。

總結

到此這篇關於PHP5和PHP7中數組實現方式比較的文章就介紹到這瞭,更多相關PHP5和PHP7數組實現比較內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: