“第3章 問題 15 : 画像変換の並列化” リベンジ
エピソード IV - 新たなる希望
画像変換の遅延評価を並列化する第3章の問題15
で
synchronizedを入れただけで、私のマシンでは20%遅くなった
私のマシンのコア数は4つなので、並列化しても挽回ならず結局遅くなってしまった（残念…）
と書いたが、何も考えずにsynchronizedで並列化をやってしまったのは、未熟であった
第6章は並列処理をテーマにしているので、名誉挽回のためにsynchronized以外の方法にトライしてみる
エピソード V - 帝国の逆襲
■ ピクセル単位のsynchronized
以前の解答では、縦のラインごとにsynchronizedで排他制御していた
これでは目が粗すぎるのだろうか?
ピクセル単位で排他制御してみる
ただ
synchronized (cache[x])
を
synchronized (cache[x][y])
に変更したのでは、NullPointerExceptionが出て撃沈する
また、cacheの初期値をnullの替わりに “あり得ない色” にすることもできない
そこで
private String[][] locks; locks = new String[width][height];
と、排他制御用のオブジェクトをピクセル分用意したが…
なんとlocksの初期化に画像変換の倍の時間が掛かってしまい、これも駄目
計測に使った画像は 512×384 ピクセルで大きくないんだけど、やはり十万単位のロックオブジェクトは多すぎて逆効果か…
■ Lockによる排他制御
ロックオブジェクトの数はピクセル分ではなく横幅分に収めておくが、synchronizedではなくLockを用いる
※ フィールド
/** 変換済みの色のキャッシュの縦ラインごとのロック */ private Lock[] locks;
※ コンストラクタ
super(transformer, original, width, height); // ロックの初期化 locks = new Lock[width]; for (int x = 0; x < cache.length; x++) { locks[x] = new ReentrantLock(); }
※ 指定された座標の色の取得
locks[x].lock(); try { if (cache[x][y] == null) { cache[x][y] = transformer.apply(x, y, original); } return cache[x][y]; } finally { locks[x].unlock(); }
■ Atomic なキャッシュ
二次元配列cacheの代わりに、各々の要素をアトミックに参照・更新できるAtomicReferenceArrayを用いる
※ フィールド
/** * Atomic な色の配列<br> * cache[][] の代わりに使用 */ private final AtomicReferenceArray<Color> pixels;
※ コンストラクタ
super(transformer, original, width, height); // AtomicReferenceArray は二次元配列をサポートしていないので、一次元配列でシミュレート pixels = new AtomicReferenceArray<Color>(width * height);
※ 指定された座標の色の取得
return pixels.accumulateAndGet( x + cache.length * y, null, (current, dummy) -> current != null ? current: transformer.apply(x, y, original) );
■ Read Lock から Write Lock へ昇格
ピクセルの色は、最初に1回だけ書き込まれ、後は読み込みだけである
そこで
- Read Lock（非排他的）を取得して
- キャッシュがまだセットされてなければ、Lock を Write Lock（排他的）に昇格
- Write Lock（排他的）を獲得したスレッドは、キャッシュに値をセット
- Write Lock（排他的）を獲得できなかったスレッドは、キャッシュに値がセットされるまで待つ
Read Lock から Write Lock への昇格を実装するため、Java 8 で導入されたStampedLockを使う
… ReentrantReadWriteLockがサポートしているのは、Write Lock から Read Lock への降格のみ
※ フィールド
/** 変換済みの色のキャッシュの縦ラインごとのロック */ private StampedLock[] locks;
※ コンストラクタ
super(transformer, original, width, height); // ロックの初期化 locks = new StampedLock[width]; for (int x = 0; x < cache.length; x++) { locks[x] = new StampedLock(); }
※ 指定された座標の色の取得
// まず Read Lock を取得 long stamp = locks[x].readLock(); try { // キャッシュがセットされているか? if (cache[x][y] == null) { // まだセットされてないので Write Lock に昇格 long writeStamp = locks[x].tryConvertToWriteLock(stamp); // Write Lock を獲得したか? if (writeStamp != 0) { // Write Lock を獲得したら、キャッシュに値をセット stamp = writeStamp; cache[x][y] = transformer.apply(x, y, original); } else { // Write Lock を獲得できなかったら、キャッシュに値がセットされるまで待つ locks[x].unlockRead(stamp); stamp = locks[x].readLock(); } } // キャッシュの値を返す return cache[x][y]; } finally { locks[x].unlock(stamp); }
エピソード VI - ジェダイの帰還
さて、これら4つの並列化のスピードを比べてみよう
参考値として
- シングルスレッドで画像変換したケース
- 一切、排他制御を行わずに並列化したケース
の二つを加える
ただし、排他制御を行わない並列化のケースでも、Pixel Reader の連鎖の最初の Pixel Reader は念のためにキャッシュに展開済みのスレッドセーフな Pixel Reader に置き換える
// PixelReader transformed = in.getPixelReader(); // スレッドセーフでない // ↓ PixelReader transformed = new TransformedPixelReader(in); // スレッドセーフ for (ImageTransformer f : pendingOperations) { transformed = new TransformedPixelReader(f, transformed, width, height); }
計測に使用した画像は 512×384 ピクセルで、以下の画像変換を32回繰り返してその平均値をとった
■ 画像変換
// 枠線を付ける ColorTransformer frame = (x, y, c) -> x < 15 || y < 15 || x >= width - 15 || y >= height - 15 ? Color.AQUAMARINE : c; // ぼかし ImageFilter blur = (x, y, m) -> { double red = 0.0; double green = 0.0; double blue = 0.0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { red += m[i][j].getRed(); green += m[i][j].getGreen(); blue += m[i][j].getBlue(); } } return ImageFilter.color(red/9.0, green/9.0, blue/9.0); }; // シャープ化 ImageFilter sharpen = (x, y, m) -> { double red = 9.0 * m[1][1].getRed() - m[0][0].getRed() - m[1][0].getRed() - m[2][0].getRed() - m[0][1].getRed() - m[2][1].getRed() - m[0][2].getRed() - m[1][2].getRed() - m[2][2].getRed(); double green = 9.0 * m[1][1].getGreen() - m[0][0].getGreen() - m[1][0].getGreen() - m[2][0].getGreen() - m[0][1].getGreen() - m[2][1].getGreen() - m[0][2].getGreen() - m[1][2].getGreen() - m[2][2].getGreen(); double blue = 9.0 * m[1][1].getBlue() - m[0][0].getBlue() - m[1][0].getBlue() - m[2][0].getBlue() - m[0][1].getBlue() - m[2][1].getBlue() - m[0][2].getBlue() - m[1][2].getBlue() - m[2][2].getBlue(); return ImageFilter.color(red, green, blue); } // 鏡像 ImageTransformer mirror = (x, y, reader) -> reader.getColor((width - 1) - x, y);
■ 画像変換の組み合わせ
Image image = LatentImage.from(original)
.transform(mirror)
.transform(blur)
.transform(mirror)
.transform(sharpen)
.transform(frame)
.toImage();
参照する座標を一点に集中させれば競合が起こりやすくなるけど、画像変換としては糞つまんないし使わんでしょう
そして、変換した全ての画像は以下のメソッドで、シングルスレッドで画像変換した画像と比較して、正しく変換されているかどうかを検証した
static boolean equals(Image image0, Image image1) { // ピクセルサイズ if (!(image0.getWidth() == image1.getWidth() && image0.getHeight() == image1.getHeight())) return false; // 全てのピクセルを比較 int width = (int)image0.getWidth(); int height = (int)image0.getHeight(); PixelReader reader0 = image0.getPixelReader(); PixelReader reader1 = image1.getPixelReader(); for (int x = 0; x < width; x++) { for (int y = 0; y < height; y++) { if (!reader0.getColor(x, y).equals(reader1.getColor(x, y))) return false; } } return true; }
さらに、画像変換のパターンとして
- 画像のサイズはそのままで、適用する変換を5つから20個に増やす
- 適用する変換はそのままで、画像サイズを縦横二倍（ピクセル数は4倍）に増やす
を追加する
| 方式 | 変換失敗 | スピード | 4倍の変換 | 4倍の画像 |
|---|---|---|---|---|
| シングル・スレッド | － | 1.00 | 1.00 | 1.00 |
| 排他制御なし | なし | 1.65 | 1.54 | 1.30 |
| synchronized | なし | 1.17 | 1.26 | 1.11 |
| Lock | なし | 1.11 | 1.15 | 1.10 |
| Atomic なキャッシュ | なし | 1.27 | 0.97 | 0.96 |
| Read Lock → Write Lock | なし | 1.18 | 1.17 | 1.12 |
AtomicReferenceArrayかStampedLockが、ぶっちぎりで速ければシナリオとしては最高 :-) だったんだけど、うまくいきませんなあ
薄々感じてはいたけど “排他制御なし” が最善の解とはね
