2013年3月26日火曜日

本日のげんなり TIFF編

 今日は参りました。 TIFFGetField という関数には、前回もやられているんですが、今回も、こてんこてんにやっつけられました。 TIFFTAG_GDAL_NODATA というタグの値を取得したくて、GDALのGeoTIFFパートを参考にコードを組んだら SIGSEGVの嵐。は〜 SIGSEGV、どんどん、ほぇー SIGSEGV、どんどん、ハイヤー SIGSEGV バンバン。
   char* pszText = NULL;
    if( TIFFGetField( hTIFF, TIFFTAG_GDAL_NODATA, &pszText ) )
    {
        bNoDataSet = TRUE;
        dfNoDataValue = CPLAtofM( pszText );
    }
突っ込んで面倒を見ていくと libtiff の tif_dir.c の int _TIFFVGetField(TIFF* tif, uint32 tag, va_list ap) という関数でお亡くなりになっている事が判明しました。
  // なんと、field_passcount > 0 が成立しているので
  if (fip->field_passcount) {
    if (fip->field_readcount == TIFF_VARIABLE2) {
      // pszText にデータサイズが格納されて
      *va_arg(ap, uint32*) = (uint32)tv->count;
    } else  /* Assume TIFF_VARIABLE */ {
      *va_arg(ap, uint16*) = (uint16)tv->count;
    }
    // ありもしない第2の可変引数に値が格納されて
    // ここであぼ~ん 
    *va_arg(ap, void **) = tv->value;
    ret_val = 1;
  }
