ようこそゲストさん

CPA-LABテクニカル

2008/03/16(日) PHPの配列上限数-PHP変数管理

配列の個数制限

PHP*1では、配列の管理にハッシュテーブル(シンボルテーブル)を使用している
そのサイズは、実質31bitであり*2、上限は16進数で80,000,000、10進数では、
21億4千7百83万3千6百48個となる。

地球の人口は66億人を超えているそうなので、全人類のデータを一度に配列に納める時には、注意しなければならない。

この制限は、ひとつのハッシュテーブルの個数なので、複数に分割、この場合は4つの変数に分割すれば、全人類データを一度に入れるに納めることが、できる*3*4


参考:世界の人口は現在

*1 : バージョン5.2.5

*2 : 32bitのuint(符号なし単精度)を使用しているけど、半分しか使わない構造になっている

*3 : 誰も突っ込まないと思うけど、その前にメモリが足りなくなる

*4 : ただし、環境によっては、個数管理に使われている変数の型unsigned int は一般的には32bitだけど、64bitのこともあるそうなので、その場合は、余裕で全世界の人々のデータを一度に配列にぶち込める。

下限は?

一番最初に作られる配列の個数は8個である。
1つの配列要素を作っただけでも*5、8個分のハッシュテーブルが用意される。


ZEND_API int _zend_hash_init()メソッドの中で、こんな感じ。
ht->nTableSizeがテーブルサイズである。
uint i = 3;
while ((1U << i) < nSize) { ## 1U 符号なしの1
    i++;
}
ht->nTableSize = 1 << i; 
(一部省略している部分あり)
nSizeは、array_init より、ゼロでコールされているので、デフォルトのiの回数3回だけ、2進数0001が左へビットシフト*6され、1000(2進数)、10進数では8となる。


PHPでは、当初、この8個の枠の中で配列をやりくりするが、足りなくなると、ひとつづつ左へビットシフトする。
つまり、配列の要素を使うにしたがって、その配列の個数の上限は、

8個→16個→32個→64個→128個→256個→・・・・→1024個→・・・→21億4千7百83万3千6百48個

と段階的に増えていく。

*5 : いや、0個 $a=array(); でも

*6 : C言語での<<は、左ビットシフトの意味。<< 1は、2の1乗、<< 2は、2の二乗を表す。

どうしてこんな管理方法なのか?

  • 「配列の個数なんて増やす度に、カウント++でええやん」
という考え方もあるが、ハッシュテーブルの考え方が、
  • 「大目に個数を確保しておいて、文字列キーを上手に数値に変換して、素早く探す」
ということなのと、ビット演算は、内部でのハッシュ関数と密接に関係する*7ので、このような実装になっているのであろう。

なお、
  • PHP関数のハッシュ関数 と ハッシュテーブル は、全く違うもの
名前こそハッシュとついているが、全くの別物である。「任意の文字列から、一意のデータを出力する」というハッシュアルゴリズムの考え方は同じであるけど、ハッシュ関数と呼ばれるmd5,hsaなどは、あくまでも、任意の文字列から、文字列のハッシュ値を計算するもの。
ハッシュテーブルは、ハッシュアルゴリズムは使用するけど、md5やhsaではなくて、独自のハッシュ関数を実装し、それをさらにC言語の配列のキーとして利用する*8


また、
  • PHP関数のハッシュ関数md5,hsaなどは、最後のアウトプットは文字列
  • ハッシュテーブルで実装されるハッシュ関数*9の最後のアウトプットは、数値
という点も大きく違う。


ハッシュテーブルの構造については、またいつか別項にて記載したい。

PHP変数管理の目次はこちら

*7 : いつか別項で書きたい

*8 : C言語の配列キーは数値のみ

*9 : PHPの内部的に使われる


名前:  非公開コメント   

  • TB-URL  http://www.cpa-lab.com/tech/0112/tb/