Clever Geek Handbook

PHP 7は、有効なハッシュテーブルの2倍になります



PHPコアを書き換えるプロセスは飛躍的に始まりました。 この記事は、PHPコアコードの作者の 1人による、ハッシュテーブルなどのデータ構造の最適化で達成された重要な進歩に関する投稿の無料のリテールです。 詳細な技術的詳細

100,000個の整数の配列を作成する簡単なスクリプトは、次の結果を示します。

32ビット 64ビット
PHP 5.6 7.37 MiB 13.97 MiB
PHP 7.0 3.00 MiB 4.00 MiB


テストコード 
$startMemory = memory_get_usage(); $array = range(1, 100000); echo memory_get_usage() - $startMemory, " bytes\n";




ご覧のように、PHP 7は32ビットバージョンで2.5メモリー、64ビットバージョンで3.5倍のメモリを消費します。



叙情的な余談



本質的に、PHPでは、すべての配列は順序付けられた辞書（つまり、キーと値のペアの順序付きリスト）であり、キーと値の関連付けはハッシュテーブルに基づいて実装されます。 これは、整数型が配列キーとして機能するだけでなく、文字列などの複雑な型としても機能できるようにするために行われます。 プロセス自体は次のように発生します-ハッシュは整数である配列キーから取得されます。 この整数は、配列のインデックスとして使用されます。



ハッシュ関数が異なるキーに対して同じハッシュを返す場合、つまり衝突が発生した場合に問題が発生します（実際に発生するのは簡単です-可能なキーの数は無限に大きく、ハッシュの数は整数型のサイズによって制限されます）。



衝突に対処するには2つの方法があります。 1つ目はオープンアドレッシングで、現在の要素が既に使用されている場合に別のインデックスで要素が格納されると、2つ目は同じインデックスを持つ要素をリンクリストに格納します。 PHPは2番目の方法を使用します。



通常、ハッシュテーブル要素はいかなる順序でも並べられていません。 しかし、PHPでは、配列を反復処理して、要素をそこに記述した正確な順序で取得します。 これは、ハッシュテーブルが要素の順序を格納するメカニズムをサポートする必要があることを意味します。



古いハッシュテーブルのメカニズム



この図は、PHP 5でハッシュテーブルがどのように機能するかを示しています。



ダイアグラム内の衝突解決要素は、バケット（バスケット）として指定されます。 そのような「バスケット」メモリごとに割り当てられます。 「バスケット」に保存されている値は、サイズが16または24バイトの個別のzval構造に配置されているため、図には表示されていません。 また、配列の要素の順序を格納するリンクリストは、画像から省略されています。 キー「a」、「b」、「c」を含む配列の場合、次のようになります。



では、なぜ古い構造はパフォーマンスとメモリ消費の点で非効率なのでしょうか？



新しいハッシュテーブルの実装は、これらの欠点に対処するために設計されています。 zval構造は、複雑なオブジェクト（前述の「バスケット」など）に直接含めることができるように書き直され、「バスケット」自体は次のようになり始めました。 

 typedef struct _Bucket { zend_ulong h; zend_string *key; zval val; } Bucket;


つまり、「バスケット」にはハッシュh、キーキー、および値valが含まれるようになりました。 整数キーは変数hに格納されます（この場合、ハッシュとキーは同一です）。

構造全体を見てみましょう。 

 typedef struct _HashTable { uint32_t nTableSize; uint32_t nTableMask; uint32_t nNumUsed; uint32_t nNumOfElements; zend_long nNextFreeElement; Bucket *arData; uint32_t *arHash; dtor_func_t pDestructor; uint32_t nInternalPointer; union { struct { ZEND_ENDIAN_LOHI_3( zend_uchar flags, zend_uchar nApplyCount, uint16_t reserve) } v; uint32_t flags; } u; } HashTable;


