ブログトップ 記事一覧 ログイン 無料ブログ開設

DELPHIER@はてな このページをアンテナに追加 RSSフィード Twitter

2014/03/15

better gyp

仕事でごりごり gyp を使って早くも3年になる。いくつか個人的に痒いところを修正して公開してみた。



修正は以下のとおり。

  1. Android: 非 cygwin でもビルドできるようにした
    1. android: Fix path separator for non-cygwin Windows ndk-build. · 22e62bd · okumura/gyp
  2. Android: *.so をビルドするときの name mangling 規則を緩められるようにした
    1. android: Allow targets to have not strict unmangled names by android_unm... · 0a70b36 · okumura/gyp
  3. Windows: MIDL オプションの ValidateParameters、GenerateTypeLibrary をサポートした
    1. win: Allow support MIDL ValidateParameters and GenerateTypeLibrary. · 879936b · okumura/gyp

ここを見てちゃんとやれば本流に取り込んでもらえるかな?

2013/06/20

faster octree color quantization

256色画像全盛期はとっくに過ぎ去った感がありますが、今回は画像を256色以下に減色するという話です。減色された画像の画質を向上させる方法として誤差拡散法がありますが、今回はそれはやりません。


減色する方法は大昔から研究されていて有名なものがいくつかあります


今回はoctreeをやります。画質を追求するのはImage Magickなどがやっていますので、速度を追求してみましょう。octreeの計算量は、画像の横幅をW、縦幅をH、深さをDとすると、O(W*H*D)となります。試した限りだと、octreeだと深さが4〜5程度で画像を人が認識するには十分な画質が得られますが、いかんせんループ回数が多すぎますピクセル処理なのにボクセル処理してるみたいな計算量です。


量子化ループ最適化その1

octreeのループ処理のコードを見ると、同じ画素に対しては全く同じ処理が繰り返されるということが分かります。これを利用した最適化を考えます画像のヒストグラムを求めることができれば、画像の色数分だけのループで済みそうですね。画像の色数Cは、必ずC<=W*H以下になるので、計算量は必ず最適化前よりも小さくなります


画像の色数分だけループする方法に処理を書き換えるには、画像のヒストグラムを求める必要があります画像画素ソートすることで画像のヒストグラムを求めることができます*1ソートは割とコストがかかるので高速化には使えません*2。よって、真面目にヒストグラムを計算する方が良さそうです。しかし、真面目にヒストグラムを計算すると大量にメモリ必要になります。RGB888で、ヒストグラムの各要素を符合なし整数で管理すると、2^24*4で64MBものメモリ必要になってしまいます最近の端末やサーバなら余裕な気もしますが、長いことクライアントアプリを作ってきた私の感覚的にはメモリを使い過ぎですし、色数が1677万色もあると最悪で65536x65536の画像に相当する処理をやらないといけなくなるので高速化できるのかが不安になってきます。というわけで、精度を落とすことを考えてみましょう。

  • RGB888 -> 2^24*4 -> 64MB (65536x65536程度の画像に相当する)
  • RGB777 -> 2^21*4 -> 8MB (2896x2896程度の画像に相当する)
  • RGB666 -> 2^18*4 -> 1MB (1024x1024程度の画像に相当する)
  • RGB565 -> 2^16*4 -> 256KB (512x512程度の画像に相当する)
  • RGB555 -> 2^15*4 -> 128KB (362x362程度の画像に相当する)
  • RGB444 -> 2^12*4 -> 16KB (128x128程度の画像に相当する)

感覚的にRGB666程度なら精度的にも速度的にも空間的にもよさそうですね。実際に試してみたところ、手元のマシンで処理時間を30〜50ミリ秒程度から10ミリ秒以下まで削減できました。いいですね。しかし、高速化前と結果が異なります高速化前の方が画質がいいです。これは高速化+RGB888でやっても高速化前の画質に劣ります・・・。せっかくのoctreeが台無しで残念ですね。


