est-il possible de comparer des régions de mémoire entières dans un cycle de processeur unique? Plus précisément est-il possible de comparer deux chaînes dans un cycle de processeur en utilisant une sorte d'instruction d'assembleur MMX? Ou est EDIT:
Ou est-il possible d'instruire C ++ compilateur de supprimer des doublons à cordes, de sorte que les chaînes puissent être comparées simplement par leur emplacement de mémoire? Au lieu de STRCMP -implementation déjà basé sur cette optimisation?
memcmp (a, b) comparé par a == b (en supposant que a et b sont les deux natif const char * cordes).
11 Réponses :
Cela dépend de la quantité de prétraitement. C # et Java ont tous deux un processus appelé Strings interne qui rend chaque carte de chaîne à la même adresse si elles ont le même contenu. En supposant un processus comme ça, vous pouvez faire une comparaison d'égalité à chaîne avec une instruction de comparaison.
La commande est un peu plus difficile.
EDIT: Évidemment, cette réponse est de contourner la question réelle de tenter de faire une comparaison de chaînes dans un seul cycle. Mais c'est le seul moyen de le faire à moins que vous n'ayez pas eu une séquence d'instructions pouvant examiner une quantité de mémoire sans bornes en temps constant pour déterminer l'équivalent d'une STRMP. Ce qui est improbable, parce que si vous avez eu une telle architecture, la personne qui vous a vendu à vous dire "hé, voici cette instruction géniale qui peut faire une chaîne comparer en un seul cycle! Quelle est la génie?" Et vous n'avez pas besoin de poster une question sur Stackoverflow.
Mais c'est juste mon avis raisonné.
Même si les deux cordes étaient en cache, il ne serait pas possible de comparer des chaînes (arbitrairement longues) dans un seul cycle de processeur. La mise en œuvre de la STRMP dans un environnement de compilateur moderne devrait être à peu optimisée. Vous ne devez donc pas la peine d'optimiser trop.
Edit (en réponse à votre édition):
Vous ne pouvez pas instruire le compilateur d'unifier toutes les chaînes en double - la plupart des compilateurs peuvent faire quelque chose comme ça, mais ce n'est que le meilleur effort (et je ne connais aucun compilateur où il fonctionne dans des unités de compilation).
Vous pouvez obtenir de meilleures performances en ajoutant les chaînes à une carte et en comparant les itérateurs après cela ... La comparaison elle-même pourrait être un cycle (ou pas beaucoup plus) alors
Si l'ensemble des chaînes à utiliser est corrigé, utilisez des énumérations - c'est ce qu'ils sont là pour.
OK, mais pensez-vous que la fonction suivante: __inline BOOL test (string a) {renvoie a == "x";} Test ("x"); va compiler dans "vrai"? Même si j'utilise une classe de cordes au lieu de Const Char *? Je devrais probablement le tester moi-même ...
Je ne pense pas, même le compilateur le plus optimisant l'optimisation ne ressemblerait pas cela loin dans la mise en œuvre de la classe de cordes. Et avec const char * == n'est pas garanti de donner le résultat correct dans ce cas ...
en supposant que vous voulez dire Mais sur le dessus de ma tête, non, je ne pense pas que vous puissiez comparer plus que la taille d'un registre à la fois.
Par curiosité, pourquoi demandez-vous? Je suis le dernier à invoquer Knuth prématurément, mais ... EDIT : LIEN Points maintenant sur la documentation moderne . x86 ... ici est la documentation Intel.
STRCMP fait généralement un bon travail.
Je suis trop paresseux pour créer des énumérations et je veux utiliser des chaînes dans des fonctions de bas niveau qui devraient être assez rapides. Ça me fait mal de voir le code comme: Si (Entrée == "SaStringing1") ... Si (INPUT == "SOMESPRING2") ... IF (INPUT == "SAOMESPRING3") ... qui est exécuté chaque cadre: )
Si vous êtes vraiment plié à l'aide du code de montage, consultez l'instruction CMPS dans le manuel. Mais je vous encourage à explorer les méthodes de cartographie et de hachage recommandées dans certaines des autres réponses d'abord.
ou est-il possible d'instruire c ++ compilateur pour éliminer les doublons à cordes, afin que les chaînes puissent être comparées simplement par leur mémoire de mémoire?
non. Le compilateur peut supprimer des duplicats en interne, mais je ne connais aucun compilateur qui garantit ou fournit des installations pour accéder à une telle optimisation (sauf éventuellement éventuellement éteindre). Certes, la norme C ++ n'a rien à dire dans cette zone.
Il n'est pas possible d'effectuer des opérations à chaîne à usage général dans un cycle, mais il existe de nombreuses optimisations que vous pouvez appliquer avec des informations supplémentaires.
memcmp , ce qui est plus rapide que strcmp . Si votre demande est multiculturelle, gardez à l'esprit que cela ne fonctionne que pour ordinal Comparaison des chaînes .
- Il apparaît que vous utilisez c ++. Si vous n'avez besoin que de comparaisons d'égalité avec des chaînes immuables, vous pouvez utiliser une solution de sort de chaîne (lien de copie / colle puisqu'un nouvel utilisateur) afin de garantir que les chaînes égales sont stockées à la même position mémoire, à laquelle vous pouvez simplement comparer pointeurs. Voir en.wikipedia.org/wiki/string_interning
- En outre, consultez le manuel de référence d'optimisation Intel, chapitre 10 pour plus de détails sur les instructions du traitement de texte SSE 4.2. www.intel.com/products/processor/manuals/
Edit: Si votre domaine de problème permet d'utiliser une énumération, que est votre solution de comparaison à cycle unique. Ne le combattez pas.
Si vous optimisez des comparaisons de chaîne, vous souhaiterez peut-être utiliser une table à chaîne (vous devez donc comparer uniquement les index des deux chaînes, qui peuvent être effectuées dans une seule instruction de la machine).
Si cela n'est pas réalisable, vous pouvez également créer un objet de chaîne haché contenant la chaîne et un hachage. Ensuite, la plupart du temps que vous devez comparer les hachages si les cordes ne sont pas égales. Si les hachages correspondent, vous devez faire une comparaison complète cependant pour vous assurer que ce n'était pas un faux positif.
Vous pouvez certainement comparer plus d'un octet dans un cycle. Si nous prenons l'exemple de X86-64, vous pouvez comparer jusqu'à 64 bits (8 octets) dans une seule instruction ( Cependant, cela ne signifie pas que vous pourrez tout le travail de comparer deux tableaux en mémoire beaucoup plus rapidement que Sauf si vous voyez beaucoup de temps passé dans CMPS ), ce n'est pas nécessairement un cycle mais sera normalement dans le bas des chiffres simples (la vitesse exacte dépend de la version de processeur spécifique).
STRCMP : -
STRCMP seront déjà hautement optimisés, y compris la vérification si A et B pointe sur la même adresse et toutes les optimisations de niveau d'instructions appropriées.
STRCMP , je ne m'inquiéterais pas à ce sujet - Avez-vous un problème de problème / utilisation spécifique que vous essayez d'améliorer?
Ensuite, il serait logique d'utiliser Pragma Pack 8 et de comparer des cordes 8-octets à la fois, car elle sautera rapidement des cordes qui ne sont pas égales. Au moins dans mon cas, il est assez rare pour les chaînes d'avoir les mêmes caractères au début.
@Aarep: Eh bien, vous devriez vous assurer qu'il y a 8 octets de données disponibles pour être chargés - la chaîne est une longueur arbitraire inconnue et donc vous venez de charger 8 octets que vous pourriez finir par lire la fin de la fin de la chaîne et segfaulting.
pas vraiment . Votre instruction de comparaison typique de 1 octet prend 1 cycle.
Votre meilleur choix serait d'utiliser les instructions de comparaison MMX 64 bits (voir Cette page pour un exemple) . Cependant, ceux-ci fonctionnent sur des registres, qui doivent être chargés de la mémoire. Les charges de la mémoire endommageront de manière significative votre temps, car vous allez au mieux au cache L1, ce qui ajoute du ralentissement de 10x fois *. Si vous faites un traitement de cordes lourde, vous pouvez probablement obtenir un peu de change, mais encore une fois, cela va faire mal.
D'autres personnes suggèrent des chaînes précontrôlantes. Peut-être que cela fonctionnera pour votre application particulière, peut-être que ce ne sera pas. avez-vous pour comparer les chaînes? Pouvez-vous comparer les numéros?
Votre édition suggère de comparer des pointeurs. C'est une situation dangereuse que si vous ne pouvez vous garantir spécifiquement que vous ne ferez pas de sous-chaînes compare (c.-à-d. Vous comparez quelques chaînes d'octets: [0x40, 0x50] avec [0x40, 0x42]. Ce ne sont pas "égaux", mais un le pointeur comparer dirait qu'ils sont).
Avez-vous regardé la source GCC STRCMP ()? Je suggérerais que ce faisant ce serait la place de départ idéale.
* LOOSELY parlant, si un cycle prend 1 unité, un hit L1 prend 10 unités, un hit L2 prend 100 unités et un coup réel de RAM prend vraiment long . . .
Oui, dans mon cas, remplacer les chaînes avec des énumérations résoudrait le problème. Mais alors je devrais modifier mes chaînes en ajoutant des préfixes (ou des postfixes) car ces noms de chaîne sont déjà réservés par un autre code.
@aarep: Vous ne pouvez pas mettre les énums dans leur propre espace de classe / noms? Les identifiants utilisés par un autre code?
Oui, devra probablement utiliser des espaces de noms. Il suffit d'essayer de garder la syntaxe de code aussi simple que possible.
@Paul: La mise en œuvre de Glibc STRCMP () est la naïve: lire des octets successifs jusqu'à ce qu'ils diffèrent. Compilé avec GCC-4 -O2, il utilise les instructions PCMPEQB et PMOVMSKB. Je ne vois pas comment cela pourrait être plus efficace.
@grey: Je soupçonnerais que plus d'efficacité proviendrait de la filetage, où un thread "court devant" et précompute le résultat. Ce qui commence à se déplacer vers une sorte d'approche "Tomasulo" ... Vous n'êtes pas sûr que ce problème particulier a besoin de ce type d'assaut lourd.
Voir ma remarque ci-dessus, un 16 octet Readahead n'est pas possible car la mémoire après # 0 pourrait ne pas être accessible. Vous auriez besoin de la longueur d'abord, mais des chaînes C ne fonctionnent pas de cette façon (ou nécessitent une passe supplémentaire). Il se pourrait que ce soit une tentative de réduction du nombre de comparaison de 2 (un pour \ 0 une pour l'égalité) à 1 1/16 (un pour \ 0 et 16 à la fois) ou. Mais je doute qu'il livre beaucoup.
Selon ma réponse, la mémoire après \ 0 ne peut avoir une protection différente que si elle se trouve dans une page différente et que les points de lecture sont toujours alignés sur 16 octets, ils ne liront jamais après la fin de la page que \ 0 Vit à.
Vous pouvez utiliser le Boost Flyweight bibliothèque pour stagiaire vos chaînes immuables. Les tests d'égalité de chaîne / d'inégalité deviennent ensuite très vite car tout ce qu'il faut faire à ce stade est comparer des pointeurs (Pun non destinés).
Il suffit d'utiliser le standard C Les implémentations d'entre eux sont raisonnablement bonnes et sont probablement compilées à un assemblage très optimisé que même les programmeurs d'assemblage talentueux trouveraient des problèmes difficiles à correspondre.
Alors ne transpirez pas les petites choses. Je suggère de regarder optimiser d'autres parties de votre code. STRCMP () ou C ++ std :: string :: opérateur == () pour vos comparaisons de chaîne.
Génial! J'ai toujours pensé à la chaîne Comparer à l'aide de SSE, mais je ne le vois jamais réellement implémenté!
Iwonder comment cela fonctionne en toute sécurité? Il peut lire 15 octets au-delà \ 0, ce qui pourrait ne pas être mappé?
Le shl% cl,% ESI ... et% ESI,% edx ajuste le masque de bit de résultat en fonction des octets précédant le \ 0 , qui est découvert par PCMPEQB (% RDI),% xmm2 . ... Je pense.
Marco: L'alignement de 16 octets est la clé, car les lectures sont toujours alignées sur 16 frontières d'octets, elles ne peuvent donc jamais franchir une limite de page.
+1 pour Utilisez simplement des implémentations standard et ne transpirez pas la petite chose
Ce n'est pas la magie de l'optimisation de GCC, mais les arts illusionnaires de Greyfade nous montrent le C pour une fonction et l'ASM pour une fonction complètement différente (qui a probablement été écrite en ASM pour commencer).
@R ..: assez contraire. J'ai tiré le démontage avec l'outil Objdump du fichier d'objet sur l'un de mes compilations plus récentes de GLIBC. J'ai même deux fois vérifié les options du GCC en le recompillant à la main.
Eh bien, pourquoi la fonction de l'ASM nommé SHLEN ?
@R ..: Je n'ai jamais remarqué. Je vais vérifier à nouveau et éditer avec un échantillon corrigé, si nécessaire.
Et maintenant, il n'y a pas de SSE dans l'ASM. Non seulement cela, c'est inutilement zéro, prolongeant les registres d'octets une seconde fois après cela l'a déjà fait. Je dirais que ce code est assez lent. Vous pouvez certainement faire beaucoup mieux si les chaînes partagent l'alignement (comparant 2, 4, 8 ou 16 octets à la fois, en fonction de l'alignement qu'ils partagent). Il peut être surchargé pour les chaînes qui sont peu susceptibles de partager beaucoup d'alignement (à moins qu'ils ne soient obtenus directement à partir de MALLOC ), mais cela fait une énorme différence pour MEMCMP qui est presque toujours donné aligné Mémoire.
@R ..: Veuillez ensuite poster un meilleur exemple au lieu de critiquer.
@R ..: ou, si vous préférez, un contre-exemple.
@R ..: La seule autre version que je peux trouver est ce gâchis d'un autre système: Pastie.org/1343515 Mais je ne peux pas dire si la décharge est même correcte ou pourquoi il y a tellement de code mort au milieu.
Je ne sais pas si optimisé STRCMP est vraiment sur le sujet pour la question de OP; C'est plus une question théorique avec la réponse appropriée étant "Ce n'est pas possible" ou "utilise STRCMP STRCMP ". Je suis juste en désaccord avec l'affirmation selon laquelle le compilateur générera du code rapide pour une implémentation naïve, qui pourrait même encourager les débutants à écrire - leur propre hypothèse que le compilateur fera un meilleur travail avec celui-ci que l'implémentation de la bibliothèque pourrait faire asm.
@R ..: Vous faites un bon point. Je vais simplement le frapper de ma réponse entièrement.
Voici une solution qui utilise des valeurs de type ENUM au lieu de cordes. Il prend en charge l'augmentation de l'héritage de valeur et soutient donc la comparaison similaire à celle de la comparaison de sous-chaîne. Il utilise également un caractère spécial "¤" pour la nommage, pour éviter les collisions de noms. Vous pouvez prendre n'importe quel nom de classe, de fonction ou de variable et de le faire en valeur ENUM (Someclassa deviendra ¤someclassa).
struct MultiEnum
{
vector<MultiEnum*> enumList;
MultiEnum()
{
enumList.push_back(this);
}
MultiEnum(MultiEnum& base)
{
enumList.assign(base.enumList.begin(),base.enumList.end());
enumList.push_back(this);
}
MultiEnum(const MultiEnum* base1,const MultiEnum* base2)
{
enumList.assign(base1->enumList.begin(),base1->enumList.end());
enumList.assign(base2->enumList.begin(),base2->enumList.end());
}
bool operator !=(const MultiEnum& other)
{
return find(enumList.begin(),enumList.end(),&other)==enumList.end();
}
bool operator ==(const MultiEnum& other)
{
return find(enumList.begin(),enumList.end(),&other)!=enumList.end();
}
bool operator &(const MultiEnum& other)
{
return find(enumList.begin(),enumList.end(),&other)!=enumList.end();
}
MultiEnum operator|(const MultiEnum& other)
{
return MultiEnum(this,&other);
}
MultiEnum operator+(const MultiEnum& other)
{
return MultiEnum(this,&other);
}
};
MultiEnum
¤someString,
¤someString1(¤someString), // link to "someString" because it is a substring of "someString1"
¤someString2(¤someString);
void Test()
{
MultiEnum a = ¤someString1|¤someString2;
MultiEnum b = ¤someString1;
if(a!=¤someString2){}
if(b==¤someString2){}
if(b&¤someString2){}
if(b&¤someString){} // will result in true, because someString is substring of someString1
}
Un personnage spécial? Ce n'est pas une bonne idée. Intelligent et mignon, mais pas bon code.
Toute cette solution était la preuve du concept, écrit juste pour le plaisir de celui-ci. Je ne l'ai pas regardé depuis ce matin, je l'ai écrit. :)
Sur Intel, il est possible de le faire avec une seule instruction. Certainement pas dans un seul cycle.
@avakar, le cycle ne sera qu'un mais cela pourrait être trop long :)
Ce que vous voulez est appelé symboles: tinyurl.com/nmoxme
@ jia3ep: Avakar est correct. Ce problème d'instruction unique prendra de nombreux cycles d'horloge.