「バスケット」はarData配列に格納されます。 この配列は2のべき乗の倍数で、現在のサイズは変数nTableSize（最小サイズ8）に格納されます。 配列の実際のサイズはnNumOfElementsに保存されます。 配列にバスケットへのポインターを保存する代わりに、すべてのバスケットが含まれるようになりました。



要素の順序



arData配列は、アイテムが挿入された順序で保存されるようになりました。 配列から削除されると、要素はIS_UNDEFラベルでマークされ、今後は考慮されません。 つまり、削除されると、ビジーセルカウンターがサイズnTableSizeに達するまで、要素は物理的に配列内に残ります。 この制限に達すると、PHPは配列の再構築を試みます。

このアプローチは、PHP 5と比較して、ポインターの8/16バイトを節約します。素晴らしいボーナスは、配列の繰り返しがメモリの線形スキャンを意味することです。これは、リンクリストをトラバースするよりもはるかに効率的です。

唯一の欠点は、arDataのサイズが減少しないことです。これにより、数百万の要素の配列で大量のメモリが消費される可能性があります。



ハッシュテーブルバイパス



ハッシュはDJBX33A関数によって管理されます。この関数は32ビットまたは64ビットの符号なし整数を返しますが、これはインデックスとして使用するには多すぎます。 これを行うには、ハッシュとテーブルのサイズを1つ減らして「AND」演算を実行し、結果を変数ht-> nTableMaskに書き込みます。 インデックスは操作の結果として取得されます 
 idx = ht->arHash[hash & ht->nTableMask]


結果のインデックスは、衝突配列の最初の要素に対応します。 つまり、ht-> arData [idx]はチェックする必要がある最初の要素です。 そこに保存されているキーが必要なキーと一致する場合、検索を終了します。 それ以外の場合は、目的の要素が見つかるまで次の要素に進むか、INVALID_IDXを取得します。つまり、このキーは存在しません。

このアプローチの利点は、PHP 5とは異なり、二重リンクリストが不要になったことです。



圧縮された空のハッシュテーブル



PHPは、すべての配列にハッシュテーブルを使用します。 ただし、特定の場合、たとえば配列キーが整数の場合、これは完全に合理的ではありません。 PHP 7では、ハッシュテーブル圧縮がこれに使用されます。 この場合のarHash配列はNULLであり、検索はarDataインデックスを通過します。 残念ながら、このような最適化は、キーが昇順の場合にのみ適用できます。 配列[1 => 2、0 => 1]の場合、圧縮は適用されません。



空のハッシュテーブルは、PHP 5およびPHP 7の特殊なケースです。空の配列が残っている可能性が高いことを実践が示しています。 この場合、arData / arHash配列は、最初の要素がハッシュテーブルに挿入されたときにのみ初期化されます。 松葉杖とチェックを回避するために、次の手法が使用されます。デフォルト値以下では、nTableMaskはゼロに設定されます。 つまり、式hash＆ht-> nTableMaskは常にゼロになります。 この場合、arHash配列には、インデックスがゼロの要素が1つだけ含まれ、その要素には値INVALID_IDXが含まれます。 配列を反復処理する場合、常に最初に検出された値INVALID_IDXを探します。この場合、空のハッシュテーブルに必要なサイズがゼロの配列を意味します。



まとめ



上記のすべての最適化により、要素が占有するサイズをPHP 5の144バイトからPHP 7の36（圧縮の場合は32）バイトに減らすことができました。新しい実装のわずかな欠点は、メモリの割り当てがわずかに過剰であり、配列のすべての値が同じ場合に加速が行われないことです。 この場合、PHP 5ではzvalが1つしか使用されないため、メモリ消費量の減少が著しいことを思い出してください。



テストコード 
 $startMemory = memory_get_usage(); $array = array_fill(0, 100000, 42); echo memory_get_usage() - $startMemory, " bytes\n";




32ビット 64ビット
PHP 5.6 4.70 MiB 9.39 MiB
PHP 7.0 3.00 MiB 4.00 MiB


それにもかかわらず、PHP 7は依然として最高のパフォーマンスを示しています。


More articles:


All Articles