• 技术文章 >后端开发 >php教程

    数组实现方式:PHP5 VS PHP7

    青灯夜游青灯夜游2021-09-02 19:27:38转载630
    本篇文章带大家来比较一下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 以双向链表的方式连接。

    1.png

      在 PHP 7 中,Bucket 按照数组元素写入的顺序依次存储,其索引值为 idx,该值存储在 *arData 左侧的映射区域中。idx 在映射区域中的索引为 nIndexnIndex 值为负数,由数组 keyhash 值与 nTableMask 进行或运算得到。

    2.png

    // 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 中数组元素的插入顺序以及 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,最终得到链表中第一个 Buckethash 碰撞链表的表头),即p

      如果是更新数组中已有的项,那么会从 p 开始遍历 hash 碰撞链表,直到找到 arkey 与给定的 key 相同的 Bucket,然后更新 pData

      如果是向数组中新增项,首先会判断给定的 key 是否为 interned string 类型,如果是,那么只需要为 Bucket 申请内存,然后将 p->arKey 指向给定的 key 的地址即可,否则在为新的 Bucket 申请内存的同时还需要为给定的 key 申请内存,然后将 p->arKey 指向为 key 申请的内存的地址。之后会对新申请的 Bucket 进行初始化,最后要做的两件事:维护 hash 碰撞链表和数组元素写入顺序链表。在维护 hash 碰撞的链表时,新增的 Bucket 是放在链表头的位置;维护数组元素写入顺序的链表时,新增的 Bucket 是放在链表的末尾,同时将 hashtablepListTail 指向新增的 Bucket

    关于 PHP 中的 interned string,之前在讲解 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;
    }

      这里需要先说明一下 nNumUsednNumOfElements 的区别:

    3.png

      按图中示例,此时 nNumUsed 的值应该为 5,但 nNumOfElements 的值则应该为 3。在 PHP 7 中,数组元素按照写入顺序依次存储,而 nNumUsed 正好可以用来充当数组元素存储位置索引的功能。

      另外就是 p = arData + idx ,前面已经讲过 arDataBucket 类型,这里 +idx 意为指针从 arData 的位置开始向右偏移 idxBucket 的位置。宏调用 HT_HASH_EX 也是同样的道理。

      最后就是 Z_NEXT(p->val),PHP 7 中的 Bucket 结构都内嵌了一个 zvalzval 中的联合体 u2 中有一项 next 用来记录hash 碰撞的信息。nIndex 用来标识 idx 在映射表中的位置,在往 hashtable 中新增元素时,如果根据给定的 key 计算得到的 nIndex 的位置已经有值(即发生了 hash 碰撞),那么此时需要将 nIndex 所指向的位置的原值记录到新增的元素所对应的 Bucket 下的 val.u2.next 中。宏调用 HT_IDX_TO_HASH 的作用是根据 idx 计算得到 Bucket 的以字节为单位的偏移量。

    ⒊ 删除元素

      在 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,然后找到 arBucketnIndex,最终找到需要删除的 Bucket 所在的 hash 碰撞的链表,通过遍历链表,找到最终需要删除的 Bucket

      在实际删除 Bucket 的过程中,主要做的就是维护两个链表:hash 碰撞链表和数组元素写入顺序链表。再就是释放内存。

      由于 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 为最后一项并且相邻的 BucketIS_UNDEF 时才会回收其内存空间。

    ⒋ 数组遍历

      由于 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 中数组的元素是按照写入的顺序存储,所以遍历的逻辑相对简单,只是在遍历过程中需要跳过被标记为 IS_UNDEF 的项。

    ⒌ hash 碰撞

      前面在谈论数组元素添加/修改的时候已有提及,每次在数组新增元素时,都会检查并处理 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 中的 hashtable 是通过 Bucket 中的 val.u2.next 项来维护 hash 碰撞的单向链表的。所以,在往 hashtable 中添加新的元素时,最后需要先将 nIndex 位置的值写入新增的 Bucketval.u2.next 中。而在删除 Bucket 时,需要同时找出要删除的 Bucket 所在的 hash 碰撞链表中的前一项,以便后续的 hash 碰撞链表的维护。

    ⒍ 扩容

      在数组元素新增/修改的 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 扩容的前提条件:数组中元素的数量超过 hashtablenTableSize 的值。之后,hashtablenTableSize 会翻倍,然后重新为 arBuckets 分配内存空间并且更新 nTableMask 的值。最后,由于 nTableMask 发生变化,需要根据数组元素的索引重新计算 nIndex,然后将之前的 Bucket 关联到新分配的 arBuckets 中新的位置。

      在 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 中,如果一个数组为索引数组,并且数组中的索引为升序排列,那么此时由于 hashtableBucket 按照写入顺序排列,而数组索引也是升序的,所以映射表已经没有必要。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

    推荐学习:《PHP视频教程

    以上就是数组实现方式:PHP5 VS PHP7的详细内容,更多请关注php中文网其它相关文章!

    声明:本文转载于:掘金社区,如有侵犯,请联系admin@php.cn删除
    上一篇:汇总!PHP操作MySQL的常用代码段 下一篇:分享实现PHP红包算法的思路(附开发代码)
    线上培训班

    相关文章推荐

    • 如何安装php7及安装memcache扩展出现新旧php版本兼容问题该怎么办• php7如何借鉴其他框架,写出自己的框架• 那些年我使用php7踩过的坑• 你不得不知道的php7小知识• 看一看!PHP7和5.6的压测对比来了

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网