合計 昨日 今日

アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)
日記
- 9月 2017
誕生日 (0)
   2017年9月22日(金) 08:46
諦めた… (4)
   2017年9月18日(月) 20:35
なんかこれおかしくない? (10)
   2017年9月18日(月) 08:27
ボクシング始めました (5)
   2017年9月09日(土) 16:11

+ 8月 2017
+ 7月 2017
+ 6月 2017
+ 5月 2017
+ 4月 2017
+ 3月 2017
+ 2月 2017
+ 1月 2017
+ 12月 2016
+ 11月 2016
+ 10月 2016
+ 9月 2016
+ 8月 2016
+ 7月 2016
+ 6月 2016
+ 5月 2016
+ 4月 2016
+ 3月 2016
+ 2月 2016
+ 1月 2016
+ 12月 2015
+ 11月 2015
+ 10月 2015
+ 9月 2015
+ 8月 2015
+ 7月 2015
+ 6月 2015
+ 5月 2015
+ 4月 2015
+ 3月 2015
+ 2月 2015
+ 1月 2015
+ 12月 2014
+ 11月 2014
+ 10月 2014
+ 9月 2014
+ 8月 2014
+ 7月 2014
+ 6月 2014
+ 5月 2014
+ 4月 2014
+ 3月 2014
+ 2月 2014
+ 1月 2014
+ 12月 2013
+ 11月 2013
+ 10月 2013
+ 9月 2013
+ 8月 2013
+ 7月 2013
+ 6月 2013
+ 5月 2013
+ 4月 2013
+ 3月 2013
+ 2月 2013
+ 1月 2013
+ 12月 2012
+ 11月 2012
+ 10月 2012
+ 9月 2012
+ 8月 2012
+ 7月 2012
+ 6月 2012
+ 5月 2012
+ 4月 2012
+ 3月 2012
+ 2月 2012
+ 1月 2012
+ 12月 2011
+ 11月 2011
+ 10月 2011
+ 9月 2011
+ 8月 2011
+ 7月 2011
+ 6月 2011
+ 5月 2011
+ 4月 2011
+ 3月 2011
+ 2月 2011
+ 1月 2011
+ 12月 2010
+ 11月 2010
+ 10月 2010
フォロー
カテゴリー
日常
1 記事

これは全然発見じゃない。弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月12日(月) 21:39

今回作っているSTGは完全にオブジェクト指向で「いかに適切な設計をするか」を求めようと思っています。

■お詫びと訂正■
vectorをoperator[]でアクセスし、flag参照関数をinline化し、最適化かけたら同じ速度になりました。。。


汎用的・拡張性の高い(便利な)設計は、実行効率や速度が低下しがちです。
しかし、リソースが豊富な現在、実行効率を少々犠牲にしても、便利な設計を重視する方が良いという考え方もあります。
そこで、便利な設計⇔実行効率のトレードオフをどの辺で判断すべきか、検証してみました。

弾幕ゲー制作の中で一番肝になるのが、「弾」データの持ち方。
弾データは弾クラスの一つのオブジェクトですが、持ち方は以下の4通り位あるでしょう。



・メモリプールから確保できる形でlistを使う(new,deleteを繰り返す弾オブジェクトのリスト)
・タスクリストを使う
・vectorを使う
・配列を使う



実行速度は上ほど遅い、下ほど早いと思われます。(vectorは安全に.at(i)でアクセス)

まずは、配列とvectorでどれ位変わるか調べてみました。

約5万個の弾を出した時の計算時間

[vector編]
画像
計算部 = 915[ms]
描画部 = 27[ms]

[配列編]
画像
計算部 = 267[ms]
描画部 = 16[ms]

なんと!vectorは配列の約3.5倍!
かなり処理に時間がかかるようです。
あらゆるアクセスに関数コールが生じるのがボトルネックのようです。(特にat?)
そこで、関数コールをなるべくしないように考えます。

弾クラスにはその弾が使用中かどうかを表すフラグ変数がありますが、この変数はprivateなので

bool IsUsing();

みたいな関数を通じてしか使用中かどうかチェック出来ません。
しかし、膨大な回数のこの関数コールが生じています。そこで、フラグ変数をpublicにし、直接参照するようにし、配列版をさらに高速に計算出来るように試みました。
すると・・・

[配列+関数コール削減版]
画像
計算部 = 49ms
描画部 = 16ms

計算時間が約1/18になったではないですか!
どうも関数コールは相当なボトルネックになるようです。
とは言え、汎用性や拡張性を意識すると、どうしても関数に細分化しがちです。
この辺のトレードオフは基準が難しそうですが、頻繁にコールする関数はなるべく作らないように設計するのが良いようです。
(ちなみに上記関数はinlineにしても変化ありませんでした。使い方が悪いのかな・・)
※追記:最適化かかってないだけでした;

