Longue histoire courte: je suis l'élaboration d'un calcul à forte intensité de traitement de l'image de l'application en C++. Il a besoin de calculer de nombreuses variantes de l'image se déforme sur de petits blocs de pixels extraites à partir des images plus grandes. Le programme ne fait pas courir aussi vite que je le voudrais. Profilage (OProfile) ont montré que la déformation/fonction d'interpolation consomme plus de 70% du temps CPU de sorte qu'il semblait évident pour essayer de l'optimiser.
J'ai été en utilisant le OpenCV bibliothèque de traitement d'images pour la tâche jusqu'à maintenant:
// some parameters for the image warps (position, stretch, skew)
struct WarpParams;
void Image::get(const WarpParams ¶ms)
{
// fills matrices mapX_ and mapY_ with x and y coordinates of points to be
// inteprolated.
updateCoordMaps(params);
// perform interpolation to obtain pixels at point locations
// P(mapX_[i], mapY_[i]) based on the original data and put the
// result in pixels_. Use bicubic inteprolation.
cv::remap(image_->data(), pixels_, mapX_, mapY_, CV_INTER_CUBIC);
}
J'ai écrit ma propre fonction d'interpolation et le mettre dans un harnais de test pour s'assurer de l'exactitude alors que j'ai l'expérience et à l'indice de référence par rapport à l'ancien.
Ma fonction s'est très lent ce qui était attendu. Généralement, l'idée est de:
- Itérer sur les mapX_, mapY_ coordonner les cartes, extrait (valeurs réelles) les coordonnées de la prochaine pixel interpolé;
- Récupérer un 4x4 neighborough de valeurs de pixel (entier coordonnées) à partir de l'image d'origine entourant l'interpolation des pixels;
- Calculer les coefficients de la convolution du noyau pour chacun de ces 16 pixels;
- Calculer la valeur de l'interpolation des pixels comme une combinaison linéaire des 16 valeurs de pixels et le noyau des coefficients.
L'ancienne fonction temporisée à 25us sur mon Wolfdale Core2 Duo. La nouvelle a pris 587us (!). Je me suis empressée de mettre mon assistant chapeau et a commencé à bidouiller le code. J'ai réussi à enlever toutes les branches, omettre certaines duplication de calculs et de transformer les 3 boucles imbriquées en une seule sur les coordonnées des cartes. C'est ce que je suis venu avec:
void Image::getConvolve(const WarpParams ¶ms)
{
__declspec(align(16)) static float kernelX[4], kernelY[4];
// grab pointers to coordinate map matrices and the original image
const float
*const mapX = mapX_.ptr<float>(),
*const mapY = mapY_.ptr<float>(),
*const img = image_->data().ptr<float>();
// grab pointer to the output image
float *const subset = pixels_.ptr<float>(),
x, y, xint, yint;
const ptrdiff_t imgw = image_->width();
ptrdiff_t imgoffs;
__m128 v_px, v_kernX, v_kernY, v_val;
// iterate over the coordinate matrices as linear buffers
for (size_t idx = 0; idx < pxCount; ++idx)
{
// retrieve coordinates of next pixel from precalculated maps,
// break up each into fractional and integer part
x = modf(mapX[idx], &xint);
y = modf(mapY[idx], &yint);
// obtain offset of the top left pixel from the required 4x4
// neighborhood of the current pixel in the image's
// buffer (sadly, the position will be unaligned)
imgoffs = (((ptrdiff_t)yint - 1) * imgw) + (ptrdiff_t)xint - 1;
// calculate all 4 convolution kernel values for every row and
// every column
tap4Kernel(x, kernelX);
tap4Kernel(y, kernelY);
// load the kernel values for the columns, these don't change
v_kernX = _mm_load_ps(kernelX);
// process a row of the 4x4 neighborhood
// get set of convolution kernel values for the current row
v_kernY = _mm_set_ps1(kernelY[0]);
v_px = _mm_loadu_ps(img + imgoffs); // load the pixel values
// calculate the linear combination of the pixels with kernelX
v_px = _mm_mul_ps(v_px, v_kernX);
v_px = _mm_mul_ps(v_px, v_kernY); // and kernel Y
v_val = v_px; // add result to the final value
imgoffs += imgw;
// offset points now to next row of the 4x4 neighborhood
v_kernY = _mm_set_ps1(kernelY[1]);
v_px = _mm_loadu_ps(img + imgoffs);
v_px = _mm_mul_ps(v_px, v_kernX);
v_px = _mm_mul_ps(v_px, v_kernY);
v_val = _mm_add_ps(v_val, v_px);
imgoffs += imgw;
/*... same for kernelY[2] and kernelY[3]... */
// store resulting interpolated pixel value in the subset's
// pixel matrix
subset[idx] = horizSum(v_val);
}
}
// Calculate all 4 values of the 4-tap convolution kernel for 4 neighbors
// of a pixel and store them in an array. Ugly but fast.
// The "arg" parameter is the fractional part of a pixel's coordinate, i.e.
// a number in the range <0,1)
void Image::tap4Kernel(const float arg, float *out)
{
// chaining intrinsics was slower, so this is done in separate steps
// load the argument into 4 cells of a XMM register
__m128
v_arg = _mm_set_ps1(arg),
v_coeff = _mm_set_ps(2.0f, 1.0f, 0.0f, -1.0f);
// subtract vector of [-1, 0, 1, 2] to obtain coorinates of 4 neighbors
// for kernel calculation
v_arg = _mm_sub_ps(v_arg, v_coeff);
// clear sign bits, this is equivalent to fabs() on all 4
v_coeff = _mm_set_ps1(-0.f);
v_arg = _mm_andnot_ps(v_coeff, v_arg);
// calculate values of abs(argument)^3 and ^2
__m128
v_arg2 = _mm_mul_ps(v_arg, v_arg),
v_arg3 = _mm_mul_ps(v_arg2, v_arg),
v_val, v_temp;
// calculate the 4 kernel values as
// arg^3 * A + arg^2 * B + arg * C + D, using
// (A,B,C,D) = (-0.5, 2.5, -4, 2) for the outside pixels and
// (1.5, -2.5, 0, 1) for inside
v_coeff = _mm_set_ps(-0.5f, 1.5f, 1.5f, -0.5f);
v_val = _mm_mul_ps(v_coeff, v_arg3);
v_coeff = _mm_set_ps(2.5f, -2.5f, -2.5f, 2.5f);
v_temp = _mm_mul_ps(v_coeff, v_arg2);
v_val = _mm_add_ps(v_val, v_temp);
v_coeff = _mm_set_ps(-4.0f, 0.0f, 0.0f, -4.0f),
v_temp = _mm_mul_ps(v_coeff, v_arg);
v_val = _mm_add_ps(v_val, v_temp);
v_coeff = _mm_set_ps(2.0f, 1.0f, 1.0f, 2.0f);
v_val = _mm_add_ps(v_val, v_coeff);
_mm_store_ps(out, v_val);
}
J'ai été heureux d'avoir réussi à obtenir le temps d'exécution sur cet au-dessous de 40 us, même avant l'introduction de l'ESS à la boucle principale, que j'ai sauvé pour la dernière. Je m'attendais à au moins un facteur 3 de l'accélération, mais il ne fonctionnait qu'à peine plus rapide à 36us, plus lent que l'ancien get() qui j'ai essayé de l'améliorer. Pire encore est le fait que quand j'ai changé l'indice de référence de la boucle pour faire plus court, l'ancienne fonction a la même moyenne de l'exécution, bien que la mine tendue à plus de 127us, sens c'est encore plus long pour certains extrême chaine des valeurs de paramètre (a un sens, car plus les croisements signifie que je dois atteindre pour largement dispersé les valeurs des pixels de l'image d'origine pour calculer le résultat).
J'ai pensé que la raison doit être le cas de non-alignement des charges, mais qui ne peut pas être aidé (j'en ai besoin pour atteindre imprévisible, les valeurs de pixels). Je ne pouvais pas voir quelque chose de plus que je pouvais faire dans l'optimisation de département, donc j'ai décidé de regarder le cv::remap() pour voir comment ils le font. Imaginez ma surprise de trouver qu'il contient un gâchis de boucles imbriquées et beaucoup de branches. Ils font également un énorme argument de vérification que je n'avais pas besoin de s'embêter avec. Aussi loin que je peux dire (pas de commentaires dans le code), ESS (non alignées de charges aussi bien!) est seulement utilisé pour extraire les valeurs de la coordonnée cartes et en les arrondissant en nombres entiers, puis on appelle une fonction qui effectue la interpolation régulièrement flotteur de l'arithmétique.
Ma question est, pourquoi ai-je manqué aussi misérablement (pourquoi mon code de la lenteur et pourquoi est leur plus vite, même s'il ressemble à un gâchis) et que puis-je faire pour améliorer mon code?
Je ne suis pas de coller le OpenCV code ici parce que c'est déjà trop long, vous pouvez le vérifier sur pastebin.
J'ai testé et compilé mon code en mode Release, sous VC++2010. Le OpenCV utilisé était un binaire précompilé faisceau de v2.3.1.
EDIT: Les valeurs des pixels sont des flotteurs dans l'intervalle 0..1. Le profilage a montré la tap4Kernel() la fonction n'était pas pertinente, plus de temps est passé à l'intérieur de getConvolve().
EDIT2: j'ai collé le démontage du code généré à pastebin. C'est compilé sur un vieux Banias Celeron (a SSE2), mais ressemble plus ou moins la même.
EDIT3: Après la lecture de Ce que Chaque Programmeur Doit Savoir à Propos de la Mémoire j'ai réalisé que j'étais en supposant à tort la OpenCV fonction met en œuvre plus ou moins le même algorithme que j'ai fait, qui ne doit pas être le cas. Pour chaque pixel je interpoler, j'ai besoin de récupérer son 4x4 quartier, dont les pixels sont non-séquentielle placé à l'intérieur de l'image de la mémoire tampon. Je suis le mauvais usage des caches CPU, et OpenCV n'a probablement pas. VTune le profilage ne semblent d'accord pour dire que ma fonction a 5,800,000 les accès à la mémoire, tandis que OpenCV n'seulement 400 000. Leur fonction est un gâchis, et il pourrait probablement être encore optimisé mais il arrive encore à avoir un avantage sur moi, sans doute en raison de certains approche plus intelligente de la mémoire et de l'utilisation du cache.
Mise à JOUR: j'ai réussi à améliorer la façon dont les valeurs des pixels sont chargés dans des registres XMM. J'alloue un tampon dans l'objet qui détient 16-élément de cellules pour chaque pixel de l'image. Lors du chargement de l'image, je remplis cette cellule mémoire tampon de pré-arrangé séquences de 4x4-quartiers pour chaque pixel. Pas très efficace en terme d'espace (image prend 16x l'espace), mais de cette façon, les charges sont toujours alignés (pas plus _mm_loadu_ps()), et je suis évitant d'avoir à faire dispersés lit de pixels de l'image de la mémoire tampon, depuis la nécessaire pixels sont stockées de manière séquentielle. À ma grande surprise, il n'y a guère d'amélioration. J'ai entendu des non alignés charges pourrait être 10x plus lent, mais clairement ce n'est pas le problème ici. Mais en commentant certaines parties du code, j'ai trouvé que la modf() les appels sont responsables de 75% de l'exécution! Je vais me concentrer sur l'élimination de ceux-ci et publier une réponse.
