最近はWindowsアプリケーションの制作にC#を使ってるんですが、Haxe/C++ってどうなのよ、C++と比べてどのくらいの速さなのよ?ってことが気になったので速度比較しました。つかったのは、マージソートです。理由は先日のCODE VS 2.0(http://codevs.jp/)で配列操作がボトルネックになってるように見えたからです。
マージソートって何?って人もいると思うのでちょっと紹介。
右上のrandomを押したあと、左上でMargeを選択してみましょう。
このような方法で数字の大小を比較して、順番に並べるのがマージソートです。
速度比較用コード
Haxe
package; class Main { static inline var SIZE = 1000000; static function main() { var start = getTime(); var arr = new Array<Int>(); //Neko,PHP,Java,C#は初めに領域確保。これをやらないと配列を伸ばすごとに時間がかかる。 #if (neko || php || java || cs) arr[SIZE - 1] = 0; #end for( i in 0...SIZE ){ arr[i] = SIZE - i; } margeSort( arr ); var time:Int = Math.round(getTime() - start); trace( time + "ms" ); } public static function margeSort( arr:Array<Int> ){ var l = arr.length; var tmp = new Array<Int>(); #if (neko || php || java || cs) tmp[SIZE - 1] = 0; #end var i = 1; while( i < l ) { var j = 0; while( true ){ var l0 = j + i; if( l0 >= l ) break; var l1 = l0 + i; if( l1 > l ) l1 = l; var p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0; while ( true ){ if( val0 <= val1 ){ tmp[ tp++ ] = val0; if( ++p0 == l0 ) break; val0 = arr[ p0 ]; }else{ tmp[ tp++ ] = val1; if( ++p1 == l1 ){ var tl = l0 - p0; copyArray( arr, p0, arr, l1 - tl, tl ); break; } val1 = arr[ p1 ]; } } copyArray( tmp, 0, arr, j, tp ); j = l1; } i <<= 1; } } public static inline function copyArray( source:Array<Dynamic>, sourceIndex:Int, target:Array<Dynamic>, targetIndex:Int, length:Int ) { var i = length; while( --i >= 0 ) target[targetIndex + i] = source[sourceIndex + i]; } public static inline function getTime() { #if (flash || js || cs) return Date.now().getTime(); #else return Sys.time() * 1000; #end } }
関数の頭にinlineと付けるだけでインライン展開できるのがポイント。Haxeから出力されたC++では、copyArrayの関数自体は消えてなくなり、中身のループが呼び出し位置に展開された形になります。
あと、配列の長さが指定できないのが特徴で、PHP, Neko, C#, Javaに出力する際は注意が必要になります。これらの言語を選択した場合、配列の長さを伸びるごとに配列の長さに比例した時間が取られてしまいます。あらかじめ配列を伸ばしておいてから数値を代入しましょう。
せっかくなので、JavaScript, AIR, NekoVM, PHP, C++, C#, Javaに出力しました。上のコードでこれらすべての言語に対応してます。
C#
using System; using System.Diagnostics; namespace SpeedTest{ class Program{ public const int SIZE = 1000000; public static void Main(string[] args){ var sw = new Stopwatch(); sw.Start(); int[] arr = new int[ SIZE ]; for( int i = 0; i < SIZE; i++ ){ arr[i] = SIZE - i; } MargeSort( arr ); Console.WriteLine( sw.ElapsedMilliseconds + "ms" ); Console.ReadKey(true); } //小さい順にソート public static void MargeSort( int[] arr ){ int l = arr.Length; int[] tmp = new int[l]; for( int i = 1; i < l; i <<= 1 ){ for( int j = 0, l0, l1; ; j = l1 ){ l0 = j + i; if( l0 >= l ) break; l1 = l0 + i; if( l1 > l ) l1 = l; int p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0; while( true ){ if( val0 <= val1 ){ tmp[ tp++ ] = val0; if( ++p0 == l0 ) break; val0 = arr[ p0 ]; }else{ tmp[ tp++ ] = val1; if( ++p1 == l1 ){ int tl = l0 - p0; var targetIndex = l1 - tl; var i1 = tl; while(--i1 >= 0) { arr[targetIndex + i1] = arr[p0 + i1]; } break; } val1 = arr[ p1 ]; } } { var i1 = tp; while(--i1 >= 0) { arr[j + i1] = tmp[i1]; } } } } } } }
copyArrayの部分はループに変更しています。普段ならそんなめんどくさいことやらないでArray.Copy()を使ってますが、Array.Copy()使うと50msくらい遅くなります。
C++
#include <iostream> #include <time.h> using namespace std; int SIZE = 1000000; void margeSort( int* arr, int l ){ int* tmp = new int[l]; for( int i = 1; i < l; i <<= 1 ){ for( int j = 0, l0, l1; ; j = l1 ){ l0 = j + i; if( l0 >= l ) break; l1 = l0 + i; if( l1 > l ) l1 = l; int p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0; while( true ){ if( val0 <= val1 ){ tmp[ tp++ ] = val0; if( ++p0 == l0 ) break; val0 = arr[ p0 ]; }else{ tmp[ tp++ ] = val1; if( ++p1 == l1 ){ int tl = l0 - p0; int targetIndex = l1 - tl; int i1 = tl; while(--i1 >= 0) { arr[targetIndex + i1] = arr[p0 + i1]; } break; } val1 = arr[ p1 ]; } } { int i1 = tp; while(--i1 >= 0) { arr[j + i1] = tmp[i1]; } } } } } int main() { int start = clock(); int* arr = new int[SIZE]; for( int i = 0; i < SIZE; i++ ){ arr[i] = SIZE - i; } margeSort( arr, SIZE ); std::cout << (clock() - start) << "ms\n"; return 0; }
C++は苦手です。やりようによってはまだまだ高速化できるのかもしれませんが、わからないのでできません。C#のコードをなるべくそのまま移植しました。
Java
public class Main { public static final int SIZE = 1000000; public static void main(String[] args) { // TODO code application logic here long start = System.currentTimeMillis(); int[] arr = new int[ SIZE ]; for( int i = 0; i < SIZE; i++ ){ arr[i] = SIZE - i; } margeSort( arr ); System.out.println( (System.currentTimeMillis() - start) + "ms" ); } //小さい順にソート public static void margeSort( int[] arr ){ int l = arr.length; int[] tmp = new int[l]; for( int i = 1; i < l; i <<= 1 ){ for( int j = 0, l0, l1; ; j = l1 ){ l0 = j + i; if( l0 >= l ) break; l1 = l0 + i; if( l1 > l ) l1 = l; int p0 = j, p1 = l0, val0 = arr[p0], val1 = arr[p1], tp = 0; while( true ){ if( val0 <= val1 ){ tmp[ tp++ ] = val0; if( ++p0 == l0 ) break; val0 = arr[ p0 ]; }else{ tmp[ tp++ ] = val1; if( ++p1 == l1 ){ int tl = l0 - p0; System.arraycopy( arr, p0, arr, l1 - tl, tl ); break; } val1 = arr[ p1 ]; } } System.arraycopy( tmp, 0, arr, j, tp ); } } } }
C#のコードをほぼそのまま移植しました。こうやって見るとほんとC#にそっくりです。配列のコピーはループよりSystem.arraycopy()のが高速でした。
PHP
<?php function margeSort($arr) { $l = count($arr); $tmp = array(); for ($i = 1; $i < $l; $i <<= 1) { $j = 0; while(true) { $l0 = $j + $i; if($l0 >= $l) { break; } $l1 = $l0 + $i; if($l1 > $l) { $l1 = $l; } $p0 = $j; $p1 = $l0; $val0 = $arr[$p0]; $val1 = $arr[$p1]; $tp = 0; while(true) { if($val0 <= $val1) { $tmp[$tp++] = $val0; if(++$p0 === $l0) { break; } $val0 = $arr[$p0]; } else { $tmp[$tp++] = $val1; if(++$p1 === $l1) { $tl = $l0 - $p0; $targetIndex = $l1 - $tl; $i1 = $tl; while(--$i1 >= 0) { $arr[$targetIndex + $i1] = $arr[$p0 + $i1]; } break; } $val1 = $arr[$p1]; } } { $i1 = $tp; while(--$i1 >= 0) { $arr[$j + $i1] = $tmp[$i1]; } } $j = $l1; } } } define( "SIZE", 1000000 ); $start = microtime(true) * 1000; $arr = array(); $_g = 0; while($_g < SIZE) { $i = $_g++; $arr[$i] = SIZE - $i; } margeSort($arr); $time = floor(microtime(true) * 1000 - $start); echo $time."ms"; ?>
Haxe/PHPがあまりにもかわいそうな結果だったので、PHPも書きました。こっちのがいくらかマシです。
結果
速い順です。
言語 | 時間[ms] | C++との比較 |
---|---|---|
C++ | 37 | – |
C# | 72 | 1.95倍 |
Java | 74 | 2倍 |
Haxe/C++ | 119 | 3.22倍 |
Haxe/JS [Node.js] | 274 | 7.41倍 |
Haxe/C# | 501 | 13.5倍 |
Haxe/AIR | 744 | 24倍 |
Haxe/Java | 1155 | 31.2倍 |
Haxe/Neko | 4282 | 116倍 |
PHP | 19853 | 537倍 |
Haxe/PHP | 132853 | 3590倍 |
やはりC++が高速。続いて、C#,Javaがほぼ同じ。ちょっと遅れてHaxe/C++。
Haxe/C++とC#で結構な差があるように見えますが、先述のArray.Copy()でひっくり返りかねない差なので、C#,Java,Haxe/C++は同じくらいのレベルと考えていいと思います。個人的にC++はあまり使いたくないので、速さが必要なプログラムはこの3つのどれかで作ることになるでしょうか。
Haxeはマージソートくらいだと他言語に簡単に移植できるのがいいですね。ついでなので他の言語への移植もしてみましたが、Haxe/JSはかなり健闘しました。Node.jsって遅いイメージがあったんですが、かなり高速らしいです。
Haxe/AIRは、まあ普通という感じです。AS3で書いてもこのへんになる気がします。
Haxe/C#、Haxe/Javaはベータ版ということもありまだ洗練されていないように見えます。これからに期待。
Haxe/Nekoも遅いですね。Node.jsの方がはるかに速いです。
PHPが遅いのは当然の結果ですね。C++の500倍遅かろうとPHPは良い言語ですし…。そもそも、PHPで速度が必要なプログラム書くこと自体が間違ってますし…。HTML生成できて、JSON出力できて、データベース操作できて、exec()でコマンド実行出来れば、それだけでPHPは価値があると思いますね。
Haxe/PHPはさらに遅いです。PHPはただでさえ遅いのに配列に独自のクラスをつかってるので、無駄な関数呼び出しが発生してるようでした。Haxe/PHPはPHPの良い部分も死んでる(HTMLに直接書き込めない、1ページに1プロジェクト必要など)気がするので、自分が使う機会はなさそうです。
ともあれ、Haxe/C++, Haxe/JS, Haxe/Flash(AIR)はかなり実用的だと思います。これだけできれば、モバイルでも、ブラウザでも、サーバーサイドでも、PCネイティブでも使えるので、プラットフォームと使える言語がマッチしなくて困ることはほぼ無さそうです。
Haxeに興味を持った人はとりあえず公式サイト(http://haxe.org/?lang=jp)にどうぞ。
使った環境について
Windows 7 Home Premium 64-bit
Intel(R) Core(TM) i5-2430M
メモリ: 4G
Haxe 2.10, cygwin gcc 3.4.4(C++), .NET Framework 4.5(C#) 4.0(Haxe/C#), Visual Studio 2010(Haxe/C++), node.js 0.8.11, AIR 3.4, neko vm 1.8.2, php 5.3.10
お久しぶりです。以前にぼろぼブロックでずいぶん遊ばさせてもらったsappyです。
ぼろぼブロックの記事が無かったので、こちらの記事でコメントします。(記事と関係無くて申し訳ないです)
この前、ふと気が向いて、以前の問題を改良して別の問題を作ったので掲示板の方に書き込もうとしたのですが、
以下の文章が出て書き込めませんでした。
お手数ですが、何とかならないでしょうか?
よろしくお願いいたします。
(ちなみに問題はこれです。
22315152315523021123021130500030015530031130013130100211000011013213313170203262262600043000000043283519488
)
Warning: fopen(datumababas/yy1.txt) [function.fopen]: failed to open stream: 許可がありません in /virtual/shohei909/public_html/bbs/yybbs.php on line 184
Warning: flock() expects parameter 1 to be resource, boolean given in /virtual/shohei909/public_html/bbs/yybbs.php on line 185
書き込みに失敗しました。もう一度送信してください
Warning: fclose(): supplied argument is not a valid stream resource in /virtual/shohei909/public_html/bbs/yybbs.php on line 195
報告ありがとうございます。
http://spheresofa.net/bbs/ の掲示板ですね。
書き込みできない状況だったのを確認しました。
ただスパム放置の状態だったので、別掲示板を設置することで対応しようと思います。
2月中には開設しますので、今しばらくお待ちください。
sappyさま
おまたせしました!新掲示板設置しました。
http://spheresofa.net/bbs/board/
お疲れ様です。
ありがとうございます。