もっとこうすればいいとかあれば、何かご意見もらえると嬉しいです!
最後に編集したユーザー Dixq (管理人) [ 2011年9月13日(火) 01:02 ], 累計 8 回

コメント数: 21 閲覧数: 34256
コメント

Re: これは発見!弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月12日(月) 21:49

ちなみに、龍神録では最大4000個の弾が出現します。(絵弾幕等)
それを考えると、この実行速度の差は目をつぶれない・・。配列にして、関数コールを減らすという方針で決まりでしょうか・・?
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは発見!弾幕の設計

パーマリンクby softya(ソフト屋) on 2011年9月12日(月) 22:00

今のコンパイラで速いかどうか分かりませんが、配列で添字を使わずにポインタで操作したら早くなりませんか?
[補足]徹底的に添字は使わないようにしてみてください。
最後に編集したユーザー softya(ソフト屋) [ 2011年9月12日(月) 22:03 ], 累計 1 回
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
アバター
softya(ソフト屋)
副管理人
 
記事: 11677
登録日時: 2010年10月16日(土) 23:56
お住まい: 東海地方
日記: 日記を見る (242)

Re: これは発見!弾幕の設計

パーマリンクby softya(ソフト屋) on 2011年9月12日(月) 22:11

まぁ、最適化されて関係ない可能性が高いんですけどね。
最後の手段はアセンブラコードを見るしか無いって事になります。

あと思いつくのは、
(1)switchはある程度数が多くなるとテーブルジャンプに置き換わるはずなので、パターンの多い場合は積極的に活用してください。
(2)分岐は極力減らしてください。if文だけでなく条件演算や3項演算子とかもですね。出来るだけストレートな計算で処理できるようにします。
(3)分岐はthen節に行く可能性が出来るだけ高くなるように設計してください。
あたりの所でしょうか。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
アバター
softya(ソフト屋)
副管理人
 
記事: 11677
登録日時: 2010年10月16日(土) 23:56
お住まい: 東海地方
日記: 日記を見る (242)

Re: これは発見!弾幕の設計

パーマリンクby SAI on 2011年9月12日(月) 22:19

とても興味深いです!
配列でも関数コールで時間がかかるのならpublicにしてしまうというのもありかもしれませんね。
配列の場合、特に弾幕STGとなると最低でも弾の計算、描画のフラグチェックに弾の最大数×2回フラグチェック関数を呼ばないといけないので重要そうですね。
私のゲームでも検討してみたいと思います。
Alea jacta est !
アバター
SAI
 
記事: 115
登録日時: 2010年10月24日(日) 12:26
お住まい: はひほーひ
日記: 日記を見る (247)

Re: これは発見!弾幕の設計

パーマリンクby xxx on 2011年9月12日(月) 22:21

>(1)switchはある程度数が多くなるとテーブルジャンプに置き換わるはずなので、パターンの多い場合は積極的に活用してください。
二分木に展開されると思ってたんですがこういうのもあるんですか?
xxx
 
記事: 26
登録日時: 2010年10月18日(月) 21:24
日記: 日記を見る (21)

Re: これは発見!弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月12日(月) 22:24

> softyaさん

アドバイスありがとうございます。

> 配列で添字を使わずにポインタで操作したら早くなりませんか?

それって
CBullet* p;
みたいなもの用意して、アクセスする度にp++;をするってことですか?
計算が入る分余計に遅くなりません?

> 最後の手段はアセンブラコードを見るしか無いって事になります。

まぁそこまでやる気はないです^^;
微々たる違いは、分かり易い設計になるようにシフトした方がずっと良いと思ってます。
今回のように1/〇〇になるとかなら別ですが・・。

> (3)分岐はthen節に行く可能性が出来るだけ高くなるように設計してください。

then節ってなんです・・?
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは発見!弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月12日(月) 22:26

> SAIさん

すみません!
追記に書いた通りなんですが、最適化かかってなかっただけでした。
積極的に関数化し、関数をinlineにするのが良いと思います。
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは発見!弾幕の設計

パーマリンクby パコネコ on 2011年9月12日(月) 22:29

ありゃ、最近リストを覚えたので、次にSTG作るときには使用しようと思ってましたが、どうやらかなりの数を処理させなければならない時には向かないみたいですね。
(特に弾幕w)

それにしてもおぞましい数ですね。
ですが、処理速度を早くしようとすると、関数を少なく(もしくは大きく)しないといけないんですね。
勉強になります。
=====================
添え字使わないポインタ操作って
p[10000];
x++;
*(p+x);
見たいなのでしょうか?
最後に編集したユーザー パコネコ [ 2011年9月12日(月) 22:32 ], 累計 1 回
ニャン!!\(゜ロ\)(/ロ゜)/
アバター
パコネコ
 
