Garbage Collection

[告知]引越します

出水洸太郎 — Sat, 24 Dec 2011 03:45:00 GMT

ながらくわんくまサーバを使ってBlogを書いていましたが、
はてなに引越し、こちらで更新を行うことにします。

今後は、こちらでの更新は停止するつもりですので、
新引越し先でよろしくお願いします。

[C++]mutexいろいろ

出水洸太郎 — Fri, 16 Dec 2011 00:38:00 GMT

これは16日目の Boost Advent Calendar 2011 の参加記事です。

マルチスレッドのプログラムを作る場合、切っても切れないのがmutexです。
同じリソースにアクセスする時はmutexのロックを使って、
複数のスレッドが同時にアクセスするのを制限しないといけません。

例えば、std::cout で文字列を出力するのはスレッドセーフではないので、
複数のスレッドから同時に呼び出すと、出力が混じり合うことがあります。
なので、こんな感じでmutexを使って排他にしなければなりません。

static boost::mutex dispmutex;
void Display(const std::string &fname, const std::string &str){
  boost::mutex::scoped_lock lk(dispmutex);
  std::cout << fname << ":" << str << std::endl;
}

scoped_lockを使うことで、そのスコープの間だけロックを掛ける、ということができます。
途中でreturnやbreakなどでスコープを抜けた場合もロックを外してくれるので、
mutexのlock/unlockを使うよりは、scoped_lockを使うといいでしょう。

さて、預金管理システムを作ってみました。
残高照会、預け入れ、引き出しができます。
預け入れに上限チェックしていませんが、
私の預金が32bitの上限が超えそうなときまでには考えます。

なお、どの関数も1秒ほどの処理時間がかかるものとします。

class Yokin{
  boost::mutex access;
  int money;
public:
  Human(int money):money(money){}
  void Zandaka(){
    boost::scoped_lock lk(access);
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  } 

  void Azukeire(int h){
    boost::scoped_lock lk(access);
    money += h;
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  } 

  void Hikidashi(int h){
    boost::scoped_lock lk(access);
    if (h <= money){
      money -= h;
    }
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  }
};

これは無駄な部分があるので、高速化してみます。
Zandaka()は値を読み込んで表示しているだけですので、
Azukeire()やHikidashi()が動いていない間なら並列で走らせても問題なさそうです。

そこで、boost::mutexより細かくロックレベルを変えられるのがboost::shared_mutexです。
それを使って先ほどのクラスを書き換えてみます。

class Yokin{
  boost::shared_mutex access;
  int money;
public:
  Human(int money):money(money){}
  void Zandaka(){
    boost::shared_lock<boost::shared_mutex> read(access);
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  } 

  void Azukeire(int h){
    boost::unique_lock<boost::shared_mutex> write(access);
    money += h;
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  } 

  void Hikidashi(int h){
    boost::unique_lock<boost::shared_mutex> write(access);
    if (h <= money){
      money -= h;
    }
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  }
};

値を読むだけならshared_lockを使い並列に動くようにして、
値を書き換える場合はunique_lockを使って排他にします。
これで、残高照会中に別スレッドの残高照会が動くようになって高速化しました。

しかし、もうちょっと高速化の余地があります。
Hikidashi()を見てみると、お金が足りない時はデータを書き換えません。
つまり、お金があるときのみ、unique_lockをすればよいです。
それを踏まえて書き換えてみます。

  void Hikidashi(int h){
    boost::shared_lock<boost::shared_mutex> shared(access);
    if (h <= money){
　    boost::unique_lock<boost::shared_mutex> unique(access);
      money -= h;
    }
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  }

更に高速化！…するどころか、返ってきません。
どうやら、デッドロックしているようです。

お金を減らすとき、unique_lockを通過するには
shared_lockを含め、すべてのロックが外れていることが条件です。
しかし、自分自身がshared_lockをかけています。

  void Hikidashi(int h){
    boost::shared_lock<boost::shared_mutex> shared(access);
    if (h <= money){
      shared.unlock();
　    boost::unique_lock<boost::shared_mutex> unique(access);
      money -= h;
    }
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  }

