重複コード改善 ジェネリックプログラミングによる実装

重複コードを避けたい

2017年8月、画像の膨張・収縮アルゴリズムについて調べたときに、双方のコードの重複が気になりました。
ポリシークラスを使用したジェネリックプログラミングによる実装を考えてみます。

画像処理 膨張・収縮アルゴリズム

膨張処理も収縮処理も、Y座標とX座標によるラスタスキャン・ループの部分は同じコードで重複しています。実際、片方のコードはコピペして作成してしまいました。

簡単なコードなので、重複していることは気になりませんし、このコードのままで良いと考えています。しかし、もう少し複雑なコードだった場合はどうでしょうか?いつまでも、コピペを続けますか?

ジェネリックプログラミングとは

動的ポリモーフィズム

共通メインルーチン化という「ポリモーフィズムによる実装」は、良い考え方だと思います。

重複コード改善 ポリモーフィズムによる実装

しかし、C++言語による継承仮想関数を利用するポリモーフィズムは、動的なポリモーフィズムとなり実行時に結合します。この仕組みは、仮想関数テーブルを作成して実行時にテーブル参照して呼ぶ関数を決定します。従って関数呼び出しのオーバーヘッドが増加します。

静的ポリモーフィズム

重複コードを改善するために、探究心の強いC++言語の名人プログラマーが考える方法はジェネリックプログラミングによる実装です。

共通メインルーチン化のポリモーフィズムを静的に実現できないだろうかと考えます。同じメソッドを呼び出しても実際のインスタンスごとにその挙動をコンパイル時に決定することは可能でしょうか?

C++はテンプレートという記述方法があり、ジェネリックプログラミングができます。テンプレートは、どんなクラス(データ型)を使用するかを明記しないでクラスを記述することができます。そして、使用するときにテンプレート引数でクラスを宣言します。しかも、すべてコンパイル時に静的に解決します。従って、実行時のオーバーヘッドは発生しません。

関数テンプレート

関数テンプレートとは、関数の引数の型を明示しないで「Tは何らかの型」として関数を定義します。この関数テンプレートを参照するときテンプレート引数で型を宣言することにより、関数定義をジェネレートします。


引数の型がint型の例を示します。

下記、int型の関数定義をジェネレートします。


引数の型がbouble型の例を示します。

下記、bouble型の関数定義をジェネレートします。

クラステンプレート

クラステンプレートとは、使用する型を明示しないで「Tは何らかの型」としてクラスを定義します。このクラステンプレートをインスタンス化するときテンプレート引数で使用する型を宣言することにより、クラス定義をジェネレートします。

int型のクラスの例を示します。

下記、int型のクラス定義をジェネレートします。


double型のクラスの例を示します。

下記、double型のクラス定義をジェネレートします。

ポリシークラステンプレート

ポリシークラステンプレートとは、クラスの挙動をテンプレートで差し替えます。

  • ポリシークラス : 振る舞いを定義するクラス (PolicyA , PolicyB)
  • ホストクラス : 受け入れるクラステンプレート (Host)

このクラステンプレートをインスタンス化するとき、テンプレート引数でポリシークラスを宣言することにより、クラス定義をジェネレートします。ホストクラスのメンバ関数 func() の振る舞いは、テンプレートパラメータに与えるポリシークラスによってコンパイル時に決定します。

ポリシークラス

ポリシークラス



ポリシークラスの参照の例を示します。

仮想的に、下記クラス定義をジェネレートします。インスタンスを二つ生成していますので、テンプレートからホストクラスを静的に二つ生成します。

ジェネリックプログラミングによる実装

3つのクラスを定義します。

  • 画像処理ホストクラス : class cImage<Cpolicy> ...Cpolicyクラスを継承し、共通メインルーチンを定義
  • 画像膨張ポリシークラス : class cDilation.... 膨張画像処理を定義
  • 画像収縮ポリシークラス : class cErasion  ....収縮画像処理を定義
画像処理ホストクラス

画像処理ホストクラス

画像膨張ポリシークラス

画像膨張ポリシークラス

画像収縮ポリシークラス

画像収縮ポリシークラス

 

画像処理ホストクラスは、Cpolicyクラスを継承して共通メインルーチンとなる ラスタスキャン・ループ loop_function() を定義します。画像膨張ポリシークラスと画像収縮ポリシークラスは、それぞれの画像処理関数 func() を定義します。


3つの関数のインターフェースを示します。

  • cDilation::func() : 画像膨張
  • cErasion::func() : 画像収縮
  • cImage::loop_function() : 画像のラスタスキャン・ループ

ホストクラス 共通メインルーチン

ポリシークラス 画像膨張

ポリシークラス 画像膨張

 

ポリシークラス 画像収縮

ポリシークラス 画像収縮


C++言語によるアルゴリズムコードを示します。

 

 

ジェネリックプログラミングによる実装の仕組み

画像処理ホストクラスに共通メインルーチン loop_function() を定義して、ポリシークラスの画像膨張クラスまたは画像収縮クラスを継承することで、膨張アルゴリズムと収縮アルゴリズムのメイン部分を共通のコードで実現することができました。

ジェネリックプログラミングによる実装

ジェネリックプログラミングによる実装

コンパイラが生成するx86アセンブラコードを確認します。

共通メインルーチンの loop_function()は、ソースコードではホストクラスの定義はひとつですがクラステンプレートによって膨張用と収縮用のふたつをジェネレートしました。

cImage<cDilation>::loop_function() : 画像膨張処理のラスタスキャン・ループ
cImage<cErasion >::loop_function() : 画像収縮処理のラスタスキャン・ループ

 

  • 画像膨張処理は、インスタンス gDilation から共通メインルーチン cImage<cDilation>::loop_function() をコールします。
  • 画像収縮処理は、インスタンス gErasion から共通メインルーチン cImage<cDilation>::loop_function() をコールします。
  • cImage<cDilation>::loop_function()では、ラスタスキャン・ループしながら1画素ごとに cDilation::func() をコールします。
  • cImage<cErasion >::loop_function()では、ラスタスキャン・ループしながら1画素ごとに cErasion ::func() をコールします。

このように共通メインルーチンで同じメソッド func()をコールしても、ポリシークラスによって膨張クラス用インスタンスと収縮クラス用インスタンスをジェネレートし、インスタンス毎にその挙動を変えています。

ポリモーフィズムを静的に実現しています。ポリシークラスは、コンパイル時にジェネレートするので実行時のオーバーヘッドはありません。ポリシークラスによるジェネリックプログラミングは、共通メインルーチンをひとつ定義するだけで、複数のインスタンス用にジェネレートするので便利な仕組みです。

さらなる改善

理想に近い形を実現できましたが、もう少し気になることがあります。

共通メインルーチン cImage<ポリシークラス>::loop_function()は、ラスタスキャン・ループしながら1画素ごとに ポリシークラス::func() をコールします。4K画像などの大画像を処理する場合は、やはりオーバーヘッドが気になります。

func() をインライン展開できないでしょうか?

 

func() の定義に __inline キーワードを付けてみました。共通メインルーチン のラスタスキャン・ループの中に func() がインライン展開できました。これで完璧です。当初の重複のあるコードとほぼ同じコードを生成することができました。

画像膨張・収縮のような簡単なコードの場合、無理して重複コードを除去する必要はないと考えます。
もう少し複雑なコードだった場合、ジェネリックプログラミングによる実装を選択するかどうかは、ソースコードの保守とパフォーマンスのトレードオフかもしれません。

 

 

このエントリーをはてなブックマークに追加