量子化ループ最適化その2



ノードキャッシュ

octreeは動的に八分木のノードに使うメモリを確保・破棄します。確かに空間的な効率はいいです。単発呼び出しなら。ただし、繰返し呼び出すとメモリ断片化が起こってOSにあまり優しくない気がします。優しくないのは紳士的ではありませんので、優しくできないかを考えてみましょう。小さいメモリの確保・破棄が連続すると断片化が発生しやすいですが、確保・破棄がなければ断片化は発生しません。ノードをプールしておけばいいわけですね。ではいくつプールしておけばいいでしょうか?これは八分木の深さによります。それぞれの深さのノードがいくつ存在しうるかを考えてみましょう。

  • 深さ 0 -> ノード数 1
  • 深さ 1 -> ノード数 8
  • 深さ 2 -> ノード数 64
  • 深さ 3 -> ノード数 512
  • 深さ 4 -> ノード数 4096 (4K)
  • 深さ 5 -> ノード数 32768 (32K)
  • 深さ 6 -> ノード数 262144 (256K)
  • 深さ 7 -> ノード数 2097152 (2MB)
  • 深さ 8 -> ノード数 16777216 (16MB)

上で深さ4〜5で十分な画質が得られると書いたので、深さ4までキャッシュすることを考えてみましょう。深さ4までのノードを連続したアドレス空間に配置するために、順序付けを考えてみましょう。例えばこんな感じです。

  • 深さ 0 -> 0
  • 深さ 1 -> 1〜8 (1+n)
  • 深さ 2 -> 9〜72 (1+(1+n)*8 = 1+8+8*n)
  • 深さ 3 -> 73〜584 (1+8+(1+n)*64 = 1+8+64+64*n)
  • 深さ 4 -> 585〜4680 (1+8+64+(1+n)*512 = 1+8+64+512+512*n)

これで深さに応じた順序付けができました。簡単ですね。


パレットインデクス付の最適化

上記の処理で高速にパレットが生成できるようになりましたが、実際に減色された画像を得るには生成したパレットと画像対応付ける必要があります。この画素パレットでいうとどの色だ、という処理ですね。octreeは全ての画素を処理するまでパレットが決定されないので、効率的な逆引きが難しいのです。何の前提条件もない場合、近似色計算画素毎にパレットの全エントリとの色空間の距離を調べて最も距離が小さいものを選択していくという処理になります計算量はパレットのエントリ数をPとするとO(W*H*P)となります。またボクセル処理みたいになってます。ボクセル処理は禁止です。感覚的には、画素からハッシュ的にパレットのインデクスを求めることができれば高速に処理できそうな気がします

*1http://d.hatena.ne.jp/izariuo440/20120320/1332212854

*2:私が試した限りでは、ソートだけで最適化前のoctreeの処理よりも時間がかかってしまいましたが、画素数によってはソートの方が速いかもしれません

2013/03/31

gyp でネイティブコードプロジェクトのビルドを多環境に対応させる

今回は「gyp でネイティブコードプロジェクトビルドを多環境対応させる」です。私がやっていることをメモしておきます


背景

私は Windowsコードをよく書いていました。ある時から AndroidWindows MobileLinuxMac OS XiOS でも動くように意識して書くようになりました。すぐに、コードビルドするための各種設定ファイルを用意するのが面倒になりました。Visual StudioXcodeMakefileAndroid NDK 用 Makefile・・・やっていられませんね。


ビルドツール巡り・・・cmake、scons、waf、そして gyp へ

ビルド設定ファイル自動生成するためのビルドツールを探してみるとすぐにいくつか出てきました。半年ほど cmake と scons を並行運用していましたが、その中で気に入らない点が出てきました。

  1. ビルドはできるが Visual StudioXcode などのプロジェクトファイルが生成できない
    1. scons、waf などはこれ
  2. Visual StudioXcodeプロジェクトファイルが生成できるが中身がイマイチ
    1. cmake では、include ディレクトリがなぜか絶対パスだったりした
  3. プロジェクト間の設定の共有がイマイチ
    1. Android NDK の export の概念に相当するものがあったりなかったり
  4. Android NDK に対応していない
    1. 当時は cmake、scons、waf どれも対応してませんでした

