摘要：中以表示所有的變量，它是一個(gè)結(jié)構(gòu)體。類型是一個(gè)聯(lián)合體，共占用。字段表示字符串的哈希值，在數(shù)組的中有用，方便快速定位。字段表示字符串長(zhǎng)度這里就是一個(gè)柔性數(shù)組，在等源碼中也被大量使用。

baiyan

全部視頻：https://segmentfault.com/a/11...

源視頻地址：http://replay.xesv5.com/ll/24...

變量本質(zhì)上就是給一段內(nèi)存空間起了個(gè)名字

如果讓我們自己基于C語(yǔ)言設(shè)計(jì)一個(gè)存儲(chǔ)如$a = 1變量的數(shù)據(jù)結(jié)構(gòu)，應(yīng)該如何設(shè)計(jì)？

變量的基本要素是類型與值，其中部分類型還有其他的描述字段（如長(zhǎng)度等）

首先應(yīng)該定義一個(gè)結(jié)構(gòu)體作為基本的數(shù)據(jù)結(jié)構(gòu)

第一個(gè)問(wèn)題：變量類型如何存儲(chǔ)？ 答：用一個(gè)unsigned char類型的字段存足夠，因?yàn)閡nsigned char類型最多能夠表示2^8 = 256種類型。

PHP7中以zval表示所有的變量，它是一個(gè)結(jié)構(gòu)體。先看zval的基本結(jié)構(gòu)：

typedef unsigned char zend_uchar;

struct _zval_struct {
    zend_value        value;            /* 存儲(chǔ)變量的zhi*/
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(             //大小端問(wèn)題，詳情看"PHP內(nèi)存管理3筆記”
                zend_uchar    type,         //注意這里就是存放變量類型的地方，char類型
                zend_uchar    type_flags,   //類型標(biāo)記
                zend_uchar    const_flags,  //是否是常量
                zend_uchar    reserved)        //保留字段
        } v;
        uint32_t type_info;
    } u1;
    union {
        uint32_t     next;                 /* 數(shù)組模擬鏈表，在下文鏈地址法解決哈希沖突時(shí)使用 */
        uint32_t     cache_slot;           /* literal cache slot */
        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     access_flags;         /* class constant access flags */
        uint32_t     property_guard;       /* single property guard */
        uint32_t     extra;                /* not further specified */
    } u2;
};

注意關(guān)注中文注釋的部分，PHP就是利用C語(yǔ)言的unsigned char類型，存儲(chǔ)了所有變量的類型。

在PHP中，所有變量的類型如下：

/* regular data types */
#define IS_UNDEF                    0
#define IS_NULL                        1
#define IS_FALSE                    2
#define IS_TRUE                        3
#define IS_LONG                        4
#define IS_DOUBLE                    5
#define IS_STRING                    6
#define IS_ARRAY                    7
#define IS_OBJECT                    8
#define IS_RESOURCE                    9
#define IS_REFERENCE                10

/* constant expressions */
#define IS_CONSTANT                    11
#define IS_CONSTANT_AST                12

/* fake types */
#define _IS_BOOL                    13
#define IS_CALLABLE                    14
#define IS_ITERABLE                    19
#define IS_VOID                        18

/* internal types */
#define IS_INDIRECT                 15
#define IS_PTR                        17
#define _IS_ERROR                    20

第二個(gè)問(wèn)題：變量的值如何存儲(chǔ)？ 答：如果是a是1用int；如果是1.1，用double；是"1"用char *等等，但是變量的值的類型只有1種，不可能同時(shí)用到多種類型去存值，故我們可以把這一大堆東西放到1個(gè)union里面即可，源碼中存儲(chǔ)變量類型的聯(lián)合體叫做zend_value：

typedef union _zend_value {
    zend_long         lval;    //存整型值
    double            dval;    //存浮點(diǎn)值
    zend_refcounted  *counted; //存引用計(jì)數(shù)值
    zend_string      *str; //存字符串值
    zend_array       *arr; //存數(shù)組值
    zend_object      *obj; //存對(duì)象值
    zend_resource    *res; //存資源值
    zend_reference   *ref; //存引用值
    zend_ast_ref     *ast; //存抽象語(yǔ)法樹(shù)
    zval             *zv;  //內(nèi)部使用
    void             *ptr; //不確定類型，取出來(lái)之后強(qiáng)轉(zhuǎn)
    zend_class_entry *ce;  //存類
    zend_function    *func;//存函數(shù)
    struct {
        uint32_t w1;
        uint32_t w2;
    } ww; //這個(gè)union一共8B，這個(gè)結(jié)構(gòu)體每個(gè)字段都是4B，因?yàn)樗新?lián)合體字段共用一塊內(nèi)存，故相當(dāng)于取了一半的union
} zend_value;

