Hatena::ブログ(Diary)

hnwの日記 このページをアンテナに追加 RSSフィード

[プロフィール]
 

2017年5月21日(日) PHPの連想配列は常にin_arrayより速いのか このエントリーを含むブックマーク このエントリーのブックマークコメント

プログラムを書いていると、入力値が辞書に含まれているかを調べたいようなことがあります。たとえば、ユーザーに都道府県名を入力させて、それが正しい都道府県名であるかどうかを調べたい、というようなことがあるかもしれません。


このような内容をPHPで書く際、キーに都道府県名を持つような連想配列を作る習慣がある人は多いはずです。これは典型的な連想配列の使い方といえるでしょう。


<?php
$prefs = array(
    "北海道" => true,
    "青森" => true,
    // ...
    "沖縄" => true,
);

if (isset($prefs[$input])) {
    // 都道府県名が正しい時の処理
}

一方で、in_array関数を使うやり方も考えられます。


<?php
$prefs = array(
    "北海道",
    "青森",
    // ...
    "沖縄",
);

if (in_array($input, $prefs)) {
    // 都道府県名が正しい時の処理
}

突然ですが、クイズです。この2つのうち、どちらの方が良いコードでしょうか?


配列から特定の要素を探すコストはO(N)であるのに対し、連想配列から特定のキーを持つ要素にアクセスするコストはO(1)ですから、一般論としては連想配列を使う方が好ましいと言えるでしょう*1。しかし、計算量の議論はNが大きい場合には正しいですが、Nが小さい範囲では係数や定数項など他の要素の影響も無視できないはずです。常に前者の方が良いコードであると言えるだけの材料を我々は持っているのでしょうか。


そこで、今回PHP 5.6.30およびPHP 7.1.5を用いて、配列サイズとアクセス回数を変えながら両者の速度を測定してみました。本稿ではその結果を紹介します。


PHP 5系では連想配列アクセスの方が速い


今回、配列連想配列とで、辞書データの構築時間と検索時間の和を比較してみました。というのも、一定規模の配列になると構築にかかる時間も無視できないため、たとえ検索が遅くても構築が速い方がトータルでは有利になる可能性があるからです。


早速ですが、PHP 5.6.30での実験結果のグラフを示します。両対数グラフなので見方に注意してください。


f:id:hnw:20170521203150p:image


配列サイズというのは辞書に含まれる単語数です。また、アクセス回数というのはその辞書に対する検索の回数です。上記グラフではアクセス回数を固定して配列サイズを倍々で増やしていく、ということをしました。


これを見ると、アクセス回数が8回ある状況であれば連想配列の方が1.2から1.5倍程度は速いと言えそうです。また、アクセス回数128回になると差が絶望的に開きます。検索回数が多い場合は(当然ですが)検索の計算量の差が支配的であることがわかります。


f:id:hnw:20170521203151p:image


連想配列の方がデータの構築に時間がかかるためアクセス回数2回では互角程度になりますが、互角であれば連想配列を使った方が事故は少なそうです。


PHP 7系では配列アクセスに逆転されることがある

面白いことに、PHP 7系だと状況が変わってきます。PHP 7.1.5, アクセス回数8回のグラフを見てみましょう。


f:id:hnw:20170521203829p:image


配列サイズが小さいうちは連想配列有利だったのが、配列サイズ2048あたりで配列が逆転し、サイズ65536あたりで連想配列が再逆転する、というような結果になっています。何が起こったのでしょうか。


配列サイズが小さいうちは配列連想配列とで構築コストに大きな差はありません。この段階で差になってくるのは、in_array($key, $array)関数呼び出しであるのに対し、isset($array[$key])はopcodeにコンパイルされて関数呼び出しにならないということです。PHP関数呼び出しは他のopcode実行に比べるとコストが高いので、この差で連想配列の方が速くなっているのです。


配列サイズが中程度になってくると、配列連想配列の構築コストの差が支配的になってきます。PHP 7からは真の配列と言うべきデータ構造が導入されており*2連想配列と比べて簡潔なデータ構造で済むようになりました。このため、同じサイズであれば連想配列より配列の方が構築コストが低く、PHP 5のときは見られなかった逆転現象が起こるというわけです。