この辺をすべてうまく対応してくれたのが、gyp*1 です。gyp は Google Chrome をはじめとした Googleクライアントプログラムを中心に利用実績があります*2Google 日本語入力ベースである mozc なんかもそうですね。node.js*3、その中で動いている v8*4、libuv なんかも gyp でビルドされるようになっています。ただし、gyp のスクリプトPython 2.4 だと動かない*5ので、Cent OS など Python 2.4 が既定の環境では地味に辛いのですが、手でビルド設定ファイルを書くことに比べればささいな問題です。


gyp をプロジェクトに配置する

gyp はただの Python スクリプト群です。New BSD ライセンスなので、自分プロジェクトに組み込んでしまうのが楽かもしれません。私の場合は、node.js を参考に以下のようにして運用しています

  1. $PROJECT_ROOT/tools/gyp
    1. gyp 一式を配置する
  2. $PROJECT_ROOT/build/common.gypi
    1. プロジェクトの共通設定を書く
      1. Visual Studioプロジェクト設定、Xcodeプロジェクト設定など
  3. $PROJECT_ROOT/configure.py
    1. gyp を呼び出してプロジェクトファイルを生成するスクリプトを書く
  4. $PROJECT_ROOT/README.md
    1. ビルド手順を書く

Android NDK 向けのテコ入れ

gyp が生成した Android NDK 用の Makefileビルドすると、やたらと長いファイル名になってしまうので、私は以下のファイルを一部修正してファイル名が短くなるようにしています

  1. $PROJECT_ROOT/tools/gyp/pylib/gyp/generator/android.py
    1. ComputeAndroidModule で return self.target するようにしている

まとめ

この記事には具体例がありませんが、Githubnode.jsコードが何よりも雄弁です。

*1https://code.google.com/p/gyp/

*2:gyp は Google Chrome などを他環境ビルドするための作られたもので、以前は scons でビルドされていました

*3:以前は waf でビルドされていました

*4:以前は scons でビルドされていました

*5:with など新しい構文を使っているため

2012/03/31

tiny hash table

Cでコードを書いているとハッシュテーブル*1が欲しくなることが多々あります。というわけで小さいのを書いてみました。


ハッシュテーブルについて

ハッシュテーブルは、あるキーハッシュ関数を使ってマッピングし、それに対応する値を関連付けるためのデータ構造です。連想配列として使われたり、ハッシュマップと呼ばれたりもしますハッシュ関数によってキーインデックスに変換し(これをハッシュと呼ぶ)、それに対応する配列の要素(スロットまたはバケツと呼ばれる)に値を入れておきます。そこそこメモリを使いますが、その分高速に動作します


探索において、木構造などの二分探索をベースとした実装では、キー比較回数がlog2(N)となりますが、ハッシュテーブルでは大抵これよりも小さくなります比較回数がこれよりも多くなるような状況、つまり衝突が多発する状況では、衝突が多発しないようなハッシュ関数を選択するか、バケツを大きくするか、木構造など二分探索をベースとした実装を用いるなどの回避策があります。ほぼWikipediaな内容ですみません


thtblの特徴


工夫したところ

オープンアドレス法だと、ポインタ管理とは別に、その値が「空」「削除済み」「使用中」を区別する必要がありますポインタと他にマーキング用のデータを用意するのは面倒だしメモリも使いそうで嫌だったので、ポインタアドレッシングの仕組みを利用してポインタのみで管理することにしました。大抵のOSでは、カーネルランドユーザランドでそれぞれアドレス空間が分かれています。以下のページを見ると、大抵のOSではカーネルランドが大きい番地を占めていることが分かります