由于某些類型的變量需要額外的一些描述信息（如字符串、數(shù)組），其復(fù)雜度更高，為了節(jié)省空間，就只在zend_value結(jié)構(gòu)體中存了一個(gè)結(jié)構(gòu)體指針，其真正的值在zend_string、zend_array這些結(jié)構(gòu)體中（下面會(huì)講）。

zend_value類型是一個(gè)聯(lián)合體，共占用8B。因?yàn)樽兞恐挥幸环N類型，所以就可以利用聯(lián)合體共用一塊內(nèi)存的特性，來(lái)存儲(chǔ)變量的類型。注意最后一個(gè)結(jié)構(gòu)體是一個(gè)小技巧，通過(guò)取ww結(jié)構(gòu)體的其中一個(gè)字段，可以取到聯(lián)合體變量高4位或者低4位，這樣就不用手動(dòng)編寫多余代碼去取了。

在PHP7中，zend_value占用8B，而u1占用4B，u2占用4B，經(jīng)過(guò)內(nèi)存對(duì)齊，一個(gè)zval占用16B，相較PHP5，占用的內(nèi)存大幅減少。

示例代碼：

首先在ZEND_ECHO_SPEC_CV_HANDLER打一個(gè)斷點(diǎn)。在PHP虛擬機(jī)中，一條指令對(duì)應(yīng)一個(gè)handler，這里對(duì)應(yīng)的就是echo的語(yǔ)法。首先我們執(zhí)行到了$a = 1處，打印這個(gè)z變量的值，可以看到lval = 1，它就是用來(lái)存放$a的值的。然后再關(guān)注聯(lián)合體u1中的type字段的值為4，對(duì)照上文類型對(duì)照表，正好對(duì)應(yīng)IS_LONG類型。記錄下它的地址0x7ffff381c080，下文將要使用。

用c命令回到PHP代碼繼續(xù)執(zhí)行到$b = 1.1處，打印zval的情況：


可以看到double類型的值被存放到了dval變量中，這里存在精度問(wèn)題（不展開(kāi)），且u1的type是5，對(duì)應(yīng)IS_DOUBLE類型。這里的地址是0x7ffff381c090，正好與上一個(gè)$a的地址0x7ffff381c080相差16B，即一個(gè)zval的大小，驗(yàn)證了zval是16B的結(jié)論。
使用c命令繼續(xù)往下執(zhí)行，到了$c = "hello“處：



可以看到這個(gè)zval中u1中type字段為6，即IS_STRING類型。遇到字符串類型會(huì)取value中的str字段，它是一個(gè)zend_string類型（專門用來(lái)存字符串，下面會(huì)講）的結(jié)構(gòu)體指針。
首先思考一個(gè)問(wèn)題，如果讓我們自己基于C語(yǔ)言設(shè)計(jì)一個(gè)zend_string，應(yīng)該如何設(shè)計(jì)？


存放字符串值的字符數(shù)組
存放長(zhǎng)度

這樣好像差不多就夠了，那么思考一個(gè)問(wèn)題：如果想臨時(shí)給字符串追加或減少應(yīng)該如何處理，如讓hello變成hello world？因?yàn)镃語(yǔ)言中的字符數(shù)組是固定的空間大小，并不能自動(dòng)擴(kuò)容。那么如何高效地將字符數(shù)組擴(kuò)容或縮小呢？那就要使用C語(yǔ)言結(jié)構(gòu)體中的柔性數(shù)組了。
我們先來(lái)看一下zend_string類型的結(jié)構(gòu)：

struct _zend_string {
    zend_refcounted_h gc;
    zend_ulong        h;                /* 冗余的hash值 */
    size_t            len;
    char              val[1];
};

