Comparaison entière non signée «correcte»

Question

Donc, nous savons tous que le C/C++ signé/non signé règles de comparaison où -1 > 2u == true, et j'ai une situation où je veux en œuvre correcte des comparaisons de manière efficace.

Ma question est, qui est plus efficace avec des considérations comme de nombreuses architectures de gens sont familiers avec. Évidemment, Intel et ARM ont plus de poids.

Donnée:

int x;
unsigned int y;
if (x < y) {}

Est-il préférable de promouvoir:

x < y  =>  (int64)x < (int64)y

ou est-il préférable d'effectuer 2 comparaisons, c'est à dire:

x < y  =>  (x < 0 || x < y)

L'ancien implique zéro, de proroger, de signe-les étendre, et une comparaison+branche, et ce dernier ne nécessite aucun signe d'étendre les opérations, mais 2 consécutifs cmp+branches.
La sagesse traditionnelle suggère que les branches sont plus chers que le signe s'étend, ce qui permettra à la fois de pipeline, mais il y a un décrochage entre la prolonge et la seule comparaison dans le premier cas, tandis que dans le second cas, je peux imaginer que certaines architectures pipeline pourrait le 2 comparaisons, mais ensuite suivi par 2 branches conditionnelles?

Un autre cas, où la valeur non signée est un type plus petit que le type signé, ce qui signifie qu'il peut être fait avec un seul zéro-étendre jusqu'à la signature du type de la longueur, puis une seule comparaison... dans ce cas, est-il préférable d'utiliser le prolonger+cmp version, ou est le 2-méthode de comparaison de toujours préféré?

Intel? BRAS? Les autres? Je ne sais pas si il y a un droit de réponse ici, mais je voudrais entendre les peuples prennent de l'. Faible niveau de performance est difficile de prévoir ces jours, en particulier sur les processeurs Intel et de plus en plus sur les BRAS.

Edit:

Je dois ajouter, il y a une évidence de la résolution, où les types sont de taille égale à l'architecture int largeur; dans ce cas, il est évident que le 2-comparaison de la solution est à privilégier, car la promotion elle-même ne peut pas être effectuée de manière efficace. Clairement mon int exemple remplit cette condition pour les architectures 32 bits, et vous pouvez transposer l'expérience de pensée d' short pour l'exercice appliqué à 32 bits plates-formes.

Edit 2:

Désolé, j'ai oublié l' u en -1 > 2u! >_<

Edit 3:

Je veux modifier la situation de supposer que le résultat de la comparaison d'une succursale, et le résultat n'est PAS retourné comme un booléen. C'est de cette façon je préfère la structure de regarder; bien que cela soulève un point intéressant qu'il existe un autre ensemble de permutations lorsque le résultat est un booléen vs une branche.

int g;
void fun(int x, unsigned in y) { if((long long)x < (long long)y) g = 10; }
void gun(int x, unsigned in y) { if(x < 0 || x < y) g = 10; }

Ce produit destiné à la branche généralement implicite lorsque vous rencontrez une if ;)

Answer 1

Eh bien, vous avez correctement caractérise la situation: C/C++ n'ont aucun moyen de faire signé int/unsigned int comparaison avec une seule comparer.

Je serais surpris si la promotion de int64 a été plus rapide que de faire deux comparaisons. Dans mon expérience, les compilateurs sont assez bien à se rendre compte qu'un sous-expression comme ça, c'est de la pure (sans effets secondaires) et donc qu'il n'y a pas besoin d'une seconde branche. (Vous pouvez également refuser explicitement le court-circuit à l'aide de bits or: (x < 0) | (x < y).) En revanche, mon expérience est que les compilateurs ont tendance à ne PAS faire beaucoup de cas de l'optimisation sur des entiers plus que le natif de la taille de mot, donc, (int64)x < (int64)y est tout à fait susceptible de réellement faire un full int comparaison.

Ligne de fond, il n'y a pas d'incantation, qui est garanti pour produire le meilleur code machine sur n'importe quel processeur, mais pour la plupart des compilateurs les plus courants processeurs, je dirais que les deux-comparaison de la forme serait pas plus lent que la promotion de int64 forme.

EDIT: Certains de déblayage sur Godbolt confirme que sur ARM32, GCC met beaucoup trop de machines dans l'int64 approche. VC fait de même sur x86. Avec x64, cependant, le int64 approche est en fait un enseignement plus court (car la promotion et 64-bit de comparaison sont triviaux). Le pipeline peut faire de la performance réelle d'aller de toute façon, si. https://godbolt.org/g/wyG4yC