(゚∀゚)アヒャ(゚∀゚)アヒャ。関数の仕様というか、TAGの仕様が変わっとるがなwww 知らねぇよヽ(`Д´)ノウワァァァン!! と言いながらコードを修正
   uint32_t textLen = 0;
   char* pszText = NULL;
    if( TIFFGetField( hTIFF, TIFFTAG_GDAL_NODATA, &textLen, &pszText ) )
    {
        bNoDataSet = TRUE;
        dfNoDataValue = CPLAtofM( pszText );
    }
あれれ?まだまだ SIGSEGV おほー、どんどん SIGSEGV ひ~~。 更に突っ込んで面倒を見ていくと、同じく tif_dir.c にて
  // えっ?今度は、field_passcount == 0
  if (fip->field_passcount) {
    //...
  } else if (fip->field_tag == TIFFTAG_DOTRANGE
     && strcmp(fip->field_name,"DotRange") == 0) {
    //...
  } else {
    // そして、field_type == TIFF_ASCII なので
    if (fip->field_type == TIFF_ASCII
      || fip->field_readcount == TIFF_VARIABLE
      || fip->field_readcount == TIFF_VARIABLE2
      || fip->field_readcount == TIFF_SPP
      || tv->count > 1) {
          // 第1引数 uint32_t にポインタ値が代入され
          // 第2引数が放置プレーで、最終的にあぼ~ん
          *va_arg(ap, void **) = tv->value;
          ret_val = 1;
    } else {
      //...
 隊長!エスパーじゃないから、推定できましぇんヽ(`Д´)ノウワァァァン!!  ということで、とりあえず、2引数を取る形態で対処しました。
    if (fip->field_type == TIFF_ASCII
      || fip->field_readcount == TIFF_VARIABLE
      || fip->field_readcount == TIFF_VARIABLE2
      || fip->field_readcount == TIFF_SPP
      || tv->count > 1) {
          if( (tag == TIFFTAG_GDAL_METADATA) || (tag == TIFFTAG_GDAL_NODATA) ) {
             *va_arg(ap, uint32*) = (uint32)strlen(tv->value);
          }
          *va_arg(ap, void **) = tv->value;
          ret_val = 1;
    } else {
 もの凄く疲れた。

2013年3月16日土曜日

Google Reader 終了で困った

 まぁ、一応書いておこうと思う。現在241フィードほど登録してます。C++ 系が多いのは置いといて、面白いと思ったブログなどは定点観測しています。RSS は死んだとか、ふざけた事を書いてるやつがいますけど、冗談はやめてください。どっちみち、面白いと思ったブログは巡回するんです。それを自動化してくれるITに相応しい手法が RSS Reader なんです。SNS の時代は情報はソーシャルから入手します?寝ぼけてんじゃねーぞコラァ?  という訳で、移行先を探しています。まだまだ保留していますが、第一候補は、livedoor reader かな?でも、なんか違うんですよね。次が Feedly か?まぁ、Google Reader 終了に備えて準備していただけあって、移行はスムーズにできました。ただ、フィードの消化が全くもって無理でした。せめてスペースキーとかでフィードをどんどん消化できるようじゃないと、使い物になりません。ここら辺が改善されれば、Feedly に決めようかなーと思いつつ保留してます。  他にも名乗りを上げているところがたくさんあるようなので、使い勝手をチェックしつつ6月中には移行先を決めたいと考えています。  どうせなら、読者購読とシェア機能を工夫して実装してもらえると、尚良いです。Google+ や Facebook とは違って、この部分のソーシャルは、ほんと面白かったんです。なんと言うか、鋭さが違います。

2013年3月12日火曜日

ポリゴンの髭を取り除く

 標準に無い変形アルゴリズムを晒してみようと思います。
  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 前方の要素検索位置
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] 2項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( pred( *first, *next ) )  return first;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 前方の要素検索位置
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist = std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next = first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next = last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( *first == *next )  return first;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 後方の要素検索位置
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_find_later(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] 2項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( pred( *first, *next ) )  return next;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の要素間隔指定バージョン
    @retval 後方の要素検索位置
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_find_later(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER  next;
    if( interval < dist / 2 ) {
      next  =  first;
      for( size_t i = 0; i < interval; ++i )  ++next;
    } else {
      next  =  last;
      for( size_t i = dist; i > interval; --i )  --next;
    }
    while( next != last ) {
      if( *first == *next )  return next;
      ++first;  ++next;
    }
    return last;
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の INTERVAL 要素間隔バージョン
    @retval イテレータ(要素検索位置)
  */
  template <class FORWARD_ITER, class BINARY_PREDICATE>
  FORWARD_ITER interval_adjacent_rotate_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last,      //!< [in] 終了位置
    BINARY_PREDICATE  pred       //!< [in] 2項演算子
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER result  =  interval_adjacent_find( interval, first, last, pred );
    if( result != last )  return result;
    return interval_adjacent_find_later( dist - interval, first, last, pred );
  }

  //! 指定間隔の隣接検索
  /*!
    @note std::adjacent_find の INTERVAL 要素間隔バージョン
    @retval イテレータ(要素検索位置)
  */
  template <class FORWARD_ITER>
  FORWARD_ITER interval_adjacent_rotate_find(
    size_t            interval,  //!< [in] 間隔
    FORWARD_ITER      first,     //!< [in] 先頭位置
    FORWARD_ITER      last       //!< [in] 終了位置
  ) {
    size_t dist  =  std::distance( first, last );
    if( dist <= interval )  return last;
    FORWARD_ITER result  =  interval_adjacent_find( interval, first, last );
    if( result != last )  return result;
    return interval_adjacent_find_later( dist - interval, first, last );
  }