gc字段表示引用計(jì)數(shù)，與引用計(jì)數(shù)和垃圾回收相關(guān)，它也是一個(gè)結(jié)構(gòu)體類型，這里不展開(kāi)。
h字段表示字符串的哈希值，在數(shù)組的key中有用，方便快速定位。這里是以空間換時(shí)間的思想，將這個(gè)值記錄下來(lái)，就不用每次用的時(shí)候都去計(jì)算字符串的哈希值，提升了性能。
len字段表示字符串長(zhǎng)度
這里char val[1] 就是一個(gè)柔性數(shù)組，在redis等源碼中也被大量使用。它的大小是不確定的，必須放在結(jié)構(gòu)體的尾部。它可以被當(dāng)做一個(gè)占位符，是緊跟著結(jié)構(gòu)體的一塊連續(xù)內(nèi)存空間。如果這里存的是一個(gè)char *的話，就會(huì)指向一塊隨機(jī)的內(nèi)存，而并不是緊跟著結(jié)構(gòu)體的連續(xù)內(nèi)存。

繼續(xù)c命令往下執(zhí)行，到了$d = [1,2,3];處。我們可以看到u1.v.type的值是7，即IS_ARRAY類型，接下來(lái)查看arr字段的內(nèi)容：

PHP數(shù)組源碼分析展開(kāi)
我們具體看一下這個(gè)數(shù)組的結(jié)構(gòu)：
struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;  //實(shí)際存儲(chǔ)數(shù)組元素的bucket
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

typedef struct _zend_array HashTable;

這是數(shù)組的基本數(shù)據(jù)結(jié)構(gòu)，其中包括一些描述數(shù)組大小以及用于遍歷的指針等，它的別名又叫HashTable。
我們主要關(guān)注*arData字段，我們往數(shù)組中插入的數(shù)據(jù)就放在bucket中，每一個(gè)bucket中存了一個(gè)key-value對(duì)，還有一個(gè)冗余的哈希值：

typedef struct _Bucket {
    zval              val;   //元素的值
    zend_ulong        h;   //冗余的哈希值
    zend_string      *key;  //元素的key
} Bucket;

要想將任意key值）（如字符串）映射到一段固定長(zhǎng)度大小的數(shù)組空間中，那么最適合的就是哈希算法（PHP中用的是time33算法），但是它不能正好映射到數(shù)組大小范圍之內(nèi)，且存在哈希沖突問(wèn)題。
在PHP中，其實(shí)在實(shí)際存儲(chǔ)數(shù)據(jù)的bucket前面，額外申請(qǐng)了一部分內(nèi)存，就是用來(lái)解決上述問(wèn)題。
我們將第一步由time33哈希算法求出來(lái)的h值，將其與nTableMask（也就是數(shù)組的size - 1）做或運(yùn)算得到bucket的索引下標(biāo)，這樣可以保證最終的索引下標(biāo)在[-n, -1]范圍之內(nèi)，這里稱之為slot，它的具體計(jì)算公式為：

 nIndex = h | nTableMask

相同hash值計(jì)算出來(lái)的nIndex（即slot）的值是相同的。

然后在slot的對(duì)應(yīng)空間內(nèi)存上第一個(gè)bucket對(duì)應(yīng)的索引下標(biāo)，然后將元素存入對(duì)應(yīng)索引下標(biāo)的bucket數(shù)組中。查找過(guò)程也是類似的（下面會(huì)細(xì)講），它們都是O(1)的時(shí)間復(fù)雜度，但是這樣就會(huì)出現(xiàn)哈希沖突，解決哈希沖突通常有兩種算法：

開(kāi)放定址法
鏈地址法





比較常用的是鏈地址法，但如果同一個(gè)hash值上的鏈表過(guò)長(zhǎng)，會(huì)把同一個(gè)hash值上的所有鏈表節(jié)點(diǎn)都遍歷一遍，時(shí)間復(fù)雜度會(huì)退化為O(n)。PHP5中有一個(gè)漏洞，攻擊者不斷讓你的鏈表變長(zhǎng)，使得數(shù)組查詢變慢，不斷消耗服務(wù)器性能，最終QPS會(huì)下降的非常之快。要解決鏈地址法的哈希沖突所帶來(lái)的性能下降問(wèn)題，有如下思路：

擴(kuò)容，重新進(jìn)行哈希運(yùn)算（rehash）
將鏈表?yè)Q成紅黑樹(shù)/跳表...（O(1)退化成O(logn)）問(wèn)題的本質(zhì)是鏈表的效率較低，故用其他數(shù)據(jù)結(jié)構(gòu)代替鏈表
PHP7中的鏈表是一種邏輯上的鏈表。每一個(gè)bucket維護(hù)下一個(gè)bucket在數(shù)組中的索引，而不通過(guò)指針維護(hù)上下游關(guān)系。上文提到的在bucket之前額外申請(qǐng)的內(nèi)存在這個(gè)地方亦要派上用場(chǎng)了。由于相同hash值經(jīng)過(guò)或運(yùn)算得到的slot值也是相同的，其slot中的值就指向第一個(gè)bucket，然后第一個(gè)bucket中的val字段中的u2聯(lián)合體中的next字段(如arData[0].val.u2.next字段)又指向了下一個(gè)相同slot的bucket單元......最終實(shí)現(xiàn)了頭插法版本的數(shù)組模擬鏈表。


