Comment memchr() travail sous le capot?
Contexte: je suis en train de créer un pur langage D la mise en œuvre de la fonctionnalité qui est à peu près équivalent à C est memchr mais utilise des tableaux et des indices au lieu de pointeurs. La raison en est ainsi que les mst.string fonctionnera avec l'évaluation de la fonction de compilation time. Pour ceux d'entre vous qui ne connaissent pas w/ D, les fonctions peuvent être évaluées au moment de la compilation si certaines restrictions sont respectées. Une restriction est qu'ils ne peuvent pas utiliser des pointeurs. Un autre est qu'ils ne peuvent pas appeler les fonctions C ou utiliser le langage d'assemblage en ligne. Avoir la bibliothèque des chaînes de caractères au moment de la compilation est utile pour certains hacks de code Temps de compilation.
Question: Comment memchr travail sous le capot pour effectuer aussi rapide? Sur Win32, tout ce que j'ai pu créer en pure d en utilisant des boucles simples est au moins 2 fois plus lent, même avec des techniques d'optimisation évidentes telles que la vérification des limites de désactivation, le déroulement des boucles, etc. Quel des sortes d'astuces non évidentes sont disponibles pour quelque chose d'aussi simple que de trouver un personnage dans une chaîne de caractères?
4 réponses
je suggère de jeter un oeil à la source de GNU libc . Comme pour la plupart des fonctions, il contiendra à la fois une version c optimisée générique de la fonction et des versions de langage d'assemblage optimisées pour autant d'architectures prises en charge que possible, en tirant parti des astuces spécifiques à la machine.
la version x86-64 SSE2 combine les résultats de pcmpeqb sur une ligne de cache entière de données à une fois (quatre vecteurs 16B), amortir les frais généraux de la sortie anticipée pmovmskb / test / jcc .
gcc et clang sont actuellement incapables d'auto-vectoriser des boucles avec des conditions de sortie précoce if() break , ils font donc naïf octet-at-a-time asm de la mise en œuvre évidente de C.
Cette mise en œuvre de memchr de newlib est un exemple de quelqu'un de l'optimisation de memchr: il lit et teste 4 octets à la fois (en dehors de memchr, les autres fonctions de la bibliothèque newlib sont ici ).
soit dit en passant, la plupart du code source de la bibliothèque MSVC run-time est disponible, en tant que partie optionnelle de L'installation MSVC (donc, vous pouvez regarder cela).
voici le memchr () de FreeBSD (sous licence BSD) De memchr.c . Le navigateur de code source en ligne de FreeBSD est une bonne référence pour les exemples de code testés dans le temps et sous licence BSD.
void *
memchr(s, c, n)
const void *s;
unsigned char c;
size_t n;
{
if (n != 0) {
const unsigned char *p = s;
do {
if (*p++ == c)
return ((void *)(p - 1));
} while (--n != 0);
}
return (NULL);
}
memchr comme memset et memcpy généralement réduire à une assez petite quantité de code machine. Il est peu probable que vous puissiez reproduire ce type de vitesse sans avec le code d'assemblage similaire . Une question importante à prendre en considération dans une mise en œuvre est alignement des données .
One technique générique que vous pouvez utiliser est d'insérer un sentinel à la fin de la chaîne être fouillé, ce qui garantit que vous le trouverez. Il vous permet de déplacer le test de fin de chaîne à partir de l'intérieur de la boucle, après la boucle.