PHP 的 in_array 效能測試

2024-07-03 2024-07-03 約 1007 字預計閱讀 5 分鐘

這是很久以前發現，但還沒有很認真實測過的問題：當在一個 array 裡尋找符合的元素時，下面這些方法的效能到底誰快誰慢？

in_array()
array_intersect()
array_flip() + array_key_exists()

這篇文章將會詳細討論這個問題，首先會先說明情境，然後測試結果，最後再說明原理。

情境

開發時常會有一種需求：要在一個資料集（Set，資料不重覆）裡，確認某個資料是否存在。例如：

$data = [1, 2, 3, 4, 5];

$target = 4;
// 尋找 4 是否在 $data 裡，結果要回傳 true

$target = 6;
// 尋找 6 是否在 $data 裡，結果要回傳 false

最直接的方法就是使用 foreach：

function (array $data, mixed $target): bool
{
    foreach ($data as $item) {
        if ($item === $target) {
            return true;
        }
    }
    
    return false;
}

這段程式很簡單，PHPer 應該很容易理解。只是問題是，用 PHP 寫的程式，在數量達到一個級數時，效能會變得非常差，這時就需要尋找更有效的方法。

其中一個方向是使用原生函數，除了可以用別人寫好的演算法，還可以省下 opcode 轉換成更低層語言的時間（參考初探 PHP Opcodes），另一個方向則是換演算法。依這些方向，可以找到一開始所提到的三個選擇：

in_array()
array_intersect()
array_flip() + array_key_exists()

範例程式碼如下：

$data = [1, 2, 3, 4, 5];

in_array(4, $data, true) // true
in_array(6, $data, true) // false

!empty(array_intersect($data,[4])) // true
!empty(array_intersect($data,[6])) // false

array_key_exists(4, array_flip($data)) // true
array_key_exists(6, array_flip($data)) // false

同場加映，Laravel Collections 的 whereIn() 也能達到類似的效果，只是 Array 的階層需要多一層。

$data = array_map(fn($item) => ['id' => $item], [1, 2, 3, 4, 5]);

Collection::make($data)->whereIn('id', [4])->isNotEmpty() // true
Collection::make($data)->whereIn('id', [6])->isNotEmpty() // false

測試

實際測試採用交集的方法來進行，能夠給演算法更大的壓力，同時我們也更能夠知道什麼情境下該如何選擇。

先建立原始資料集 $source，然後再建立尋找的資料集 $target，最後透過交集的方法得到 $intersects。白話地說，$intersects 裡面是從 $source 裡找 $target 的結果。

為公平起見，資料集有做亂數處理，然後分四個情境測試：

原始資料集 10 筆，尋找資料集 10 筆，尋找的資料集 10 筆全部都在資料集裡
原始資料集 10,000 筆，尋找資料集 10 筆，尋找的資料集 10 筆全部都在資料集裡
原始資料集 10 筆，尋找資料集 10,000 筆，只有 10 筆在資料集裡
原始資料集 10,000 筆，尋找資料集 10,000 筆，只有 10 筆在資料集裡

而演算法有 6 種如下：

原生 foreach
in_array()
array_intersect()
array_flip() + array_key_exists()
Laravel Collections + whereIn()
Laravel Collections + intersect()

測試環境如下：

PHPBench 1.3.1
illuminate/collections 8.83.27
PHP version 8.2.20
xdebug ✔
opcache ❌

情境一

原始資料集 10 筆，尋找資料集 10 筆，尋找的資料集 10 筆全部都在資料集裡。

這是資料量很少，且命中率極高的情境。Collection 因為還有物件處理時間，所以會比較慢一點，而底層函數和寫法則差不多，看數據的結果是 array_intersect() 獲勝。

+--------------+------------------------------------+---------+----------+----------+----------+--------+---------+
| benchmark    | subject                            | memory  | min      | max      | mode     | rstdev | stdev   |
+--------------+------------------------------------+---------+----------+----------+----------+--------+---------+
| InArrayBench | benchForeach ()                    | 2.706mb | 3.400μs  | 3.500μs  | 3.406μs  | ±1.37% | 0.047μs |
| InArrayBench | benchInArray ()                    | 2.706mb | 2.300μs  | 2.350μs  | 2.303μs  | ±1.02% | 0.024μs |
| InArrayBench | benchArrayIntersect ()             | 2.706mb | 1.500μs  | 1.500μs  | 1.500μs  | ±0.00% | 0.000μs |
| InArrayBench | benchArrayFlipAndArrayKeyExists () | 2.706mb | 2.300μs  | 2.300μs  | 2.300μs  | ±0.00% | 0.000μs |
| InArrayBench | benchCollectionWhereIn ()          | 2.728mb | 84.350μs | 86.600μs | 84.944μs | ±1.10% | 0.935μs |
| InArrayBench | benchCollectionIntersect ()        | 2.706mb | 58.850μs | 59.450μs | 58.911μs | ±0.46% | 0.272μs |
+--------------+------------------------------------+---------+----------+----------+----------+--------+---------+