何に使うかというと、---ABA--- みたいな構成のポリゴンは、髭のように変な辺が飛び出しているので、それを消去するのに使います。--ABCBA--みたいなパターンもあるので、--ABA-- を消去しても油断できません。地道に再帰で消し去ります。
  //! 単純な連続重複があるか調べる
  /*!
    @retval true 重複あり
    @retval false 重複なし
  */
  template <typename T>
  bool check_duplicate( const vector<T>& sec ) {
    return (std::adjacent_find( sec.begin(), sec.end() ) != sec.end());
  }

  //! 単純な連続重複点を除去する
  /*!
    @note 先頭と末尾は連続としない
  */
  template <typename T>
  void deduce_duplicate( vector<T>& sec ) {
    vector<T>::iterator f  =  std::adjacent_find( sec.begin(), sec.end() );
    while( f != sec.end() ) {
      sec.erase( f );
      f  =  std::adjacent_find( sec.begin(), sec.end() );
    }
  }

  //! 単純な連続重複があるか調べる
  /*!
    @retval true 重複あり
    @retval false 重複なし
  */
  template <typename T>
  bool check_closed_duplicate( const vector<T>& sec ) {
    if( sec.size() < 3 )  throw std::exception();
    return check_duplicate( sec ) || (*(sec.begin()) == *(sec.rbegin()));
  }

  //! 単純な連続重複点を除去する
  /*!
    @note 先頭と末尾を連続とする
  */
  template <typename T>
  void deduce_closed_duplicate( vector<T>& sec ) {
    if( sec.size() < 3 )  throw std::exception();
    deduce_duplicate( sec );
    if( *(sec.begin()) == *(sec.rbegin()) )  sec.pop_back();
  }

  //! ABAタイプの無駄な尾を除去する
  /*!
    @note ポリラインに使用する
  */
  template <typename T>
  void deduce_tail( vector<T>& sec ) {
    vector<T>::iterator f  =    interval_adjacent_find( 2, sec.begin(), sec.end() );
    while( f != sec.end() ) {
      vector<T>::iterator g  =  f;
      ++g;  sec.erase( g );  sec.erase( f );
      f  =    interval_adjacent_find( 2, sec.begin(), sec.end() );
    }
  }

  //! ABAタイプの無駄な尾を除去する
  /*!
    @note ポリゴンに使用する
  */
  template <typename T>
  void deduce_closed_tail( vector<T>& sec ) {
    vector<T>::iterator f  =    interval_adjacent_rotate_find( 2, sec.begin(), sec.end() );
    while( f != sec.end() ) {
      vector<T>::iterator g  =  f;
      ++g;
      if( g == sec.end() ) {
        sec.erase( f );  sec.erase( sec.begin() );
      } else {
        sec.erase( g );  sec.erase( f );
      }
      f  =    interval_adjacent_rotate_find( 2, sec.begin(), sec.end() );
    }
  }

あんま、おもしろくないですかね。

2013年3月11日月曜日

std::move ではまった事

 いまの所、std::move ではまった事なぞを、思い出せる範囲で書いてみようと思います。

 直近では、ndk での話ですが、std::unique に move constructor と move operator しか持たないクラスの deque をかけると、見事にデータが壊れました。move に一部対応している状況なので、文句は言えません。自前で move 用の unique をこさえました。特に、このバグは場所を特定できるまでに凄い時間がかかりました。どこで壊れているのか探すのも大変でした。

 vector を std::move にかけて移動させると、要素が倍で増えました。これは、move 後の変数の状態は不定なので、move した後にも残骸が残っており、残骸要素が加算されていくというバグでした。move した後に clear() をコールする事で回避しました。

move constructor だけでなく、copy constructor も追加したら、copy が優先されて、予期せぬ挙動を引き起こしました。copy constructor は封印して、copy ファンクタを利用するようなアルゴリズムをこさえる事で回避しました。

一応、こんなところでしょうか?

2013年3月9日土曜日

Webサービスの難しさ

 会社で納品しているシステムで、PostgreSQL からデータを引いてサーバ側で地図を描画して配信しているシステムがあるんです。このシステムの難しさは、5分間隔とかでリアルタイムに大量の軌跡を描画しなければならん所です。しかも、24時間以内の長さで、好きな期間を指定できるのと、軌跡を表示する移動体を自由に選択できるところも難しいです。輪をかけて難易度を上げているのが、軌跡の点の上にマウスを置いとくと、その点の通過時刻を表示するという仕様です。この仕様のおかげで、データを点としてデータベースに保持するよりありません。大抵、負荷のかかる見方をするのが、直近の24時間程度という特性もあります。

 ポリラインとか、ポリゴンで登録されていれば、空間インデックスにかけて関係する部分だけを取り出し描画すれば良いんですが、軌跡の場合は、点と点を結ぶ線の情報が必要なので、空間インデックスで絞るわけにもいきません。なので、指定された期間中のデータを総なめする必要があります。

 さて、閲覧する人数が増えて負荷がかかると、PostgreSQL に対する負荷が膨大になり、ストールを起こします。PostgreSQL のチューニングもパンパンにやってて、1個のクエリー自体は普段、10 から 20 mm sec 程度で、それが移動体分になります。しょうがないんで、MySQL でやれば、もっと速いんじゃないの?と指示してテストさせてみましたが、あまりチューニング無しの MySQL だとスタート時点で、100 mm sec 以上かかっていて、MySQLに変更したからと言ってバラ色の人生が待ち受けている訳でもなく、成果も見込めないので、MySQL は辞めました。まぁ、MySQLがそんなに性能が凄い良いとも思っていなかったのを裏付けした格好になります。

 次に、pgpool-2 を使って、接続イニシャルを減らす方法を試してみました。しかし、pgpool-2 だと、通常接続の 1.2倍のペナルティを受けてしまいました。十分にプール数を確保しても、そうだったので、今時のPostgreSQLは、相当に速いんだなぁと実感できました。

 システム構成上、今のところスケール・アウトができないので、今度は memcached を使って PostgreSQL の負荷を低減させる方策を思いつきました。冒頭に示した要件があるので、キーを [移動体番号]-[日付+時刻] にして、5分間隔に軌跡の点を保存して、そこから引くようにしてみました。ところが、実装して試してみると遅い。はい、冷静に考えると5分刻みデータなので24時間だと12*24= 288回のリクエストを発行する計算になります。これが移動体1台分。今度は socket の往復分のコストが馬鹿にならず、性能が 1/2 に落ちました。これを裏付けるべく、15分間隔にして試してみたところ、性能が 1.5 倍になりました。という訳で、memcached も使いよう。今回のケースでは威力を発揮できない感じです。

 結局、結論としては、いつか NoSQL でやらないと、この部分は破綻すると提言していたように、Redis に置き換えてやってみるよりない感じになりました。

 5分間隔でPostgreSQLのテーブルにポリラインを登録しておいて、そこから引くという構成も考えられます。しかし、更新負荷等のバランスから考えて、NoSQL に置き換えるのが王道かな?と考えている次第であります。

