前言

這幾天在翻github的時候, 碰巧看到了php的源碼, 就 down 下來隨便翻了翻. 地址: https://github.com/php/php-src

那么PHP中什么玩意最引人注目嘞? 一定是數組了, PHP中的數組太強大了, 于是就想著不如進去看看數組的實現部分. 這篇文章打算全程針對代碼進行解讀了.

以下代碼基于最新 php8.1. commitId: ea62b8089acef6551d6cece5dfb2ce0b040a7b83 .感興趣的可自行下載查看.

探究

首先, 如此強大的數組功能應該是有單獨文件進行定義的. 因此搜索了array.h array.c文件, 哎, array.c文件是存在的.

查看后發現, array.c文件中定義了PHP數組的系統函數, 比如krsort count等等. 但是, array的實現又在哪里呢?

隨便找一個方法array_flip, 其中第一行定義變量如下:

zval *array;

也就是說, 方法接收的參數是結構體zval. 但是, zval這個結構體看名字應該是變量而不是數組啊. 果然, 再看下面變量的使用:

拿到變量后, 判斷變量的類型, 會根據不同類型進行不同的處理.

那么這里為什么不直接接數組類型呢? 因為PHP的弱類型, 所有的變量都是zval, 其實際類型定義在zval結構體中. 這里順便看一下zval結構體的實現:

(從這里開始, 下方所有內容不再詳細說明查找過程, 反正就七找八找的)

zval

zval結構體定義在zend_types.h文件中, 這就是PHP弱類型的秘密了. 對其中各個部分的個人理解, 以注釋的形式添加到代碼中了.

/* * 其在 大端和小端 使用了不同的順序定義. * 想來是為了解決大小端環境的問題, 保證在不同的設備上可以讀取到相同的位 */ #ifdef WORDS_BIGENDIAN # define ZEND_ENDIAN_LOHI_3(lo, mi, hi) hi; mi; lo; #else # define ZEND_ENDIAN_LOHI_3(lo, mi, hi) lo; mi; hi; #endif// 對不同變量類型的定義 /* Regular data types: Must be in sync with zend_variables.c. */ #define IS_UNDEF 0 #define IS_NULL 1 #define IS_FALSE 2 // ...// 進行結構體的重命名 typedef struct _zval_struct zval;/* * 變量聯合體定義. * 此聯合體和保存各種類型的變量 */ typedef union _zend_value {zend_long lval; // 8Bdouble dval; // 8Bzend_refcounted *counted; // 引用計數. 8Bzend_string *str; // 字符串. 8Bzend_array *arr;zend_object *obj;zend_resource *res;zend_reference *ref;zend_ast_ref *ast;zval *zv;void *ptr;zend_class_entry *ce;zend_function *func;struct {uint32_t w1;uint32_t w2;} ww; // 8B } zend_value; // 綜上: 8B// 變量的結構體 struct _zval_struct {// 使用 zend_value 聯合體保存當前元素的值. 8Bzend_value value; /* value *//** 用來保存變量類型* 這里為什么要使用聯合體呢?* 眾所周知, 聯合體中變量是共用內存的* 而其中的兩個內容都是4字節的.* 因此, 我認為是為了方便使用.* 在統一操作時可使用 type_info, 有可以通過結構體分別獲取每一位* (不過這只是個人理解, 沒有進行求證)*/union {uint32_t type_info; // 4Bstruct {ZEND_ENDIAN_LOHI_3(// 用來保存當前變量的類型. 也就是上面的一批定義. 1Bzend_uchar type, /* active type */// 當前變量的一些標志位. 如: 常量類型/不可修改 等等. 1Bzend_uchar type_flags,union { // 2Buint16_t extra; /* not further specified */} u)} v; // 4B} u1; // 4B// 上面兩個結構體共占用 12B, 而內存對其需要16B, 因此有4個字節是空著的// 下面的聯合體可以將這4B 充分利用.// 這里根據不同的變量類型使用不同的變量. 比如: next, 在下面介紹數組的時候有用union {uint32_t next; /* hash collision chain */uint32_t cache_slot; /* cache slot (for RECV_INIT) */uint32_t opline_num; /* opline number (for FAST_CALL) */uint32_t lineno; /* line number (for ast nodes) */uint32_t num_args; /* arguments number for EX(This) */uint32_t fe_pos; /* foreach position */uint32_t fe_iter_idx; /* foreach iterator index */uint32_t property_guard; /* single property guard */uint32_t constant_flags; /* constant flags */uint32_t extra; /* not further specified */} u2; };

zend_array

在查看zval的時候, 應該注意到其中的zend_array類型了. 不用看了, 看名字也知道, 數組就是它了.

為了在下面查看數組結構體時, 這里對PHP中數組的實現做一個簡短的介紹.

結構介紹

眾所周知, PHP中數組是通過hashTable實現的, 但是hashTable又是如何保證讀取順序的呢? 通過如下兩個數組實現了一個有序 hash:

每次新增元素都向data 數組后面添加, 這樣foreach的時候遍歷data 數組, 讀到的順序就和放入的順序是一樣的了.

