PHP7 数组排序函数源码解析

今天来看看经常使用的数组排序函数如 sort, rsort, asort, arsort, ksort, krsort 。话不多说直接找 sort 函数吧。

在 php7.3 源码中搜索 PHP_FUNCTION(sort) 可以搜到如下

其中 .h 文件是C语言的头文件，直接打开 .c 文件。
sort 函数如下，其中我加了一点注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PHP_FUNCTION(sort)
{
	zval *array;
	zend_long sort_type = PHP_SORT_REGULAR; // 默认的排序规则
	compare_func_t cmp;

	// 这里开始接请求参数
	ZEND_PARSE_PARAMETERS_START(1, 2)
		Z_PARAM_ARRAY_EX(array, 0, 1)
		Z_PARAM_OPTIONAL
		Z_PARAM_LONG(sort_type)
	ZEND_PARSE_PARAMETERS_END_EX(RETURN_FALSE);

	// 根据排序规则获取使用的排序函数
	cmp = php_get_data_compare_func(sort_type, 0);

	// 进行排序
	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 1) == FAILURE) {
		RETURN_FALSE;
	}
	RETURN_TRUE;
}

不但 rsort, asort, arsort, ksort, krsort 这些函数在 array.c 文件中，PHP数组相关的也都在其中。
先说下 rsort, asort, arsort, ksort, krsort 函数内容与 sort 只有细微的差别。
ksort、krsort 是根据键排序所以排序规则获取排序函数用的是 php_get_key_compare_func 参数与 php_get_data_compare_func 是一样的。
php_get_data_compare_func、php_get_key_compare_func 函数第二个参数意思是是否降序排列，rsort、arsort、krsort 第二个参数都是1。
进行排序时 zend_hash_sort(Z_ARRVAL_P(array), cmp, 1) 第三个参数意思是是否重新排列索引， sort、rsort 传的都是1。
做个表格看下

获取排序函数调用排序
sortphp_get_data_compare_func(sort_type, 0)zend_hash_sort(Z_ARRVAL_P(array), cmp, 1)
rsortphp_get_data_compare_func(sort_type, 1)zend_hash_sort(Z_ARRVAL_P(array), cmp, 1)
asortphp_get_data_compare_func(sort_type, 0)zend_hash_sort(Z_ARRVAL_P(array), cmp, 0)
arsortphp_get_data_compare_func(sort_type, 1)zend_hash_sort(Z_ARRVAL_P(array), cmp, 0)
ksortphp_get_key_compare_func(sort_type, 0)zend_hash_sort(Z_ARRVAL_P(array), cmp, 0)
krsortphp_get_key_compare_func(sort_type, 1)zend_hash_sort(Z_ARRVAL_P(array), cmp, 0)

其中调用 php_get_data_compare_func 与 php_get_key_compare_func 获取的 cmp 后面再说明。

继续找 zend_hash_sort ，在 zend_hash.h 中。

1
2
#define zend_hash_sort(ht, compare_func, renumber) \
	zend_hash_sort_ex(ht, zend_sort, compare_func, renumber)

看来 zend_hash_sort 中调用了 zend_hash_sort_ex 。 zend_hash_sort_ex 在 zend_hash.c 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
ZEND_API int ZEND_FASTCALL zend_hash_sort_ex(HashTable *ht, sort_func_t sort, compare_func_t compar, zend_bool renumber)
{
	Bucket *p;
	uint32_t i, j;

	IS_CONSISTENT(ht);
	HT_ASSERT_RC1(ht);

	if (!(ht->nNumOfElements>1) && !(renumber && ht->nNumOfElements>0)) { /* Doesn't require sorting */
		return SUCCESS;
	}

	// 这里获取数组元素数，判断hash table是否没有洞，"洞"意思是数组里面元素被unset过，被unset过的val type是IS_UNDEF，不能通过nNumUsed直接获取数组的元素数。
	if (HT_IS_WITHOUT_HOLES(ht)) {
		i = ht->nNumUsed;
	} else {
		for (j = 0, i = 0; j < ht->nNumUsed; j++) {
			p = ht->arData + j;
			if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) continue;
			if (i != j) {
				ht->arData[i] = *p;
			}
			i++;
		}
	}

	// 这个sort是由上面直接传进来的zend_sort，终于到最重要的排序了
	sort((void *)ht->arData, i, sizeof(Bucket), compar,
			(swap_func_t)(renumber? zend_hash_bucket_renum_swap :
				((HT_FLAGS(ht) & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap)));

	// 后面是根据renumber判断是否需要重排索引内存回收等操作先省略了
}

