Type d’entier le plus rapide pour les architectures communes

L’entête stdint.h ne int_fastest_t pas int_fastest_t et uint_fastest_t pour correspondre aux types {,u}int_fastX_t . Dans les cas où la largeur du type entier n’a pas d’importance, comment choisir le type entier permettant de traiter la plus grande quantité de bits avec le moins de perte de performances? Par exemple, si on cherchait le premier bit défini dans une mémoire tampon en utilisant une approche naïve, une boucle comme celle-ci pourrait être considérée:

 // return the bit offset of the first 1 bit size_t find_first_bit_set(void const *const buf) { uint_fastest_t const *p = buf; // use the fastest type for comparison to zero for (; *p == 0; ++p); // inc p while no bits are set // return offset of first bit set return (p - buf) * sizeof(*p) * CHAR_BIT + ffsX(*p) - 1; } 

Naturellement, utiliser char donnerait plus d’opérations que int . Mais une long long peut entraîner des opérations plus coûteuses que les frais généraux int utilisation de l’ int sur un système 32 bits, etc.

Mon hypothèse actuelle est pour les architectures classiques, l’utilisation de long est le pari le plus sûr: c’est 32 bits sur les systèmes 32 bits et 64 bits sur les systèmes 64 bits.

    int_fast8_t est toujours le type entier le plus rapide dans une implémentation correcte. Il ne peut jamais y avoir de types entiers inférieurs à 8 bits (car CHAR_BIT>=8 est requirejs), et puisque int_fast8_t est le type entier le plus rapide avec au moins 8 bits, il s’agit donc du type entier le plus rapide, point.

    Théoriquement, int est le meilleur choix. Il doit correspondre à la taille du registre natif de la CPU, et donc être “optimal” dans le sens que vous demandez.

    Cependant, vous pouvez toujours constater qu’un int-64 ou int-128 est plus rapide sur certains processeurs qu’un int-32, car même s’ils sont plus grands que la taille du registre, ils réduiront le nombre d’itérations de votre boucle et travaillez plus efficacement en minimisant les frais généraux de la boucle et / ou en tirant parti du DMA pour charger / stocker les données plus rapidement.

    (Par exemple, sur les processeurs ARM-2, il fallait 4 cycles de mémoire pour charger un registre 32 bits, mais seulement 5 cycles pour en charger deux de manière séquentielle et 7 cycles pour en charger quatre de manière séquentielle. La routine que vous proposez ci-dessus serait optimisée pour être utilisée en tant que autant de registres que vous pourriez libérer (de 8 à 10 en général), et donc pouvant s’exécuter jusqu’à 3 ou 4 fois plus rapidement en utilisant plusieurs registres par itération de boucle)

    Le seul moyen de vous en assurer est d’écrire plusieurs routines, puis de les profiler sur la machine cible spécifique afin de déterminer celle qui produit les meilleures performances.

    Je ne suis pas sûr de bien comprendre la question, mais pourquoi n’utilisez-vous pas simplement int ? Citant mon standard (version brouillon libre du mauvais, c’est-à-dire C ++), “Plain ints a la taille naturelle suggérée par l’architecture de l’environnement d’exécution”.

    Mais je pense que si vous voulez avoir le type entier optimal pour une opération donnée, ce sera différent en fonction de l’opération. Essayer de trouver le premier bit dans un grand tampon de données, ou trouver un nombre dans une séquence d’entiers, ou les déplacer, pourrait très bien avoir des types optimaux complètement différents.

    MODIFIER:

    Pour ce que ça vaut, j’ai fait un petit repère. Sur mon système particulier (Intel i7 920 avec Linux, gcc -O3), il s’avère que les longs ints (64 bits) sont un peu plus rapides que les simples ints (32 bits), dans cet exemple particulier. J’aurais deviné le contraire.

    Si vous voulez être sûr d’avoir l’implémentation la plus rapide, pourquoi ne pas comparer chaque système aux systèmes sur lesquels vous prévoyez de tourner plutôt que d’essayer de le deviner?

    La réponse est int elle-même. Au moins en C ++, où 3.9.1 / 2 de la norme dit:

    Plain int s ont la taille naturelle suggérée par l’architecture de l’environnement d’exécution

    Je suppose que la même chose est vraie pour C, bien que je n’ai aucun des documents de normes.

    Je suppose que les types size_t (pour un type non signé) et ptrdiff_t (pour un type signé) correspondront généralement à des types entiers assez efficaces sur une plate-forme donnée.

    Mais rien ne peut prouver cela en inspectant l’assembleur produit et en effectuant des comparaisons.

    Modifier , y compris les différents commentaires, ici et dans d’autres réponses:

    size_t et ptrdiff_t sont les seuls typedefs normatifs en C99 et pour lesquels on peut raisonnablement supposer qu’ils sont liés à l’architecture.

    Il existe 5 classements possibles pour les types entiers standard ( char , short , int , long , long long ). Toutes les forces vont vers les types de largeur 8, 16, 32, 64 et dans un avenir proche 128. En conséquence, int sera bloqué sur 32 bits. Sa définition n’aura rien à voir avec l’efficacité de la plate-forme, mais sera simplement limitée par cette exigence de largeur.

    Il n’est pas possible de répondre à cette question car celle-ci est incomplète. Par analogie, considérons la question:

    Quel est le véhicule le plus rapide

    Une Bugatti Veyron ? Certainement rapide, mais inutile pour aller de Londres à New York.

    Ce qui manque à la question, c’est le contexte dans lequel l’entier sera utilisé. Dans l’exemple original ci-dessus, je doute que vous constatiez une grande différence entre les valeurs de 8, 32 ou 64 bits si le tableau est grand et clairsemé atteindre les limites de bande passante mémoire avant les limites du processeur.

    Le point principal est que l’architecture ne définit pas la taille des différents types d’entiers, c’est le concepteur du compilateur qui le fait. Le concepteur examinera avec soin les avantages et les inconvénients de différentes tailles pour chaque type d’architecture et choisira la plus appropriée.

    Je suppose que l’int 32 bits sur le système 64 bits a été choisi parce que, pour la plupart des opérations, les ints utilisés sont suffisants. Etant donné que la bande passante mémoire est un facteur limitant, économiser sur l’utilisation de la mémoire était probablement le facteur déterminant.

    Pour toutes les architectures grand public existantes, long est le type le plus rapide actuellement pour le débit de boucle.

    Si vous comstackz avec gcc, je vous conseillerais d’utiliser __builtin_ffs () pour trouver le premier jeu de bits:

    Fonction intégrée: int __builtin_ffs (unsigned int x) Retourne un plus l’index du bit le moins significatif de x, ou si x vaut zéro, renvoie zéro.

    Cela sera compilé dans (souvent une seule) instruction d’assemblage native.