Commit: 4b1196c90fb583a3002d91b6997db06f780726fe - color_quantizer (git)

減色プログラム

Commit MetaInfo

• Revisão: 4b1196c90fb583a3002d91b6997db06f780726fe (tree)
• Hora: 2011-05-22 13:48:48
• Autor: beru <berupon@gmai...>
• Commiter: beru

Mensagem de Log

used AVX intrinsics but it doesn't improve processing speed. actually, it's slow compared to SSE version. why is that?

Mudança Sumário

• modified: Array.h
• delete: Color4d.h => Color4d_sse.h
• add: Color4d_avx.h
• delete: Color4f.cpp => Color4f_sse.cpp
• delete: Color4f.h => Color4f_sse.h
• modified: quantize.h
• modified: vs2008/color_quantizer.vcproj
• modified: vs2010/color_quantizer.vcxproj

Diff

--- a/Array.h
+++ b/Array.h
@@ -12,7 +12,7 @@ struct Array2D
 	
 	void allocate() {
 //		pBuff_ = new T[width_ * height_];
-		pBuff_ = (T*) _aligned_malloc(sizeof(T) * width_ * height_, 16);
+		pBuff_ = (T*) _aligned_malloc(sizeof(T) * width_ * height_, 32);
 	}
 
 	Array2D(const Array2D& arr)
@@ -52,102 +52,102 @@ struct Array2D
 	}
 	
 	__forceinline
-	T* operator[] (int row) {
-		return &pBuff_[row * width_];
-	}
-	
-	__forceinline
-	const T* operator[] (int row) const {
-		return &pBuff_[row * width_];
-	}
+	T* operator[] (int row) {
+		return &pBuff_[row * width_];
+	}
+	
+	__forceinline
+	const T* operator[] (int row) const {
+		return &pBuff_[row * width_];
+	}
 	