情境二

原始資料集 10,000 筆，尋找資料集 10 筆，尋找的資料集 10 筆全部都在資料集裡。

這是原始資料量大，但命中率一樣很高的情境。這裡有出現極大的差異了，結果是 array_flip() + array_key_exists() 獲勝。

+--------------+------------------------------------+---------+----------+----------+----------+--------+----------+
| benchmark    | subject                            | memory  | min      | max      | mode     | rstdev | stdev    |
+--------------+------------------------------------+---------+----------+----------+----------+--------+----------+
| InArrayBench | benchForeach ()                    | 6.431mb | 3.761ms  | 3.827ms  | 3.777ms  | ±0.73% | 27.784μs |
| InArrayBench | benchInArray ()                    | 6.431mb | 1.640ms  | 1.646ms  | 1.644ms  | ±0.15% | 2.538μs  |
| InArrayBench | benchArrayIntersect ()             | 7.287mb | 4.148ms  | 4.239ms  | 4.223ms  | ±0.93% | 39.159μs |
| InArrayBench | benchArrayFlipAndArrayKeyExists () | 7.352mb | 57.850μs | 66.600μs | 65.282μs | ±6.05% | 3.821μs  |
| InArrayBench | benchCollectionWhereIn ()          | 7.016mb | 15.033ms | 15.150ms | 15.048ms | ±0.34% | 51.908μs |
| InArrayBench | benchCollectionIntersect ()        | 7.444mb | 4.153ms  | 4.247ms  | 4.221ms  | ±0.93% | 39.018μs |
+--------------+------------------------------------+---------+----------+----------+----------+--------+----------+

情境三

原始資料集 10 筆，尋找資料集 10,000 筆，只有 10 筆在資料集裡。

這是原始資料少，但找的資料很多，可是命中率極低的情境，這裡是 in_array() 獲勝。

但這裡也會發現，Collection + whereIn() 也很快，這是因為它裡面是使用 in_array()；另外也會發現 foreach 是第三名，因為 in_array() 的 C++ 實作原理，其實跟 foreach 是一樣的。

+--------------+------------------------------------+---------+-----------+-----------+-----------+---------+----------+
| benchmark    | subject                            | memory  | min       | max       | mode      | rstdev  | stdev    |
+--------------+------------------------------------+---------+-----------+-----------+-----------+---------+----------+
| InArrayBench | benchForeach ()                    | 6.431mb | 909.900μs | 1.059ms   | 1.045ms   | ±6.75%  | 67.877μs |
| InArrayBench | benchInArray ()                    | 6.431mb | 40.350μs  | 58.700μs  | 44.372μs  | ±16.06% | 7.734μs  |
| InArrayBench | benchArrayIntersect ()             | 6.756mb | 4.062ms   | 4.200ms   | 4.151ms   | ±1.37%  | 56.805μs |
| InArrayBench | benchArrayFlipAndArrayKeyExists () | 6.432mb | 1.410ms   | 1.422ms   | 1.411ms   | ±0.38%  | 5.403μs  |
| InArrayBench | benchCollectionWhereIn ()          | 7.016mb | 120.550μs | 127.850μs | 124.093μs | ±2.40%  | 2.980μs  |
| InArrayBench | benchCollectionIntersect ()        | 7.178mb | 4.159ms   | 4.198ms   | 4.195ms   | ±0.43%  | 18.101μs |
+--------------+------------------------------------+---------+-----------+-----------+-----------+---------+----------+

情境四

原始資料集 10,000 筆，尋找資料集 10,000 筆，只有 10 筆在資料集裡。

這是兩種資料都極大，但是真正要找的資料只有小部分。這裡跟情境二相同，是 array_flip() + array_key_exists() 獲勝。

+--------------+------------------------------------+----------+----------+----------+----------+--------+-----------+
| benchmark    | subject                            | memory   | min      | max      | mode     | rstdev | stdev     |
+--------------+------------------------------------+----------+----------+----------+----------+--------+-----------+
| InArrayBench | benchForeach ()                    | 10.719mb | 2.025s   | 2.039s   | 2.026s   | ±0.31% | 6.264ms   |
| InArrayBench | benchInArray ()                    | 10.719mb | 95.410ms | 96.298ms | 95.465ms | ±0.44% | 418.137μs |
| InArrayBench | benchArrayIntersect ()             | 11.899mb | 8.680ms  | 8.766ms  | 8.715ms  | ±0.40% | 34.978μs  |
| InArrayBench | benchArrayFlipAndArrayKeyExists () | 11.641mb | 1.435ms  | 1.473ms  | 1.449ms  | ±1.07% | 15.544μs  |
| InArrayBench | benchCollectionWhereIn ()          | 11.304mb | 78.948ms | 79.143ms | 78.979ms | ±0.11% | 84.569μs  |
| InArrayBench | benchCollectionIntersect ()        | 12.056mb | 8.618ms  | 8.847ms  | 8.745ms  | ±1.07% | 93.555μs  |
+--------------+------------------------------------+----------+----------+----------+----------+--------+-----------+