Answer 2

Vous avez à juger au cas par cas. Il y a plusieurs raisons pour lesquelles les types signés serait utilisé dans un programme:

1. Parce que vous avez réellement besoin d'avoir des nombres négatifs dans les calculs ou de sortie.
2. "Sloppy de frappe", ce qui signifie que le programmeur juste des types d' int tous les cours de leur programme, sans donner beaucoup de pensée.
3. Accidentellement signé. La programmation n'a pas vraiment l'intention des nombres signés, mais a terminé avec eux par accident, soit par le biais implicite type de promotions ou en utilisant les constantes entières telles que 0, qui est de type int.

---

Dans le cas de 1), alors le calcul doit être effectué à la signature de l'arithmétique. Ensuite, vous devez convertir le plus possible le type qui est nécessaire pour contenir le maximum des valeurs attendues.

Supposons par exemple qu'une valeur peut avoir une autonomie de -10000 de 10000. Vous devrez alors utiliser un 16 bits type signé pour le représenter. Le bon type d'utilisation de la plate-forme de manière indépendante, est int_fast16_t.

L' int_fastn_t et uint_fastn_t types de besoin que le type est au moins aussi grand que n , mais le compilateur est autorisé à sélectionner un type plu si elle donne plus rapidement du code/le meilleur alignement.

---

2) est guéri par l'étude de la stdint.h et par cesser d'être paresseux. En tant que programmeur, on doit toujours tenir compte de la taille et de ce paramètre de chaque variable déclarée dans le programme. Cela doit être fait au moment de la déclaration. Ou si vous obtenez une sorte de révélation plus tard, revenir en arrière et changer le type.

Si vous ne considérez pas les types attentivement, vous aurez la certitude absolue de la fin jusqu'à la rédaction de nombreux, souvent bogues subtils. Cela est particulièrement important en C++, ce qui est plus pointilleux sur le type de l'exactitude de C.

Lorsque "sloppy tapant" est utilisé, le type est le plus souvent non signés plutôt que signé. Considérez ceci bâclée en tapant par exemple:

for(int i=0; i<n; i++)

Il ne fait aucun sens du tout à l'utiliser signé int ici, alors pourquoi le feriez-vous? Le plus vous êtes susceptible de parcourir un tableau ou un récipient, puis le type correct à utiliser est - size_t.

Ou sinon, si vous connaissez la taille maximale, n peut contenir, par exemple 100, alors vous pouvez utiliser le type le plus approprié pour que:

for(uint_fast8_t i=0; i<100; i++)

---

3) est également guéri par l'étude. Notamment les différentes règles implicites promotions qui existent dans ces langues, comme l'habitude de l'arithmétique des conversions et entier de la promotion.

Answer 3

Les deux branches de la version serait certainement plus lent, mais en réalité, aucun des deux... une branche, ni succursale unique... sur x86.

Par exemple x86 gcc 7.1 pour C++ source:

bool compare(int x, unsigned int y) {
    return (x < y); // "wrong" (will emit warning)
}

bool compare2(int x, unsigned int y) {
    return (x < 0 || static_cast<unsigned int>(x) < y);
}

bool compare3(int x, unsigned int y) {
    return static_cast<long long>(x) < static_cast<long long>(y);
}

Produire de la présente assemblée (godbolt démonstration en direct):

compare(int, unsigned int):
        cmp     edi, esi
        setb    al
        ret

compare2(int, unsigned int):
        mov     edx, edi
        shr     edx, 31
        cmp     edi, esi
        setb    al
        or      eax, edx
        ret

compare3(int, unsigned int):
        movsx   rdi, edi
        mov     esi, esi
        cmp     rdi, rsi
        setl    al
        ret