さらに配列サイズが大きくなってくるとO(N)とO(1)というアクセス時の計算量の差が効いてくるので、ふたたび連想配列の方が有利になります。


このように、アクセス回数8付近では複雑な状況が見られるわけです。一方、アクセス回数32であれば基本的には連想配列の方が有利となります。


f:id:hnw:20170521203830p:image


また、アクセス回数8192回では絶望的な差がついてきます。


f:id:hnw:20170521203831p:image


このように、アクセス回数が大きくなってくると予想通り連想配列の方が有利だということがわかります。


一方、アクセス回数が少ない場合に限れば配列を採用する可能性もゼロではないと言えそうです。とはいえ、プログラムの改修などでアクセス回数が増える可能性を考えると基本的には連想配列を採用しておく方が無難でしょう。


この文章をどう読むかについての補足(2017/5/25追記)

一般論として、マイクロベンチの結果に引っ張られすぎるのは良い習慣ではありません。たとえば、echoとprintfとでどちらが速い、みたいな内容に引っ張られて書くコードを変える必要はないでしょう。もしそれがボトルネックになっていることが判明したら、判明した後で変えれば良いはずです。


その一方で、マイクロベンチの速度差がなぜ生まれたのか、その原因を調べることで何らかの新しい知見を得ることもあるはずです。本稿で一番お伝えしたかったのは、その面白さについてでした。


加えて、計算量の話題、オーダーの違いの怖さ、といった部分も盛り込んだわけですが、このあたりは実感が無い人もいるのかもしれません。私個人の意見としては計算量の観点で不利な実装を採用する際は常に理由が必要だと思っており(もちろん保守性も大事な理由です)、「まとめ」もそのような前提で書かれていますが、世界中の全員が同じ前提を持っているわけではないとも思います。


まとめ

PHP連想配列配列in_array()とで、どちらが有利かを検討してみました。


  • PHP 5.6では連想配列が有利
  • PHP 7では「真の配列」のおかげで配列が有利な状況もありうる
    • アクセス回数小、配列サイズ中程度の場合に限る
    • 配列の方が検索コストは高いが、構築コストが低いため
  • 現実には配列が正解という状況は少ないはず
    • アクセス回数と配列サイズの両方が極端に少ない場合は配列の方が読みやすいかも

連想配列の方が有利だというのは特に驚きのない結論ですが、PHP 7の「真の配列」による性能向上が垣間見えたのは面白いと感じました。


ネイティブコードにコンパイルするような言語であれば、辞書サイズが小さいときは連想配列よりも配列が正解という状況もありうると思うんですが、PHPの場合はin_array()関数呼び出しであることのペナルティが大きく、そのような状況は確認できませんでした。


追試用資料

筆者の手元のマシンはCore M採用のノートマシンであり、Turbo Boostのせいで結果が安定しなかったりするので、結果の信用性は保証できません。追試したいと思われた方は下記URLをご確認ください。


*1:たとえば入力値が辞書に存在しないことを示す場合に、配列だと全要素とN回の比較が発生しますが、連想配列だとハッシュ値が一致する要素(平均では1要素)と比較すれば良いので、計算の効率が格段に違うことになります

*2:参考資料:「PHP7で変わること ——言語仕様とエンジンの改善ポイント

2017年5月20日(土) PHPのシンボルテーブルを覗いてみる このエントリーを含むブックマーク このエントリーのブックマークコメント

PHPのシンボルテーブルというのはC実装のレベルの用語で、その時点で有効な変数テーブルのことを指します。つまり、グローバルスコープならグローバル変数を管理する変数テーブル関数スコープならローカル変数を管理する変数テーブルの意味になります。


今回、自作エクステンションhnw/php-arraydumperでシンボルテーブルvar_dump()するだけの関数symbol_table_dump()を実装してみました。下記のように使います。


<?php
function foo($a = 1) {
    $b = 2
    symbol_table_dump();
}
foo("bar");

出力は次のようになります。