在 zend_sort.c 中找到 zend_sort ，通过备注发现这个排序是源于 LLVM 的 libc++ 中的 std::sort 实现的。算是快排的优化版，当元素数小于等于16时有特殊的优化，当元素数小于等于5时直接通过 if else 嵌套判断排序，真是优化的极致。zend_sort_2 、 zend_sort_3 、 zend_sort_4 、 zend_sort_5 中是 if else 嵌套的判断排序就不贴出来了。其中基准点(pivot)计算方式也进行了优化。相比 PHP5 时代的标配快排实现要稳定多了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
{
	while (1) {
		if (nmemb <= 16) {
			zend_insert_sort(base, nmemb, siz, cmp, swp);
			return;
		} else {
			char *i, *j;
			char *start = (char *)base;
			char *end = start + (nmemb * siz);
			size_t offset = (nmemb >> Z_L(1));
			char *pivot = start + (offset * siz);

			if ((nmemb >> Z_L(10))) {
				size_t delta = (offset >> Z_L(1)) * siz;
				zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);
			} else {
				zend_sort_3(start, pivot, end - siz, cmp, swp);
			}
			swp(start + siz, pivot);
			pivot = start + siz;
			i = pivot + siz;
			j = end - siz;
			while (1) {
				while (cmp(pivot, i) > 0) {
					i += siz;
					if (UNEXPECTED(i == j)) {
						goto done;
					}
				}
				j -= siz;
				if (UNEXPECTED(j == i)) {
					goto done;
				}
				while (cmp(j, pivot) > 0) {
					j -= siz;
					if (UNEXPECTED(j == i)) {
						goto done;
					}
				}
				swp(i, j);
				i += siz;
				if (UNEXPECTED(i == j)) {
					goto done;
				}
			}
done:
			swp(pivot, i - siz);
			if ((i - siz) - start < end - i) {
				zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);
				base = i;
				nmemb = (end - i)/siz;
			} else {
				zend_sort(i, (end - i)/siz, siz, cmp, swp);
				nmemb = (i - start)/siz - 1;
			}
		}
	}
}

ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) {
	switch (nmemb) {
		case 0:
		case 1:
			break;
		case 2:
			zend_sort_2(base, (char *)base + siz, cmp, swp);
			break;
		case 3:
			zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp);
			break;
		case 4:
			{
				size_t siz2 = siz + siz;
				zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp);
			}
			break;
		case 5:
			{
				size_t siz2 = siz + siz;
				zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp);
			}
			break;
		default:
			{
				char *i, *j, *k;
				char *start = (char *)base;
				char *end = start + (nmemb * siz);
				size_t siz2= siz + siz;
				char *sentry = start + (6 * siz);
				for (i = start + siz; i < sentry; i += siz) {
					j = i - siz;
					if (!(cmp(j, i) > 0)) {
						continue;
					}
					while (j != start) {
						j -= siz;
						if (!(cmp(j, i) > 0)) {
							j += siz;
							break;
						}
					}
					for (k = i; k > j; k -= siz) {
						swp(k, k - siz);
					}
				}
				for (i = sentry; i < end; i += siz) {
					j = i - siz;
					if (!(cmp(j, i) > 0)) {
						continue;
					}
					do {
						j -= siz2;
						if (!(cmp(j, i) > 0)) {
							j += siz;
							if (!(cmp(j, i) > 0)) {
								j += siz;
							}
							break;
						}
						if (j == start) {
							break;
						}
						if (j == start + siz) {
							j -= siz;
							if (cmp(i, j) > 0) {
								j += siz;
							}
							break;
						}
					} while (1);
					for (k = i; k > j; k -= siz) {
						swp(k, k - siz);
					}
				}
			}
			break;
	}
}

最后来说说 cmp 这个函数，当 sort_flags 为 SORT_REGULAR 时 sort 函数的 cmp 调用的是 array.c 中的下面这个函数，返回值分成 小于0(b>1), 0(b==a), 大于0(a>b)对比失败也是0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static int php_array_data_compare(const void *a, const void *b)
{
	Bucket *f;
	Bucket *s;
	zval result;
	zval *first;
	zval *second;

	f = (Bucket *) a;
	s = (Bucket *) b;

	first = &f->val;
	second = &s->val;

	if (UNEXPECTED(Z_TYPE_P(first) == IS_INDIRECT)) {
		first = Z_INDIRECT_P(first);
	}
	if (UNEXPECTED(Z_TYPE_P(second) == IS_INDIRECT)) {
		second = Z_INDIRECT_P(second);
	}
	if (compare_function(&result, first, second) == FAILURE) {
		return 0;
	}

	ZEND_ASSERT(Z_TYPE(result) == IS_LONG);
	return ZEND_NORMALIZE_BOOL(Z_LVAL(result));
}

再往下追就是 compare_function 很长我就不贴了，简单说下其中先判断 first 和 second 类型，再进行各种分支比较。比较好奇其中的都是字符串时对比方法，追了下发现底层使用的是C的 memcmp 比较这两个串的前N个字节，这个N是这两个串中较小的那个。

最后总结下 PHP7 对比 PHP5 时代数组排序调用逻辑相差不大，但是排序算法优化了很多，更不用说底层的hash table了。

最后的最后文中如有理解错误的点也请指教。