スコープの途中でも、unlock関数を使うことで、ロックを外すことができます。
もう使わない！となったらすぐに開放したほうがいいでしょう。

こうして、デッドロックはなくなりましたが…残高がマイナス？？
どうやら、if文を抜けた後、別のスレッドで値を書き換えられたようです。

ロックは一度確保したら使い終わるまで一瞬でも開放してはいけません。
今回はshared_lockのアンロック→unique_lockの間に一瞬ロックが外れていて
その間に別のスレッドが値を書き換えているわけです。

こういう、書き換えるかもしれないときに使うロックがupgrade_lockです。

  void Hikidashi(int h){
    boost::upgrade_lock<boost::shared_mutex> upgrade(access);
    if (h <= money){
      boost::upgrade_to_unique_lock<boost::shared_mutex> write(upgrade);
      money -= h;
    }
    Display(__FUNCTION__, boost::lexical_cast<std::string>(money));
  }

upgrade_lockはshared_lockとは干渉しないので
引き出し額が足りないときはZandaka()とは並列して動きます。
引き出し額が足りているときは、upgrade_to_unique_lockを使ってunique_lockに切りかえ、
その時にshared_lockが解除されるまで待ちます。

まとめると以下のようになります。

shared_lock	unique_lockがあるときにブロック
upgrade_lock	upgrade_lock, unique_lockがあるときにブロック unique_lockに変更可能
unique_lock	shared_lock, upgade_lock, unique_lockがあるときにブロック

アクセスが集中するリソースではこれらのロックを適切に使っていきたいです。

以上、Boost Advent Calender 2011 16日目、shared_mutexの紹介でした。
明日の17日目は @egtra さんです。
よろしくお願いします。

コミケの頒布物の事

出水洸太郎 — Sun, 14 Aug 2011 03:22:00 GMT

コミケ80、お疲れさまでした。

今回新刊だった「ゲームの修羅場４」も三月兎さんに委託します。

こっそり、サークルカットにあった「ソートの本」が出ていました。
告知しようと思ったけれど、できたのが前日なもので…。

昼過ぎには完売したのですが、わりと残念がっていた人がいたので、
冬にも少し刷っておこうかな、と思っています。
奥付に「2010年8月14日発行」となってますが、完全に去年だそうとしていたそのままです。

PSP開発読本＋、ゲームの修羅場３は手持ちの在庫含めて完売しました。
なお、のこりの「InsideGames」「ゲームの修羅場1,2」も在庫少部数のため、
冬でこちらもなくなるんじゃないかな、と思っています。

再版の予定はありませんが、三月兎さんの方には
「PSP開発読本＋」、「ゲームの修羅場３」共に在庫があると思うのでそちらでお求め下さい。

ではまた冬に会いましょう～。

[告知]コミケ80頒布物

出水洸太郎 — Sat, 09 Jul 2011 02:42:00 GMT

えー、毎度おなじみのコミケ案内です。
今回は、8/13（土）東S-27bとなりました。
今までお誕生日席のいい位置貰ってたのですが、今回は島中なのでちょっと目立たないかな…？

・ゲーム制作現場の合同誌　ゲームの修羅場4　B5 46p 300円

ということで、今回の頒布物はこれ！
表紙はSukai(石ころGames)さんです。
内容は以下のとおりです。

[Interview]
「吉里吉里」作者 W.Dee

[Topic]
スグリ制作で学んだ3D背景表現方法    jyunpyon(橙汁)
げーむようちえん(仮題)    leimonZ(礼門屋)
ネーミング右往左往    サク(ASTRO PORT)
桝田省治論    しゅん
初めての同人ノベル制作    柚坂みる(こんくら～べ/Blank Script)
他人に遊んでもらうために    出水洸太郎(にじけん)

今回も面白いです。原稿チェックしていていいなぁと思ってました。
ということで、またコミケで会いましょう。

[数学…算数？]算数オリンピック

出水洸太郎 — Wed, 26 Jan 2011 23:16:00 GMT

はてな若手エンジニアが「算数オリンピック」の問題を解いてみた - はてなブックマークニュース

これの問題７に挑戦！
小学生でも2%の人が解いた問題ですね。
むむ、小学生に負けるわけには行きませんな！