本日のバグ lambda

本日のバグ。今回は、boost::shared_ptr と boost::weak_ptr にまつわる話です。
集合セット S に foo クラスが入っており、集合セット S は生成と破棄を行います。
集合セット S に含まれる foo は、それぞれ異なりますが、重複する場合があります。
foo を shared_ptr でラップして、集合セットに保持し、全体としての foo のカタログを weak_ptr で持たそうかなぁ?とも思いましたが、カタログにアクセスする度に weak_ptr::lock を呼び出すのも非効率的です。何よりも、foo オブジェクトを探したいのに死んでいたら foo オブジェクトの値を取り出せないので、lower_bound とかで検索できないのも痛いです。
という事で、shared_ptr::use_count を調べて、カタログ以外に所有者がいなければ、消せばええやん!という風にしましたが、うまく行きませんでした。以下のコードです。
#include <iostream>
#include <vector>
#include <boost/shared_ptr.hpp>
#include <boost/range/algorithm_ext/erase.hpp>

struct foo {
};

typedef boost::shared_ptr<foo>  foo_t;

int main()
{
  std::vector<foo_t>  v;
  for( int i = 0; i < 10; ++i )  v.push_back( foo_t( new foo ) );
  std::cout << "=== run remove_erase_if" << std::endl;
  boost::remove_erase_if( v, 
    [](foo_t val) -> bool {
     std::cout << val.use_count() << std::endl;
      return val.use_count() <= 1;
    }
  );
  std::cout << "erased -> " << v.size() << std::endl;
  
  return 0;
}
はい、正解は、
   [](foo_t& val) -> bool {
参照でアクセスしないと、カウント増えますよねwwwwwって事でした。

2013年3月7日木曜日

CentOS に libmemcached をインストール

 rpmforge から入れろとか、情報がありますが、libmemcache-devel までは入るんですが、肝心の libmemcached が影も形も無い。ほぇー。ま、こんな時は、ソースからコンパイルやね。
$ wget https://launchpad.net/libmemcached/1.0/1.0.16/+download/libmemcached-1.0.16.tar.gz
$ sudo mv libmemcached-1.0.16.tar.gz /usr/local/src
$ su
# tar xvf libmemcached-1.0.16.tar.gz
# cd libmemcached-1.0.16
# ./configure --prefix=/usr
# make
はい、tr1/cstdint が無いと怒られます。モンキーパッチで対応です
# vi libmemcached-1.0/memcached.h
こんな感じに修正
#ifdef __cplusplus
//#  include <tr1/cinttypes>
#  include <inttypes.h>
#ifndef INT64_C
#define INT64_C(c) (c ## LL)
#define UINT64_C(c) (c ## UL)
#endif
#  include <cstddef>
#  include <cstdlib>
#else
#  include <inttypes.h>
#  include <stddef.h>
#  include <stdlib.h>
#  include <stdbool.h>
#endif
気をとりなおして
# make
# make test
# make install