關於PHP7中字串處理邏輯的最佳化！

##推薦教學： 《 PHP7》

##一、透過程式碼對比PHP 5 和PHP 7 中字串處理的差異

  先看如下範例程式碼：

$a = 'foo';
$b = 'bar';

$c = "I like $a and $b";

   在PHP 5.6 中執行程式碼，得到的操作碼輸出如下圖：

   具體的執行過程：

## 首先為I like 申請記憶體

• 然後為我喜歡foo 申請內存，然後將我喜歡foo 和foo 複製到新申請的內存空間並返回
• 繼續為我喜歡f​​oo 和foo 申請內存，然後將我喜歡foo 和復製到新申請的內存空間並返回
• 最後為I like foo and bar 申請返回內存，然後將I like foo and and bar 複製到新申請的內存並
• 釋放字符串處理過程中申請的內存空間
•    在PHP 7 中執行程式碼，得到的操作碼輸出如下：

#   PHP 7 中對字串的處理過程相對簡單，先建立一個堆疊，然後將要連接的字串片段存入堆疊空間中，最後只需要分配一次記憶體空間，然後將結果從堆疊中移動到所分配的記憶體空間。透視於PHP 5，PHP 7在處理過程中避免了反复申請記憶體的過程。而PHP 7 在字串處理方面效能的提升汲取資料結構Rope 的使用。

二、 Rope 資料結構介紹

⒈ Rope 介紹

#繩子是一棵二叉樹，其中葉子每個節點存儲是字符串的子串，每個非葉子節點存儲是位於該節點葉子的每個葉子節點存儲的子串中所包含的字符總數（方便了根據索引尋找字元指定）。

#⒉ Rope 的優點和不足

   優點：

• Rope 讓字串的插入、刪除等操作更快速，相較於傳統額字元陣列的方式，Rope 的時間複雜度為$\#\#O(logN)$#)$N$N)
• $O($O(N))
• ，而Rope 不需要事先進行拷貝
• Rope 不需要像字元陣列那樣需要大塊連續的記憶體

使用Rope 資料結構，字串操作的撤銷會非常方便

使用Rope，無論所操作的字串的size 多大，效能都十分穩定

•    不足：
• 需要額外的記憶體空間儲存非葉子節點，相較於字元陣列增加了記憶體空間的消耗

由於二元樹的結構相較於字元陣列比較複雜，這樣在操作size 較小的字串時效能反而比較差

使用Rope 操作字串，增加了程式碼的複雜度，同時也增加了出現BUG 的風險

⒊ Rope 的程式碼實作

   Rope 的本質是一棵二元樹，其基本的插入、刪除、搜尋操作與二元樹相同。這裡只對字串的聯結（concat）和拆分（split）進行介紹。

另外，為了盡量減少操作的時間複雜度，可以將 Rope 建構成一棵 AVL 樹，這樣在每次操作完成後實現自平衡。但這樣可能會增加一些撤銷操作的複雜度。例如，將兩棵高度不等的Rope 進行concat 操作後形成的新的Rope，透過節點旋轉實現自平衡後可能會破壞原先兩棵樹的結構，這樣如果要撤銷先前的concat 操作會變得非常複雜。

⓵ concat

   concat 操作相對簡單，只需要將兩棵Rope 樹聯接成一棵新的Rope 樹即可

⓶ split

#   對Rope 樹進行拆分的時候，會遇到兩種情況：拆分的位置正好位於某個節點的末尾或拆分的位置在某個葉子節點的中間。對於第二種情況，我們可以把對應的葉子節點進行拆分，從而轉換成第一種情況。而對於第一種情況，根據節點所處的位置又可以分為兩種情況：

  a. 節點位於最左側或最右側的分支

  b. 節點位於Rope 樹內部的分支############

class Node:
    def __init__(self, data):
        self.parent = None
        self.left = None
        self.right = None
        self.data = data
        self.weight = 0

    def __repr__(self):
        return str(self.__dict__)

    def __str__(self):
        return str(self.__dict__)