-	Array2D<T>& operator *= (const T& scalar) {
-#if 1
-		for (size_t i=0; i<width_*height_; ++i) {
-			pBuff_[i] *= scalar;
-		}
-#else
-		for (int i=0; i<width_; i++) {
-			for (int j=0; j<height_; j++) {
-				(*this)[j][i] *= scalar;
-			}
-		}
-#endif
-		return *this;
-	}
-	
-	template <typename T2>
-	Array2D<T> operator * (const T2& scalar) {
-		Array2D<T> result(*this);
-		result *= scalar;
-		return result;
-	}
-
-	std::vector<T> operator * (const std::vector<T>& vec) {
-		std::vector<T> result(height_);
-		T sum;
-		for (int row=0; row<height_; row++) {
-			sum = 0;
-			for (int col=0; col<width_; col++) {
-				sum += (*this)[row][col] * vec[col];
-			}
-			result[row] = sum;
-		}
-		return result;
+	Array2D<T>& operator *= (const T& scalar) {
+#if 1
+		for (size_t i=0; i<width_*height_; ++i) {
+			pBuff_[i] *= scalar;
+		}
+#else
+		for (int i=0; i<width_; i++) {
+			for (int j=0; j<height_; j++) {
+				(*this)[j][i] *= scalar;
+			}
+		}
+#endif
+		return *this;
 	}
 	
-	Array2D<T>& multiply_row_scalar(int row, double mult) {
-		for (int i=0; i<width_; i++) {
-			(*this)[row][i] *= mult;
-		}
-		return *this;
-	}
-
-	Array2D<T>& add_row_multiple(int from_row, int to_row, double mult) {
-		for (int i=0; i<width_; ++i) {
-			(*this)[to_row][i] += mult*(*this)[from_row][i];
-		}
-		return *this;
-	}
-
-	// We use simple Gaussian elimination - perf doesn't matter since
-	// the matrices will be K x K, where K = number of palette entries.
-	Array2D<T> matrix_inverse() {
-		Array2D<T> result(width_, height_);
-		Array2D<T>& a = *this;
-
-		// Set result to identity matrix
-		result *= 0;
-		for (int i=0; i<width_; i++) {
-			result[i][i] = 1;
-		}
-		// Reduce to echelon form, mirroring in result
-		for (int i=0; i<width_; i++) {
-			result.multiply_row_scalar(i, 1/a[i][i]);
-			multiply_row_scalar(i, 1/a[i][i]);
-			for (int j=i+1; j<height_; j++) {
-				result.add_row_multiple(i, j, -a[j][i]);
-				add_row_multiple(i, j, -a[j][i]);
-			}
-		}
-		// Back substitute, mirroring in result
-		for (int i=width_-1; i>=0; i--) {
-			for (int j=i-1; j>=0; j--) {
-				result.add_row_multiple(i, j, -a[j][i]);
-				add_row_multiple(i, j, -a[j][i]);
-			}
-		}
-		// result is now the inverse
-		return result;
-	}
+	template <typename T2>
+	Array2D<T> operator * (const T2& scalar) {
+		Array2D<T> result(*this);
+		result *= scalar;
+		return result;
+	}
+
+	std::vector<T> operator * (const std::vector<T>& vec) {
+		std::vector<T> result(height_);
+		T sum;
+		for (int row=0; row<height_; row++) {
+			sum = 0;
+			for (int col=0; col<width_; col++) {
+				sum += (*this)[row][col] * vec[col];
+			}
+			result[row] = sum;
+		}
+		return result;
+	}
+	
+	Array2D<T>& multiply_row_scalar(int row, double mult) {
+		for (int i=0; i<width_; i++) {
+			(*this)[row][i] *= mult;
+		}
+		return *this;
+	}
+
+	Array2D<T>& add_row_multiple(int from_row, int to_row, double mult) {
+		for (int i=0; i<width_; ++i) {
+			(*this)[to_row][i] += mult*(*this)[from_row][i];
+		}
+		return *this;
+	}
+
+	// We use simple Gaussian elimination - perf doesn't matter since
+	// the matrices will be K x K, where K = number of palette entries.
+	Array2D<T> matrix_inverse() {
+		Array2D<T> result(width_, height_);
+		Array2D<T>& a = *this;
+
+		// Set result to identity matrix
+		result *= 0;
+		for (int i=0; i<width_; i++) {
+			result[i][i] = 1;
+		}
+		// Reduce to echelon form, mirroring in result
+		for (int i=0; i<width_; i++) {
+			result.multiply_row_scalar(i, 1/a[i][i]);
+			multiply_row_scalar(i, 1/a[i][i]);
+			for (int j=i+1; j<height_; j++) {
+				result.add_row_multiple(i, j, -a[j][i]);
+				add_row_multiple(i, j, -a[j][i]);
+			}
+		}
+		// Back substitute, mirroring in result
+		for (int i=width_-1; i>=0; i--) {
+			for (int j=i-1; j>=0; j--) {
+				result.add_row_multiple(i, j, -a[j][i]);
+				add_row_multiple(i, j, -a[j][i]);
+			}
+		}
+		// result is now the inverse
+		return result;
+	}
 
 };
 
-template <typename T>
-Array2D<T> operator * (T scalar, const Array2D<T>& a) {
-	Array2D<T> tmp = a;
-	return tmp * scalar;
-}
+template <typename T>
+Array2D<T> operator * (T scalar, const Array2D<T>& a) {
+	Array2D<T> tmp = a;
+	return tmp * scalar;
+}
 
 template <typename T>
 struct Array3D
@@ -186,11 +186,11 @@ public:
 	}
 
 /*
-	Array2D<T> operator[] (int depth) {
-		return Array2D<T>(width_, height_, &pBuff_[depth * width_ * height_]);
+	Array2D<T> operator[] (int depth) {
+		return Array2D<T>(width_, height_, &pBuff_[depth * width_ * height_]);
 	}
-	Array2D<T> operator[] (int depth) const {
-		return Array2D<T>(width_, height_, &pBuff_[depth * width_ * height_]);
+	Array2D<T> operator[] (int depth) const {
+		return Array2D<T>(width_, height_, &pBuff_[depth * width_ * height_]);
 	}
 */
 	__forceinline

