タグ別アーカイブ: altJS

マージソートで速度比較【C#, C++, Java, PHP vs. Haxe】

 最近は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

Haxe vs TypeScript でベンチマーク対決

TypeScriptって速度はどうなの?速いの?ってことが気になったので、HaXeや素のJavaScriptと比較してみました。

比較にはAOBenchを使いました。

比較に使ったプログラム

HaXe版(HaXe2.10 @yoshihiro503さん移植https://github.com/yoshihiro503/aobench_haxe)
TypeScript版(https://github.com/shohei909/TypeScript_AOBench)
JSX版(JSX0.0.2 @kioku_systemkさん移植 http://kioku.sys-k.net/aobench_jsx/)
JavaScript版(http://kioku.sys-k.net/aobench_jsx/)

HaXe版はデッドコード削除を使用するにあたりちょっとだけ改変してあります。TypeScript版はHaXe版を元に書き変えて移植しました。

結果

HaXe TypeScript JSX(修正前) JSX(修正後) JavaScript
Google Chrome (Windows) [ms] 974 995 968 1125 1076
Firefox (Windows) 1544 3698 3766 1604 1649
Browser (Android) 63158 64636 61327 57338 70425
Safari (iOS) 54876 59792 57831 43200 70800
JavaScriptのファイルサイズ [Byte] 6010 8163 7963 17591 6968

HaXeは安定して高速ですね。ファイルサイズも小さくなっています。以前のHaXeはもうちょっと大きいファイルを出力してたんですが、HaXe2.10で強力なデッドコード削除最適化が実装されて、未使用なコードがJavaScriptファイルに反映されなくする–dead-code-eliminationオプションが強化されました。

一方、TypeScriptで出力されたJavaScriptは直訳っぽい素直なコードで読みやすいんですが、あんまり速くありません。基本的にはインライン展開が無い分の差だと思うんですが、気になるのは2倍以上の差がついたFirefoxの結果です。インライン展開されてるはずのJSXでも遅い結果になっています。
続きを読む

HaxeやTypeScriptで使えるソースマップが便利。

JavaScriptを吐く言語を使う場合、ソースマップを使うとデバッグが楽ですよ。

ソースマップを使うとJavaScriptが実行エラーを起こしたときに、JavaScriptの行番号じゃなくってHaXeやTypeScriptの行番号が表示されるようになります。

こんな感じ。

これでまた一つJavaScriptを直接書く理由がなくなりますね。

ブラウザの設定

Chromeだとプラグインなしでこの機能が使えます。

方法

F12を押すと、Webインスペクタが開きます。その右下に設定ボタンがあるので、それをクリック。Enable source mapsにチェックを入れます。

コンパイルの設定

ソースマップを使うにはブラウザの設定だけじゃなく、.js.mapのファイルが必要です。HaXeやTypeScriptでは、このファイルをコンパイル時に生成するように設定できます。

HaXeの場合

コンパイラオプション-debugを使う

haxe -js script.haxe.js -main Main -debug

TypeScriptの場合

コンパイラオプション-sourcemapを使う

tsc script.ts -sourcemap

参考

Source debugging in Javascript – Haxe
Using Source Maps with TypeScript

TypeScriptをVisual Studioで使う。

先日、MicrosoftからTypeScriptという言語がリリースされました。

窓の杜 – 【NEWS】Microsoft、プログラミング言語“TypeScript”を公開。VS 2012向けのプラグインも

近頃、乱立しているJavaScriptを出力する言語です。
JavaScriptを出力する言語はすでにCoffeeScript, Dart, Haxe, JSXなどがあるわけですが、TypeScriptが魅力的なのが以下の点。

  1. すべてのJavaScriptはTypeScriptであり、JavaScriptライブラリの利用が簡単。
  2. 文法がActionScript3.0(EMCAScript4)に近く、厳密な型指定が可能。
  3. 有力なIDE(Visual Studio 2012)がサポートしている。

これ全部満たしてる言語っていままで無かったんじゃないでしょうか?
とりあえず、Visual Studioの使い心地がどんなものか気になるので、インストールして試してみました。ちなみにOSはWindows7。

続きを読む