記事: 139
登録日時: 2010年10月16日(土) 22:49
お住まい: 大阪
日記: 日記を見る (75)

Re: これは発見!弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月12日(月) 22:34

>パコネコさん

リストはありだと思うんですが、弾幕って何かの弾に依存した動きする時、特定の弾にアクセスしたい時ありません?
4000個ある内の2000番目の弾とか・・。
そうなるとリストって一気にアクセスが遅くなるんじゃないかと思います。
そこまで弾の量が多くなく、特定の弾へのアクセスも無いなら、リストが良いと思いますよ。
ただ、メモリプールしないといけないから、結局メモリは最初にガッツリ取っちゃうし、あんま恩恵無いかもしれませんが・・。
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは発見!弾幕の設計

パーマリンクby a5ua on 2011年9月12日(月) 22:35

範囲外にアクセスしないことがわかっているなら、atでの範囲チェックは無駄になると思うのですが、
vectorでoperator[]を使った場合は、どうなるか気になります。
アバター
a5ua
 
記事: 194
登録日時: 2010年10月17日(日) 17:52
日記: 日記を見る (14)

Re: これは発見!弾幕の設計

パーマリンクby softya(ソフト屋) on 2011年9月13日(火) 00:20

CBullet* p;
みたいなもの用意して、アクセスする度にp++;をするってことですか?
計算が入る分余計に遅くなりません?


簡単なコードの実装状態を教えて下さいね。

then節ってなんです・・?


あっとC/C++なら真になる条件の確率が高くなるようにして下さいということです。
Pascal/FORTRAN/BASICだとそう言うので、つい・・・。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
アバター
softya(ソフト屋)
副管理人
 
記事: 11677
登録日時: 2010年10月16日(土) 23:56
お住まい: 東海地方
日記: 日記を見る (242)

Re: これは発見!弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月13日(火) 00:30

> softyaさん

あ~例えば構造体配列だとすると
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
for( int i=0; i<N; i++ ){
    BulList[i].flag;
}
 
じゃなく
 
Bullet_t* p=BulList;
for( int i=0; i<N; i++ ){
    ( p+i )->flag;
}


って参照の方が速いってことですか?

> then節

なるほど。
コード[C++]: 全て選択
1
2
3
4
5
if( ... ){
    proc1();
} else {
    proc2();
}

これはproc1()が呼ばれる可能性が高いようにした方がよいということですか?
最後に編集したユーザー Dixq (管理人) [ 2011年9月13日(火) 00:31 ], 累計 1 回
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは発見!弾幕の設計

パーマリンクby softya(ソフト屋) on 2011年9月13日(火) 00:49

コード[C++]: 全て選択
1
2
3
4
Bullet_t* p=BulList;
for( int i=0; i<N; i++ ){
    ( p+i )->flag;
}

2~3つ以上参照すると速いはずです。
あと
コード[C++]: 全て選択
1
2
3
4
Bullet_t* p=BulList;
for( int i=0; i<N; i++,p++ ){
    p->flag;
}

じゃないと意味が無いですね。

これはproc1()が呼ばれる可能性が高いようにした方がよいということですか?

thenの確率が高いなら、elseが無いほうが速いと言う話ですね。
場合によってですが、
コード[C++]: 全て選択
1
2
3
4
5
if( x< 10 ) {
 a=1;
} else {
 a=0;
}

よりも
コード[C++]: 全て選択
1
2
3
4
a=0;
if( x<10 ) {
 a=1;
}

が速いはずですが、昨今のコンパイラの最適化とCPUのパイプラインの挙動までは把握しきれてません。
by softya(ソフト屋) 方針:私は仕組み・考え方を理解して欲しいので直接的なコードを回答することはまれですので、すぐコードがほしい方はその旨をご明記下さい。私以外の方と交代したいと思います(代わりの方がいる保証は出来かねます)。
アバター
softya(ソフト屋)
副管理人
 
記事: 11677
登録日時: 2010年10月16日(土) 23:56
お住まい: 東海地方
日記: 日記を見る (242)

Re: これは全然発見じゃない。弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月13日(火) 01:05

なるほど。
しかし上の場合、「p++」という余計なインクリメント計算が入りますが、それでもなお速いということですか?
実際の測定は明日やってみようと思います。
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

RE: これは全然発見じゃない。弾幕の設計

パーマリンクby ISLe on 2011年9月13日(火) 01:21