--- /dev/null
+++ b/Color4d_avx.h
@@ -0,0 +1,115 @@
+#pragma once
+
+#include <immintrin.h>
+
+struct Color4d
+{
+	__m256d v;
+	
+	Color4d() {
+		;
+	}
+	
+	Color4d(const Color4d& c) {
+		*this = c;
+	}
+	
+	Color4d(double r, double g, double b, double a) {
+		v = _mm256_setr_pd(r,g,b,a);
+	}
+	
+	Color4d& operator = (const Color4d& rhs) {
+		v = rhs.v;
+		return *this;
+	}
+
+	Color4d direct_product(const Color4d& rhs) const {
+		Color4d result;
+		result.v = _mm256_mul_pd(v, rhs.v);
+		return result;
+	}
+
+	double dot_product(const Color4d& rhs) {
+// http://www.icnet.ne.jp/~nsystem/simd_tobira/dpps.html
+		__m256d s = _mm256_mul_pd(this->v, rhs.v);
+		__m128d s1 = _mm256_extractf128_pd(s, 0);
+		__m128d s2 = _mm256_extractf128_pd(s, 1);
+		__m128d as = _mm_add_pd(s1, s2);
+		as = _mm_hadd_pd(as, as);
+		return as.m128d_f64[0];
+	}
+
+	Color4d& operator += (const Color4d& rhs) {
+		v = _mm256_add_pd(v, rhs.v);
+		return *this;
+	}
+
+	Color4d operator + (const Color4d& rhs) {
+		return Color4d(*this) += rhs;
+	}
+
+	Color4d& operator -= (const Color4d& rhs) {
+		v = _mm256_sub_pd(v, rhs.v);
+		return *this;
+	}
+
+	Color4d operator - (const Color4d& rhs) {
+		return Color4d(*this) -= rhs;
+	}
+	
+	Color4d& operator *= (const Color4d& rhs) {
+		v = _mm256_mul_pd(v, rhs.v);
+		return *this;
+	}
+
+	Color4d operator * (const Color4d& rhs) {
+		return Color4d(*this) *= rhs;
+	}
+
+	Color4d& operator *= (double scalar) {
+		__m256d s = _mm256_set1_pd(scalar);
+		v = _mm256_mul_pd(v, s);
+		return *this;
+	}
+
+	Color4d operator * (double scalar) {
+		return Color4d(*this) *= scalar;
+	}
+	
+	double& operator[] (int idx) {
+		return ((double*)&v)[idx];
+	}
+	const double& operator[] (int idx) const {
+		return ((double*)&v)[idx];
+	}
+	
+	double norm_squared() {
+#if 1
+		__m256d s = _mm256_mul_pd(v, v);
+		__m128d s1 = _mm256_extractf128_pd(s, 0);
+		__m128d s2 = _mm256_extractf128_pd(s, 1);
+		__m128d as = _mm_add_pd(s1, s2);
+		as = _mm_hadd_pd(as, as);
+		return as.m128d_f64[0];
+#else
+		double result = 0;
+		for (int i=0; i<3; i++) {
+			result += (*this)[i] * (*this)[i];
+		}
+		return result;
+#endif
+	}
+	
+	void zero() {
+		v = _mm256_setzero_pd();
+	}
+};
+
+inline Color4d operator * (double scalar, const Color4d& c) {
+	return Color4d(c) *= scalar;
+}
+
+inline Color4d operator * (const Color4d& c, double scalar) {
+	return Color4d(c) *= scalar;
+}
+

--- a/Color4d.h
+++ b/Color4d_sse.h
@@ -1,5 +1,7 @@
 #pragma once
 
+#include <intrin.h>
+
 struct Color4d
 {
 	__m128d v[2];
@@ -24,16 +26,16 @@ struct Color4d
 	}
 
 	Color4d direct_product(const Color4d& rhs) const {
-		Color4d result;
-#if 1
-		result.v[0] = _mm_mul_pd(v[0], rhs.v[0]);
-		result.v[1] = _mm_mul_pd(v[1], rhs.v[1]);
-#else
-		for (int i=0; i<3; i++) {
-			result[i] = (*this)[i] * rhs[i];
-		}
-#endif
-		return result;
+		Color4d result;
+#if 1
+		result.v[0] = _mm_mul_pd(v[0], rhs.v[0]);
+		result.v[1] = _mm_mul_pd(v[1], rhs.v[1]);
+#else
+		for (int i=0; i<3; i++) {
+			result[i] = (*this)[i] * rhs[i];
+		}
+#endif
+		return result;
 	}
 
 	double dot_product(const Color4d& rhs) {
@@ -44,10 +46,10 @@ struct Color4d
 		v = _mm_hadd_pd(v, v);
 		return v.m128d_f64[0];
 #else
-		double result = 0;
-		for (int i=0; i<3; i++) {
-			result += (*this)[i] * rhs[i];
-		}
+		double result = 0;
+		for (int i=0; i<3; i++) {
+			result += (*this)[i] * rhs[i];
+		}
 		return result;
 #endif
 	}