但是, 這不就是數組么? hash呢? 如何保證讀取的高效呢? 在第二個hash 數組中, hash 數組中保存的是元素在data 數組中的索引.

從數組中讀取keya 元素的步驟是這樣的:

計算a的hash值為2

idx=indexList[2]

data=dataList[idx]

那么hash沖突又是如何解決的呢? 對于哈希沖突, 目前有開放尋址和鏈表兩種處理方式, 不過大部分實現都采用鏈表的方式. 這里也不例外.

數組中, b c d 的hash值均為4, 他們三個直接組成一個鏈表. 而index 數組中保存鏈表頭的地址.

好, PHP數組的實現結構概念部分介紹完了. 接下來看一下PHP是如何實現的吧.

結構體

在介紹結構體代碼之前, 還是得先上一個圖. 在上方介紹中存在dataList indexList兩個數組. 在PHP的實現中, 或許是為了節省空間. 將這兩個數組合并成了一個, 只需要記錄一個地址. 如下圖:

上圖的說明是為了防止你看到結構體中的union會懵. 一樣的, 我將自己的理解放到注釋中了.

typedef struct _zend_array zend_array; // 沒毛病, 數組的別名就是 hashTable typedef struct _zend_array HashTable;// 用來保存數組中的數據 typedef struct _Bucket {// 當前元素值zval val;// 當前元素的 hashzend_ulong h; /* hash value (or numeric index) */// 元素的 keyzend_string *key; /* string key or NULL for numerics */ } Bucket;typedef struct _zend_array HashTable;struct _zend_array {zend_refcounted_h gc; // 對數組進行引用計數. 8Bunion {struct {ZEND_ENDIAN_LOHI_4(/** 標志位. 其常量定義如下:* #define HASH_FLAG_CONSISTENCY ((1<<0) | (1<<1))* #define HASH_FLAG_PACKED (1<<2)* #define HASH_FLAG_UNINITIALIZED (1<<3)* #define HASH_FLAG_STATIC_KEYS (1<<4) // long and interned strings* #define HASH_FLAG_HAS_EMPTY_IND (1<<5)* #define HASH_FLAG_ALLOW_COW_VIOLATION (1<<6)*/zend_uchar flags,zend_uchar _unused,zend_uchar nIteratorsCount,zend_uchar _unused2)} v;uint32_t flags; // 4B} u; // 4B// 用來保存數組中的元素信息. 這是一個數組, 記錄數組首地址.// 關于這里的 兩個數組為什么使用 聯合體記錄, 在上圖中解釋了. union {// 用來讀取上方的 hashList 8Buint32_t *arHash; /* hash table (allocated above this pointer) */// 用來讀取上方的 dataList 8BBucket *arData; /* array of hash buckets */// 當前數組中其實保存了兩個數組, 但是對于key是連續數字的數組來說, arrHash 其實并不需要. 可以直接使用數組存儲// 所以使用了 arPacked 來表示key全部為數字的, 通過標識位 HASH_FLAG_PACKED 來標識. 以節省內存占用// 所以, 其實對于連續數字的數組, 其底層真的是數組, 而不是 hashTable// 這里你可以簡單的實驗一下, 通過構造一個連續數字索引的數字, 然后在給其賦值一個key 為字符串的元素, 通過 memory_get_usage 函數查看內存的變化. 很明顯的. zval *arPacked; /* packed array of zvals */}; // 8B// 數組中存儲的元素個數. 4Buint32_t nNumOfElements;/** 向數組中添加元素時, 使用的數組索引. * 此變量與 nNumOfElements 的區別是,* 當數組中元素釋放的時候, 比如 unset 操作.* nNumOfElements 進行減一操作, 而 nNumUsed 變量不變.* 同時, 元素也并沒有從數組中抹去, 僅僅是將其 type 修改為 IS_UNDEF* 等到下一次內存擴充的時候, 在將這些元素釋放掉, 以保證釋放的高效* 4B*/uint32_t nNumUsed;// 記錄當前數組已經分配的地址大小. 2的 n 次冪(分配地址每次乘2). 4Buint32_t nTableSize;// 計算 key 的 hash 散列值時使用(在下方具體介紹). 4Buint32_t nTableMask;// 數組遍歷是使用的游標, 如調用函數: next/prev/end/reset/current 等. 4Buint32_t nInternalPointer;/** 用來記錄下一個元素插入時的默認 key.* 比如代碼:* $arr = [];* $arr[] = 1; // 相當于 $arr[0]=1;* 但是, 你或許會疑惑, 這還需要單獨記錄么? 直接使用數組的大小計算不就行了?* 再看一段:* $arr = [];* $arr['a'] = 1;* $arr[] = 2; // 相當于 $arr[0] = 1;* 是不是懂了??* 8B*/zend_long nNextFreeElement;/** 此方法在數組中的元素更新或刪除時調用.* 若元素是引用計數的類型, 會更新其引用計數* 相當于元素的析構函數* 8B*/dtor_func_t pDestructor; }; // 56B

nTableMask

nTableMask變量在計算元素的的散列值(在indexList中的索引)時使用.