array(2) {
 ["a"]=>
 string(3) "bar"
 ["b"]=>
 int(2)
}

このシンボルテーブル$$varのようなイカれた変数アクセスの際に参照する必要がありますが、そうでも無い限り不要です。通常のローカル変数コンパイル時に全部解決できてしまうので、通常の変数アクセスのみであれば実行時にシンボルテーブルへのアクセスは発生しないのです。


実際、PHP 5.3以降ではローカル変数に対応するシンボルテーブルは必要になるまで作られません。$$varのような変数アクセスがあったタイミングで内部的にzend_rebuild_symbol_table()が呼び出され、そのスコープに対応するシンボルテーブルが構築されます。


逆に言うと、$$varのような変数アクセスを多用するのは性能面ペナルティがあると言えるかもしれません。もちろん致命的な性能差が出るほどではないでしょうし、そもそもそんな変数アクセスをしたい状況が珍しいとは思いますが。

トラックバック - http://d.hatena.ne.jp/hnw/20170520

2017年5月2日(火) Windows Subsystem for Linux上でphp-fpmを動かしてみた このエントリーを含むブックマーク このエントリーのブックマークコメント

最近のWindows 10にはLinuxバイナリをそのまま動かすような仕組みが導入されています。これは Windows Subsystem for Linux (WSL) とか Bash on Ubuntu on Windows (BoW) などと呼ばれているもので、VM実行でなくWindowsネイティブLinuxを動かすという意欲的な取り組みです。


この環境で最新版のPHPソースコードからビルドし、アプリケーションサーバとして動作させてみました。


本稿執筆時点(2017年5月)ではWSL自体がまだ不安定な印象ですが、nginx+php-fpmを動作させることができました。以下はWindowslocalhost 80番ポートでPHPが動作している証拠画像です。「System」欄のunameの表示にMicrosoftという文字列が入っているのがオシャレですね。


f:id:hnw:20170502120845p:image


以下、WSL上でnginx+php-fpmを動かすまでの手順を紹介します。


WSLのセットアップ

Bash on Ubuntu on Windows - Installation Guide」に従ってセットアップします。


PHPビルド

まずはWSL上でPHPビルドしてみましょう。


コンパイル済みバイナリaptインストールしてもいいのですが、普通にビルドできる程度にWSLが安定してるのかな?という興味から自前ビルドしてみました。


まずは必要パッケージをインストールします。


$ sudo apt update
$ sudo apt install build-essential libxml2-dev zlib1g-dev libcurl4-openssl-dev \
    libjpeg62-dev libpng12-dev libmcrypt-dev libreadline-dev libtidy-dev \
    libxslt1-dev libssl-dev libbz2-dev git autoconf

今回はphpenv+php-buildでPHPビルドします。


$ curl -L https://raw.github.com/CHH/phpenv/master/bin/phpenv-install.sh | bash
$ mkdir $HOME/.phpenv/plugins
$ cd $HOME/.phpenv/plugins
$ git clone https://github.com/php-build/php-build.git

下記の内容を .bashrc に追記してシェル再起動します。


PATH=$HOME/.phpenv/bin:$PATH
eval "$(phpenv init -)"

あとはphpenv経由でPHPビルドするだけです。


$ PHP_BUILD_EXTRA_MAKE_ARGUMENTS=-j4 phpenv install 7.1.4

ビルドにはかなり時間がかかるので注意してください。筆者の手元のマシン(Thinkpad X260、Intel Core i7 2.5GHz)で30分以上かかりました。同じビルドが12インチMacBook(Early 2016、Intel Core m5 1.2GHz)で10分を切ることを考えると、まだお仕事で使えるレベルではない印象です。今後のパフォーマンスチューニングに期待しましょう。


ちょっと遅いことを除けば、ビルド自体は正常に終了します。ここまでは普通のLinuxと大差ありません。


nginx+php-fpmの設定

つぎに、nginxをaptインストールします。


$ sudo apt install nginx

設定ファイル /etc/nginx/sites-enabled/default の設定のうち、下記部分のコメントアウトを外して有効化します。


        # pass the PHP scripts to FastCGI server listening on 127.0.0.1:9000
        #
        location ~ \.php$ {
                include snippets/fastcgi-php.conf;
                fastcgi_pass 127.0.0.1:9000;
        }

