お客様の業界問わず最適なITソリューションを提供しています。

処理中心思考とオブジェクト中心思考(1)

»

 ひでみさんのコラムで面白いお題目が上がっていたので先日コメントさせていただきました。今回は、そのときに感じたこと、わたしのコメントの意図を書きたいと思います。

■はじめに

 一般的にFizzBuzz問題を目にして、実装を考えた場合の最も簡単で実用的なコードは、以下だと思います(言語はJavaです)。

public class FizzBuzz {
 public static void main(String[] args) {
  StringBuffer sb = new StringBuffer();
  for( int i = 1; i <= 100; i++ ) {
   if( i % 3 == 0 && i % 5 == 0 ) { sb.append("FizzBuzz"+System.getProperty("line.separator")); }
   else if( i % 3 == 0 ) { sb.append("Fizz"+System.getProperty("line.separator"));  }
   else if( i % 5 == 0 ) { sb.append("Buzz"+System.getProperty("line.separator"));  }
   else { sb.append(i+System.getProperty("line.separator")); }
  }
  System.out.println(sb.toString());
 }
} 

 ひでみさんのコラムでは、コレをいろいろな切り口で無駄に遊んでみようというのが趣旨でしたが、わたしは無駄(何をもって無駄なのか、その無駄が良いという感覚も分かりますが)なことをしたくないマジメくんなもので、実用的なエッセンスがないとイカンだろうと思ってしまいます。

 そんなわけで、「実用」という観点で、処理中心思考とオブジェクト中心思考という切り口で、2回にわけてコラムしようと思います。今回は、処理中心思考です。

■処理中心思考

 わたしの考える「処理中心思考」とは、アルゴリズムを軸に考えるアプローチです。何かお題があった時に「処理はこうなるはず」という発想が第一にくる考え方であると思います。

 で、この発想だとインプットとアウトプットが重要で、例えば、関数の引数がインプット、関数の戻り値や関数で出力する情報がアウトプットになります。

 例えば、上述のコードを処理中心で考えた場合、以下みたいな感じになります。

public class FizzBuzz {
 public static void main(String[] args) {
  new FizzBuzz().run(1,100);
 }
 public void run( int start, int end ) {
  StringBuffer sb = new StringBuffer();
  for( int i = start; i <= end; i++ ) {
   if( i % 3 == 0 && i % 5 == 0 ) { sb.append("FizzBuzz"+System.getProperty("line.separator")); }
   else if( i % 3 == 0 ) { sb.append("Fizz"+System.getProperty("line.separator"));  }
   else if( i % 5 == 0 ) { sb.append("Buzz"+System.getProperty("line.separator"));  }
   else { sb.append(i+System.getProperty("line.separator")); }
  }
  System.out.println(sb.toString());
 }
}

 ココで、実務での実用性(FizzBuzzが実用でないのは置いといて)を考えた場合、ココでは「1から100まで」が範囲だけど、「1から1,000,000まで」が範囲になった場合、時間がやたらとかかってしまいます(わたしの環境では、110秒くらい)。

 そこで、並列化を考えてみます。実務では、不可変オブジェクトで統一可能なのか、Swingのイベントディスパッチスレッドのようなモデルを採用するのか、共有リソースでロックをかけちまうかなどの視点で、その業務や機能に適した並列化アーキテクチャを考えます。

 このお題では、そういった視点は不要(やり方次第の部分はあります)になりますが、1点だけストリーム出力のFIFO(書き出し順序を保障することと等価)を保障する必要があります。

 並列化したコードは以下です。わたしの環境では、1,000,000を100threadで処理させると78秒程度に改善しました。

※各スレッドへのタスク割り振りロジックは、穴だらけでございます。誰か良い方法を提示して下さい。

