重複コードを避けたい

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

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

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

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

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

動的ポリモーフィズム

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

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

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

静的ポリモーフィズム

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

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

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

関数テンプレート

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

template  <class T>
T MAX(T x , T y)
{
    return ( (x>y)? x : y );
}

---

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

  int z = MAX<int>(2,3);    // Tは、int型

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

int MAX(int x , int y)
{
    return ( (x>y)? x : y );
}

---

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

  double z = MAX<double>(0.2 , 0.3);    // Tは、double型

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

double MAX(double x , double y)
{
    return ( (x>y)? x : y );
}

クラステンプレート

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

template  <class T>
class cVar
{
   T  var;
public:
   void set(T v) { var=v;      }
   T    get()    { return var; }
};

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

cVar<int> iVar;    // Tは、int型
  iVar.set(2);
  int i = iVar.get();

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

class cVar
{
   int  var;
public:
   void set(int v) { var=v;      }
   int  get()      { return var; }
};

---

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

cVar<double> iVar;    // Tは、double型
  iVar.set(0.2);
  double i = iVar.get();

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

class cVar
{
   double  var;
public:
   void set(double v) { var=v;      }
   double  get()      { return var; }
};

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

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

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

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

// ホストクラス
template  <class Policy>
class Host : public Policy
{
public:
  void go()
  {
      Policy::func();
  }
};

class PolicyA     // ポリシークラスA
{
protected:
  void func()
  {
      std::cout << "PolicyA" << std::endl;
  }
};

class PolicyB     // ポリシークラスB
{
protected:
  void func()
  {
      std::cout << "PolicyB" << std::endl;
  }
};

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

  Host<PolicyA> A;     // インスタンス  ホスト＋ポリシーA
  Host<PolicyB> B;     // インスタンス  ホスト＋ポリシーB
  A.go();              // "PolicyA" を表示
  B.go();              // "PolicyB" を表示

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

// ホストクラス
class Host_PolicyA : public PolicyA
{
public:
  void go()
  {
      PolicyA::func();
  }
};

class Host_PolicyB : public PolicyB
{
public:
  void go()
  {
      PolicyB::func();
  }
};

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

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

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

 

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

---

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

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

 

---

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

template <class Cpolicy>  
class cImage : public Cpolicy
{
public:
  void loop_function( int iw ,int ih ,const unsigned char *pucSrc ,unsigned char *pucDst );
};

class cDilation
{
public:
  unsigned char func( unsigned char uc ,unsigned char ua ,unsigned char ub ,unsigned char ul ,unsigned char ur );
};

class cErasion
{
public:
  unsigned char func( unsigned char uc ,unsigned char ua ,unsigned char ub ,unsigned char ul ,unsigned char ur );
};

unsigned char  cDilation::func(  unsigned char uc ,unsigned char ua ,unsigned char ub ,unsigned char ul ,unsigned char ur )
{
    unsigned char ux =  0x00;
    if (uc != 0x00)   { ux = 0xFF; }
    if (ua != 0x00)   { ux = 0xFF; }
    if (ub != 0x00)   { ux = 0xFF; }
    if (ul != 0x00)   { ux = 0xFF; }
    if (ur != 0x00)   { ux = 0xFF; }
    //
    return ux;
}

 

unsigned char  cErasion::func(  unsigned char uc ,unsigned char ua ,unsigned char ub ,unsigned char ul ,unsigned char ur )
{
    unsigned char ux =  0xFF;
    if (uc != 0xFF)   { ux = 0x00; }
    if (ua != 0xFF)   { ux = 0x00; }
    if (ub != 0xFF)   { ux = 0x00; }
    if (ul != 0xFF)   { ux = 0x00; }
    if (ur != 0xFF)   { ux = 0x00; }
    //
    return ux;
}

 

template  <class Cpolicy>
void cImage::loop_function( int iw ,int ih ,const unsigned char *pucSrc ,unsigned char *pucDst )
{
    for(int iy=1; iy<ih-1; iy++)
    {
        for(int ix=1; ix<iw-1; ix++)
        {
            unsigned char uc = pucSrc[ (iy+0)*iw + (ix+0) ];    // 中央
            unsigned char ua = pucSrc[ (iy-1)*iw + (ix+0) ];    // 上
            unsigned char ub = pucSrc[ (iy+1)*iw + (ix+0) ];    // 下
            unsigned char ul = pucSrc[ (iy+0)*iw + (ix-1) ];    // 左
            unsigned char ur = pucSrc[ (iy+0)*iw + (ix+1) ];    // 右
            //
            unsigned char ux =  func( uc ,ua ,ub ,ul ,ur );
            pucDst[ iy*iw + ix ] = ux;
        }
    }
}

  // 画像膨張
   cImage  gDilation;
   gDilation.loop_function( iw ,ih ,pucSrc ,pucDst );

  // 画像収縮
  cImage  gErasion;
  gErasion.loop_function( iw ,ih ,pucSrc ,pucDst );

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

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

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

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

  cImage　 gDilation;    // 画像膨張
  cImage　  gErasion;     // 画像収縮

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

 

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

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

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

さらなる改善

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

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

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

__inline unsigned char  cDilation::func(  unsigned char uc ,unsigned char ua ,unsigned char ub ,unsigned char ul ,unsigned char ur )
{
    unsigned char ux =  0x00;
    if (uc != 0x00)   { ux = 0xFF; }
    if (ua != 0x00)   { ux = 0xFF; }
    if (ub != 0x00)   { ux = 0xFF; }
    if (ul != 0x00)   { ux = 0xFF; }
    if (ur != 0x00)   { ux = 0xFF; }
    //
    return ux;
}

 

__inline unsigned char  cErasion::func(  unsigned char uc ,unsigned char ua ,unsigned char ub ,unsigned char ul ,unsigned char ur )
{
    unsigned char ux =  0xFF;
    if (uc != 0xFF)   { ux = 0x00; }
    if (ua != 0xFF)   { ux = 0x00; }
    if (ub != 0xFF)   { ux = 0x00; }
    if (ul != 0xFF)   { ux = 0x00; }
    if (ur != 0xFF)   { ux = 0x00; }
    //
    return ux;
}

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

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