さて、紙と鉛筆を用意・・・しないでVisualStudioを起動…っと！

変な見え張って解けないほうがよっぽど恥ずかしい！
聞くは一時の恥聞かぬは一生の恥！！
私は文明の利器で戦う！！

ということで、できました。
「25bitだな！」と言っているとおり、ビット操作を使うことにします。

#include <iostream>

int numofbits5(unsigned int bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

bool Check(unsigned int board){
  if (numofbits5(board) != 6) return false;

  for(int i = 0; i < 5; i++){
    // 0x1b     = 11111
    // 0x108421 = 1 0000 1000 0100 0010 0001
    if ((board & (0x1f << i * 5)) == 0) return false;
    if ((board & (0x108421 << i)) == 0) return false;
  }

  return true;
}

int main(){
  int count = 0;
  for(unsigned int i = 0; i < (1 << 25); i++){
    if (Check(i)) count++;
  }
  std::cout << "count = " << count << std::endl;

  return 0;
}

まずはコマが６個なので、立っているビットを数えます。
ぐぐる様に聞いたら、このサイトを教えてくれたのでコピペ…。
ええい、文明の利器で戦うと言ったではないか！！

そのかわり、縦横のいずれかのマスにコマがある部分は考えました。
論理積（AND）を使えば、関係ないビットをすべてオフにできるので、
一列(or 一行)だけのビットを取り出します。
もし、取り出した結果が0ならば、その列(or 行)にはコマがないことになります。

あとはこれを2^25回forでぶん回すだけ！
Releaseなら1秒以内で答えが出たよ！！

小学生でも解ける問題なだけに楽勝でしたね！

[アルゴリズム]移動の探索

出水洸太郎 — Tue, 25 Jan 2011 09:36:00 GMT

移動力にしたがってマップを移動していくタイプの
戦略シミュレーションゲームがあります。

昔だと大戦略といえば通用したのでしょうが、
最近だとスーパーロボット大戦とかファイアーエムブレムとか言えばいいんでしょうかね？

その移動アルゴリズムについて作成してみました。
普通に書くとこんな感じですかね？

class Board{
public:
  int mx, my;
  int *bd;

  Board(int mx, int my):mx(mx), my(my){
    bd = new int [mx * my];
  }
  ~Board(){
    delete [] bd;
  }

  int & operator()(int x, int y){return bd[mx * y + x];}
  int size()const{return mx * my;}

  void fill(int a){
    for(int i = 0; i < size(); i++){bd[i] = a;}
  }
};

bool range(int x, int y, Board &board){
  if (x < 0 || y < 0) return false;
  if (board.mx <= x || board.my <= y) return false;
  return true;
}
void check(Board &map, Board &out, int x, int y, int now = 0){
  // ボード範囲内かのチェック
  if (range(x, y, map) == false) return;

  int move = map(x, y);
  // 空白か移動力が大きい(遠回りしている)なら探索する
  if (out(x, y) == 0 || move + now < out(x, y)){
    out(x, y) = move + now;
    count++;
    check(map, out, x + 1, y, now + move);
    check(map, out, x - 1, y, now + move);
    check(map, out, x, y + 1, now + move);
    check(map, out, x, y - 1, now + move);
  }
}

int main(void){
  Board board(10, 10);
  Board idou(10, 10);

  board.fill(1);
  idou.fill(0);

  check(map, out, 7, 5);
}

Boardクラスは単なる二次元配列を作るためのクラスです。
boardがそのマスの地形(必要移動力)が入った変数、
idouがそのマスに移動するために必要な移動力を計算する変数となっています。
check関数を実行すると、idouに計算結果が帰ってきます。

さて、これは余り効率が良い方法とは言えません。

再帰を使っていますので、まず今回の場合は右、左、下、上の順で探索しています。
最初に右に移動した場合を全て探索した後、次は左、下、上、というふうに探索するわけです。
すると、以下のような状態が起こります。

A地点からB地点に行く場合、明らかに遠回りしています。
しかし、再帰を使った場合は、下→左というルートを探索する前に
右→下→左→左というルートを確認します。
実際は、これ以上の更なる無駄なルートを探索しています。

そこで、まずは１歩で移動できるマスすべてを探索した後、
２歩で移動できるマス、３歩で移動できるマス、という風に探索するとよいでしょう。

この方法を使うためにキューを使います。
check関数は以下のように変更します。

struct Data{
  int x, y, move;
  Data(int x, int y, int move):x(x), y(y), move(move){}
};

void check(Board &map, Board &out, int x, int y){
  std::deque<Data> queue;
  queue.push_back(Data(x, y, 0));

  while(!queue.empty()){
    Data &dat = queue.front();

    if (range(dat.x, dat.y, map)){
      int move = map(dat.x, dat.y);
      if (out(dat.x, dat.y) == 0 || move + dat.move < out(dat.x, dat.y)){
        out(dat.x, dat.y) = move + dat.move;
        count++;
        queue.push_back(Data(dat.x + 1, dat.y, dat.move + move));
        queue.push_back(Data(dat.x - 1, dat.y, dat.move + move));
        queue.push_back(Data(dat.x, dat.y + 1, dat.move + move));
        queue.push_back(Data(dat.x, dat.y - 1, dat.move + move));
      }
    }
    queue.pop_front();
  }
}

計算したい物をキューの後ろに入れ、先頭から計算していきます。
まず、スタート地点を登録して、その後１歩で移動できる４箇所がキューに入ります。
それらを順に計算し、２歩で移動できる場所が後ろに追加されます。
キューなので、１歩で移動できる場所がすべて探索された後、２歩目の探索が始まります。

最初の再帰を使う方法を「深さ優先探索」、次のキューを使う方法を「幅優先探索」と言います。
どちらを使うか、というのは問題によって様々なのですが、
今回の場合は一歩目、二歩目という感じで順番に探索するほうが向いています。

次回はキューの大きさについて考えてみます。

[告知]コミケ79頒布物更新

出水洸太郎 — Fri, 31 Dec 2010 02:38:00 GMT

場所は「東ヘ-53a にじけん」です。

売り物

新刊
「ゲーム制作現場の合同誌　ゲームの修羅場３ B5 50p 300円」
「GarbageCollection vol.3 バッチファイル活用テクニック B5 22p 200円」←New!

委託
「ゲームエンジンAIMS(D.N.A. Softwares) 256p 1500円」

既刊
「ゲームの修羅場１」
「ゲームの修羅場２」
「InsideGames」
「GarbageCollection vol.1.1　PSP開発読本＋」
「GarbageCollection vol.2.1　Lua開発読本 SE」
全部200円です

今から製本作業入ります…。

[告知]コミケ79頒布品紹介

出水洸太郎 — Wed, 15 Dec 2010 22:53:00 GMT

今年の冬コミは12/29-31、大晦日まで今年は終わらない！

そして、その最終日の12/31にサークルを出します。
場所は「東ヘ-53a にじけん」です。

・ゲーム制作現場の合同誌　ゲームの修羅場３　B5 50p 300円

前回より10ページ増えたのにお値段据え置き、お買い得です。
表紙はicewind(ふろーずんおーぶ)さん。
内容は以下のような感じです。

[Interview]
カタテマ　てつ

[Topic]
多言語対応ゲームを作る    マサシロウ(ぜろじげん)
映画研究部ハンドブック    サク(ASTRO PORT)
げーむようちえん    leimonZ(礼門屋)
orzしないゲーム開発手法    しゅん
ゲームアイデアのお手軽発想法    しゅん
Visual Studio2010のC++0x    出水洸太郎(にじけん)

後はD.N.A. Softwaresさんの委託のAIMS本があります。
なんだこの表紙ｗ

AIMSというのはLuaを使った2Dゲーム開発用のゲームエンジンです。
Luaってなに？って人は、既刊の「Lua開発読本」も持っていくので、ご一緒にどうぞ。
(なんか、Luaそのものの解説は少ないらしいですし)

あとは、既刊本も若干持って行きます。
ただ、さすがに本が増えすぎているので、持っていく分は少ないです。

カタログに書いてあるあれは、出せる目処が付けばまた更新します。
ごめんね、ごめんね…。

ｵｰｽ! ｵｰｽ! ｵｰｽ! ｵｰｽ! ｶﾓｰﾝ!!

出水洸太郎 — Sat, 27 Nov 2010 07:03:00 GMT

iPod Touchをなくしました。
電車に置き忘れたのは確実に覚えているので、
駅員の人に聞いたけど見つからないとの事で多分誰かに取られているわけです。

正直、端末そのものは手痛いとはいえ買い直せば済みます。
問題はメールや各種Webサービスがアクセスできてしまう事ですね。

あわててメールやTwitterのパスワードは変更しました。
それでも、すでにDLされているメールは読めてしまうのが辛いところ。

しかし、問題はTwitterです。
Twitterのパスワードを変えたところで、
今まで使っていたアプリは新パスワードを入れることなくアクセスできます。

Twitterを使うアプリの入った端末を遮断するには以下の方法を取るといいと思います。
・パスワードを変更する
・Twitterの設定→コネクションから一度全部のアプリの許可を取り消す
・使っているTwitterアプリから一度アカウント削除をして再度新パスワードを入力して認証する

なんでこんな事になっているか、って言うとTwitterの認証にOAuthが使われているからです。
これが一度認証成功してしまうと、パスワードを変更しても関係なくアクセスできるんですね。

端末をなくす、という事をした場合は注意しましょう。orz...

個人の作ったゲーム制作本

出水洸太郎 — Mon, 01 Nov 2010 02:21:00 GMT

ゲーム制作に関する本、というのが話題になっていますが、
最近（といっても、1,2年ぐらいの間）でこんな本がでてたよ、と言うのを書いてみます。

「GAMOOK」http://bu.f-sp.net/mook/
コミティアの同人ゲーム部が主催している本です。
コミティアが創作系オンリーのイベント(二次創作不可)ということからか、
ノベルゲームが多いので、そういう話が多いです。
現在第4号まで制作されています。

11月14日にのコミティアは拡大らしいので、どこかでまとめて手に入るんじゃないでしょうか。
第2号からはショップにも委託しています。

「魔王物語物語のつくりかた」http://d.hatena.ne.jp/wtetsu/20100801
カタテマさんの作品、「魔王物語物語」の制作について書いた本です。
内容がとても濃くて面白い本です。

2010年の夏コミで少部数だけ頒布していたものなので、現状は入手困難ですが、
何らかの形で再版したいと言っていたので、それを待ちたいですね。

ちなみに、｢ゲームの修羅場３｣のインタビューはカタテマのてつさんです。
「愛と勇気とかしわもち」「いりす症候群」の裏話を色々聞いています。

「Why did we DeathMarch on 同人ノベルゲーム～錬電術師で死にかけるまで～」http://hexaquarker.com/wdwd_shokai.html
不機嫌亭さんの「錬電術師第一章 gate_way」の制作中からリリース後までの話です。
陥りやすい失敗談を面白おかしく書いています
これも読んでおきたい本です。

「教えてワイヤー処理１，２」
http://wheeloffortune.jp/kabegiwa/book/wire/
http://wheeloffortune.jp/kabegiwa/book/wire2/
海腹川背のクローンである筍の、ワイヤー処理についての本です。
基本的に数学の本ですので、ベクトルの基礎をしっかりわかってないと難しいです。

今度のコミケでサークル出すらしいので、入手はコミケで。
残部少らしいです。

「プログラミングの魔導書」
http://longgate.co.jp/products.html
ゲーム制作本ではありませんが、プログラム関係の本ということで載せてみました。
C++ ~~闇の軍団~~ に理解の深い人が集まって書いた本で、内容もかなり濃いです。
本の受付は終了していますが、現在はpdfを販売しています。

あと、Togatterから拾い集めてきた、制作系のWebコンテンツです。
更新終了しているのが残念ですが、結構な情報量です。

すろーふーど　http://slowfood09.web.fc2.com/
こんにちはゲーム開発室　http://gb.square-enix.com/gbstatic/guest_beginners.html

まだまだあるよ～、ってのがあれば、コメント欄に書いてもらえると嬉しいです。