Comment accélérer l'exécution d'un calcul chronophage

Question

J'essaie d'écrire une fonction pour convertir une image en caractères et couleurs pour la console Windows. Pour le moment, le calcul prend environ 13 secondes avec une image de 700x700 pixels mais ce temps n'est pas souhaitable surtout quand je prévois de rendre la fonction plus complexe afin de prendre en compte les formes de caractères.

Quelles sont les méthodes pour accélérer les calculs lourds et les boucles comme ci-dessous en C++? J'ai été recommandé plusieurs threads, SIMD, et inline assembly mais comment pourrais-je améliorer une fonction comme ci-dessous avec ces méthodes?

Ceci est le code que j'utilise actuellement.

unsigned char characterValues[256] = { 0 }; 

// This operation can be done ahead of time when the program is started up 
{ 
    ResourceInputStream in = ResourceInputStream(); 
    // This image is the font for the console. The background color is black while the foreground color is white 
    in.open(BMP_FONT, 2); // 2 is for RT_BITMAP, BMP_FONT is a resource 
    if (in.isOpen()) { 
     auto bmp = readBitmap(&in, true); 
     in.close(); 
     for (int x = 0; x < bmp->size.x; x++) { 
      for (int y = 0; y < bmp->size.y; y++) { 
       int charIndex = (x/8) + (y/12) * 16; 
       if (bmp->pixels[x][y].r == 255) 
        characterValues[charIndex]++; 
      } 
     } 
    } 
} 
// This operation is for asciifying the image 
{ 
    FileInputStream in = FileInputStream(); 
    in.open(R"(image-path.bmp)"); 
    if (in.isOpen()) { 
     auto bmp = readBitmap(&in, false); 
     in.close(); 

     auto image = /* make default image here */ 
     Point2I imageSize = (Point2I)GMath::ceil((Point2F)bmp->size/Point2F(8.0f, 12.0f)); 
     int totalImageSize = imageSize.x * imageSize.y; 
     image->resize(imageSize); 
     auto palette = /* get palette of 16 colors here */ 

     // Iterate through each (character area) 
     for (int imgx = 0; imgx < imageSize.x; imgx++) { 
      for (int imgy = 0; imgy < imageSize.y; imgy++) { 

       // Read image color value 
       int r = 0, g = 0, b = 0; 
       int totalRead = 0; 
       // Read each pixel inside the bounds of a single character 
       for (int px = 0; px < 8; px++) { 
        for (int py = 0; py < 12; py++) { 
         Point2I p = Point2I(imgx * 8 + px, imgy * 12 + py); 
         if (p < bmp->size) { 
          r += bmp->pixels[p.x][p.y].r; 
          g += bmp->pixels[p.x][p.y].g; 
          b += bmp->pixels[p.x][p.y].b; 
          totalRead++; 
         } 
        } 
       } 
       Color imageValue = Color(r/totalRead, g/totalRead, b/totalRead); 

       // A combo of a character and foreground/background color 
       Pixel closestPixel = Pixel(); 
       float closestScore = std::numeric_limits<float>().max(); 
       for (int col = 1; col < 255; col++) { 
        unsigned char f = getFColor(col); 
        unsigned char b = getBColor(col); 
        for (int ch = 1; ch < 255; ch++) { 
         // Calculate values 
         Color value = Color(
          (palette[f].r * characterValues[ch] + palette[b].r * (TOTAL_CHARACTER_VALUE - characterValues[ch]))/TOTAL_CHARACTER_VALUE, 
          (palette[f].g * characterValues[ch] + palette[b].g * (TOTAL_CHARACTER_VALUE - characterValues[ch]))/TOTAL_CHARACTER_VALUE, 
          (palette[f].b * characterValues[ch] + palette[b].b * (TOTAL_CHARACTER_VALUE - characterValues[ch]))/TOTAL_CHARACTER_VALUE 
         ); 
         // Add up score here 
         float score = 
          (float)((int)value.r - (int)imageValue.r) * (float)((int)value.r - (int)imageValue.r) + 
          (float)((int)value.g - (int)imageValue.g) * (float)((int)value.g - (int)imageValue.g) + 
          (float)((int)value.b - (int)imageValue.b) * (float)((int)value.b - (int)imageValue.b); 
         if (score < closestScore) { 
          closestPixel = Pixel((unsigned char)ch, (unsigned char)col); 
          closestScore = score; 
         } 
        } 
       } 
       // Set the character/color combo here 
      } 
     } 
    } 
} 

Answer 1

Vous avez une boucle x et une boucle y imbriquée, êtes-vous sûr que c'est l'ordre des octets en mémoire? C'est peut-être mais vous pouvez toujours essayer l'inverse si cela vous aide.