public class FizzBuzz {
 public static void main(String[] args) {
  new FizzBuzz().prun(1,1000000,100);
  }
  public void prun( final int start, final int end, final int threadMax ) {
  if( threadMax <= 0 ) throw new IllegalArgumentException(" threadMax must be larger than 0.");
  ExecutorService service = Executors.newFixedThreadPool(threadMax);
  List results = new ArrayList();
  // 1スレッドの計算責務は、end/threadMaxとしてしまう(10000件で100threadなら1threadあたり100件となる)
  // このコードでは、start,end,threadMaxが任意の値で正しく動作する保障はしない。マジメなんて言っておきながら……。
  for( int i = 0; i < threadMax; i++ ) {
   final int threadStart = i*(end/threadMax);
   final int threadEnd = (i+1)*(end/threadMax);
   Future future = service.submit(new Callable() {
    public String call() {
     StringBuffer sb = new StringBuffer();
     for( int j = threadStart+start; j <= threadEnd; j++ ) {
      if( j % 3 == 0 && j % 5 == 0 ) { sb.append("FizzBuzz"+System.getProperty("line.separator")); }
      else if( j % 3 == 0 ) { sb.append("Fizz"+System.getProperty("line.separator")); }
      else if( j % 5 == 0 ) { sb.append("Buzz"+System.getProperty("line.separator")); }
      else { sb.append(j+System.getProperty("line.separator")); }
     }
     return sb.toString();
    }
   });
   results.add(future);
  }
  // ここでFIFOを保証させている
  try {
   StringBuffer sb = new StringBuffer();
   for( Iterator itr = results.iterator(); itr.hasNext(); ) {
    Future future = itr.next();
    sb.append(future.get());
   }
   System.out.print(sb.toString());
  } catch( Exception e ) {
   e.printStackTrace();
  } finally {
   service.shutdown();
  }
 }

■おわりに

 何度もアレですが、ひでみさんのコラムのコメント欄で上がっていた並列化について、掘り下げてみました。

