Moyen le plus rapide en C pour déterminer si un entier est entre deux entiers (inclus) avec des ensembles connus de valeurs

Question

Est-il un moyen plus rapide que x >= start && x <= end C pour tester si un entier est entre deux nombres entiers?

Mise à JOUR: Mon spécifiques de la plateforme iOS. Cette est une partie d'une zone de flou de fonction qui limite les pixels d'un cercle dans un carré donné.

Mise à JOUR: Après avoir accepté de répondre, j'ai reçu un ordre de grandeur de l'accélération sur une ligne de code en plus de faire de la normale x >= start && x <= end .

Mise à JOUR: Voici le avant et après le code avec l'assembleur à partir de XCode:

NOUVELLE FAÇON

// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)

Ltmp1313:
 ldr    r0, [sp, #176] @ 4-byte Reload
 ldr    r1, [sp, #164] @ 4-byte Reload
 ldr    r0, [r0]
 ldr    r1, [r1]
 sub.w  r0, r9, r0
 cmp    r0, r1
 blo    LBB44_30

ANCIENNE

#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end && p++ >= range.start)

Ltmp1301:
 ldr    r1, [sp, #172] @ 4-byte Reload
 ldr    r1, [r1]
 cmp    r0, r1
 bls    LBB44_32
 mov    r6, r0
 b      LBB44_33
LBB44_32:
 ldr    r1, [sp, #188] @ 4-byte Reload
 adds   r6, r0, #1
Ltmp1302:
 ldr    r1, [r1]
 cmp    r0, r1
 bhs    LBB44_36

Assez incroyable de voir comment la réduction ou l'élimination de ramification peut fournir une telle vitesse.

Answer 1

Il y a un vieux truc à faire avec seulement une comparaison ou d'une direction. Si ça va vraiment améliorer la vitesse peuvent être ouverts à la question, et même si elle le fait, c'est probablement trop peu d'avis ou de soins à propos, mais quand vous êtes seulement à partir de deux comparaisons, les chances d'un énorme amélioration sont assez éloignées. Le code ressemble à ceci:

// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
//  upper-lower, simply add + 1 to upper-lower and use the < operator.
    if ((unsigned)(number-lower) <= (upper-lower))
        in_range(number);

Typiquement, ordinateur moderne (c'est à dire, quelque chose à l'aide de complément à deux), la conversion en unsigned est vraiment un nop, juste un changement dans la façon dont les mêmes bits sont considérées.

Notez que dans un cas typique, vous pouvez pré-calculer, upper-lower à l'extérieur d'un (présumé) de la boucle, donc ça ne marche pas normalement une contribution significative le temps. En plus de réduire le nombre d'instructions de branchement, cela aussi (en général), améliore la direction de la prévision. Dans ce cas, la même branche est prise si le nombre est au-dessous de l'extrémité inférieure ou au-dessus de l'extrémité supérieure de la gamme.

Comment cela fonctionne, l'idée de base est assez simple: un nombre négatif, lorsqu'on la considère comme un nombre non signé, sera plus grande que tout ce qui a commencé comme un nombre positif.

Answer 2

Il est rare pour être en mesure de faire d'importantes optimisations de code sur une petite échelle. De grands gains de performance à venir de l'observation et modifiant le code à partir d'un niveau plus élevé. Vous pouvez être en mesure d'éliminer la nécessité pour l'essai de portée tout à fait, ou seulement O(n) au lieu de O(n^2). Vous pouvez être en mesure de ré-ordonner les tests de sorte que d'un côté de l'inégalité est toujours implicite. Même si l'algorithme est idéal, les gains sont plus susceptibles de venir quand vous voyez comment ce code ne la gamme d'essai de 10 millions de fois, et vous trouver un moyen de lot et de l'utilisation de l'ESS à faire de nombreux tests en parallèle.

Answer 3

Cela dépend de combien de temps vous voulez effectuer le test sur les mêmes données.

Si vous effectuez le test qu'une seule fois, il n'y a probablement pas de façon significative à la vitesse de l'algorithme.

Si vous faites cela pour un très ensemble fini de valeurs, vous pouvez créer une table de recherche. Effectuer l'indexation peut être plus cher, mais si vous pouvez l'adapter à toute la table dans le cache, alors vous pouvez supprimer tous les ramification à partir du code, ce qui devrait accélérer les choses.

Pour vos données de la table de recherche serait de 128^3 = 2 097 152 sommets. Si vous pouvez contrôler l'un des trois variables, de manière à envisager tous les cas où l' start = N , à un moment, alors que la taille de l'ensemble de travail descend 128^2 = 16432 octets, ce qui devrait convenir à la plupart des modernes caches.

Vous auriez encore à l'indice de référence le code pour voir si un dépourvu de branches table de recherche est suffisamment rapide que l'évidence des comparaisons.

Answer 4

N’est-il pas possible d’effectuer seulement une opération de bits sur les entiers ?

Puisqu’elle doit être comprise entre 0 et 128, si le 8e bit est défini (2 ^ 7) c’est 128 ou plus. Le cas de bord sera une douleur, cependant, puisque vous voulez une comparaison inclusivement.