マージソートで速度比較【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