Je suis intéressé à obtenir le reste de la Division Euclidean , c'est-à-dire pour un paire d'entiers (i, n), trouvez r tels que: La solution simple est la suivante: mais depuis que j'ai besoin de Exécutez ces dizaines de millions de fois (il est utilisé à l'intérieur d'un itérateur pour les tableaux multidimensionnels), je voudrais éviter la ramification si possible. Exigences: Il est en fait assez facile d'obtenir le problème en erreur, voici un exemple des résultats attendus: Certaines personnes craignent également qu'il n'a pas de sens d'optimiser cela. J'en ai besoin de cela pour un itérateur multidimensionnel où des éléments hors limites sont remplacés par des éléments dans un "réseau virtuel" qui répète le tableau d'origine. Donc, si mon tableau X est [1, 2, 3, 4], la matrice virtuelle est [...., 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 4, 1, 2, 3, 4], et par exemple, x [-2] est x 1 , etc ... pour un tableau ND de dimension D, j'ai besoin de DIVISION EULCIDEN pour chaque point. Si je dois faire une corrélation entre un réseau N ^ D avec un noyau M ^ D, j'ai besoin de divisions euclidiennes. Pour une image 3D de 100x100x100 points et un noyau de 5 * 5 * 5 points, c'est déjà environ 400 millions de divisions euclidiennes.
Modifier
12 Réponses :
Edit: Aucune multiplication ou des branches Woot.
; Original post 00401000 cdq 00401001 idiv eax,ecx 00401003 mov eax,edx 00401005 test eax,eax 00401007 jge euc+0Bh (40100Bh) 00401009 add eax,ecx 0040100B ret ; Mine 00401020 cdq 00401021 idiv eax,ecx 00401023 xor eax,eax 00401025 test edx,edx 00401027 setl al 0040102A neg eax 0040102C and eax,ecx 0040102E add eax,edx 00401030 ret
Il y a une bonne chance que le compilateur utilisera réellement une succursale pour calculer (R <0) et les multiplications sont coûteuses.
Malheureusement, cette méthode ne fonctionne pas non plus. Par exemple, l'EUC (-3, 3) renvoie 3 (si n == 3, la valeur renvoyée doit être dans [0, 2] et -3 = -1 * 3 + 0).
Oups, c'est arrivé parce que j'ai changé r sur i . Fixé.
Sur une duo Core 2, les deux sont fondamentalement les mêmes, en utilisant une boucle simple avec RDTSC pour les tests. On dirait que ça ne va pas beaucoup plus vite est assez difficile.
J'ai eu les résultats similaires ici dans le profileur d'instrumentation MSVC ++.
int euc(int i, int n)
{
return (i % n) + (((i % n) < 0) * n);
}
Si vous pouvez également garantir que je n'étais jamais moins de--n, vous pouvez simplement mettre l'ajout facultatif avant le modulo. De cette façon, vous n'avez pas besoin de la succursale et le modulo coupe ce que vous avez ajouté si vous n'aviez pas besoin de.
int euc(int i, int n)
{
return (i + n) % n;
}
C'est une solution simple et belle. Il n'est à nouveau pas vraiment plus rapide sur Core Duo, mais c'est assez rapide (~ 15% plus rapide) que les autres méthodes sur Pentium 4.
@Arke: Je crois que mon code est correct pour tout I: votre code retourne -2 pour F (-5, 3), mais le mien retourne 1, comme prévu.
Oups, tu as raison. Pourtant, vous pouvez toujours échouer n avant de l'ajouter :). Maintenant que j'y pense, je me suis écoulé au lieu de se multiplier. Devrait encore être plus rapide sur le P4.
La multiplication entière est beaucoup plus rapide que la division. Pour un grand nombre d'appels avec un n connu N, vous pouvez remplacer la division par N en multiplication par un pseudo-inverse de N.
Je l'illustrerai sur un exemple. Prendre n = 29. Puis calculez une fois qu'un pseudo inverse 2 ^ 16 / n: k = 2259 (tronqué de 2259.86 ...). Je suppose que je suis positif et je * k convient sur 32 bits. dans mon exemple, prenons i = 753, nous obtenons quo = 25 et mod = 28. (Pas de compensation requise) éditer. Dans votre exemple de convolution 3D, la plupart des appels vers i% n seront avec i de 0..n-1, donc dans la plupart des des cas, une première ligne comme contournera le coûteux et ici inutile idiv. aussi, si vous avez assez de RAM, il suffit d'aligner toutes les dimensions à Pouvoirs de 2 et utilisez des manipulations de bits (décalage et) au lieu de divisions. Editer 2. Je l'ai effectivement essayé sur 10 ^ 9 appels. I% n: 2.93s, mon code: 1.38s. Gardez simplement à l'esprit que cela implique une liaison sur i (i * k doit correspondre sur 32 bits). une autre pensée: Si vos valeurs sont X + DX, avec x en 0..n-1 et DX petit, alors ce qui suit couvrira tous les cas:
Vous avez raison que mon analyse était très grossière et, en effet, dans l'itérateur, je fais exactement ce test avant de manipuler la situation des limites. Je ne peux rien assumer de mémoire (et si la mémoire n'est pas un problème, la convolution / corrélation basée sur FFT est beaucoup plus rapide pour la plupart des cas).
J'ai chronométré les propositions de chacun dans GCC -O3 à l'aide de TSC (à l'exception de celui de la constante N), et ils ont tous pris le même temps (dans 1%).
Ma pensée était que (((((i% n) + n)% n (pas de ramification), ou (i + (n << 16))% N (échoue évidemment pour le grand n ou extrêmement négatif i) serait plus rapide , mais ils ont tous pris la même heure.
J'ajouterai que cela est toujours vrai à partir de maintenant - personne n'a une implémentation plus rapide (il existe d'énormes différences si vous compilez sans optimisation; aucun avec).
J'aime vraiment l'expression:
004135AC mov eax,dword ptr [i] 004135AF cdq 004135B0 idiv eax,dword ptr [n] 004135B3 add edx,dword ptr [n] 004135B6 mov eax,edx 004135B8 cdq 004135B9 idiv eax,dword ptr [n] 004135BC mov dword ptr [r],edx
C'est plus long que le mien, qui n'a pas non plus de sauts et peut être inlincé? C'est un autre si intelligent cependant. :)
BTW: C'est l'assemblage non optimisé. Avec optimisation, le compilateur doit éviter la charge redondante de [N], à la place d'un registre.
Cela utilise deux instructions idiv et est donc beaucoup plus coûteuse que toutes les autres suggestions!
Si vous avez une fourchette assez faible, créez une table de recherche - deux matrices DIM. De plus, vous pouvez faire la fonction en ligne et vous assurer qu'il s'agit d'examiner le code produit.
Je pense que 280z28 et Christopher ont l'assembleur golf couvre mieux que je le ferais, et qui traite d'un accès aléatoire.
Ce que vous faites réellement, cependant, semble traiter des réseaux entiers. Évidemment, pour des raisons de mise en cache de mémoire, vous voulez déjà faire cela dans l'ordre si possible, car éventuellement éviter un cache Miss, c'est une optimisation beaucoup, une meilleure meilleure optimisation que d'éviter une petite branche.
Dans ce cas, avec une vérification des limites appropriées, vous pouvez d'abord faire la boucle interne dans ce que j'appellerai "tirets". Vérifiez que les incréments de K suivants ne donnent pas de débordement dans la plus petite dimension de la matrice, puis de «Dash» K étapes à l'aide d'une nouvelle boucle encore plus interne qui incrémente simplement l'index «physique» de 1 à chaque fois. de faire une autre idiv. Vous ou le compilateur peut dérouler cette boucle, utiliser le périphérique de Duff, etc.
Si le noyau est petit, et surtout s'il est une taille fixe, cela (ou un multiple de celui-ci avec déroulement approprié pour soustraire occasionnellement de soustraire au lieu d'ajouter), est probablement la valeur à utiliser pour la longueur du "Dash" . La longueur du tableau de bord constant de la compilation est probablement la meilleure, car vous pouvez (ou le compilateur) peut dérouler complètement la boucle de pointe et éliminer la condition de continuation. Tant que cela ne rend pas le code trop gros pour être rapide, il remplace essentiellement l'ensemble de l'opération positive-modulo avec un incrément entier.
Si le noyau n'est pas une taille fixe, mais est souvent très faible dans sa dernière dimension, envisagez de disposer de différentes versions de la fonction de comparaison pour les tailles les plus courantes, avec la boucle de tableau de bord entièrement déroulée dans chaque.
Une autre possibilité est de calculer le point suivant à laquelle un débordement se produira (dans l'un ou l'autre tableau), puis sur cette valeur. Vous avez toujours une condition de continuation dans la boucle de Dash, mais cela va aussi longtemps que possible en utilisant uniquement des incréments.
Alternativement, si une opération que vous effectuez est l'égalité numérique ou une autre opération simple (je ne sais pas quelle "corrélation" est) que vous pourriez consulter les instructions de SIMD ou quoi que ce soit, auquel cas la longueur de bord devrait être une Plusieurs instructions simples à instruction (ou appropriée SIMD OP) sur votre architecture. Ce n'est pas quelque chose que j'ai de l'expérience avec, cependant.
Je ne pense pas que la version originale de la question mentionnait l'application, mais c'est la seule réponse utile jusqu'à présent. Personne n'a une implémentation plus rapide de l'EUC, mais il est certainement possible d'accélérer le calcul de niveau supérieur.
La question initiale ne fait que laisser allondi, affirmant que cela a été utilisé des millions de fois. Je ne pense pas que j'ai posté cela jusqu'à ce que après une modification indiquait que nous avions (au moins parfois) accès séquentiel. Et d'être juste, utile! = Répondre à la question: OP a demandé une implémentation sans succursale, pas une solution rapide, et dit «ramification» mais plus rapide est également souhaitable »;-) Même avec -O3 Le code de l'OP a une succursale sur GCC 3 (Tout ce que j'ai sur cette machine en ce moment).
Sans une branche, mais un peu-bit-filedling: sans multiplier: Ceci donne:
La deuxième version ne fonctionne que si des quarts de droite signés sont arithmétiques
Il assume également des entiers 32 bits. La source devrait donc être fournie avec des directives de portage (ou utiliser STDINT.H). Vous pouvez forcer un changement logique en cas de non signé, puis manipulez: ~ ((((((non signé) R) >> 31) -1). Ou quelque chose.
Vous pouvez facilement substituer le 31. E.g. (Tailleof (int) * 8 - 1) Lorsqu'il n'existe aucun changement arithmétique, vous devez l'abandonner et utiliser quelque chose de plus approprié. ~ (((((non signé) R) >> 31) -1) semble bon au premier coup d'œil.
En fait, si vous voulez être vraiment portable, rien ne garantit qu'un caractère est de 8 bits. C'est résolu avec Char_bit. Cependant, il n'ya également aucune garantie pour que tous les bits de la représentation de stockage participent à la valeur. IIRC seul caractère a cette garantie. Une implémentation conforme pourrait avoir un octet de 9 bits avec des entiers 32 bits (auquel cas Tailleof (int) * 8 fonctionne mais Tailleof (int) * Char_bit ne), ou un octet de 9 bits avec des entiers 36 bits (auquel cas Tailleof (int) * Char_bit fonctionne mais Tailleof (int) * 8 ne signifie pas. Je pense que c ++ a < Code> numeric_limits :: chiffres .
... En résumé, je pense que vous avez juste besoin du porteur de faire quelque chose de plate-forme spécifique ou de régler une version portable légèrement moins bonne si elles ne veulent ni ne pas la battre. Sur certaines plates-formes, le portier voudra quand même à l'ASM. C'est à peu près quelles fonctions en ligne statiques sont pour, après tout :-)
@ onebyone.livejournal.com: Cela fonctionnerait toujours pour 9 bits d'octets et des entiers 32 bits: pour les entiers 32 bits, vous pouvez déplacer arithmétiquement par n'importe quelle valeur> = 31 pour obtenir tous les 1 pour les valeurs négatives et 0 pour les valeurs non négatives
Non, un changement de trop de bits n'est pas défini. À partir de ce projet de standard ( vmunix.com/~gabor/c/draft.html # 101 ): "Si la valeur de l'opérande droit est négative ou est supérieure ou égale au nombre de valeurs et de signer des bits dans la représentation de l'objet de l'opérande de gauche promu, le comportement est indéfini". Remarque «Valeur et bits de signer», qui correspond à la taille de l'entier (32), pas nécessairement le nombre total de bits dans les octets utilisés pour le stockage.
Si vous vous trouvez à la place, où l'algorithme échoue, repliez à l'algorithme d'origine. Il n'est pas très difficile de vérifier. C'est plus ou moins une question sur une optimisation de bas niveau, qui introduit un compromis. BTW: L'assembleur généré à la main ne vous aidera pas vraiment ici. C'est aussi simple que possible. Seules les optimisations sur un niveau supérieur (ou des ensembles d'instructions spéciales) rendront cela plus rapide, ou je manque quelque chose?
Ce n'est pas non plus plus rapide que la version originale avec GCC -O3
Non, vous n'avez rien oublié, je spécule simplement qu'il existe une architecture avec une instruction de module positive. Je ne sais pas d'appeler cette instruction "spéciale" ou non. Le compilateur peut ne pas être en mesure de déterminer que cette superchine multiligne est mathématiquement équivalente à positive-mod, de sorte que ce n'est pas "aussi simple que possible" pour ce jeu d'instructions. Par conséquent, pour une performance optimale sur cette plate-forme, le porteur voudrait l'absorbation de l'ASM.
Vous dites dans votre réponse à Eric Bainville que la plupart du temps comme première ligne de votre Comme vous faites les comparaisons de toute façon, vous pouvez aussi bien les utiliser: p> 0 et que vous avez EUC () Code> Quoi qu'il en soit. P> int euc(int i, int n)
{
if (n <= i) return i % n;
else if (i < 0) return ((i + 1) % n) + n - 1;
else /* 0 <= i < n */ return i; // fastest possible response for common case
}
ne fonctionne pas pour i = -n car il retournera n au lieu de 0
Si vous pouvez garantir que les dimensions de votre matrice sont toujours des pouvoirs de deux, vous pouvez le faire:
template<int n>
int euc(int i) {
return (i & (n - 1));
}
int euc(int i, int n) {
switch (n) {
case 2: return euc<2>(i);
case 4: return euc<4>(i);
}
}
voici Version de Christopher avec une fuite à #include <limits.h>
static inline int euc(int i, int n)
{
// check for arithmetic shift
#if (-1 >> 1) == -1
#define OFFSET ((i % n >> (sizeof(int) * CHAR_BIT - 1)) & n)
#else
#define OFFSET ((i % n < 0) * n)
#endif
return i % n + OFFSET;
}
Comme je l'ai mentionné plus tôt, ils sont tous la même vitesse (même le code d'origine) avec g ++ -o3.
N toujours positif (> 0), comme dans vos exemples? ou pourrions-nous rencontrer des valeurs N négatives?
Pour mon usage, n est toujours positif, oui.
Des tableaux multidimensionnels avec enveloppe d'enveloppe? mmm, beignets :-)
Est le même n utilisé pour toutes les divisions?
Quel est le problème avec l'opérateur de% standard? Est-ce vraiment trop lent?
L'opérateur de% standard est indéfini pour l'ANSI C, à proprement parler et même en prenant la signification C99, elle ne fonctionne pas comme requise pour les nombres négatifs.