Strategy vs. Policy for Image Processing Algorithms

I was wondering for quite a while how much speed-up one can roughly expect by a policy[1] based design of algorithms in C++ using templates compared to the strategy[2] pattern using polymorphism. Thereby, I am especially interested in algorithms for image processing.

Strategy vs. Policy in C++

Both, policy and strategy, can be used to modularize algorithms. For more details I refer to the textbooks listed below. To compare both approaches exclusively in terms of speed, I created a simple example. I consider the binary operations addition and subtraction of two images pixel-wise and in place, e. g.,

for all image pixels i.

For the polymorphism based strategy pattern I use an abstract super class and the two aforementioned particular examples of binary operators on scalars, namely addition and subtraction.

Further, I have a class that iterates over the image and applies the binary operation pixel-wise. The binary operation is contained as a polymorphic member.

For the policy based design with templates, I use the classes Add and Subtract (but not their base class BinaryOperator) and the following class to operate on images. In contrast to the strategy pattern, the binary operation is not a member but passed as template parameter.

For instance, I write in case of the addition

for the strategy pattern and

for the template based policy pattern.

Speed Comparisons

Using OpenCV 2.4.9[3] , I loaded the gray-scale 512×512 Lenna/Lena test image and added and subtracted the image from itself 10000 times with the policy based design and 10000 times with the strategy pattern. On my quite old Intel Core 2 Duo processor[4] the policy based design was about 1.24 times faster than the strategy based design with no gcc optimization. However, if we switch on compiler optimization in terms of the CMake option -DCMAKE_BUILD_TYPE=RELEASE the speed-up is increased to a factor of ca. 4.13. The CMake option uses the gcc flags -O3 -DNDEBUG. If I replace addition and subtraction with max and min, the speed-up decreases to ca. 1.76. If I use the Christoph-Operators where I replace a+b with \sqrt{a+b}\sqrt{a+b} and analogously for minus, the speed-up is 1.02. On Christoph’s i7[5] , policy is slower than strategy for these operators and the speed-up factor is 0.78. All results including the time measurements of a third machine with an Intel Xeon CPU[6] are summarized in the following table.

method machine opt. speed-up policy time [s] strategy time [s]
add/sub Core 2 Duo no 1.24 51.67 64.05
add/sub Core 2 Duo yes 4.13 5.14 21.27
max/min Core 2 Duo yes 1.76 12.03 21.17
Christoph's add/sub Core 2 Duo yes 1.02 44.29 45.23
add/sub i7 yes 3.69 3.41 12.59
max/min i7 yes 2.31 5.44 12.58
Christoph's add/sub i7 yes 0.78 41.01 32.1
add/sub Xeon yes 4.04 2.64 10.66
max/min Xeon yes 1.55 17.81 27.69
Christoph's add/sub Xeon yes 1.5 18.52 27.86

The complete program is depicted subsequently.

 

Output without compiler optimization only for addition and subtraction:

Time passed in seconds using policy: 51.6706
Time passed in seconds using strategy: 64.0456
Policy is about 1.2395 times faster than strategy.

Output with compiler optimization (-O3 -DNDEBUG):

Time passed in seconds using policy: 5.14101
Time passed in seconds using strategy: 21.271
Policy is about 4.13752 times faster than strategy for addition and subtraction.

Time passed in seconds using policy: 12.0251
Time passed in seconds using strategy: 21.1691
Policy is about 1.76041 times faster than strategy for the pixel-wise max/min.

Time passed in seconds using policy: 44.2865
Time passed in seconds using strategy: 45.2317
Policy is about 1.02134 times faster than strategy for the Christoph operators.

References

  1. Modern C++ Design, A. Alexandrescu, 2001 ^
  2. Design Patterns, E. Gamma, R. Helm, R. Johnson, and J. Vlissides, 1995 ^
  3. http://opencv.org, OpenCV copyright notice ^
  4. Intel Core 2 Duo CPU E7300 @ 2.66GHz, Ubuntu 12.04, 32bit, gcc 4.6.3 ^
  5. Intel Core i7 CPU 920 @ 2.67GHz, Ubuntu 64bit, gcc 4.6.3 ^
  6. Intel Xeon E5-2637 @ 3.5 GHz, Win7 64bit, Visual Studio 12 ^