@@ -101,14 +103,14 @@ struct Color4d
 		return Color4d(*this) *= scalar;
 	}
 	
-	double& operator[] (int idx) {
-		return ((double*)&v)[idx];
+	double& operator[] (int idx) {
+		return ((double*)&v)[idx];
 	}
-	const double& operator[] (int idx) const {
-		return ((double*)&v)[idx];
+	const double& operator[] (int idx) const {
+		return ((double*)&v)[idx];
 	}
 	
-	double norm_squared() {
+	double norm_squared() {
 #if 1
 		__m128d t = _mm_add_pd(
 			_mm_mul_pd(v[0], v[0]),
@@ -117,13 +119,13 @@ struct Color4d
 		t = _mm_hadd_pd(t, t);
 		return t.m128d_f64[0];
 #else
-		double result = 0;
-		for (int i=0; i<3; i++) {
-			result += (*this)[i] * (*this)[i];
-		}
-		return result;
-#endif
-	}
+		double result = 0;
+		for (int i=0; i<3; i++) {
+			result += (*this)[i] * (*this)[i];
+		}
+		return result;
+#endif
+	}
 	
 	void zero() {
 		v[0] = _mm_setzero_pd();
@@ -131,11 +133,11 @@ struct Color4d
 	}
 };
 
-inline Color4d operator * (double scalar, const Color4d& c) {
-	return Color4d(c) *= scalar;
-}
+inline Color4d operator * (double scalar, const Color4d& c) {
+	return Color4d(c) *= scalar;
+}
 
-inline Color4d operator * (const Color4d& c, double scalar) {
-	return Color4d(c) *= scalar;
-}
+inline Color4d operator * (const Color4d& c, double scalar) {
+	return Color4d(c) *= scalar;
+}
 

--- a/Color4f.cpp
+++ b/Color4f_sse.cpp
@@ -1,7 +1,6 @@
 #include "stdafx.h"
-#include "Color4f.h"
-
-#include "Color4d.h"
+#include "Color4f_sse.h"
+#include "Color4d_sse.h"
 
 Color4f& Color4f::operator = (const Color4d& rhs)
 {

--- a/Color4f.h
+++ b/Color4f_sse.h
@@ -30,23 +30,23 @@ struct Color4f
 	Color4f& operator = (const Color4d& rhs);
 	
 	Color4f direct_product(const Color4f& rhs) const {
-		Color4f result;
-#if 1
-		result.v = _mm_mul_ps(v, rhs.v);
-#else
-		for (int i=0; i<3; i++) {
-			result[i] = (*this)[i] * rhs[i];
-		}
-#endif
-		return result;
+		Color4f result;
+#if 1
+		result.v = _mm_mul_ps(v, rhs.v);
+#else
+		for (int i=0; i<3; i++) {
+			result[i] = (*this)[i] * rhs[i];
+		}
+#endif
+		return result;
 	}
 
 	float dot_product(const Color4f& rhs) {
 // http://www.icnet.ne.jp/~nsystem/simd_tobira/dpps.html
-		float result = 0;
-		for (int i=0; i<3; i++) {
-			result += (*this)[i] * rhs[i];
-		}
+		float result = 0;
+		for (int i=0; i<3; i++) {
+			result += (*this)[i] * rhs[i];
+		}
 		return result;
 	}
 
@@ -95,28 +95,28 @@ struct Color4f
 		return result;
 	}
 
-	float& operator[] (int idx) {
-		return v.m128_f32[3-idx];
+	float& operator[] (int idx) {
+		return v.m128_f32[3-idx];
 	}
-	const float& operator[] (int idx) const {
-		return v.m128_f32[3-idx];
+	const float& operator[] (int idx) const {
+		return v.m128_f32[3-idx];
 	}
 
-	float norm_squared() {
-		float result = 0;
-		for (int i=0; i<3; i++) {
-			result += (*this)[i] * (*this)[i];
-		}
-		return result;
-	}
+	float norm_squared() {
+		float result = 0;
+		for (int i=0; i<3; i++) {
+			result += (*this)[i] * (*this)[i];
+		}
+		return result;
+	}
 
 	void zero() {
 		v = _mm_setzero_ps();
 	}
 };
 
-inline Color4f operator * (float scalar, const Color4f& c) {
-	Color4f tmp = c;
-	return tmp * scalar;
-}
+inline Color4f operator * (float scalar, const Color4f& c) {
+	Color4f tmp = c;
+	return tmp * scalar;
+}
 

--- a/quantize.h
+++ b/quantize.h
@@ -1,8 +1,8 @@
 #pragma once
 
 #include "Array.h"
-#include "Color4f.h"
-#include "Color4d.h"
+#include "Color4d_sse.h"
+//#include "Color4d_avx.h"
 
 typedef Color4d Color;
 typedef Array2D<Color> Image;

--- a/vs2008/color_quantizer.vcproj
+++ b/vs2008/color_quantizer.vcproj
@@ -339,7 +339,7 @@
 			UniqueIdentifier="{4FC737F1-C7A5-4376-A066-2A32D752A2FF}"
 			>
 			<File
-				RelativePath="..\Color4f.cpp"
+				RelativePath="..\Color4f_sse.cpp"
 				>
 			</File>
 			<File
@@ -385,11 +385,11 @@
 				>
 			</File>
 			<File
-				RelativePath="..\Color4d.h"
+				RelativePath="..\Color4d_sse.h"
 				>
 			</File>
 			<File
-				RelativePath="..\Color4f.h"
+				RelativePath="..\Color4f_sse.h"
 				>
 			</File>
 			<File

--- a/vs2010/color_quantizer.vcxproj
+++ b/vs2010/color_quantizer.vcxproj
@@ -50,11 +50,12 @@
       </PrecompiledHeader>
       <WarningLevel>Level3</WarningLevel>
       <Optimization>Disabled</Optimization>
-      <PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <PreprocessorDefinitions>WIN32;_DEBUG;_CONSOLE;_CRT_SECURE_NO_WARNINGS;%(PreprocessorDefinitions)</PreprocessorDefinitions>
       <AdditionalIncludeDirectories>../</AdditionalIncludeDirectories>
       <BrowseInformation>true</BrowseInformation>
       <MultiProcessorCompilation>true</MultiProcessorCompilation>
       <ForcedIncludeFiles>common.h</ForcedIncludeFiles>
+      <AdditionalOptions>/arch:AVX %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
     <Link>
       <SubSystem>Console</SubSystem>
@@ -75,6 +76,9 @@
       <FloatingPointModel>Fast</FloatingPointModel>
       <MultiProcessorCompilation>true</MultiProcessorCompilation>
       <ForcedIncludeFiles>common.h</ForcedIncludeFiles>
+      <EnableEnhancedInstructionSet>StreamingSIMDExtensions2</EnableEnhancedInstructionSet>
+      <RuntimeLibrary>MultiThreaded</RuntimeLibrary>
+      <AdditionalOptions>/arch:__AVX %(AdditionalOptions)</AdditionalOptions>
     </ClCompile>
     <Link>
       <SubSystem>Console</SubSystem>
@@ -93,7 +97,8 @@
   </ItemGroup>
   <ItemGroup>
     <ClInclude Include="..\Array.h" />
-    <ClInclude Include="..\Color4d.h" />
+    <ClInclude Include="..\Color4d_avx.h" />
+    <ClInclude Include="..\Color4d_sse.h" />
     <ClInclude Include="..\common.h" />
     <ClInclude Include="..\dxor.h" />
     <ClInclude Include="..\quantize.h" />