首先在上面, indexList與dataList大小相等, 且都等于nTableSize. 也就是說, 散列值的取值范圍為: [-nTableSize, -1].

PHP中是如何處理的呢? 其計算規則為: nIndex = h | ht->nTableMask; 其中 nTableMask=-nTableSize.

這里簡單證明一下, 還記得上面提到過, nTableMask的取值為2的 n 次冪. 我們假設長度為16. (為了簡化邏輯, 以8byte 為例).

那么, nTableMask等于 -16, 其二進制補碼表示為: 11110000. 我們分別使用兩個極端值和nTableMask進行或運算.

11110000與00000000進行或運算, 結果為11110000, 其值等于-16.

11110000與01111111進行或運算, 結果為11111111, 其值等于 -1.

剛好與需要的取值范圍相等. 既然是通過變量nTableSize計算得到的, 為什么要單獨使用變量記錄呢? 我想是為了效率吧. 畢竟hash取值的操作是很頻繁的. 而位運算是很快的, 如果加上額外的計算操作會導致其效率下降.

數組插入操作

通過上面的介紹, 對于其插入操作應該如何實現想比心中有數了. 這里簡單羅列一下:

// 判斷需要時對數組進行擴容 #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \if ((ht)->nNumUsed >= (ht)->nTableSize) { \zend_hash_do_resize(ht); \}static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag) {// 一些額外處理...// 需要時對數組進行擴充ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */add_to_hash:// INTERNED 字符串不會被銷毀, 用來實現相同字符串共用內存// 當數組中所有key 都是 INTERNED 字符串// 那么數組釋放的時候就不需要釋放 key 了, 同時數組 copy 的時候也不需要增加字符串引用計數// HASH_FLAG_STATIC_KEYS 標記位就是用來標記數組中所有 key 均為 INTERNED 字符串// 若當前字符串不是 INTERNED 的, 則修改數組的標記位if (!ZSTR_IS_INTERNED(key)) {zend_string_addref(key);HT_FLAGS(ht) &= ~HASH_FLAG_STATIC_KEYS;}// 獲取當前元素的 dataList indexidx = ht->nNumUsed++;// 數組中元素內容增加ht->nNumOfElements++;// 元素賦值arData = ht->arData;p = arData + idx;p->key = key;p->h = h = ZSTR_H(key);// 計算 hashList indexnIndex = h | ht->nTableMask;// 這一步就是用來處理 hash 沖突的// 將當前元素的 next 指向原來 hashList 中的值Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);// 更新 hashListHT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);// 對 val 進行賦值. // 這里判斷標志位 HASH_LOOKUP, 然后將 val 置為 null. 這里看了半天沒看懂其作用, 如果有知道的還望不吝賜教if (flag & HASH_LOOKUP) {ZVAL_NULL(&p->val);} else {ZVAL_COPY_VALUE(&p->val, pData);}return &p->val; }

其他的數組操作函數這里就不再羅列了, 感興趣的下載源碼自己看一下吧.

hash 函數

在上面查看函數zend_hash_do_resize的時候, 突然想到了一個有意思的事情, 函數每次擴容都是乘2的操作. 如果說, 有一個長度為65536的數組, 每一個 key 的散列值計算后均為0, 那么hashTable不就退化為鏈表了么?

具體是什么思路呢? 第一個元素 key 為0, 那么根據長度取模, 第二個元素就是 65536, 第三個元素就是 65536*2, 這樣每次插入的時候都需要遍歷鏈表, 導致插入效率變慢. 整個demo 試一下.

<?php// 統計函數的耗時 function echoCallCostTime($msg, $call){$startTime = microtime(true) * 1000;$call();$endTime = microtime(true) * 1000;$diffTime = $endTime - $startTime;echo "$msg 耗時 $diffTime", PHP_EOL; }$size = 2**16; $array = []; echoCallCostTime('異常數組-構造', function () use ($size, &$array){$array = array();for ($i = 0; $i <= $size; $i++) {$key = $size * $i;$array[$key] = 0;} }); echoCallCostTime('異常數組-首個元素訪問', function () use ($array){$b = $array[0]; }); echoCallCostTime('異常數組-最后元素訪問', function () use ($array, $size){$b = $array[$size * $size]; }); echoCallCostTime('普通數組-構造', function () use ($size, &$array){$array = array();for ($i = 0; $i <= $size; $i++) {$array[$i] = 0;} }); echoCallCostTime('普通數組-首個元素訪問', function () use ($array){$b = $array[0]; }); echoCallCostTime('普通數組-最后元素訪問', function () use ($array, $size){$b = $array[$size]; });

我們先按照這個邏輯推理一下, 異常數組的構造一定比普通數組耗時要久, 因為每次插入都要遍歷鏈表嘛.

而且, 異常數組的首個元素訪問時間要更新, 因為它現在出在鏈表的末尾, 要想訪問它就要將鏈表遍歷一遍. 看下結果:

和之前的推論絲毫不差, 而且性能相差很多倍哦. 不過這里hash算法的具體實現我沒有看

原文鏈接: https://hujingnb.com/archives/746

總結

以上是生活随笔為你收集整理的PHP 数组的内部实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。