Quel est le moyen le plus rapide d'échanger des valeurs en C ?

Question

Je veux échanger deux entiers, et je veux savoir laquelle de ces deux implémentations sera la plus rapide : La méthode évidente avec une variable temporaire :

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Ou la version xor que je suis sûr que la plupart des gens ont vu :

void swap(int* a, int* b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

Il semble que le premier utilise un registre supplémentaire, mais le second effectue trois chargements et stockages alors que le premier n'en fait que deux de chaque. Quelqu'un peut-il me dire lequel est le plus rapide et pourquoi ? Le pourquoi étant plus important.

Answer 1

Le numéro 2 est souvent cité comme étant la façon "intelligente" de procéder. En fait, elle est très probablement plus lente car elle masque l'objectif explicite du programmeur - échanger deux variables. Cela signifie qu'un compilateur ne peut pas l'optimiser pour utiliser les opérations assembleur réelles pour échanger. Cela suppose également la capacité de faire un xor bit à bit sur les objets.

Tenez-vous-en au numéro 1, c'est l'échange le plus générique et le plus compréhensible, et il peut être facilement modélisé/généralisé.

Cette section de wikipedia explique assez bien les problèmes : http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

Answer 2

La méthode XOR échoue si a et b pointent vers la même adresse. Le premier XOR efface tous les bits à l'adresse mémoire pointée par les deux variables, de sorte qu'une fois la fonction renvoyée (*a == *b == 0), quelle que soit la valeur initiale.

Plus d'informations sur la page Wiki : Algorithme d'échange XOR

Bien qu'il soit peu probable que ce problème se pose, je préfère toujours utiliser la méthode dont le fonctionnement est garanti, plutôt que la méthode intelligente qui échoue à des moments inattendus.

Answer 3

Sur un processeur moderne, vous pourriez utiliser la méthode suivante pour trier de grands tableaux et ne voir aucune différence de vitesse :

void swap (int *a, int *b)
{
  for (int i = 1 ; i ; i <<= 1)
  {
    if ((*a & i) != (*b & i))
    {
      *a ^= i;
      *b ^= i;
    }
  }
}

La partie vraiment importante de votre question est le "pourquoi". Si l'on revient 20 ans en arrière, à l'époque du 8086, ce qui précède aurait été un véritable tueur de performances, mais sur le dernier Pentium, il serait aussi rapide que les deux que vous avez affichés.

La raison est purement liée à la mémoire et n'a rien à voir avec le CPU.

La vitesse des processeurs par rapport à celle de la mémoire a augmenté de façon astronomique. L'accès à la mémoire est devenu le principal goulot d'étranglement des performances des applications. Tous les algorithmes de swap passent la plupart de leur temps à attendre que les données soient extraites de la mémoire. Les systèmes d'exploitation modernes peuvent avoir jusqu'à 5 niveaux de mémoire :

• Cache de niveau 1 - fonctionne à la même vitesse que l'UC, a un temps d'accès négligeable, mais est de petite taille.
• Cache de niveau 2 - fonctionne un peu plus lentement que L1 mais est plus grand et a une plus grande surcharge pour l'accès (généralement, les données doivent être déplacées vers L1 d'abord).
• Cache de niveau 3 - (pas toujours présent) Souvent externe au CPU, plus lent et plus grand que le L2.
• RAM - la mémoire principale du système, qui met généralement en œuvre un pipeline de sorte qu'il y a une latence dans les demandes de lecture (le CPU demande des données, le message est envoyé à la RAM, la RAM reçoit les données, la RAM envoie les données au CPU).
• Disque dur - lorsqu'il n'y a pas assez de RAM, les données sont transférées sur le disque dur, ce qui est très lent et n'est pas vraiment contrôlé par le CPU.

Les algorithmes de tri détériorent l'accès à la mémoire, car ils accèdent généralement à la mémoire de manière très désordonnée, ce qui entraîne des frais généraux inefficaces liés à l'extraction de données de L2, de la RAM ou du disque dur.

Ainsi, l'optimisation de la méthode d'échange est vraiment inutile - si elle n'est appelée que quelques fois, toute inefficacité est cachée en raison du petit nombre d'appels, si elle est appelée souvent, toute inefficacité est cachée en raison du nombre d'absences de cache (où le CPU doit obtenir des données de L2 (quelques cycles), L3 (quelques dizaines de cycles), RAM (quelques centaines de cycles), HD ( !)).

Ce que vous devez vraiment faire, c'est examiner l'algorithme qui appelle la méthode swap. Ce n'est pas un exercice trivial. Bien que la notation Big-O soit utile, un O(n) peut être significativement plus rapide qu'un O(log n) pour un petit n. (Je suis sûr qu'il y a un article de CodingHorror à ce sujet.) De plus, de nombreux algorithmes ont des cas dégénérés où le code en fait plus que nécessaire (utiliser qsort sur des données presque ordonnées pourrait être plus lent qu'un tri à bulles avec un contrôle de sortie précoce). Vous devez donc analyser votre algorithme et les données qu'il utilise.

Ce qui nous amène à la façon d'analyser le code. Les profileurs sont utiles mais vous devez savoir comment interpréter les résultats. N'utilisez jamais une seule exécution pour rassembler les résultats, faites toujours la moyenne des résultats sur plusieurs exécutions - car votre application de test pourrait avoir été paginée sur le disque dur par le système d'exploitation à mi-chemin. Établissez toujours le profil des versions optimisées, le profilage du code de débogage est inutile.

Quant à la question initiale - lequel est le plus rapide ? - c'est comme essayer de déterminer si une Ferrari est plus rapide qu'une Lambourgini en regardant la taille et la forme du miroir d'aile.

Answer 4

La première est plus rapide parce que les opérations par bit telles que xor sont généralement très difficiles à visualiser pour le lecteur.

Plus rapide à comprendre bien sûr, ce qui est la partie la plus importante ;)

Answer 5

Je serais fasciné de voir la sortie du profileur qui montre que cette opération est le goulot d'étranglement dans votre code.