class Rope:
    # 每个叶子节点最多存储 5 个字符，包括空字符在内
    LEAF_DATA_LEN = 5

    def __init__(self):
        self.root = None

    def create_rope(self, parent, data, left_index, right_index):
        """
        创建 rope 数据结构
        :param parent: 父节点（根节点的父节点为空）
        :param data: 用于创建 rope 数据结构的原始数据，这里只接受 list 和 str 两种类型
        :param left_index: 起始位置索引
        :param right_index: 结束位置索引
        :return: Node
        """
        if isinstance(data, str):
            data = list(data)
        elif not isinstance(data, list):
            return

        if right_index - left_index > self.LEAF_DATA_LEN:
            node = Node("")

            node.parent = parent
            middle_index = (left_index + right_index) // 2
            node.weight = middle_index - left_index
            node.left = self.create_rope(node, data, left_index, middle_index)
            node.right = self.create_rope(node, data, middle_index, right_index)
        else:
            node = Node(data[left_index: right_index])

            node.parent = parent
            node.weight = right_index - left_index

        if node.parent is None:
            self.root = node

        return node

    @staticmethod
    def calc_weight(node):
        """
        计算节点 weight 值
        :param node:
        :return:
        """
        if node is None:
            return 0

        init_weight = node.weight
        while node.right is not None:
            node = node.right
            init_weight += node.weight

        return init_weight

    def concat_rope(self, data1, data2):
        """
        字符串连接
        :param data1:
        :param data2:
        :return:
        """
        r1 = Rope()
        r1.create_rope(None, data1, 0, len(data1))
        r2 = Rope()
        r2.create_rope(None, data2, 0, len(data2))

        node = Node("")
        node.left = r1.root
        node.right = r2.root
        r1.root.parent = node
        r2.root.parent = node

        node.weight = self.calc_weight(r1)

        self.root = node

    def split_rope(self, data, index):
        """
        字符串拆分
        :param data: 要拆分的字符串
        :param index: 拆分的位置（字符串索引从 0 开始计算）
        :return: Rope
        """
        if index < 0 or index > len(data) - 1:
            return

        node = self.create_rope(None, data, 0, len(data))
        original_index = index

        if index == self.root.weight - 1:
            # 在根节点拆分
            rope_left = node.left
            rope_left.parent = None
            rope_right = node.right
            rope_right.parent = None
            return rope_left, rope_right
        elif index < self.root.weight - 1:
            while index < node.weight - 1 and node.data == "":
                node = node.left
        else:
            while index > node.weight - 1 and node.data == "":
                index -= node.weight
                node = node.right

        if node.data != "":
            # index 落在了最左侧和最右侧的两个叶子节点
            if original_index < self.root.weight - 1:
                # index 落在了最左侧的叶子节点
                rope_left = self.create_rope(None, node.data[0:index + 1], 0, index + 1)
                rope_right = self.root
                # 更新 rope_right 的 weight
                node.data = node.data[index + 1:]
                while node is not None:
                    node.weight -= (index + 1)
                    node = node.parent
            else:
                # index 落在了最右侧的叶子节点
                rope_left = self.root
                rope_right = self.create_rope(None, node.data[index + 1:], 0, len(node.data[index + 1:]))
                node.data = node.data[0:index + 1]
        elif index == node.weight - 1:
            # index 正好落在了节点的末尾
            if original_index < self.root.weight:
                # index 落在了最左侧分支中的非叶子节点的末尾
                weight_sub = node.weight
                rope_left = node.left
                rope_left.parent = None
                node.left = None
                rope_right = self.root
                # 更新节点 weight
                while node is not None:
                    node.weight -= weight_sub
                    node = node.parent
            else:
                # index 落在了最右侧分支中的非叶子节点的末尾
                rope_left = self.root
                rope_right = node.right
                rope_right.parent = None
                node.right = None
        else:
            stack = []
            if original_index < self.root.weight:
                # index 落在了左子树中的节点
                index -= node.weight
                rope_left = node
                rope_right = self.root
                node.parent.left = None
                node.parent = None
                node = node.right
            else:
                # index 落在了右子树中的节点
                rope_left = self.root
                stack.append(node.right)
                rope_right = None
                node.right = None
                node = node.left
            while node.data == "" and index >= 0:
                if index < node.weight - 1:
                    stack.append(node.right)
                    node.right = None
                    node = node.left
                elif index > node.weight - 1:
                    node = node.right
                    index -= node.weight
                else:
                    stack.append(node.right)
                    node.right = None
                    break
            if node.data != "":
                # 需要拆分叶子节点
                new_node = Node(node.data[index + 1:])
                new_node.weight = node.weight - index - 1
                stack.append(new_node)
                node.data = node.data[0:index + 1]
            # 更新节点的 weight 信息
            while node is not None:
                if node.data != "":
                    node.weight = len(node.data)
                else:
                    node.weight = self.calc_weight(node.left)
                node = node.parent
            # 组装 rope_right并更新节点的 weight 值
            left_node = None
            while len(stack) > 0:
                root_node = Node("")
                if left_node is None:
                    left_node = stack.pop()
                    root_node = left_node
                else:
                    root_node.left = left_node
                    left_node.parent = root_node
                    right_node = stack.pop()
                    root_node.right = right_node
                    right_node.parent = root_node
                    root_node.weight = self.calc_weight(root_node.left)
                    left_node = root_node

            if rope_right is None:
                # index > self.root.weight - 1
                rope_right = root_node
            else:
                # index < self.root.weight - 1
                tmp = rope_right
                while tmp.left is not None:
                    tmp = tmp.left
                tmp.left = root_node
                root_node.parent = tmp
                while tmp.parent is not None:
                    tmp.weight = self.calc_weight(tmp.left)
                    tmp = tmp.parent
                rope_right = tmp
                rope_right.weight = self.calc_weight(rope_right.left)

        return rope_left, rope_right