nginxを再起動します。


$ sudo service nginx restart

php-fpmの方はデフォルトの設定ファイルをコピーしてそのまま使います。


$ cd $HOME/.phpenv/versions/7.1.4/etc/
$ cp php-fpm.conf.default php-fpm.conf
$ cp php-fpm.d/www.conf.default php-fpm.d/www.conf

下記コマンドでphp-fpmを起動します。


$ $HOME/.phpenv/versions/7.1.4/sbin/php-fpm

ここで /var/www/phpinfo.php などを設置すれば、nginx経由でphp-fpmを利用することができます。


ただし、この設定だと1秒に1回下記のエラーが出続けます。getsockopt(2) の実装がまだ不完全のようですね。


[01-May-2017 20:06:06] ERROR: failed to retrieve TCP_INFO for socket: Protocol not available (92)
[01-May-2017 20:06:07] ERROR: failed to retrieve TCP_INFO for socket: Protocol not available (92)
[01-May-2017 20:06:08] ERROR: failed to retrieve TCP_INFO for socket: Protocol not available (92)

TCPでのプロセス通信に問題があるならunix domain socketにすればいいじゃない、と考えてunix domain socketも試してみたのですが、phpinfo() の結果が途中で切れてしまうようです。こちらも実装が不完全なようで、16KB超のデータがうまく扱えないとか、そんな制限がありそうな挙動に見えました。TCPの方がまだ安定している状況だといえるでしょう。


まとめ

WSLはまだbeta版なので過度の期待をする方が悪いと言えばそうなのですが、まだ性能が出なかったり未実装のシステムコールもあったりで、お仕事で使えるようになる日は遠いかな、という印象を持ちました。


とはいえ、長期的に期待できる技術なのは間違いないところでしょう。さらなる安定と正式リリースが待ち遠しいですね。

2017年4月30日(日) アメリカで何年の4月1日がサマータイムだったか調べてみた このエントリーを含むブックマーク このエントリーのブックマークコメント

日付関連のテストケースを書いていたら、ロサンゼルスの1970年4月1日0時はサマータイムではないけれど、2012年4月1日0時はサマータイムであることに気づきました。何かの間違いじゃないかと思って改めて調べてみたところ、ロサンゼルスで4月1日がサマータイムだった年は以下の5つの時期に含まれることがわかりました。



このうち、1番目は第一次世界大戦中に制定された「標準時間法」 (Standard Time Act)によるものです。アメリカでは初のサマータイム導入でしたが、不評のため2年で廃止されたとか(おそらく終戦の影響もあったでしょう)。


2番目は第二次世界大戦時の省エネ対策として通年の「War Time」が実施されたもので、1942年2月9日から1945年9月30日まで継続的に運用されました。


3番目は1948年カリフォルニアで電力危機があり、その対策でカリフォルニア州のみ3月14日から通年のサマータイムが実施されたようです。このころ各州バラバラでサマータイムを実施していたようですが、開始時期は大半が4月でした。


4番目は第一オイルショック1973年)によるもの。1967年から全米でサマータイムが実施されていますが、この開始時期は4月第1週からでした。しかし、オイルショックの影響により1974年は1月6日から、1975年は2月23日からサマータイム開始だったとのこと。


5番目は「包括エネルギー政策法」(Energy Policy Act of 2005)が2007年から施行され、サマータイム開始が4月第1週から3月第2週にズレたことによるもの。


サマータイムについて調べていたはずが、歴史の教科書に載っているような出来事が関係してくるのは面白いですね。


上のリストを作る方法

上記リストは以下のPHPスクリプトを使って求めました。


<?php
for ($i = 1900; $i <= 2017; $i++) {
    $dt = new DateTime("$i-04-01 00:00:00",
                       new DateTimezone("America/Los_Angeles"));
    var_dump($dt->format("c T"));
}

このスクリプトの出力を下記のようにgrepすれば標準時でないもの(≒夏時間)が抜き出せます。