 次回は、オブジェクト中心思考についてです。デザインパターンを無駄にフル活用しますし、処理中心思考とのそもそもの考え方違いを明示します。お楽しみに。

Comment(27)

コメント

ビガーさん、こんばんは。

こういう処理は、まずやらないので私はよくわからないのですけれど……。

// ここでFIFOを保証させている
以降は、

たとえば、もし、割り込みが入って25番目のスレッドが100番目のスレッドよりも遅かったとき問題ないのでしょうか?

順番に処理が終わっていることを確認するためには、無駄な処理が必要になって結果的に普通に処理した方が速い気がするのですが……。


上半分は、 else if にしないとまずそうです。

CMP

ビガーさん、こんばんは。

ソースについて質問なんですが、並列化ではなく並行化されたサンプルですよね?
並列化なら、出力結果が予定通り順番に出てくることはかぎらないので。
(スレッド処理内にランダムでスリープする処理を追加して検証)
並列と並行の違いをご確認下さい。

P.S.
久しぶりのJavaだったので、動作検証するのに時間がかかり、見ようと思ってたテレビ番組を見損ねてしまった(涙)。

インドリ

ビガーさんこんにちは。
面白そうなので私も試してみたのですが・・・
FizzBuzzの画面出力以外の処理を測ってみました。
するとこんなの出ました♪

直列:563667788 ナノ秒
並列:19557933 ナノ秒

すごい性能アップです。
たぶんちゃんと測定できていないな(笑)
並列処理の時間を測定すのが難しいです。

Soda

>ビガーさん
Javaは触れたことがないので、コードを深く読めないのが悔しいw
開発環境の作り方から調べないといけないからなぁ(^^;
感覚的に読み取ったのはー
1000000を10000件づつ分担し、100人で処理してるって感じですかね。
速度を求めるなら、人数減らしたほうが速いですね。
下に張ったインドリさんのソースみると、CPUの数取得できるみたいだから、ソレ使うのがよさそうですね。

CMPさんのいう並列と並行の違いがちとわかりませんが(^^;

>インドリさん
>直列:563667788 ナノ秒
>並列:19557933 ナノ秒

約29倍ってとこでしょうか・・・
その・・・並列に動作させるとなぜ速くなるのか・・・わかってます?
誤差とかそういうレベルじゃない間違いなんですよ。
数字だけみてバグだとわかるんですよ(^^;

http://indori.blog32.fc2.com/blog-entry-901.html

そのソースがアップされたみたいだったので確認したのですがー
>//同じ数の仕事をスレッドに割り振る
の所が間違ってるように見えます。
結果的に、無駄なスレッドがいくつかと、直列と同じ処理を行ってることになっているかと。
だから、直列よりも時間がかかるはずなんですが・・・減ってますねぇ。
これ、スレッドが完了してないんじゃないかと想像しますが・・・

CMP

Sodaさんへ および皆様へ

あ!すみません、間違えました。
「newFixedThreadPool」の説明文と「newSingleThreadExecutor」の説明文を間違えて読んで、曲解していました。
「並列と並行の違いをご確認下さい。」は[無し]よってことで一つお願いします(大汗)

「個人的解釈」
並行:自スレッドは前スレッドが実行中なら処理を実行するが、前スレッドが終了するまでは自スレッドを終了せず待機する。前スレッドが終了次第、自スレッドも終了する。

並列:他スレッドに関係なく処理を実行し、終了する。

のつもりでした。
大変失礼しました。

CMP

ビガーさんとは異なる並列化されたソースをアップします。
肝は、全スレッドが終了したか確認するところと、実行結果を配列に格納することで順序性を確保しているところです。
------------------------以下ソース------------------------------
import java.util.ArrayList;

public class sample3 {
 public static void main(String[] args){
  // スレッド数を設定
  int ThreadCount = 100;
  // 実行する値を設定
  int ProcCount = 1000000;

  // 処理結果を格納する配列を確保
  String[] results = new String[ThreadCount];
  // スレッド終了フラグを格納する領域を確保
  ArrayList endFlags = new ArrayList();
  // 実行するスレッドを格納する領域を確保
  FizzBuzzThread[] threadList = new FizzBuzzThread[ThreadCount];

  // スレッド数分繰り返す
  for(int i=0; i endFlag;
  private String[] result;
  private int threadId;

  FizzBuzzThread(ArrayList endFlags, String[] results, int id, int start, int end){
   endFlag = endFlags;
   result = results;
   threadId = id;
   procStart = start;
   procEnd = end;
  }
  public void run(){
   StringBuffer sb = new StringBuffer();
   for(int i=procStart; i <= procEnd; i++){
    if(i % 3 == 0){
     sb.append("Fizz");
    }
    if(i % 5 == 0){
     sb.append("Buzz");
    }
    if(i % 3 != 0 && i % 5 != 0){
     sb.append(Integer.toString(i));
    }
    sb.append(System.getProperty("line.separator"));
   }
   result[threadId] = sb.toString();
   endFlag.add(sb.toString());
  }
 }
}

CMP

すみません、アップに失敗しました(涙)
今度こそ!
------------------------以下ソース------------------------------
import java.util.ArrayList;

public class sample3 {
 public static void main(String[] args){
  // スレッド数を設定
  int ThreadCount = 100;
  // 実行する値を設定
  int ProcCount = 1000000;

  // 処理結果を格納する配列を確保
  String[] results = new String[ThreadCount];
  // スレッド終了フラグを格納する領域を確保
  ArrayList endFlags = new ArrayList();
  // 実行するスレッドを格納する領域を確保
  FizzBuzzThread[] threadList = new FizzBuzzThread[ThreadCount];

  // スレッド数分繰り返す
  for(int i=0; i<ThreadCount; i++){
   // 各スレッドが担当する値を設定
   int start = (ProcCount / ThreadCount) * i + 1;
   int end = (ProcCount / ThreadCount) * (i + 1);
   // スレッドを生成し実行
   results[i] = new String();
   threadList[i] = new FizzBuzzThread(endFlags, results, i, start, end);
   threadList[i].start();
  }
  // 全スレッドが終了するまで出力をしない
  while(endFlags.size() != ThreadCount){
   try{
    Thread.sleep(10);
   }
   catch (InterruptedException e){
    e.printStackTrace();
   }
  }
  // 処理結果を出力する
  for(int i=0;i<ThreadCount; i++){
   System.out.print(results[i]);
  }
 }

 // FizzBuzz実行クラス
 public static class FizzBuzzThread extends Thread{
  private int procStart;
  private int procEnd;
  private ArrayList endFlag;
  private String[] result;
  private int threadId;

  FizzBuzzThread(ArrayList endFlags, String[] results, int id, int start, int end){
   endFlag = endFlags;
   result = results;
   threadId = id;
   procStart = start;
   procEnd = end;
  }
  public void run(){
   StringBuffer sb = new StringBuffer();
   for(int i=procStart; i <= procEnd; i++){
    if(i % 3 == 0){
     sb.append("Fizz");
    }
    if(i % 5 == 0){
     sb.append("Buzz");
    }
    if(i % 3 != 0 && i % 5 != 0){
     sb.append(Integer.toString(i));
    }
    sb.append(System.getProperty("line.separator"));
   }
   result[threadId] = sb.toString();
   endFlag.add(sb.toString());
  }
 }
}

おはようございます。

私は待機するループが嫌いなので、各スレッドの最後でカウンターをカウントアップ。カウンターが最終予定回数と一致すれば、出力処理を開始。

ってするかな。

インドリ

私の手法はTBBを簡略化して自分の解釈を加えたものです。
TBBのソースを見て学びました。
スピードUPのポイントは以下の通りです。

・CPUの数よりも多くスレッドを作成することにより暇な時間をなくす。
・粒度をある程度細かくすることにより処理を早く終わらせる。
・スレッドプールによりスレッド作成コストを抑える。
・違う範囲を担当させる事により同期の必要性をなくす。

後はCPUのキャッシュがヒットするように考慮すると良いでしょう。
それから・・・
shutdownメソッドは登録されたすべてのタスクが終了した後、Executorオブジェクトをシャットダウンする筈では?
このメソッドで全ての処理が終わっていると思っていたんだけどな・・・

Soda

>インドリさん
>・粒度をある程度細かくすることにより処理を早く終わらせる。

今回のケースで、粒度を細かくすることで、速度が上がる理由がわからないのですが(^^;
粒度とは何を指しているのでしょうか?

>後はCPUのキャッシュがヒットするように考慮すると良いでしょう。

ずいぶんとハード依存するコードをJavaに求めるのですね(^^;
実際に実現しようとするとかなり難しいと思いますが・・・

>shutdownメソッドは登録されたすべてのタスクが終了した後、Executorオブジェクトをシャットダウンする筈では?

JavaにもSleepに該当するようなものがあると思いますが、それをスレッド内で使えばわかることではないですか?
10秒ぐらいSleepするようにして、そのSleep時間が加算されているかどうかで判断できますよね?

今みたら、私が指摘した部分のバグは修正されてますね。
記事のほうに修正したということが書かれていないので、いつ修正したのかわかりませんが(^^;

でも、時間はかわらずにブログのほうでは、52.4倍なんですね。
インドリさんの環境ではCPU数が2ということですから、絶対にありえない数字ですね。
・・・ありえない数字ってのはご理解されていますよね?

その結果(52.4倍)から少なくとも、規定回数分処理を行っていないのは確実ですよ。

こー私がJavaを知らないせいなのかもしれませんがー
速度を求めてるなら、皆さんスレッド数多くないですか?
ビガーさんとCMPさんは固定で100、インドリさんはCPU数(?)×20+α。
今回の場合、私だったらCPU数+1かなーと思うのですが、なにかセオリーみたいなものがあるのでしょうか?

PS.
>ビガーさん
復旧しましたねー、突然消えて驚きましたよw

CMP

Sodaさんへ

私の場合は、ビガーさんの仕様を真似ただけです。
ついでに教えてほしいのですが、CPU数+1の根拠はなんでしょう?

私のソースは、ワンタイムスレッドなので担当の処理が終了したら領域を解放する仕様(のつもり)です。スレッドを使いまわすことはしません。
強いて言えば、私のタイプの最適スレッド数はCPU数-1ですね。
(親プロセスが1コアを使用するため)

ビガー

皆様、コメントありがとうございます。
返事が遅くなり&コラムを落としてしまいすみません^^;
コメントいただきました皆様には別途メールを送付させていただきました。

また、コラムの修正箇所は、生島さんご指摘のスレッド化した以外の2つの関数の以下部分、
if( i % 3 == 0 ) → else if( i % 3 == 0 )
if( i % 5 == 0 ) → else if( i % 5 == 0 )
それと、スレッド化したコードのレイアウト崩れを直しました。


>生島さん
>たとえば、もし、割り込みが入って25番目のスレッドが100番目のスレッドよりも遅かったとき
>問題ないのでしょうか?

future.get()でスレッドの実行終了を待っているのですが、割り込みが入った場合は、このコードの場合は、Exception(InterruptExceptionとExecutionException)で捕捉され、e.printStackTrace()とservice.shutdown()を実行して終了します。

一般論として、Javaで割り込みを捕捉してどう処理(続行か終了か)させるかは、Thread#interrupt()を使うしかなく、システムアーキテクチャでどう担保するか(実際は、プロファイルしやすいようログを吐かせる程度)が重要ですが、私が経験したプロジェクトでは、このあたりを完全に制御しているモノは見たことないです。組み込みのJVMとかは、このあたりをカスタマイズしているでしょうね、たぶん。


>CMPさん
>Thread.sleep(10);

私のコードのfuture.get()でリアルタイムにスレッドの実行待ちをしています。
詳しくはソースを呼んでいただくか、絶版ですが、以下が参考になります。
http://www.amazon.co.jp/Java%E4%B8%A6%E8%A1%8C%E5%87%A6%E7%90%86%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-%E2%80%95%E3%81%9D%E3%81%AE%E3%80%8C%E5%9F%BA%E7%9B%A4%E3%80%8D%E3%81%A8%E3%80%8C%E6%9C%80%E6%96%B0API%E3%80%8D%E3%82%92%E7%A9%B6%E3%82%81%E3%82%8B%E2%80%95-Brian-Goetz/dp/4797337206


>インドリさん
>並列処理の時間を測定すのが難しいです。

私の環境では、System.currentTimeMillis()を使いました。開始と終了で引き算するだけです。一度お試しを。

>shutdownメソッドは登録されたすべてのタスクが終了した後、Executorオブジェクトを
>シャットダウンする筈では?

もう少し実務的なお題であれば、futureの終了状態(DONE/CANCELLED)を調べるなどは必要ですが、今回の場合は、future.get()でDONEはほぼ保障されるので、ExecutorService#shutdown()でリソース開放して終わらせています。


>Sodaさん
>1000000を10000件づつ分担し、100人で処理してるって感じですかね。
>速度を求めるなら、人数減らしたほうが速いですね。

処理速度については、私の環境(CPU:2/JVM:1.6のHotSpotClient)10より100の方が上記例では平均で3秒程度早いです。
Javaの場合は、JVMの実装(ネイティブスレッドやカーネルスレッドの割り当てなど)次第なので
マジメにやるなら、プロファイルする必要がありますね。
ただ、メモリは無駄に食うので、100以下を目処に考えるべきです。

Soda

>CMPさん
>ついでに教えてほしいのですが、CPU数+1の根拠はなんでしょう?

+1の部分ですよね。
今回の場合、スレッド1つ1つの計算時間はほぼ均等ですが、終了に若干の差がでますよね。
+1することで、その差を減らしていると。
計算中はCPU数のスレッドが動作するのが理想的なんですが、計算が終了した時点でCPUが遊んでしまう。
スレッド数を若干増やすことで、遊び時間を減らすのが目的です。
スレッド切り替え負荷が増えるけれど、遊び時間のほうが長いならば、スレッドを増やしたほうが速いということになります。
どれぐらい増やすかは状況によって変わるのでなんともいえませんが(^^;

メインループはスレッドの完了待ちをして遊んでいることが多いので、スレッド数として考えていません。
CMPさんのコードの場合も、終了待ちでsleepによりメインループが遊んでいるので、理想よりも多いスレッド数のほうが速くなるはずです。

>ビガーさん
>処理速度については、私の環境(CPU:2/JVM:1.6のHotSpotClient)10より100の方が上記例では平均で3秒程度早いです。

あう、そうなんだ、間違ったこと言って申し訳ないです(^^;
どういう理由でそのような結果が生まれるのかはわかりませんが3秒も差がでるのは大きいですねぇ。
なんでだろう?
今見たらインドリさんのところに追記がされていて、変化することがないはずの数値が極端な変化しているんですよねぇ。
これはスレッドが完了していなのに表示しているということで納得できそうですが、それにしても極端な負荷がかかるんですね。
ビガーさんのコードでも1.4倍ぐらいですから、Javaのスレッドって癖があるんですね。

CPUも極端な差があるんですね、インドリさんの場合は、2,000,000を1スレッドで580275249ナノ秒。
ビガーさんの場合は、1,000,000を1スレッドで110秒・・・
あっ、文字追加方法の違いのほうが大きいのかな?

CMP

ビガーさんへ
>私のコードのfuture.get()でリアルタイムにスレッドの実行待ちをしています。
とありますが、resultsにappendされていないfutureをどうやって待つのでしょうか?
なぜ全てのスレッドが完了しているという保証があるのかわからないので、おすすめの本を探して読んでみます。

Sodaさんへ
なるほど、+1というよりは+αだったんですね。で現実的な数字としての「+1」、了解しました。
私のコードだと、全スレッドの完了を保証する手段がなかった(ちゃんと組み込んでいない)ので、保証する意味で追加した処理です。スレッド数次第では常に遊んでいることにもなりますね。

やっぱ、ビガーさんやインドリさんのもですが、2,3時間くらいで作ったマルチスレッドプログラムは、他の言語や直列に比べるとサンプルとしては微妙ですね。

インドリ

・実行時間の計測について
JavaはVM上で動くから正確な数値をとれている可能性がありますが、
C++では並列用のタイマーを使用しないとちゃんと計測できません。
VMだからJavaの場合はOKなのかな?


・52倍について
ネタです。大受けしたので掲載しました。
普通は追記した通り1.5倍ぐらいですw
とはいえ、TBBだと1.8倍なんて出るんですよね。
並列処理は奥が深いです。

ビガー

皆様、再度コメントありがとうございます。

> Sodaさん
>ビガーさんの場合は、1,000,000を1スレッドで110秒・・・
>あっ、文字追加方法の違いのほうが大きいのかな?

私のサンプルはStringBuffer使ってバッファリングしているので。しない場合は、250秒くらいでしたね、確か。

>CMPさん
>resultsにappendされていないfutureをどうやって待つのでしょうか?

service.submit()が実行された段階でスレッドが生成されて、当該スレッドがcall()を実行します。call()の実行待ちをfuture.get()で同期しているイメージです。

>やっぱ、ビガーさんやインドリさんのもですが、2,3時間くらいで作った
>マルチスレッドプログラムは、他の言語や直列に比べるとサンプルとしては
>微妙ですね。
Poolさせている意味がまったく無いですしね。もうちょい実用的なお題でないとお遊びで終わっちゃいますね、確かに。

>インドリさん
>VMだからJavaの場合はOKなのかな?

私のサンプルコードの場合は、結局メインスレッドだけがストリーム出力をしているので、正確な値がとれているのかと。ストリーム出力を並列化すると、実装によっては不正確な時間になるかもしれませんね。

TBB。時間あるときにでも遊んでみたいと思います。

Soda

>ビガーさん
>私のサンプルはStringBuffer使ってバッファリングしているので。しない場合は、250秒くらいでしたね、確か。

あぁ、時間は演算時間だけじゃなくて、表示も含んだ時間でしたか(^^;
スレッド数を増やすと速くなる理由を色々考えてみましたがー実際に動作させないとわからないですねw
1.4倍程度にしかならないのも謎ですが、それだけ長時間ブロックされてる部分があるってことかな?
・・・って記事の本質から外れてますねw

しかし、明確にネタと書かれているので、この記事にコメントした人達をからかっていたということですねぇ。
そんなことしてなにが楽しいのか理解できませんが(^^;
いまだにバグ有りのコードを提示してあるのも、その延長なのかなぁ。
並列用のタイマーってのも謎だし・・・まぁ、いいか。

>TBB。時間あるときにでも遊んでみたいと思います。

http://codezine.jp/article/detail/4404
こちらで、インドリさんが連載されていますよ・・・というか宣伝なんですかね(^^;
連載でも不思議なコードが書かれているのは、ネタなのかもしれませんが・・・

CMP

ビガーさんへ

ってことは、スレッドの処理が何らかの原因で終了していなかった場合は、future.get()の際にExceptionが発生して強制終了してしまうわけですね。

生成した各スレッドに対し、順番に処理依頼を出しても、出した順に終わるとは限らないけど、resultsにappendした順は順番どおりになっているから「ここでFIFOを保証させている」に繋がるんですね。
ようやく理解できた(大汗)。頭固いなあ、俺。

さて、次はオブジェクト中心思考ですね。
どういう展開になるんだろうw

Jitta

C でかる~く遊んでみた。
スレッド数を可変にして、2百万までの FizzBuzz を求めた。
デュアル コアのとき、スレッド1個で120msecくらい。
スレッド2個で70msecくらい。
スレッド3個で60msecくらい。
スレッド4個で65msecくらい。
スレッド5個で65msecくらい。
スレッド6個から、面倒になった。
スレッド40個で70msecくらい。増やしすぎると逆効果。
あ、純粋に、計算部分だけです。

ただ、VC++ のスレッドって、UNIX のと違う。結構戸惑った。

ビガー

Jittaさん、コメントありがとうございます。

本来なら計算部分と出力部分を分けて考えるべきなんですよね。
私の例は、出力部分を含めているので、出力小分けにした方が効果が出ているようですね。まぁ、そのときのPCの負荷具合でも変わりますしね。

>ただ、VC++ のスレッドって、UNIX のと違う。結構戸惑った。

どのあたりが違うのか、伺いたいところです。暇があったらお願いします!

教えてください。

インドリさん:
> JavaはVM上で動くから正確な数値をとれている可能性がありますが、
> C++では並列用のタイマーを使用しないとちゃんと計測できません。

「なぜ」VM上で動くから正確かもしれない のですか?
並列用のタイマーってなんのことですか?
wall-clockではなく、プロセス内の経過時間を測れてこと?
# だとすれば並列うんぬんは関係ありませんけども。

ビガー

επιστημηさん、コメントありがとうございます。

>http://blogs.wankuma.com/episteme/archive/2009/10/21/182315.aspx

拝見しました。なるほど、tbb::parallel_forの中身が気になりますね。
関数ポインタとその関数の引数がパラメータみたいですが、オブジェクトを渡しちゃった方がシンプルになる気がするな。

あと、resultがカプセル化されていないようですが、Futureみたいに戻りオブジェクトに詰めちゃった方が馬鹿な私には考える範囲が狭くなって嬉しいかなと^^;

> 関数ポインタとその関数の引数がパラメータみたいですが、オブジェクトを渡しちゃった方がシンプルになる気がするな。

parallel_forは関数テンプレートで、関数ポインタだけでなく、operator()を持ったものならなんでもいけます。この例ではlambda式(関数オブジェクト/ファンクタ)を渡してます。

for-loopのloop範囲を与えると、parallel_forはテキトーな大きさにぶったぎってそれぞれをスレッドに与え、全スレッドが終了すればparallel_forから抜けてきます。

> あと、resultがカプセル化されていないようですが、Futureみたいに戻りオブジェクトに詰めちゃった方が馬鹿な私には考える範囲が狭くなって嬉しいかなと^^;

parallel_forはfor-loopの繰り返し単位が他に影響を与えない場合に使うものですから。たとえば「全要素の合計を求める」なんてな場合にはparallel_reduceが用いられます。こっちなら結果を掻き集める部分でスレッドの競合が起こらんようにできてます。

ビガー

επιστημηさん、再度コメントありがとうございます。

詳細ありがとうございます。
などほど、parallel_forは今回のお題に最適ですね。
「範囲を適当な大きさに」というのは気になりますな~ソースみよ。

>parallel_reduce
参照渡しで結果をもらうわけですね。他にもいろいろと機能が用意されているようだと。

しかし、TBB面白そうですね。紹介いただきありがとうございます!

>「範囲を適当な大きさに」

範囲20万を8つに切ってました。
起こしたスレッド数はこれより少なく、切り分けられた範囲を何度もスレッドに与えることでスレッドをリサイクルしているみたい。

かなり賢い実装がなされてるみたいす。
# 実際に起こしたスレッド数までは追いかけらんなかった。
# おそらくはコア数とかから決定してんでしょね。

ビガー

επιστημηさん、ありがとうございます。

>かなり賢い実装がなされてるみたいす。
ソースまだ見てないですが、物理リソースに踏み込んだ世界ですね。
こういう領域が職人と呼ばれてよい人種だと私は認識しています。大学時代を思い出します。

私の方でも純粋に計算部分だけ測定してみました。
範囲数は100万です。(20万くらいだと差があまりでなかったので)
CPUはdual-coreの1cpuでした。

スレッド数:1⇒781ms
スレッド数:10⇒658ms
スレッド数:20⇒650ms
スレッド数:30⇒620ms
スレッド数:40⇒660ms
スレッド数:50⇒612ms
スレッド数:60⇒617ms
スレッド数:70⇒655ms
スレッド数:80⇒698ms
スレッド数:90⇒702ms
スレッド数:100⇒668ms

そのソースは以下。

public class FizzBuzz {
 public void prun( final int start, final int end, final int threadMax ) {
  long startTime = System.currentTimeMillis();
  ExecutorService service = Executors.newFixedThreadPool(threadMax);
  List results = new ArrayList();
  for( int i = 0; i future = service.submit(new Callable() {
    public String call() {
     StringBuffer sb = new StringBuffer();
     //...FizzBuzz本体
     return sb.toString();
    }
   });
   results.add(future);
  }
  try {
   for( Iterator itr = results.iterator(); itr.hasNext(); ) {
    Future future = itr.next();
    future.get();
   }
  } catch( Exception e ) { e.printStackTrace();
  } finally {
   service.shutdown();
   long endTime = System.currentTimeMillis();
   System.out.println("スレッド数:"+threadMax+"⇒"+(endTime-startTime)+"ms");
  }
 }
 public static void main(String[] args) {
  // Single Thread Execution
  new FizzBuzz().prun(1, 1000000, 1);
  // Multi Thread Execution
  for(int i = 10; i <= 100; i+=10) {
   new FizzBuzz().prun(1, 1000000, i);
   try { Thread.sleep(1000); } // リソース待ちをしてみる。
   catch (InterruptedException ie) { ie.printStackTrace(); }
  }
 }
}

で、以下が、results.add(future)の代わりにfuture.get()で計ったときの時間。
そういう実装(即同期)ではほとんど意味がないという例ですな。

スレッド数:1⇒790ms
スレッド数:10⇒681ms
スレッド数:20⇒653ms
スレッド数:30⇒721ms
スレッド数:40⇒748ms
スレッド数:50⇒691ms
スレッド数:60⇒724ms
スレッド数:70⇒747ms
スレッド数:80⇒772ms
スレッド数:90⇒771ms
スレッド数:100⇒709ms

コメントを投稿する