原理

為什麼會有這些差異呢？這個問題需要看原始碼才知道了。

in_array() 原始碼

先看 in_array() 的 PHP function 定義：

PHP_FUNCTION(in_array)
{
    php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
}

它對應的 php_search_array 定義裡，有個重要的關鍵字是 ZEND_HASH_FOREACH_KEY_VAL，這代表它是將 array 一個一個拿出來確認內容的，所以它的時間複雜度是 O(N)。

從原始碼可以看得出 array_search() 也是一樣的操作，只是 return 的資料不同。

array_flip() + array_key_exists() 原始碼

先看 array_flip() 的 PHP function 定義：

原始碼就不貼全部了，重點在裡面有段程式有個關鍵字是 FOREACH，這裡的時間複雜度會是 O(N)，也就是隨著 array 大小呈線性變化

ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
    // ...
} ZEND_HASH_FOREACH_END();

再看 array_key_exists() 的 PHP function 定義

PHP_FUNCTION(array_key_exists)
{
    zval *key;
    HashTable *ht;

    ZEND_PARSE_PARAMETERS_START(2, 2)
        Z_PARAM_ZVAL(key)
        Z_PARAM_ARRAY_HT(ht)
    ZEND_PARSE_PARAMETERS_END();
    
    switch (Z_TYPE_P(key)) {
        //...
    }
}

這裡開頭先定義好了 key 和 array 的原型 HashTable *ht

接著會看 key 的類型來找 ht 裡的內容，正常的 key 會是字串或數字，所以只要看這兩個就好

case IS_STRING:
    RETVAL_BOOL(zend_symtable_exists(ht, Z_STR_P(key)));
    break;
case IS_LONG:
    RETVAL_BOOL(zend_hash_index_exists(ht, Z_LVAL_P(key)));
    break;

其中 zend_symtable_exists 裡面會再判斷 key 是否是數字，再決定呼叫不同的方法：

static zend_always_inline bool zend_symtable_exists(HashTable *ht, zend_string *key)
{
    zend_ulong idx;

    if (ZEND_HANDLE_NUMERIC(key, idx)) {
        return zend_hash_index_exists(ht, idx);
    } else {
        return zend_hash_exists(ht, key);
    }
}

這兩個方法又會再對應到 zend_hash_index_find 與 zend_hash_find。

只是再往下找就是 Zend 底層的 HashTable 找 key 演算法，這段我就看不懂了。但以 HashTable 這個關鍵字所代表的資料結構，找 key 的時間複雜度通常是 O(1)。

因此 array_flip() + array_key_exists() 會是 O(N)。但在量極少的時候，會比其他的方法慢，原因是有兩次 Function 呼叫的開銷，加上 array_flip() 要建立新 array 會有固定開銷。

array_intersect()

先看 PHP function 定義：

PHP_FUNCTION(array_intersect)
{
    php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_NORMAL, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_INTERNAL);
}

往下追 php_array_intersect 一直到 4909 行，雖然演算法還無法很好地理解，但能發現這裡有兩層的迴圈（4909 行和 4951 行，但裡面有一段是在省略不必要的迴圈操作（4918 行），因此它應該是屬於特定情境比 O(N) 快，大多數情境比 O(N) 慢，但能夠穩定比 O(N^2) 快。但因為前置操作太多東西了，所以當資料很少的時候，效能還是會輸 in_array。

Laravel Collections

這裡就不貼原始碼了，whereIn() 是用 array_filter()（一個一個元素確認，跟 foreach 差不多） + in_array()；intersect() 就是直接用 array_intersect()。

結論

以上這些分析，也就能解釋為什麼 in_array 在資料極少的時候很快；但資料剛開始變多時，array_intersect() 在一些情境會是最快的；接著再增加到更多時，反而變成 array_flip() + array_key_exists() 是最快的。

從這些測試與研究結果得知，不同情境應該會有不同的選擇：

當有大量的資料要做搜尋或比對時，使用 array_flip() + array_key_exists() 是最有效率的，適用在資料庫讀取資料或是使用者輸入大量資料時。
而原始資料小，或是搜尋資料小的時候，使用 in_array() 反而是有效率的（資料小的那組放入 in_array 裡），適用在程式已有明確的清單要做判斷，例如：確認目前 route 是否在白名單裡。
如果第二點都使用 in_array() 的話，那 array_intersect() 在這些情境裡好像就沒有用處了？這段就不大確定了，array_intersect() 會比較慢的原因是，它可以直接回傳交集的元素內容，或許是應用在這個情境。

目錄

目錄

PHP 的 in_array 效能測試

情境

測試

情境一

情境二

情境三

情境四

原理

in_array() 原始碼

array_flip() + array_key_exists() 原始碼

array_intersect()

Laravel Collections

結論