$ php dst-investigate.php | grep -v ST
string(29) "1918-04-01T00:00:00-07:00 PDT"
string(29) "1919-04-01T00:00:00-07:00 PDT"
string(29) "1942-04-01T00:00:00-07:00 PWT"
string(29) "1943-04-01T00:00:00-07:00 PWT"
string(29) "1944-04-01T00:00:00-07:00 PWT"
string(29) "1945-04-01T00:00:00-07:00 PWT"
string(29) "1948-04-01T00:00:00-07:00 PDT"
string(29) "1974-04-01T00:00:00-07:00 PDT"
string(29) "1975-04-01T00:00:00-07:00 PDT"
string(29) "2007-04-01T00:00:00-07:00 PDT"
string(29) "2008-04-01T00:00:00-07:00 PDT"
string(29) "2009-04-01T00:00:00-07:00 PDT"
string(29) "2010-04-01T00:00:00-07:00 PDT"
string(29) "2011-04-01T00:00:00-07:00 PDT"
string(29) "2012-04-01T00:00:00-07:00 PDT"
string(29) "2013-04-01T00:00:00-07:00 PDT"
string(29) "2014-04-01T00:00:00-07:00 PDT"
string(29) "2015-04-01T00:00:00-07:00 PDT"
string(29) "2016-04-01T00:00:00-07:00 PDT"
string(29) "2017-04-01T00:00:00-07:00 PDT"

上のように、タイムゾーン名がPDT(Pacific Daylight-saving Time、太平洋夏時間)やPWT(Pacific War Time、太平洋戦争時間)などと表示されているのがわかります。


PHPの日付関数はTime Zone Databaseを元にしているので、他の言語でも同じ結果を得る方法があると思います。


感想など

調べてみると、省エネ対策としてカジュアルサマータイムを実施している歴史がわかって面白いですね。サマータイムが身近でない日本人の感覚だと「本当に省エネ効果あるの?」という気もしちゃいますけど、きっと効果があるからやってるんでしょう。


また、州ごとに夏時間の適用状況が違うのもアメリカならではです。上のスクリプトを America/Detroit とか America/Phoenix などで試すと全然違う結果になって面白いです。


参考URL

トラックバック - http://d.hatena.ne.jp/hnw/20170430

2017年4月1日(土) PHP 7.1.3で時刻の差を取ると時々1マイクロ秒ズレる このエントリーを含むブックマーク このエントリーのブックマークコメント

本日はエイプリルフールなので、ウソでも本当でも誰も困らないPHPバグの話をします。


PHP 7.1.0からPHPのDateTimeクラスでマイクロ秒の扱いを強化しているようで、挙動やコードの変更がチラホラ見受けられます。(参考:「PHP 7.1からDateTimeが現在時刻のマイクロ秒まで見るようになった - Qiita」)


時刻と時刻の差分を扱うDateIntervalクラスでもPHP 7.1.0以降マイクロ秒に対応したようで、DateInterval::formatメソッドもマイクロ秒の表示に対応しているようです。さっそく実験してみましょう。


<?php
$dt1=new DateTime("2000-01-01 00:00:00");
$dt2=new DateTime("2006-01-02 03:04:05.6");
$interval = $dt1->diff($dt2);
var_dump($interval->format("%R%Y-%M-%D %H:%I:%S.%F"));
/* Output: string(25) "+06-00-01 03:04:05.600000" */

パラメータ%Fで差分のマイクロ秒が表示できました。ところで、次のような例を試すと奇妙なことに気づきます。


<?php
$dt1=new DateTime("2000-01-01 00:00:00");
$dt2=new DateTime("2006-01-02 03:04:05.000251");
$interval = $dt1->diff($dt2);
var_dump($interval->format("%R%Y-%M-%D %H:%I:%S.%F"));
/* Output: string(25) "+06-00-01 03:04:05.000250" */

0と251の差なので「000251」と表示されるはずが「000250」となっており、1マイクロ秒ズレた結果になっています。


ドキュメント化もされていない機能なので誰も困らないと思いますが、一応バグ報告しておきました。


 
ページビュー
2173899