rope = Rope()
data = "php is a script language"
index = 18
left, right = rope.split_rope(data, index)
print(left)
print(right)

三、 PHP 5 和 PHP 7 底层字符串处理逻辑比较

⒈ PHP 5 中字符串处理逻辑以及存在的问题

⓵ 处理逻辑

• PHP 5 中的字符串并没有固定的数据结构，而是采用 C 中以 NULL 结尾的字符数组的方式来处理
• 为了支持二进制字符串（字符串中包含 NULL 字符），还需要额外记录字符串的长度

⓶ 存在的问题

  a. 字符串的长度

   PHP 5 中 zval 中定义的字符串的长度为 int（有符号整型） 类型，这就导致即使是在 64 为机器上字符串的长度也不能超过 $2^{31}$ （LP64 数据模型中，int 永远只有 32 位）。

  b. 格式不统一

// zval 中对字符串的定义，长度为 int 类型
typedef union _zvalue_value {
		long lval;
		double dval;
		struct {
			char *val;     /* C string buffer, NULL terminated */
			int len;      /* String length : num of ASCII chars */
		} str;            /* string structure */
		HashTable *ht;
		zend_object_value obj;
		zend_ast *ast;
} zvalue_value;
	
// 类实例结构体中对字符串的定义，此时字符串的长度为 zend_uint 类型，相较于 int 类型，字符串长度提升了一倍
struct _zend_class_entry {
	char type;
	const char *name;		/* C string buffer, NULL terminated */
	zend_uint name_length;		/* String length : num of ASCII chars */
	struct _zend_class_entry *parent;
	int refcount;
	zend_uint ce_flags;

	/*……*/
}	

// hashtable 的 key 中对字符串的定义，长度为 uint 类型
typedef struct _zend_hash_key {
		const char *arKey;  /* C string buffer, NULL terminated */
		uint nKeyLength;    /* String length : num of ASCII chars */
		ulong h;
} zend_hash_key;

    PHP 5 中很多地方都支持二进制字符串，由于字符串没有一个固定的结构体，这就导致很多地方都有对字符串的定义。同时，由于各处对字符串长度的定义不同，导致各处支持的字符串长度也不同。

  c. 内存消耗大

   在较老版本的 PHP 中，由于没有引入 interned string，同一个字符串如果在多处被使用，为了互不影响，就需要复制多份出来，这就造成了对内存空间大量消耗。

static PHP_FUNCTION(session_id)
	{
		char *name = NULL;
		int name_len, argc = ZEND_NUM_ARGS();

		if (zend_parse_parameters(argc TSRMLS_CC, "|s", &name, &name_len) == FAILURE) {
		    return;
		}
	
		/* …… */

		if (name) {
		    if (PS(id)) {
		        efree(PS(id));
		    }
		    PS(id) = estrndup(name, name_len);
		}
	}

   以 PHP 函数 session_id 为例，该函数最终将 name 完全复制一份然后存入 PS(id)。这样，后续代码对 name 进行的任何操作都不会影响 PS(id) 中存储的值。