というわけで、以下のように区別することにしました。私はカーネルランドで動作するものは書かないので。

  • 空 → NULL
  • 削除済み → 0xffffffff または 0xffffffffffffffffLLU
  • 使用中 → 上記以外

GNU hashtabというハッシュテーブルライブラリも似たようなことをしていて、mallocなどは1を返さないという前提の元に実装されています。小さい番地は大抵何らかのアプリスタックが使っているので、確かにその前提はたいてい成立するんでしょうね。


実行結果

いくつかのハッシュ関数、いくつかのバケツの大きさで衝突させまくりで挿入だけベンチマークをとってみました。衝突率の低さだけが性能の決定的要素ではなく、比較関数コスト重要な要素だよ、ということがよく分かる結果になっていますね。

128

string

searches: 128, collisions: 204 (1.593750%)

0.000243 [sec]

zackw

searches: 128, collisions: 416 (3.250000%)

0.000212 [sec]

FNV-1a

searches: 128, collisions: 51 (0.398438%)

0.000214 [sec]

1024

string

searches: 1024, collisions: 5048 (4.929688%)

0.001869 [sec]

zackw

searches: 1024, collisions: 1920 (1.875000%)

0.001591 [sec]

FNV-1a

searches: 1024, collisions: 503 (0.491211%)

0.001523 [sec]

8192

string

searches: 8192, collisions: 43510 (5.311279%)

0.013948 [sec]

zackw

searches: 8192, collisions: 51554 (6.293213%)

0.012849 [sec]

FNV-1a

searches: 8192, collisions: 3827 (0.467163%)

0.011939 [sec]

16384

string

searches: 16384, collisions: 849376 (51.841797%)

0.042020 [sec]

zackw

searches: 16384, collisions: 38040 (2.321777%)

0.024676 [sec]

FNV-1a

searches: 16384, collisions: 6266 (0.382446%)

0.024592 [sec]

32768

string

searches: 32768, collisions: 1692528 (51.651855%)

0.083191 [sec]

zackw

searches: 32768, collisions: 23370 (0.713196%)

0.047768 [sec]

FNV-1a

searches: 32768, collisions: 17951 (0.547821%)

0.049201 [sec]

65536

string

searches: 65536, collisions: 2047008 (31.234863%)

0.141463 [sec]

zackw

searches: 65536, collisions: 121870 (1.859589%)

0.098748 [sec]

FNV-1a

searches: 65536, collisions: 45944 (0.701050%)

0.100855 [sec]

1048576

string

searches: 1048576, collisions: 30468520 (29.057045%)

2.362834 [sec]

zackw

searches: 1048576, collisions: 3814406 (3.637701%)

1.755987 [sec]

FNV-1a

searches: 1048576, collisions: 515284 (0.491413%)

1.933815 [sec]



その他

実装にあたり参考にしたページなど。

2012/03/20

画像の色数を求めたりヒストグラムを作るためのソートをいろいろ実装してみた

画像の色数を求めるにはハッシュ的なものを使うよりもソートした方が速いという話です。


また、ヒストグラムを高速に作ろうとすると色の深度に応じてメモリを食いますRGBそれぞれが8ビットだと64MBほどメモリを食います。対してソートでやろうとすると、画素数分だけで済むのでメモリ的にも優しいです。


そんなわけで、ソートです。上記ではクイックソートを使ってますが、クイックソートが最善手とは限りません。最近メモリが豊富なので、バケツソート分布数え上げソートや基数ソートも十分実用的です。どれがいいだろう、というわけでいくつか試してみました。クイックソート分布数え上げソート、基数ソートを手持ちのMac Book Airで試してみました。コードはこちら。


4バイトの符合なし整数をソートするという簡単なコードです。以下のソートを比べています


