Cレベルの低レベルなレイヤでは、配列はどう実装されているのか?

翻訳その2。だんだん和訳が目的っぽくなってきてめんどい。とりあえずやっつけで書いとく。

こっちの方が新しいらしい。
元ネタ:http://stackoverflow.com/questions/2350361/how-is-the-php-array-implemented-on-the-c-levelその魚拓

質問

The PHP array is one of the language's core features IMHO. It is sparse, allows multi-typed keys in the same array, and supports set, dictionary, array, stack/queue and iterative functionality.

BUT after working with PHP for a while now, I've found that quite a few of the array_* functions are much slower than you'd think at first glance. Like in the case of array_rand on a very large array (10000+). array_rand is so slow in fact, that in cases where your using the php array as an indexed array, a function like rand( 0, array_length( $array ) - 1 ) runs MUCH faster than array_rand.

Now onto my question.

How is the PHP array implemented on the C level? This would be very helpful for predicting the Big O of a function that heavily uses the different functionality of the PHP array datatype.

asked Feb 28 '10 at 6:54
Kendall Hopkins

私見だけど、PHPの配列は言語のコア*1に含まれる機能だと思う。
*2同一の配列で異なる型のキーを利用でき、集合、辞書、スタック/キュー、(キーやインデックスにより)繰り返し処理が出来る機能として利用できるよね。

でも、しばらくPHPで仕事をしてきた今、多数のarray_*関数は、君たちがぱっと見て期待するよりずっと遅いことに気づいたんだ。例えば、大きい配列(要素が10000以上くらい)に対するarray_randとか。実際、array_randはめっちゃ遅くて、rand(0, array_length($array) - 1)の方がずっと速く動くんだ。

で、質問なんだけど。

CのレベルでPHPの配列ってどう実装されてんだろ?PHPの配列は異なる機能【前述の配列や連想配列や集合やスタックなど】として、とても頻繁に使われるけど、この事*3は、その関数*4の計算量を予測する助けになるんじゃないかな。

返信

Take a look at the source code: http://svn.php.net/viewvc/php/php-src/trunk/ext/spl/spl_array.c?view=markup

Feb 28 '10 at 16:01
Gumbo

ソースコード読めっつーの。

回答1

See this comment in the documentation confirming your dilemma that array_rand, while fast for small arrays, scales very poorly.

I modified fake_array_rand to always only return 1 element, and did some benchmarks against calling array_rand with the second parameter as 1. I ran 100 samples for each function for each number of elements and took the average result. While the internal array_rand is faster for a small number of elements, it scales very poorly.

1 elements: 2.0619630813599E-05 sec. for array_rand,8.4352493286133E-05 sec. for fake_array_rand
10 elements: 2.1675825119019E-05 sec. for array_rand,8.427619934082E-05 sec. for fake_array_rand
100 elements: 2.9319524765015E-05 sec. for array_rand,8.4599256515503E-05 sec. for fake_array_rand
1000 elements: 0.0001157283782959 sec. for array_rand,8.5572004318237E-05 sec. for fake_array_rand
10000 elements: 0.0016669762134552 sec. for array_rand,8.5201263427734E-05 sec. for fake_array_rand
100000 elements: 0.015599734783173 sec. for array_rand,8.5580348968506E-05 sec. for fake_array_rand
1000000 elements: 0.18011983394623 sec. for array_rand,8.6690187454224E-05 sec. for fake_array_rand

<?php 
function fake_array_rand ($array) 
{ 
  $count = count ($array); 
  # Help keep the number generator random :) 
  $randval and usleep ("0.$randval"); 

  # Seed the random number generator 
  # Generate a random number 
  srand ((double) microtime() * 10000000); 
  $randval = rand(); 

  # Use the random value to 'pick' an entry from the array 
  # Count the number of times that the entry is picked 
  ++$index[$randval % $count]; 

  return $array[$randval % $count]; 
} 
?>

http://us.php.net/manual/en/function.array-rand.php#22360

answered Feb 28 '10 at 15:57
Chacha102

ドキュメントの中に、君が言ってる「array_rand()は、配列が小さいうちは速く動くけど、nの増加に伴う所用時間の増加がハンパない」という問題を裏付ける次のコメントがあるから、参照すると良いよ。
<略>

返信

That's exactly what I'm talking about. It seems the array datatype doesn't have the ability to seek to an offset in O(c) time, like a normal array in C would. Instead it seems to do a linear poll which is O(n), which gets pretty scary quick when it's put into a loop (O(n^2)). On a side note, that's a pretty horrible use of srand.

Feb 28 '10 at 16:07
Kendall Hopkins

