摘要：中以表示所有的變量，它是一個結構體。類型是一個聯合體，共占用。字段表示字符串的哈希值，在數組的中有用，方便快速定位。字段表示字符串長度這里就是一個柔性數組，在等源碼中也被大量使用。

baiyan

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

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

變量本質上就是給一段內存空間起了個名字

如果讓我們自己基于C語言設計一個存儲如$a = 1變量的數據結構，應該如何設計？

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

首先應該定義一個結構體作為基本的數據結構

第一個問題：變量類型如何存儲？ 答：用一個unsigned char類型的字段存足夠，因為unsigned char類型最多能夠表示2^8 = 256種類型。

PHP7中以zval表示所有的變量，它是一個結構體。先看zval的基本結構：

typedef unsigned char zend_uchar;

struct _zval_struct {
    zend_value        value;            /* 存儲變量的zhi*/
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(             //大小端問題，詳情看"PHP內存管理3筆記”
                zend_uchar    type,         //注意這里就是存放變量類型的地方，char類型
                zend_uchar    type_flags,   //類型標記
                zend_uchar    const_flags,  //是否是常量
                zend_uchar    reserved)        //保留字段
        } v;
        uint32_t type_info;
    } u1;
    union {
        uint32_t     next;                 /* 數組模擬鏈表，在下文鏈地址法解決哈希沖突時使用 */
        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;
};

注意關注中文注釋的部分，PHP就是利用C語言的unsigned char類型，存儲了所有變量的類型。

在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

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

typedef union _zend_value {
    zend_long         lval;    //存整型值
    double            dval;    //存浮點值
    zend_refcounted  *counted; //存引用計數值
    zend_string      *str; //存字符串值
    zend_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; //這個union一共8B，這個結構體每個字段都是4B，因為所有聯合體字段共用一塊內存，故相當于取了一半的union
} zend_value;

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

zend_value類型是一個聯合體，共占用8B。因為變量只有一種類型，所以就可以利用聯合體共用一塊內存的特性，來存儲變量的類型。注意最后一個結構體是一個小技巧，通過取ww結構體的其中一個字段，可以取到聯合體變量高4位或者低4位，這樣就不用手動編寫多余代碼去取了。

在PHP7中，zend_value占用8B，而u1占用4B，u2占用4B，經過內存對齊，一個zval占用16B，相較PHP5，占用的內存大幅減少。

示例代碼：

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

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


可以看到double類型的值被存放到了dval變量中，這里存在精度問題（不展開），且u1的type是5，對應IS_DOUBLE類型。這里的地址是0x7ffff381c090，正好與上一個$a的地址0x7ffff381c080相差16B，即一個zval的大小，驗證了zval是16B的結論。
使用c命令繼續往下執行，到了$c = "hello“處：



可以看到這個zval中u1中type字段為6，即IS_STRING類型。遇到字符串類型會取value中的str字段，它是一個zend_string類型（專門用來存字符串，下面會講）的結構體指針。
首先思考一個問題，如果讓我們自己基于C語言設計一個zend_string，應該如何設計？


存放字符串值的字符數組
存放長度

這樣好像差不多就夠了，那么思考一個問題：如果想臨時給字符串追加或減少應該如何處理，如讓hello變成hello world？因為C語言中的字符數組是固定的空間大小，并不能自動擴容。那么如何高效地將字符數組擴容或縮小呢？那就要使用C語言結構體中的柔性數組了。
我們先來看一下zend_string類型的結構：

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

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

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

PHP數組源碼分析展開
我們具體看一下這個數組的結構：
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;  //實際存儲數組元素的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;

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

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

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

 nIndex = h | nTableMask

相同hash值計算出來的nIndex（即slot）的值是相同的。

然后在slot的對應空間內存上第一個bucket對應的索引下標，然后將元素存入對應索引下標的bucket數組中。查找過程也是類似的（下面會細講），它們都是O(1)的時間復雜度，但是這樣就會出現哈希沖突，解決哈希沖突通常有兩種算法：

開放定址法
鏈地址法





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

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


下面舉一個PHP代碼的例子來描述數組的插入與查找過程：

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

這是一個非常簡單的幾個數組賦值語句，我們具體看一下它們的插入過程：
- $a["foo"] = 1;這里的key和value如果是字符串，需要多帶帶在zend_string結構中存儲其真實的值和長度，這里做了簡化。


 - $a[] = 2;

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

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


再來看一個數組查詢過程，例如訪問$a["s"]的值：

經過time33哈希算法算出哈希值h
計算出索引數組的nIndex = h | nTableMask = -7（假設）
訪問索引數組，取出索引為-7位置上的元素值為3
訪問bucket數組，取出索引為3位置上的key，為x，發現并不等于s，那么繼續查找，訪問val.u2.next指針，為2
取出索引為2位置上的key，為s，發現正好是我們要找的那個key
取出對應的val值3


下面我們再看一段PHP代碼：
=0; $i--) {
    $arr2[$i] = $i;
}

思考：這兩段代碼占用的內存是否相同？
答：第一個for循環占用的內存更少。

那么為什么會這樣呢？先看兩個概念：packed array與hash array


packed array的特點：

key是數字，且順序遞增
位置固定，如訪問key是0的元素，即$arr1[0]，就直接訪問bucket數組的第0個位置即可（即arData[0]）
因為可以直接訪問，不需要使用前面額外的索引數組，PHP中只使用了2個數組單元并賦值為初始的-1


由此可見，第一個循環就是以packed array的形式存儲的，由于不用索引數組，索引節省了200000 - 2 個內存單元
如果不滿足上述條件，就是一個hash array
我們看第二個for循環，如果想訪問key是200000的元素，若按照packed array的方法，直接訪問bucket數組的第200000元素（即arData[200000]），就會得到錯誤的值0（因為$arr2[200000] = 200000），所以只能通過使用索引數組來間接訪問元素
因為索引數組需要索引到bucket數組的所有位置，所以其大小等于bucket數組的大小，多使用了200000 - 2個內存單元，故占用的內存更多，所以在工作中，盡量使用packed array，來減少對服務器內存的使用量。




思考：如果一個packed array中間空出來許多元素，即：
$arr = [
    0 => 0,
    1 => 1,
    2 => 2,
    100000 => 3
];
顯然這樣如果使用packed array會浪費許多bucket數組的空間，在這種情況下，可能用hash array的效率就會更高一些，在這里，PHP內核就需要做出權衡，經過比較之后，選擇一種最優化的方案。