// could be faster, depending on data structure 
for (int y = 0; y < bmp->size.y; y++) { 
    for (int x = 0; x < bmp->size.x; x++) { 

mais étant donné que les indices vont bmp [x] [y], il semble que ses données de colonne premier, ce qui est étrange.

Il existe également des divisions coûteuses dans votre boucle interne. Vous pouvez faire des calculs de boucle invariante extérieur de chaque boucle:

for (int x = 0; x < bmp->size.x; x++) { 
    int charIndex_x = (x/8); 
    for (int y = 0; y < bmp->size.y; y++) { 
      int charIndex = charIndex_x + (y/12) * 16; 
      // other stuff 

Il pourrait encore être améliorée, mais vous venez d'éviter de faire presque 65536 opérations de division à faire cela pour un bitmap 256x256.

En outre, il existe un déréférencement de matrice 2D dans votre boucle interne, ce sont des opérations coûteuses. Vous pouvez enregistrer un pointeur vers le début de la colonne puis incrémenter le pointeur:

for (int x = 0; x < bmp->size.x; x++) { 
    int charIndex_x = (x/8); 
    auto current_pixel = &bmp->pixels[x][0]; 
    for (int y = 0; y < bmp->size.y; y++) { 
      int charIndex = charIndex_x + (y/12) * 16; 
      if (*current_pixel.r == 255) 
       characterValues[charIndex]++; 
      ++current_pixel; 

et l'incrément dans la boucle interne. Vous pourriez en fait déplacer la configuration de current_pixel, juste en dehors de la boucle x, mais j'ai eu une situation où c'était plus lent car il doit garder plus de variables en vie dans la mémoire. Généralement, vous voulez des variables locales dans la boucle interne si possible. Les calculs de déplacement en dehors des boucles accélèrent les choses mais utilisent plus de mémoire CPU, ce qui signifie qu'il peut être plus lent en jonglant avec les valeurs stockées. La dernière chose à noter est que chaque fois que vous parcourez votre boucle interne, vous vérifiez si la valeur y est inférieure à "bmp-> size.y" cela inclut la recherche de bmp, puis la taille de référence, puis le référencement size.y , qui est trois opérations, en passant 65536 fois pour un bitmap 256x256. Vous pouvez enregistrer la taille de y dans une variable locale avant d'avoir besoin il:

for (int x = 0; x < bmp->size.x; x++) { 
    int charIndex_x = (x/8); 
    auto current_pixel = &bmp->pixels[x][0]; 
    int bmp_size_y = bmp->size.y; 
    for (int y = 0; y < bmp_size.y; y++) { 
      int charIndex = charIndex_x + (y/12) * 16; 
      if (*current_pixel.r == 255) 
       characterValues[charIndex]++; 
      ++current_pixel; 

Vous pouvez le déplacer en dehors de la boucle x tout à fait, pour éviter de définir la valeur 256 fois, comme BMP> size.y ne change jamais, mais l'économie pour cela est très faible, et cela pourrait même ralentir les choses, car cela consomme et enregistre plus, ce qui peut signifier que le programme doit jongler avec plus de choses en mémoire.

La mémoire du processeur est comme la mémoire virtuelle sur votre PC Windows. Si trop de choses sont utilisées, les choses ralentissent parce que c'est la pagination sur le disque, mais avoir plus de choses en mémoire peut aussi accélérer les choses car il n'a pas besoin de chercher constamment des choses sur le disque. Le codage est similaire en ce que les variables locales peuvent être stockées uniquement dans la CPU, évitant ainsi de les rechercher dans la mémoire, mais trop de variables locales peuvent surcharger le CPU, ce qui signifie qu'il faut les jongler comme la mémoire virtuelle. Donc, rendre les variables locales aussi "locales" que possible pour éviter de les surutiliser.Vous devriez toujours profiler les changements que vous faites pour voir s'ils ont vraiment aidé.

~~~

Quant à votre autre boucle, vous avez de nombreux calculs complexes répétés à l'intérieur de la boucle intérieure:

bmp->pixels[p.x][p.y] 

est calculé trois fois, et cela comprend un déréférencement de pointeur, deux dereferces membres (px et py) puis un déréférencement de tableau 2D (qui au mieux est une multiplication et un ajout, puis un déréférencement de pointeur). C'est au moins 6 calculs atomiques juste là, juste pour obtenir la référence à ce pixel à chaque fois.

Au lieu de cela vous pouvez aller:

auto current_pixel = bmp->pixels[p.x][p.y]; 

Mieux, vous calculez un Point2I vérifier ensuite si les valeurs x et y sont à l'intérieur de cette taille bmp. Vous n'avez pas du tout besoin du Point2I, calculez simplement les tailles x et y et comparez les à la taille bmp x et y individuellement.

Calculez les bornes x dans la boucle externe, faites le if-check pour x là, et vous éviterez de frapper la boucle interne du tout si x est hors des limites. Ajoutez à cela en évitant d'avoir à créer ou à des structures d'index dans la boucle intérieure et vous obtenez:

  for (int px = 0; px < 8; px++) { 
       int p_x = imgx * 8 + px; 
       if(p_x < bmp->size.x) { 
        for (int py = 0; py < 12; py++) { 
         int p_y = imgy * 12 + py; 
         if (p_y < bmp->size.y) { 
          auto pixel = bmp->pixels[p_x][p_y]; 
          r += pixel.r; 
          g += pixel.g; 
          b += pixel.b; 
          totalRead++; 
         } 
        } 
       } 
      } 

Answer 2

for (int x = 0; x < bmp->size.x; x++) { 
    for (int y = 0; y < bmp->size.y; y++) { 

Démarrer ces deux boucles à la valeur supérieure, à savoir bmp->size.x-1 et bmp->size.y-1 respectivement, et de les exécuter vers le bas à zéro. De cette façon, vous évaluez uniquement les conditions aux limites une fois par boucle au lieu de chaque itération.

int charIndex = (x/8) + (y/12) * 16; 

Ne pas calculer sauf si vous allez l'utiliser, à savoir le mettre dans le bloc if suivant.