Comment laisser le compilateur faire un mouvement de code invariant en boucle avec std :: map?

Question

est ici une partie de mon code: (notez que M est un grand nombre)

void myFunc(std::map<int, int>& myMap, int** arr) { 

    for (int i = 0; i < N; i++) { 
     for (int j = 0; j < M; j++) { 
      arr[i][j] = myMap[i] * j + i; 
     } 
    } 

} 

myMap[i] est un invariant de boucle dans la boucle interne. Donc je pense que gcc le sortira automatiquement de la boucle interne quand j'utiliserai -O1. Mais ça ne marche pas. Depuis quand je me déplace manuellement comme suit:

void myFunc(std::map<int, int>& myMap, int** arr) { 

    for (int i = 0; i < N; i++) { 
     int tmp = myMap[i]; 
     for (int j = 0; j < M; j++) { 
      arr[i][j] = tmp * j + i; 
     } 
    } 

} 

L'exécution est bien meilleure que la première version.

Peut-être que le compilateur pense myMap modifierait la carte de sorte qu'il choisit de ne pas faire l'optimisation. Mais je suis sûr que je veux juste lire la valeur de myMap et ne le modifiera pas. Comment puis-je faire comprendre au compilateur?

Answer 1

Vous avez raison car la carte operator[] renvoie toujours une référence modifiable à la valeur, donc le compilateur ne peut pas supposer qu'il est sûr de le déplacer en dehors de cette boucle interne. C'est parce que l'opérateur insérera la valeur si elle n'est pas là. Ce qui est probablement pas ce que vous voulez.

Il est assez facile de corriger en itérant plutôt sur la carte en utilisant seulement les méthodes const. Vous pouvez passer la carte à myFunc en tant que const&, puis utiliser les fonctions membres cbegin() et cend() pour obtenir des références aux valeurs qui y sont stockées.

.: par exemple

void myFunc(const std::map<int, int>& m, int** arr) { 
    int i = 0; 
    auto it = m.cbegin(); 
    while (it != m.cend()) { // assumes m.size() == N 
     for (int j = 0; j < M; j++) { 
      arr[i][j] = (*it).second * j + i; 
     } 
     it++; 
     i++; 
    } 
} 

est ici quelques points de référence rapide sur ma machine, pour N=10 et M=1000000. (J'ai couru chacun quelques fois, ce sont quelque part au milieu.)

Votre version originale:

real 0m0.449s 
user 0m0.434s 
sys 0m0.012s 

Votre deuxième version:

real 0m0.162s 
user 0m0.148s 
sys 0m0.012s 

Ma solution:

real 0m0.176s 
user 0m0.162s 
sys 0m0.012s 

Votre deuxième solution semble en fait constamment plus rapide d'environ 10%, donc si vous vous souciez de chaque dernière vitesse, ju st héiste cette cession vous-même.