結果としては、概ねワード単位の基数ソートが最も速かったです。つうわけで、画像処理ではワード単位の基数ソートを使うのがよさそうです。基数ソートは少しだけ工夫しました。基数ソートでは、普通単位毎に結果をコピーするのですが、ダブルバッファリングすることでその手間をなくしました。画素数が大きくなればなるほど効いてくるはずです。以下は、Mac Book Air 2.13 GHz Intel Core 2 Duo, Memory 4 GB 1067 MHz DDR3で実行した結果です。まずは実機での結果。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)

qsort : 0.023937 [sec]

quick_sort : 0.022483 [sec]

counting_sort : 0.211722 [sec]

counting_sort2 : 0.146360 [sec]

counting_sort3 : 0.133482 [sec]

radix_sort : 0.006259 [sec]

radix_sort2 : 0.005574 [sec]

radix_sort3 : 0.005545 [sec]

radix_sort4 : 0.004007 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)

qsort : 0.105436 [sec]

quick_sort : 0.092361 [sec]

counting_sort : 0.184831 [sec]

counting_sort2 : 0.184686 [sec]

counting_sort3 : 0.169230 [sec]

radix_sort : 0.025758 [sec]

radix_sort2 : 0.024495 [sec]

radix_sort3 : 0.023203 [sec]

radix_sort4 : 0.015684 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)

qsort : 0.288884 [sec]

quick_sort : 0.260471 [sec]

counting_sort : 0.274694 [sec]

counting_sort2 : 0.272200 [sec]

counting_sort3 : 0.257774 [sec]

radix_sort : 0.069239 [sec]

radix_sort2 : 0.066146 [sec]

radix_sort3 : 0.060907 [sec]

radix_sort4 : 0.040482 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)

qsort : 0.134426 [sec]

quick_sort : 0.118140 [sec]

counting_sort : 0.198503 [sec]

counting_sort2 : 0.198470 [sec]

counting_sort3 : 0.182864 [sec]

radix_sort : 0.033405 [sec]

radix_sort2 : 0.031146 [sec]

radix_sort3 : 0.029891 [sec]

radix_sort4 : 0.019964 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)

qsort : 0.492288 [sec]

quick_sort : 0.439028 [sec]

counting_sort : 0.376246 [sec]

counting_sort2 : 0.370595 [sec]

counting_sort3 : 0.353696 [sec]

radix_sort : 0.113894 [sec]

radix_sort2 : 0.110131 [sec]

radix_sort3 : 0.102530 [sec]

radix_sort4 : 0.069099 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)

qsort : 1.493648 [sec]

quick_sort : 1.320081 [sec]

counting_sort : 0.833016 [sec]

counting_sort2 : 0.819314 [sec]

counting_sort3 : 0.810189 [sec]

radix_sort : 0.332729 [sec]

radix_sort2 : 0.316817 [sec]

radix_sort3 : 0.292213 [sec]

radix_sort4 : 0.200232 [sec]

同じマシンWindows XP on Virtual Boxで実行した結果がこちら。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)

qsort : 0.016000 [sec]

quick_sort : 0.000000 [sec]

counting_sort : 0.485000 [sec]

counting_sort2 : 0.765000 [sec]

counting_sort3 : 0.719000 [sec]

radix_sort : 0.000000 [sec]

radix_sort2 : 0.031000 [sec]

radix_sort3 : 0.000000 [sec]

radix_sort4 : 0.016000 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)

qsort : 0.093000 [sec]

quick_sort : 0.047000 [sec]

counting_sort : 0.687000 [sec]

counting_sort2 : 0.844000 [sec]

counting_sort3 : 0.828000 [sec]

radix_sort : 0.062000 [sec]

radix_sort2 : 0.047000 [sec]

radix_sort3 : 0.047000 [sec]

radix_sort4 : 0.047000 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)

qsort : 0.234000 [sec]

quick_sort : 0.188000 [sec]

counting_sort : 0.656000 [sec]

counting_sort2 : 0.781000 [sec]

counting_sort3 : 0.812000 [sec]

radix_sort : 0.188000 [sec]