⓷ interned string

   从 PHP 5.4 起，为了解决上述字符串复制导致内存消耗大的问题，PHP 引入了 interned string 。另外，由于 interned string 需要共享内存空间，所以在线程安全的 PHP 版本中并不被支持。

   所谓 interned string，即一个字符串在一个进程中只存储一次。当一个 php-fpm 进程启动时，会申请一块 size 为 1MB 的 buffer，持久化的字符串（字符串常量、函数名、变量名、类名、方法名……）会被存储到该缓冲并添加到一个 hashtable 中。由于 PHP 处理的 request 之间是相互独立的，所以一个 request 处理完成后，其间在内存中产生的数据都会被销毁。为了在处理 request 的过程中也能使用 interned string，在 request 到来时 PHP 会记录当前 interned string buffer 的 top 位置，在该 request 请求的处理完成后，top 位置之后消耗的空间又会被恢复。

• interned string 的初始化，只会发生在 PHP 启动以及 PHP 脚本的编译阶段
• interned string 是只读的，既不能修改，也不能销毁
• 由于 interned string buffer 只有 1MB 的空间，当 1MB 的空间存满后，后续的字符串处理还会回到引入 interned string 之前的状态

   interned string 的优势

• 一个字符串只会存储一次，节省了内存空间
• interned string 的 hash 只会计算一次，然后被多次使用
• interned string 的比较最终转换成了指针地址的比较

   由于需要操作 hashtable，interned string 的初始化和创建会比较复杂，也正因为如此，并不是所有的字符串都适合存入 interned string。

⒉ PHP 7 中对字符串处理进行的优化

struct _zend_string {
	zend_refcounted_h gc;
	zend_ulong        h;                /* hash value */
	size_t            len;
	char              val[1];
};

typedef struct _zend_refcounted_h {
	uint32_t         refcount;			/* reference counter 32-bit */
	union {
		uint32_t type_info;
	} u;
} zend_refcounted_h;

   PHP 7 中字符串有了固定的结构 zend_string

   PHP 7 中字符串的长度类型为 size_t，字符串的长度不再局限于 PHP 5 中的 $2^{31}$ ，尤其在 64 位的机器上，字符串的长度取决于平台支持的最大长度。

  PHP 7 中字符串内容的存储不再像之前使用 char * ，而是使用了 struct hack ，使得字符串内容和 zend_string 一起存储在一块连续的内存空间。同时，zend_string 还内嵌了字符串的 hash 值，这样，对于一个指定的字符串只需要进行一次 hash 计算。

  PHP 7 中字符串引入了引用计数，这样，只要字符串还在被使用，就不用担心会被销毁。

static PHP_FUNCTION(session_id)
{
	zend_string *name = NULL;
	int argc = ZEND_NUM_ARGS();

	/* …… */

	if (name) {
	    if (PS(id)) {
	        zend_string_release(PS(id));
	    }
	    PS(id) = zend_string_copy(name);
	}
}

static zend_always_inline zend_string *zend_string_copy(zend_string *s)
{
	if (!ZSTR_IS_INTERNED(s)) {
	    GC_REFCOUNT(s)++;
	}
	return s;
}

static zend_always_inline void zend_string_release(zend_string *s)
{
	if (!ZSTR_IS_INTERNED(s)) {
	    if (--GC_REFCOUNT(s) == 0) {
	        pefree(s, GC_FLAGS(s) & IS_STR_PERSISTENT);
	    }
	}
}

  仍以函数 session_id 为例，设置 session_id 时不再需要将 name 完全复制，而只是将 name 的引用计数加 1。在删除字符串时也是同样，将字符串的引用计数减 1，只有引用计数为 0 时才会真正销毁字符串。

  PHP 7 中的 interned string 不再需要单独申请 interned string buffer 来存储，而是在 zend_string 的 gc 中将 type_info 标记为 IS_STR_INTERNED。这样，在销毁字符串时，zend_string_release 会检查字符串是否为 interned string，如果是则不会进行任何操作。

以上是關於PHP7中字串處理邏輯的最佳化！的詳細內容。更多資訊請關注PHP中文網其他相關文章！