Présentation du problème

L'article décrit une optimisation d'un algorithme de compression de données. L'algorithme utilise une matrice de références pour déterminer l'ordre optimal de codage pour chaque symbole. La partie la plus critique de l'algorithme est la recherche du chemin le plus court dans une grille, ce qui équivaut à trouver la meilleure cellule suivante pour chaque cellule.

Fonctionnement de l'algorithme

L'algorithme utilise des instructions SIMD pour calculer les coûts et les chemins les plus courts. Le code utilise des registres __m128i pour stocker les coûts et les chemins, et des instructions telles que _mm_add_epi16 et _mm_min_epu16 pour calculer les coûts et les chemins les plus courts.

__m128i best_path_length = _mm_setzero_epi16();
for (int i = n_symbols - 1; i >= 0; i--) {
    __m128i tmp = _mm_add_epi16(cost[i], best_path_length);
    __m128i minpos = _mm_minpos_epu16(tmp);
    __m128i cost_without_switching = _mm_sub_epi16(tmp, _mm_broadcastw_epi16(minpos));
    __m128i cost_with_switching = _mm_set1_epi16(switch_cost);
    best_path_length = _mm_min_epu16(cost_without_switching, cost_with_switching);
    __m128i choice = _mm_blendv_epi8(
        _mm_set1_epi16(_mm_extract_epi16(minpos, 1)),
        _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0),
        _mm_cmpeq_epi16(best_path_length, cost_without_switching)
    );
    _mm_storeu_si64(&next_j[i], _mm_packs_epi16(choice, choice));
}

Optimisation de la boucle

La boucle la plus critique de l'algorithme est la recherche de l'encodage optimal pour chaque symbole. La boucle originale est la suivante :

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

Cependant, cette boucle peut être améliorée en ajoutant un if pour simuler la prédiction de branchement. L'idée est de faire en sorte que le processeur prévoie que j reste inchangé, ce qui permettrait à la boucle de devenir limitée par le débit plutôt que par la latence.

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}

Résultats et analyse

Les résultats montrent que cette optimisation peut améliorer les performances de la boucle de manière significative. Cependant, il est important de noter que cette optimisation est spécifique à cet algorithme et peut ne pas être applicable à d'autres cas. De plus, l'utilisation de volatile pour contourner les optimisations du compilateur peut ne pas être la solution la plus élégante.