下面舉一個(gè)PHP代碼的例子來(lái)描述數(shù)組的插入與查找過(guò)程：

$a["foo"] = 1;
$a[] = 2;
$a["s"] = 3;
$a["x"] = 4;

這是一個(gè)非常簡(jiǎn)單的幾個(gè)數(shù)組賦值語(yǔ)句，我們具體看一下它們的插入過(guò)程：
- $a["foo"] = 1;這里的key和value如果是字符串，需要多帶帶在zend_string結(jié)構(gòu)中存儲(chǔ)其真實(shí)的值和長(zhǎng)度，這里做了簡(jiǎn)化。


 - $a[] = 2;

 - $a["s"] = 3; 這里注意需要先修改索引數(shù)組，保證索引數(shù)組中第一個(gè)指向的bucket數(shù)組單元是最后插入bucket數(shù)組的值（頭插法），并且修改val.u2.next指針（因?yàn)樗衯al都是zval類型），指向上一個(gè)具有相同hash值的元素。

 - $a["x"] = 4;同上


再來(lái)看一個(gè)數(shù)組查詢過(guò)程，例如訪問(wèn)$a["s"]的值：

經(jīng)過(guò)time33哈希算法算出哈希值h
計(jì)算出索引數(shù)組的nIndex = h | nTableMask = -7（假設(shè)）
訪問(wèn)索引數(shù)組，取出索引為-7位置上的元素值為3
訪問(wèn)bucket數(shù)組，取出索引為3位置上的key，為x，發(fā)現(xiàn)并不等于s，那么繼續(xù)查找，訪問(wèn)val.u2.next指針，為2
取出索引為2位置上的key，為s，發(fā)現(xiàn)正好是我們要找的那個(gè)key
取出對(duì)應(yīng)的val值3


下面我們?cè)倏匆欢蜳HP代碼：
=0; $i--) {
    $arr2[$i] = $i;
}

思考：這兩段代碼占用的內(nèi)存是否相同？
答：第一個(gè)for循環(huán)占用的內(nèi)存更少。

那么為什么會(huì)這樣呢？先看兩個(gè)概念：packed array與hash array


packed array的特點(diǎn)：

key是數(shù)字，且順序遞增
位置固定，如訪問(wèn)key是0的元素，即$arr1[0]，就直接訪問(wèn)bucket數(shù)組的第0個(gè)位置即可（即arData[0]）
因?yàn)榭梢灾苯釉L問(wèn)，不需要使用前面額外的索引數(shù)組，PHP中只使用了2個(gè)數(shù)組單元并賦值為初始的-1


由此可見(jiàn)，第一個(gè)循環(huán)就是以packed array的形式存儲(chǔ)的，由于不用索引數(shù)組，索引節(jié)省了200000 - 2 個(gè)內(nèi)存單元
如果不滿足上述條件，就是一個(gè)hash array
我們看第二個(gè)for循環(huán)，如果想訪問(wèn)key是200000的元素，若按照packed array的方法，直接訪問(wèn)bucket數(shù)組的第200000元素（即arData[200000]），就會(huì)得到錯(cuò)誤的值0（因?yàn)?arr2[200000] = 200000），所以只能通過(guò)使用索引數(shù)組來(lái)間接訪問(wèn)元素
因?yàn)樗饕龜?shù)組需要索引到bucket數(shù)組的所有位置，所以其大小等于bucket數(shù)組的大小，多使用了200000 - 2個(gè)內(nèi)存單元，故占用的內(nèi)存更多，所以在工作中，盡量使用packed array，來(lái)減少對(duì)服務(wù)器內(nèi)存的使用量。




思考：如果一個(gè)packed array中間空出來(lái)許多元素，即：
$arr = [
    0 => 0,
    1 => 1,
    2 => 2,
    100000 => 3
];
顯然這樣如果使用packed array會(huì)浪費(fèi)許多bucket數(shù)組的空間，在這種情況下，可能用hash array的效率就會(huì)更高一些，在這里，PHP內(nèi)核就需要做出權(quán)衡，經(jīng)過(guò)比較之后，選擇一種最優(yōu)化的方案。