Et si vous essayez d'utiliser ces à l'intérieur du code plus complexe, ils se seraient intégrées dans 99% des cas. Sans profilage c'est juste deviner, mais "par un intestin" je voudrais aller avec compare3 comme "plus rapide", en particulier lors de l'exécution de l'ordre à l'intérieur du code (sorte de drôle qu'elle ne la bonne 32->64 de promotion de même pour uint argument, alors qu'il nécessite très peu d'effort pour produire du code appelant peut se comparer à une certaine confusion, dans le haut-32b de l' esi ... mais il serait sans doute de s'en débarrasser quand inline dans calcul plus complexe, où il note l'argument est également uint64 prolongée déjà, donc l' compare3 est alors encore plus simple+plus courte).

... comme je l'ai dit dans un commentaire, je ne frappe pas les tâches dont j'aurais besoin c'est, par exemple je ne peux pas imaginer de travailler sur quelque chose où la plage valide de données est inconnue, donc pour la tâche que je travail sur le C/C++ est un ajustement parfait et j'ai apprécier exactement la façon dont il fonctionne (c' < pour signé / non signé de types bien définis et les résultats dans les plus courts et les plus rapides de code, plus d'avertissement est émis pour me faire de programmeur responsable de la valider, et en cas de besoin de modification de la source de façon appropriée).

Answer 4

Compte tenu de la configuration propre à vous présenter:

int x;
unsigned int y;

et votre intention apparente d'évaluer si la valeur de x est numériquement inférieure à celle de y, en respectant le signe de l' x, je serais enclin à écrire comme

if ((x < 0) || (x < y)) {}

c'est votre deuxième alternative. Il exprime l'intention clairement, et il est extensible à plus de types, aussi longtemps que le maximum représentable valeur de y's type est au moins aussi grande que la valeur maximale représentable valeur de xs'type. Donc, si vous êtes prêt à stipuler que les arguments auront que le formulaire, puis vous pouvez même écrire que: détourner les yeux, C++ adeptes, une macro.

La conversion à la fois des arguments pour une signature, type entier 64 bits n'est pas une solution portable, car il n'y a aucune garantie que ce serait en fait une promotion soit à partir d' int ou unsigned int. Il n'est pas non plus extensible à plus de types.

Comme pour la performance relative de votre deux autres, je doute qu'il ya beaucoup de différence, mais si c'est important pour vous, alors vous voulez écrire une attention à l'indice de référence. Je pourrais imaginer le portable de remplacement nécessitant encore une instruction machine que les autres, et je peux aussi imaginer nécessitant une moins. Seulement si de telles comparaisons dominer les performances de votre application une seule instruction de faire une différence notable d'une façon ou de l'autre.

Bien sûr, ceci est spécifique à la situation que vous avez présenté. Si vous souhaitez gérer mixte signé / non signé comparaisons dans l'ordre, pour beaucoup de différents types, comme le tri au moment de la compilation, puis un modèle à base de wrapper peut vous aider avec ça (et qui serait discutable, la question de l'aide d'une macro), mais je vous demande spécifiquement sur les détails de la comparaison elle-même.

Answer 5

Un portable truc que vous pouvez faire est de vérifier si vous pouvez élargir à la fois les arguments de intmax_t de <stdint.h>, qui est la plus intégrale type de mise en œuvre prend en charge. Vous pouvez le vérifier (sizeof(intmax_t) > sizeof(x) && sizeof(intmax_t) >= sizeof(y)) et, si oui, un élargissement de conversion. Cela fonctionne dans le cas très commun où int 32 bits de large et long long int 64 bits de large.

En C++, vous pouvez faire intelligent choses où vous avez un coffre-comparaison modèle qui vérifie std::numeric_limits<T> sur ses arguments. Ici est une version. (Compilation avec -Wno-sign-compare sur gcc ou clang!)

#include <cassert>
#include <cstdint>
#include <limits>

using std::intmax_t;
using std::uintmax_t;

template<typename T, typename U>
  inline bool safe_gt( T x, U y ) {
    constexpr auto tinfo = std::numeric_limits<T>();
    constexpr auto uinfo = std::numeric_limits<U>();
    constexpr auto maxinfo = std::numeric_limits<intmax_t>();

    static_assert(tinfo.is_integer, "");
    static_assert(uinfo.is_integer, "");

    if ( tinfo.is_signed == uinfo.is_signed )
      return x > y;
    else if ( maxinfo.max() >= tinfo.max() &&
              maxinfo.max() >= uinfo.max() )
      return static_cast<intmax_t>(x) > static_cast<intmax_t>(y);
    else if (tinfo.is_signed) // x is signed, y unsigned.
      return x > 0 && x > y;
    else // y is signed, x unsigned.
      return y < 0 || x > y;      
  }

int main()
{
  assert(-2 > 1U);
  assert(!safe_gt(-2, 1U));
  assert(safe_gt(1U, -2));
  assert(safe_gt(1UL, -2L));
  assert(safe_gt(1ULL, -2LL));
  assert(safe_gt(1ULL, -2));
}

Il pourrait être mis au courant de floating-point en modifiant les deux lignes.