そうそう!僕が言ってるのはそれ。普通のCと違って、配列はオフセット*5をO(c)*6で探せないっぽいんだよね。その代わり、O(n)の線形探索*7をするみたいで、O(n^2)のループ*8の中で使うと酷いことになるよ。あ、あと、srandすんのは最悪やなぁ*9 *10

返信

Why O(n)? It's direct access. It's slower, but in good enough hash function doesn't relate to the number of elements in array. See my answer.

Feb 28 '10 at 17:23
Sagi

なんでO(n)なんだ?ダイレクトアクセスだろ。遅いけど、まともなハッシュ関数の中では、計算量は配列の要素の個数に関係しないよね。僕のコメントも参照してみて。

返信

Sorry I wasn't clear that I was talking about using array_rand in the loop. The way array_rand is implemented it has to use linear polling though the linked-list to find the offset it randomly generated, since it doesn't know if there are gaps in the range.

Feb 28 '10 at 17:34
Kendall Hopkins

array_randをループの中で使うことに関して話してたんだが、それが分かりづらかったみたいでスマソ。array_randの実装では、キーの範囲の中に切れ目があるかどうか分からないから線形探索をしないとダメなんだよな*11

返信

Yes, that's true. And your solution is impressive. Worth trying profiling with several arrays and adding this kind of optimization to PHP source code.

Feb 28 '10 at 19:27
Sagi

うん、その通りだと思うよ。PHPのソースにこの最適化を追加して分析してみる価値はありそうだね。

回答2

Take a look at zend/zend_hash.c and zend/zend_hash.h

I don't know c, but to me it looks like a chained hash table.

answered Feb 28 '10 at 16:22
chris

zend/zend_hash.c と zend/zend_hash.hを読めばいいんじゃね?

俺はCは知らんけど、チェインハッシュか何かじゃね?

回答3

Since PHP arrays are ordered maps (even when using contiguous integer indices) array_rand() likely has to cons up a list of keys to select an element from. I'm guessing that it would be prohibitively space and time ineffective to cache the (frequently invalidated) key list so every call is going to incur at least an O(n) traversal and construction cost.

Because your rand(... length ...) implementation takes advantage of the special knowledge you have that the keys are contiguous integers, you'll get O(log n) lookup costs. This seems consistent with Chacha102's data.

answered Feb 28 '10 at 16:58
msw

PHPの配列は(たとえそれが連続した整数の配列だとしても)順序付きマップだから、array_rand()は要素を選択するために、キーのリスト*12を連結していく*13だろうね。
各呼び出しにおいて、走査と(戻り値の)構築にかかるコストを少なくともO(n)にする為に、キーのリストをキャッシュしておくことは、空間的にも時間的にもとても無駄なことだと思う。

君が書いたrand(... length ...) は、連続した整数のキーを持っているという特別な情報を持つことで有利になるから、検索にO(log n)のコストで済むだろう。このことはChacha102氏のデータとも合致するね。

回答4

PHP associative arrays are in fact implementation of HashTables.

Internally, it is possible to make numeric arrays or associative arrays. If you combine them, it is associative array.

In numeric arrays, it is very similar to C. You have array of pointers to ZVAL structs.