配列の高速アクセスはこうですね。
コード[C++]: 全て選択
1
2
3
4
5
Bullet_t* p=BulList;
Bullet_t* end=&BulList[NUM];
for( ; p<end; p++ ){
    p->flag;
}


でもリストを活用したほうが速いですよ。
使用中弾リストを作れば弾の存在確認自体が要らなくなります。
他の弾に依存する処理も依存弾リストを持たせれば良いです。
メモリプールも、事前に確保したメモリをリスト管理して、オーバーライドしたnewで使用していないメモリのリストから取り出して使用しているリストに移動、オーバーライドしたdeleteで使用しているリストから使用していないリストに移動、って感じに。
最後に編集したユーザー ISLe [ 2011年9月13日(火) 01:24 ], 累計 1 回
ISLe
 
記事: 2577
登録日時: 2010年10月16日(土) 22:47
日記: 日記を見る (16)

Re: これは発見!弾幕の設計

パーマリンクby h2so5 on 2011年9月13日(火) 20:01

Dixq (管理人) さんが書きました:>パコネコさん

リストはありだと思うんですが、弾幕って何かの弾に依存した動きする時、特定の弾にアクセスしたい時ありません?
4000個ある内の2000番目の弾とか・・。
そうなるとリストって一気にアクセスが遅くなるんじゃないかと思います。

弾幕のプログラムは書いたことがないですが、
自分だったら特定の弾に関連した動きをさせたい場合は弾を生成した時点で、
弾自体に他の弾へのポインタを持たせる方法を使うと思います。
そうすればlistへのランダムアクセスは発生しないので。
アバター
h2so5
副管理人
 
記事: 2212
登録日時: 2010年12月05日(日) 11:52
お住まい: 東京
日記: 日記を見る (27)

Re: これは全然発見じゃない。弾幕の設計

パーマリンクby tk-xleader on 2011年9月13日(火) 22:47

内部で頻繁にアロケートしたりしてもvectorが遅くなるとは思います。通常、push_backする前にreserveしておくのが定石ですが…
VisualC++では、最適化をかければvectorは大抵の関数がインライン展開されて普通に動的配列使うのと全く同一のコード、あるいはそれに近いコードが生成されるはずです。
アバター
tk-xleader
 
記事: 138
登録日時: 2011年4月23日(土) 01:23
お住まい: 関西某所
日記: 日記を見る (50)

Re: これは全然発見じゃない。弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月14日(水) 21:44

> ISLeさん
> カロさん

>他の弾に依存する処理も依存弾リストを持たせれば良いです。

依存した弾のポインタを持たせるということですか?
同じ実体を示すポインタが複数あるというのはあまり・・な気がするんですが、私の認識違いでしょうか。
実体deleteしたのに、参照しちゃうとか。

> tkさん

vectorでpush_backは使ってないですね~。なのでatも使わないし、特にvector化する必要性も感じてないです。
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは全然発見じゃない。弾幕の設計

パーマリンクby ISLe on 2011年9月14日(水) 22:35

Dixq (管理人) さんが書きました:同じ実体を示すポインタが複数あるというのはあまり・・な気がするんですが、私の認識違いでしょうか。
実体deleteしたのに、参照しちゃうとか。

そういうときのためのスマートポインタですよ。
参照されなくなったらオブジェクト自身がdeleteする設計にすると、ダングリングを回避できます。

(追記)
まだ参照されているのに実体が削除できてしまうのは問題なので、参照が無くなるまでオブジェクトの破棄が保留されるようにすべきです。
参照する側とされる側をどちらから削除するかという順番を気にしなくても良くなるというメリットもあります。
最後に編集したユーザー ISLe [ 2011年9月14日(水) 22:43 ], 累計 2 回
ISLe
 
記事: 2577
登録日時: 2010年10月16日(土) 22:47
日記: 日記を見る (16)

Re: これは全然発見じゃない。弾幕の設計

パーマリンクby Dixq (管理人) on 2011年9月14日(水) 23:19

> ISLeさん

なるほど・・・。今までの疑問がすごく晴れました。。。
まだまだC++初心者なので、情報ありがたいです。
早速あちこち修正してきます。
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

Re: これは全然発見じゃない。弾幕の設計

パーマリンクby Dixq (管理人) on 2011年10月09日(日) 13:29

>a5uaさん

そうですね、atはどの辺りまで使用すべきなのでしょう・・。
[]でアクセスした結果は更新した日記の通りです。
結局メモリプール+リストが一番効率よかったのでそうしました。
ご意見ありがとうございます。
アバター
Dixq (管理人)
管理人
 
記事: 1505
登録日時: 2010年10月12日(火) 20:16
お住まい: 北海道札幌市
日記: 日記を見る (564)

オンラインデータ

登録ユーザー: みけCAT