やる気
すぐに始めましょう、ここに2つの同様のコードがあります：
回
$arr = []; for ($i =0; $i < 300; $i++) { $arr[rand(1,1000)] = 1; } $sum = 0; for ($i = 1001; $i < 200000000; $i++){ if (array_key_exists($i, $arr)){ $sum++; } }
二
$arr = []; for ($i =0; $i < 300; $i++) { $arr[rand(1,1000)] = 1; } sort($arr); $sum = 0; for ($i = 1001; $i < 200000000; $i++){ if (array_key_exists($i, $arr)){ $sum++; } }
それらの違いは、2番目のケースでは$ arr配列をソートし、それによってキー0..count（$ arr）-1を更新することです。 そして、最初のスクリプトが6.0秒実行され、2番目のスクリプトが4.7秒実行される瞬間に興味がありました。 違いの約20％が判明しました。
phpハッシュテーブルの内部構造とハッシュ関数に精通している場合は、すでに答えを知っているか、簡単に推測できます。 さて、残りの部分については、デバッグ用の環境を設定し、問題を調べる方法を説明します。
環境をカスタマイズする
必要なもの：
- PHPソース
- gdbデバッガー。
- php自体がデバッグmodにコンパイルされました。
PHPソースを自分自身にクローンします。
git clone https://git.php.net/repository/php-src.git cd php-src git checkout -b PHP-7.1 origin/PHP-7.1
コンパイルに必要なライブラリがない場合は、それらを配置します。
sudo apt-get install build-essential autoconf automake libtool
そしてコンパイル：
./buildconf ./configure --disable-all --enable-debug –prefix=$HOME/dev/bin/php make && make install
検索を開始する
まず、調査の開始点を決定します。これはarray_key_exists関数です。 PHPで関数がどのように宣言されているかを知っていれば、ソースで見つけるのは難しくありません。これはマクロPHP_FUNCTION（％function_name％）です。 PHP_FUNCTION（array_key_exists）という文字列のソースコードを検索し、 extension / standart / array.cで関数を見つけます。 コード：
PHP_FUNCTION（array_key_exists）
/* {{{ proto bool array_key_exists(mixed key, array search) Checks if the given key or index exists in the array */ PHP_FUNCTION(array_key_exists) { zval *key; /* key to check for */ HashTable *array; /* array to check in */ ZEND_PARSE_PARAMETERS_START(2, 2) Z_PARAM_ZVAL(key) Z_PARAM_ARRAY_OR_OBJECT_HT(array) ZEND_PARSE_PARAMETERS_END(); switch (Z_TYPE_P(key)) { case IS_STRING: if (zend_symtable_exists_ind(array, Z_STR_P(key))) { RETURN_TRUE; } RETURN_FALSE; case IS_LONG: if (zend_hash_index_exists(array, Z_LVAL_P(key))) { RETURN_TRUE; } RETURN_FALSE; case IS_NULL: if (zend_hash_exists_ind(array, ZSTR_EMPTY_ALLOC())) { RETURN_TRUE; } RETURN_FALSE; default: php_error_docref(NULL, E_WARNING, "The first argument should be either a string or an integer"); RETURN_FALSE; } }
コア言語関数の高レベルラッパーになる前に、 zend_hash_index_exists関数をもう少し深く掘り下げます。
Zend / zend_hash.cにあります：
ZEND_API zend_bool ZEND_FASTCALL zend_hash_index_exists(const HashTable *ht, zend_ulong h) { Bucket *p; IS_CONSISTENT(ht); if (ht->u.flags & HASH_FLAG_PACKED) { if (h < ht->nNumUsed) { if (Z_TYPE(ht->arData[h].val) != IS_UNDEF) { return 1; } } return 0; } p = zend_hash_index_find_bucket(ht, h); return p ? 1 : 0; }
デバジム
デバッガーを実行します。
gdb --args /home/your_pc/dev/bin/php/bin/php /home/your_pc/array_w_sort_test.php
1番目のパラメーターはコンパイルされたphpへのパスで、2番目のパラメーターはソートを使用するテストへのパスです。
デバッガーに入ったら、次のコマンドを実行する価値があります。
(gdb) source ~/dev/c/php-src/.gdbinit
これにより、非常に便利なコマンドが提供されます。リストを表示するには、次のように記述します。
(gdb) help user-defined
zend_hash_index_exists関数にブレークポイントを設定します。
(gdb) break zend_hash_index_exists
そして、スクリプトを実行します。
(gdb) run
次のような画面が表示されます。
(gdb) run Starting program: /home/your_pc/dev/bin/php/bin/php /home/your_pc/array_w_sort_test.php Breakpoint 1, zend_hash_index_exists (ht=0x7ffff7059780, h=1001) at /home/your_pc/dev/c/php-src/Zend/zend_hash.c:2030 2030 IS_CONSISTENT(ht);
素晴らしい、私たちは実行のスレッドの中にいます！
PHPコードのどこにいるかを確認するには、次のコマンドを実行します。
(gdb) zbacktrace
結果は、エントリポイントが正しく決定されたことを示しています。
[0x7ffff7015240] array_key_exists(1001, array(251)[0x7ffff70152a0]) [internal function] [0x7ffff7015030] (main) /home/your_pc/array_w_sort_test.php:14
ソースコード内を移動するには、次のコマンドを使用します。
(gdb) next
または
(gdb) step
前者は途中で発生する機能に該当せず、後者はそれに応じて機能します。
コマンドを実行して、関数が呼び出されるパラメーターを表示します。
(gdb) info args ht = 0x7ffff7059780 h = 1001
htはハッシュテーブルへのポインタ、hは検索するキーです。
そして、次の行に進みます。
if (ht->u.flags & HASH_FLAG_PACKED) {
次は、条件が満たされます！ さて、ソートせずにテストのために同じステップを実行しましょう-条件は満たされていません！ まあ、私たちはそのような「プラグ」を見つけました。 よく見てみましょう。
PHPテーブルのハッシュの構造について少し。
ptypeコマンドを実行して、htハッシュテーブルの内容を確認します
(gdb) ptype ht type = const struct _zend_array { zend_refcounted_h gc; union { struct {...} v; uint32_t flags; } u; uint32_t nTableMask; Bucket *arData; uint32_t nNumUsed; uint32_t nNumOfElements; uint32_t nTableSize; uint32_t nInternalPointer; zend_long nNextFreeElement; dtor_func_t pDestructor; } *
ここに興味があります：
- arData -Cバケットを含む配列。 Bucket-zvalを含むC構造体-格納された要素、php配列のキー、およびこのキーのハッシュも数値として。
- NnumUsed - arData + 1配列の最大ビジーインデックス。
- u.flags-各ビットがフラグに対応する符号付き整数なし。
- さらに、構造を注意深く見て、キーハッシュがarData配列にどのようにマッピングされるかを尋ねますか？ これを行うために、PHP開発者は変換テーブルを使用します 。 arData配列（ arData [-1] 、 arData [-2]など）の「背後」に保存され、 arData配列のインデックスへのハッシュのマッピングです。
- 最後に、ハッシュ操作は整数キーには適用されず、テーブルのハッシュキーに「そのまま」変換されることを知っておく必要があります。
コードに戻る
ht→u.flagsは 、数値に折り畳まれた一連のフラグです。 HASH_FLAG_PACKEDフラグについては、3番目のビットに興味があります。
フラグの値を取得するには、次のコマンドを実行します：
(gdb) print ht->u.flags $1 = 30
ですから、3番目のビットでは1つです。
条件が真であるため、ここに到達します。
if (h < ht->nNumUsed) { if (Z_TYPE(ht->arData[h].val) != IS_UNDEF) { return 1; } } return 0;
1行目では、検索キーの値がarData配列に関して有効かどうかを確認します。 その場合、要素がアドレスhの arData配列に含まれているかどうかのみを確認できます。
さて、 HASH_FLAG_PACKEDフラグが設定されていない場合、ここに到達します
p = zend_hash_index_find_bucket(ht, h);
この関数は必要な要素を検索しますが、既に上記の変換テーブルを使用しています。
まあ、それはすべて魔法です。 デバッガーを閉じることができます。 残り1問です。 しかし、 HASH_FLAG_PACKEDフラグとは正確に何であり、どこに表示されますか？
このフラグは、 パックされたハッシュテーブルの最適化について通知します。php配列のすべてのキーは数字であり、昇順でソートされます。 テスト例について推測することは難しくありません;このフラグはsort関数内で設定されます。 結局のところ、そのような最適化は、言語での作業のかなり多くの側面に影響します。 ここでは、おそらく、他の記事を書くことはできません。
そして、私の話はここで終わります。php+ dbgを操作するコツをいくつか調べて、ハッシュテーブルアルゴリズムの興味深い最適化の1つに注目しました。 上記の方法がすばらしいPHPツールの探索に役立つことを願っています。