radix_sort2 : 0.235000 [sec]

radix_sort3 : 0.171000 [sec]

radix_sort4 : 0.109000 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)

qsort : 0.125000 [sec]

quick_sort : 0.063000 [sec]

counting_sort : 0.625000 [sec]

counting_sort2 : 0.719000 [sec]

counting_sort3 : 0.813000 [sec]

radix_sort : 0.047000 [sec]

radix_sort2 : 0.046000 [sec]

radix_sort3 : 0.047000 [sec]

radix_sort4 : 0.047000 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)

qsort : 0.359000 [sec]

quick_sort : 0.282000 [sec]

counting_sort : 0.563000 [sec]

counting_sort2 : 0.906000 [sec]

counting_sort3 : 0.969000 [sec]

radix_sort : 0.297000 [sec]

radix_sort2 : 0.281000 [sec]

radix_sort3 : 0.250000 [sec]

radix_sort4 : 0.156000 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)

qsort : 0.719000 [sec]

quick_sort : 0.766000 [sec]

counting_sort : 0.765000 [sec]

counting_sort2 : 1.234000 [sec]

counting_sort3 : 1.188000 [sec]

radix_sort : 0.797000 [sec]

radix_sort2 : 0.640000 [sec]

radix_sort3 : 0.563000 [sec]

radix_sort4 : 0.390000 [sec]


次は、画像処理向けの高速なmemcmp、memcpy、bzeroあたりをやってみましょうかね。

bswap

今日コードWindows XPMac OS X 10.6.8で動作することを確認しています


バイナリプログラミングをやっていると、エンディアンに応じてバイトオーダーをひっくり返す(バイトスワップ)というのがよくありますバイトスワップは高速にやろうと思うと中々厄介で、マクロにすると分かりづらいし、ライブラリ関数にするとインライン展開が効かなくなります。というわけでいい方法がないのか少しだけ調べてみました。


ここまでのまとめ。


なかなか面倒そうだな、ということが分かりました。でも、こんなよくあることは誰かがうまいことやってくれているはずです。ということでさらに調べてみると、以下のようなコードが見つかりました。


コードを眺めてみると以下のようになっているようです。


Cだけで書くならこんな感じでヘッダに書くのが定石みたいですね。まるで魔法のようですが、自分計算してもコンパイルして実行してもちゃんと動きます特に、bswap_32。右シフトも左シフトも論理和も論理積もすべて二回ずつなのでとても美しい感じがします。

static inline uint16_t bswap_16(uint16_t x) {
  return (x >> 8) | (x << 8);
}

static inline uint32_t bswap_32(uint32_t x) {
  x= ((x << 8) & 0xFF00FF00) | ((x >> 8) & 0x00FF00FF);
  return (x >> 16) | (x << 16);
}

static inline uint64_t bswap_64(uint64_t x) {
    union {
        uint64_t ll;
        uint32_t l[2];
    } w, r;
    w.ll = x;
    r.l[0] = bswap_32 (w.l[1]);
    r.l[1] = bswap_32 (w.l[0]);
    return r.ll;
}

bswap_32、普通に考えたらこうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(((x & 0x000000ff) >> 0x00) << 0x18) |
		(((x & 0x0000ff00) >> 0x08) << 0x10) |
		(((x & 0x00ff0000) >> 0x10) << 0x08) |
		(((x & 0xff000000) >> 0x18) << 0x00);
}

んで、こうなって・・・

static inline uint32_t bswap_32(uint32_t x) {
  return
		((x & 0x000000ff) << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		((x & 0xff000000) >> 0x18);
}

こうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(x << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		(x >> 0x18);
}

さっきのbswap_32よりも、論理和が一回多くなります。それだけですけど、それを減らせるってのがさっきのbswap_32のすごいところ。Graphic Gems Iにはこういうことが一杯書いてありそうだな。

Graphics Gems (Graphics Gems - IBM)

Graphics Gems (Graphics Gems - IBM)