Ich habe mich schon eine Weile gefragt, wie viel Geschwindigkeitssteigerung man ungefähr erwarten kann, wenn man eine Policy-basierte Entwurfsstrategie für die Entwicklung von Algorithmen in C++ unter Verwendung von Templates im Vergleich zum Strategy-Muster mit dynamischer Polymorphie einsetzt. Dabei interessieren mich insbesondere Algorithmen zur Bildverarbeitung.
Hinweis
Diesen Artikel habe ich ursprünglich auf englisch geschrieben und im August 2023 mit ChatGpts Hilfe ins Deutsche übersetzt. Das ist eine seltene und alte Ausnahme. Üblicherweise schreibe ich Artikel auf deutsch und die Übersetzung ins Englische passiert in Kollaboration mit einer Maschine.
Strategie vs. Policy in C++
Sowohl Policy als auch Strategy können verwendet werden, um Algorithmen zu modularisieren. Für weitere Details verweise ich auf entsprechende Fachliteratur:
- Modern C++ Design, A. Alexandrescu, 2001
- Design Pattern, E. Gamma, R. Helm, R. Johnson und J. Vlissides, 1995
Um beide Ansätze ausschließlich hinsichtlich der Geschwindigkeit zu vergleichen, habe ich ein einfaches Beispiel erstellt. Ich betrachte die binären Operationen Addition und Subtraktion von zwei Bildern pixelweise und inplace für alle Bildpixel i. Für das polymorphismusbasierte Strategy-Muster verwende ich eine abstrakte Oberklasse.
template <class t_data>
struct BinaryOperator
{
virtual t_data sBinOperation(t_data a, t_data b) = 0;
};
template<class t_data>
struct Add : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return a+b;
}
};
template<class t_data>
struct Subtract : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return a-b;
}
};
Weiterhin habe ich eine Klasse, die über das Bild iteriert und die binäre Operation pixelweise anwendet. Die binäre Operation ist als polymorphes Element enthalten.
template <class t_data>
struct ImBinaryOperatorStrategy
{
BinaryOperator<t_data> *binOp;
ImBinaryOperatorStrategy(BinaryOperator<t_data> *binOp):binOp(binOp){}
void imBinOperation(t_data* im1, t_data* im2, int width, int height, int step1,
int step2)
{
for (int y=0; y<height; y++)
for (int x=0; x<width; x++)
im1[x+y*step1] = binOp->sBinOperation(im1[x+y*step1],im2[x+y*step2]);
}
};
Für das Policy-basierte Design mit Templates verwende ich die Klassen Add und Subtract (aber nicht ihre Basisklasse BinaryOperator) und die folgende Klasse, um auf Bilder zu arbeiten. Im Gegensatz zum Strategy-Muster ist die binäre Operation kein Element, sondern wird als Template-Parameter übergeben.
template <template <class> class t_binOp, class t_data>
struct ImBinaryOperatorPolicy : t_binOp<t_data>
{
void imBinOperation(t_data* im1, t_data* im2,int width, int height, int step1,
int step2)
{
for (int y=0; y<height; y++)
for (int x=0; x<width; x++)
im1[x+y*step1] =
t_binOp<t_data>::sBinOperation(im1[x+y*step1],im2[x+y*step2]);
}
};
Beispielsweise schreibe ich im Falle der Addition
Add<float> add;
ImBinaryOperatorStrategy<float> addOpStrategy(&add);
addOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
für das Strategy-Muster und
ImBinaryOperatorPolicy<Add, float> addOpPolicy;
addOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
für das Policy-Muster.
Geschwindigkeitsvergleiche
Unter Verwendung von OpenCV 2.4.9*http://opencv.org habe ich das Graustufen-Testbild mit 512x512 geladen und das Bild 10000-mal mit dem Policy-basierten Entwurf und 10000-mal mit dem Strategy-Muster addiert und subtrahiert. Auf meinem recht alten Intel Core 2 Duo-Prozessor*Intel Core 2 Duo CPU E7300 @ 2,66 GHz, Ubuntu 12.04, 32 Bit, gcc 4.6.3 war das Policy-basierte Design ohne gcc-Optimierung etwa 1,24-mal schneller als das Strategy-basierte Design. Wenn wir jedoch die Compiler-Optimierung durch die CMake-Option -DCMAKE_BUILD_TYPE=RELEASE einschalten, erhöht sich der Geschwindigkeitszuwachs auf einen Faktor von ca. 4,13. Die CMake-Option verwendet die gcc-Flags -O3 -DNDEBUG. Wenn ich Addition und Subtraktion durch Maximum und Minimum ersetze, verringert sich die Geschwindigkeitssteigerung auf ca. 1,76. Wenn ich die Christoph-Operatoren verwende, bei denen ich o.B.d.A. $a+b$ durch $\sqrt{a+b}\sqrt{a+b}$ ersetze, beträgt die Geschwindigkeitssteigerung 1,02. Auf Christophs i7*Intel Core i7 CPU 920 @ 2,67 GHz, Ubuntu 64 Bit, gcc 4.6.3 ist das Policy-Muster langsamer als die Strategy-Version für diese Operatoren und der Geschwindigkeitsfaktor beträgt 0,78. Alle Ergebnisse, einschließlich der Zeitmessungen einer dritten Maschine mit einem Intel Xeon-Prozessor*Intel Xeon E5-2637 @ 3,5 GHz, Win7 64 Bit, Visual Studio 12 sind in der folgenden Tabelle zusammengefasst.
| Methode | Maschine | Opt. | Geschwindigkeitssteigerung | Policy Zeit [s] | Strategie Zeit [s] |
|---|---|---|---|---|---|
| add/sub | Core 2 Duo | nein | 1,24 | 51,67 | 64,05 |
| add/sub | Core 2 Duo | ja | 4,13 | 5,14 | 21,27 |
| max/min | Core 2 Duo | ja | 1,76 | 12,03 | 21,17 |
| Christoph’s add/sub | Core 2 Duo | ja | 1,02 | 44,29 | 45,23 |
| add/sub | i7 | ja | 3,69 | 3,41 | 12,59 |
| max/min | i7 | ja | 2,31 | 5,44 | 12,58 |
| Christoph’s add/sub | i7 | ja | 0,78 | 41,01 | 32,1 |
| add/sub | Xeon | ja | 4,04 | 2,64 | 10,66 |
| max/min | Xeon | ja | 1,55 | 17,81 | 27,69 |
| Christoph’s add/sub | Xeon | ja | 1,5 | 18,52 | 27,86 |
Das vollständige Programm wird im Anschluss dargestellt.
#include <opencv2/opencv.hpp>
#include <string>
using namespace cv;
using namespace std;
// This base class is needed for strategy
template <class t_data>
struct BinaryOperator
{
virtual t_data sBinOperation(t_data a, t_data b) = 0;
};
// That Add inherits from BinaryOperator is only necessary for strategy not for
// policy
template<class t_data>
struct Add : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return a+b;
}
};
// That Subtract inherits from BinaryOperator is only necessary for strategy not for
// policy
template<class t_data>
struct Subtract : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return a-b;
}
};
// That Maximum inherits from BinaryOperator is only necessary for strategy not for
// policy
template<class t_data>
struct Maximum : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return max(a,b);
}
};
// That Minimum inherits from BinaryOperator is only necessary for strategy not for
// policy
template<class t_data>
struct Minimum : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return min(a,b);
}
};
// That ChristophOperator inherits from BinaryOperator is only necessary for strategy
// not for policy
template<class t_data>
struct ChristophAdd : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return sqrt(a+b)*sqrt(a+b);
}
};
// That ChristophSubtract inherits from BinaryOperator is only necessary for strategy
// not for policy
template<class t_data>
struct ChristophSubtract : BinaryOperator<t_data>
{
t_data sBinOperation(t_data a, t_data b)
{
return sqrt(a-b)*sqrt(a-b);
}
};
// Implements binary operations on images using policy based design
template <template <class> class t_binOp, class t_data>
struct ImBinaryOperatorPolicy : t_binOp<t_data>
{
inline void imBinOperation(t_data* im1, t_data* im2,int width, int height,
int step1, int step2)
{
for (int y=0; y<height; y++)
for (int x=0; x<width; x++)
im1[x+y*step1] = t_binOp<t_data>::sBinOperation(im1[x+y*step1],im2[x+y*step2]);
}
};
// Implements binary operations on images using stragey based design
template <class t_data>
struct ImBinaryOperatorStrategy
{
BinaryOperator<t_data> *binOp;
ImBinaryOperatorStrategy(BinaryOperator<t_data> *binOp):binOp(binOp){}
void imBinOperation(t_data* im1, t_data* im2,int width, int height, int step1,
int step2)
{
for (int y=0; y<height; y++)
for (int x=0; x<width; x++)
im1[x+y*step1] = binOp->sBinOperation(im1[x+y*step1],im2[x+y*step2]);
}
};
int main()
{
/*
Loading image and converting to float using OpenCV
*/
string inFileName("im.png");
Mat im;
im = imread( inFileName, 0 );
Mat im_f(im.rows, im.cols, CV_32F);
Mat imTmp_f(im.rows, im.cols, CV_32F);
im.convertTo(im_f,CV_32F);
im_f.copyTo(imTmp_f);
int rows = im_f.rows;
int cols = im_f.cols;
int step = im_f.step1();
int stepTmp = imTmp_f.step1();
float *data = reinterpret_cast<float*> (im_f.data);
float *dataTmp = reinterpret_cast<float*> (imTmp_f.data);
int numExperiments = 10000;
/*
Policy addition subtraction
*/
ImBinaryOperatorPolicy<Add, float> addOpPolicy;
ImBinaryOperatorPolicy<Subtract, float> subtractOpPolicy;
double t1 = (double)getTickCount();
for (int i=0; i<numExperiments; i++)
{
addOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
subtractOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
}
t1 = ((double)getTickCount() - t1)/getTickFrequency();
cout << "Time passed in seconds using policy: " << t1 << endl;
/*
Strategy addition subtraction
*/
Add<float> add;
Subtract<float> sub;
ImBinaryOperatorStrategy<float> addOpStrategy(&add);
ImBinaryOperatorStrategy<float> subtractOpStrategy(&sub);
double t2 = (double)getTickCount();
for (int i=0; i<numExperiments; i++)
{
addOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
subtractOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
}
t2 = ((double)getTickCount() - t2)/getTickFrequency();
cout << "Time passed in seconds using strategy: " << t2 << endl;
cout << "Policy is about " << t2/t1 <<
" times faster than strategy for addition and subtraction." << endl;
/*
Policy max/min
*/
ImBinaryOperatorPolicy<Maximum, float> maxOpPolicy;
ImBinaryOperatorPolicy<Minimum, float> minOpPolicy;
t1 = (double)getTickCount();
for (int i=0; i<numExperiments; i++)
{
maxOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
minOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
}
t1 = ((double)getTickCount() - t1)/getTickFrequency();
cout << "Time passed in seconds using policy: " << t1 << endl;
/*
Strategy max/min
*/
Maximum<float> max;
Maximum<float> min;
ImBinaryOperatorStrategy<float> maxOpStrategy(&max);
ImBinaryOperatorStrategy<float> minOpStrategy(&min);
t2 = (double)getTickCount();
for (int i=0; i<numExperiments; i++)
{
maxOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
minOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
}
t2 = ((double)getTickCount() - t2)/getTickFrequency();
cout << "Time passed in seconds using strategy: " << t2 << endl;
cout << "Policy is about " << t2/t1 <<
" times faster than strategy for the pixel-wise max/min." << endl;
/*
Policy ChristophOp
*/
ImBinaryOperatorPolicy<ChristophAdd, float> chaOpPolicy;
ImBinaryOperatorPolicy<ChristophSubtract, float> chsOpPolicy;
t1 = (double)getTickCount();
for (int i=0; i<numExperiments; i++)
{
chaOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
chsOpPolicy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
}
t1 = ((double)getTickCount() - t1)/getTickFrequency();
cout << "Time passed in seconds using policy: " << t1 << endl;
/*
Strategy ChristophOp
*/
ChristophAdd<float> chaOp;
ChristophSubtract<float> chsOp;
ImBinaryOperatorStrategy<float> chaOpStrategy(&chaOp);
ImBinaryOperatorStrategy<float> chsOpStrategy(&chsOp);
t2 = (double)getTickCount();
for (int i=0; i<numExperiments; i++)
{
chaOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
chsOpStrategy.imBinOperation(data, dataTmp, rows, cols, step, stepTmp);
}
t2 = ((double)getTickCount() - t2)/getTickFrequency();
cout << "Time passed in seconds using strategy: " << t2 << endl;
cout << "Policy is about " << t2/t1 <<
" times faster than strategy for the Christoph operator." << endl;
return 0;
}