Because pointers have fixed-length (let's call it n), the offset (x) calculation is easy: x * n.

In PHP types are ZVAL structs (because that way it implements dynamic types), but it also helps in associative array, because you can assume fixed-length. So even if direct access to array is slower, it is still considered O(1).

So what happens in string keys? PHP uses hash function to convert them to intergers.

Searching in numeric and associative array has similar efficiency, because internally they are all numeric.

Only direct-access to array keys is slower, because of the additional level (hash function).

answered Feb 28 '10 at 17:08
Sagi

edited Dec 10 '10 at 3:14
alex

PHP連想配列は、ハッシュテーブルで実装されているよ。内部的には*14、配列*15連想配列にしろ作れるよ。配列を連想配列に変換してしまえば、連想配列になってまうよ。

配列はCにとても似てて、ZVAL構造体へのポインタ配列を持ってる。

ポインタは固定長(以下n)だから、オフセットxは簡単に x*n で求められる。

PHPでは型はZVAL構造体で(動的型がそうやって実装されてるから)、固定長だと見なせる*16から、???*17。だからたとえ配列へのランダムアクセスであっても遅いけど、でも定数時間だと見なせるよ。

んじゃ、文字列のキーに対して何が起きると思う?PHPはキーを整数へ変換するハッシュ関数を使うんだ。

内部的には全部配列だから、配列にしろ連想配列にしろ効率は似たようなもんさ。

ハッシュ関数かます分、キーへ直接アクセスするのだけが遅いんだよ。

回答5

After reading over zend/zend_hash.h and ext/standard/array.c I think I have found the answer (Thankyou Chris and gumbo for the suggestions).

The PHP array is a chained hash table (lookup of O(c) and O(n) on key collisions) that allows for int and string keys. It uses 2 different hashing algorithms to fit the two types into the same hash key space. Also each value stored in the hash is linked to the value stored before it and the value stored after (linked list). It also has a temporary pointer which is used to hold the current item so the hash can be iterated.

The catch for the array_rand function is that in order to assure that key is truly random, the array_rand function must iterate over the array rand(0, count($array)) times (O(n)). This is because there is no way to move to an offset in the hash table in O(c) time because there is no guarantee that there isn't missing keys in the range.

This discovery has somewhat troubled me, because it means there is NO datatype in PHP that has normal C array characteristics. Now most of the time this is ok, because hash lookups are very faster, but it's faults show through in cases like array_rand.

Another thing that also troubled me was the difference between the implementation of array_key_exists and in_array. array_key_exists uses the hash lookup (most of the time O(c)) to see if a key is in the array, while in_array has to linearly search the hash (O(n)).

Consider the two examples below:

in_array version

<?php
$array = range(0, 100000);
if( in_array( $random_key, $array ) ) {
  //we found a value
}
?>

array_key_exists version

<?php
$array = array_fill_keys( range(0, 100000), NULL );
if( array_key_exists( $random_key, $array ) ) {
  //we found a value, err key
}
?>

While the in_array version looks much cleaner and simpler to understand, it's actually very slow on large arrays (O(n)), where array_key_exists (despite is annoyingly long name) is very fast (O(c) or close).

In conclusion: I wish there was a transparent flag in the zend HashTable data-structure that would be set in cases where the array was created using array_push or array[] = $value that would allow for scaling like a C array instead of a linked list.

answered Feb 28 '10 at 17:12
Kendall Hopkins

zend/zend_hash.hとext/standard/array.cを読み終わって分かったよ。(Chrisとgumbo、提案ありがとう。)

PHPの配列は整数と文字列のキーを利用できる、チェイン型のハッシュ表だった(値の検索はO(c)で、キーの検索はO(n))。それら2つの型*18を同一のキースペース*19に適合させるために、2つの異なったハッシュアルゴリズムが使われてる。ハッシュ表に格納される各値は、前に格納された値、次に格納される値とリンクされる(連結リスト)。また、ハッシュ表の値を巡回するために、現在の値を指す一時的なポインタも持っている。

これらの発見で少し懸念があるんだよな。だって、PHPにはCの配列の特徴を持ったデータ型が存在しないってことになるやん。ハッシュ表の検索はめっちゃ速いから、ほとんどの場合は良いかもしれないけど、array_randみたいな場合に欠点になるよね。

もいっこの難点だと思うのが、array_key_existsとin_arrayの実装の違いなんだよね。array_key_existsは、キーが配列に存在するか探すためにハッシュ表を使う(だから計算量はO(c)になる*20)。一方で、in_arrayは線形探索をしてるんだ(だから計算量はO(n))。

次の例を見てみてよ。

<コード例は英文の方を参照>

in_arrayの方は見た目綺麗だし理解しやすいけど、実際はデカい配列に対して実行するとめっちゃ遅くて(O(n))、array_key_exitsの方は(長い名前がウザいけど)めっちゃ速いんだ(O(n)かそれくらい)。

ってことで結論:zendのハッシュ表を表すデータ型内に、連結リストじゃなくてC配列みたいなアクセス時間を実現するための、array_pushやarra[]=$valueで生成された配列かどうかを示す透過な*21フラグがあったらなーって思う。

返信

You are right :) But look at SplFixedArray

Feb 28 '10 at 17:26
Sagi

そだねー。でもSplFixedArrayも参照してみ。

*1:ライブラリとして提供されているわけではなく、言語自体に組み込まれている、という言う意味?

*2:「It is sparse,」の意味が取れなかった。

*3:どのように実装されているか知ること

*4:array_randのこと?

*5:任意の要素の位置、つまりランダムアクセスするにはって感じかな?

*6:定数時間って意味かな?

*7:「線形探索」で良いのか?

*8:2重ループってこと?

*9:なんで最悪なのかな?

*10:もしこのfake_array_randがループの中で呼ばれた場合、microtimeが返す値が変化しなかったりするかな?そうすると、randって同じ値を返してきたりするのかな?

*11:thoughをどう訳していいのかわからん

*12:array_rand内部でランダムに選ばれるもの

*13:cons upの訳がよく分からん

*14:「ハッシュ表を使えば配列も連想配列も実現できるよ」って事を言いたいんだろうから、「内部的には」なんて訳さなくても良いのかな

*15:「numeric arrays」を単に配列と訳

*16:何が?

*17:ここ全く分からん...

*18:キーとして利用できる整数と文字列のこと

*19:適当な日本語ェ...

*20:え?キーを探すのが定数時間???

*21:意味が分からん