conseil en bit hacks

Version imprimable

15/12/2016, 14h22
LEK

conseil en bit hacks

Bonjour,
Cette question aurait pu être posée pour tout autres langagues car je crois que les opérateurs de traitements de bits et concepts doivent être les mêmes...
Mais voilà, je suis en train de m'exercer en C, sur la lecture et le parsing d'un fichier CSV, et je voulais expérimenter une manière innovante qui ne m'oblige pas à tester octet par octet le contenu du fichier chargé en mémoire pour repérer les saut de ligne et l'utilisation du caractère séparateur (virgule dans mon cas)...
Je me demandais donc s'il était possible d'optimiser ce parsing de manière à repérer avec le moins d'instructions possible la position des caractères "\n" et "," dans mon buffer à l'aide de Xor+bit shifting ?

Je ne demande pas forcément à ce qu'on me donne une solution toute faite, mais j'aimerais plus avoir un avis/retour sur la faisabilité ou est-ce que de toute manière tout parsing se soldera forcément par une boucle sur tous les octets de mon fichier?

Merci pour tout aide,
Lek
15/12/2016, 14h56
Matt_Houston

Comme pour toute recherche au sein d'une collection non triée, il n'est pas possible de faire autrement que de comparer chaque élément à la valeur recherchée. À tout « raccourci » dont on pourrait faire usage correspond une contrainte sur la collection.
15/12/2016, 14h58
ternel

En fait, tu peux assez facilement, ce sont des caractères commes les autres. Mais quelque soit ton opération, elle ne sera pas plus rapide que l'opération d'égalité.
Et en prime, tu as le problème que certains OS injectent des \r avant les \n (windows) ou à leur place (OS X).

tu peux le remplacer par xor + shift, mais ca ne sera pas plus optimisé.

Bonjour,

nous sommes en 2016, nous ne sommes plus dans les années 1970/1980 où ce genre de micro optimisations avait son utilité ou son importance. Les compilateurs C sont plus évolués et souvent bien plus malins que ceux qui les utilisent. On ne peut plus s'attendre réellement «qu'à un ensemble d'instruction C correspondent un ensemble similaire d'instruction en code machine».
L'exemple le plus simple sera sans doute la division 10. Prenons un code hyper simple comme :
Code:

1 2 3 4 5 6 7 8 9 10 11 #include <stdio.h> int main(void) { int a; printf("a="); scanf("%d", &a); int b=a/10; printf("a/10=%d",b); return 0; }
Ligne 8 tu as une division par 10, rien d'exceptionnel. Mon processeur a une instruction div, je m'attends naïvement à ce qu'elle soit utilisée. Je compile mon code, je regarde le code machine produit :
Code:

1 2 3 4 5 6 7 8 9 10 11 int b=a/10; 7a0: 8b 4d f0 mov -0x10(%rbp),%ecx 7a3: ba 67 66 66 66 mov $0x66666667,%edx 7a8: 89 c8 mov %ecx,%eax 7aa: f7 ea imul %edx 7ac: c1 fa 02 sar $0x2,%edx 7af: 89 c8 mov %ecx,%eax 7b1: c1 f8 1f sar $0x1f,%eax 7b4: 29 c2 sub %eax,%edx 7b6: 89 d0 mov %edx,%eax 7b8: 89 45 f4 mov %eax,-0xc(%rbp)
J'ai tout (une multiplication, deux shift et une soustraction) sauf une division utilisant l'instruction div.
[ code compilé avec gcc6.2 option -g sur linux64 ; exécutable desassemblé avec un objdump -dS ]

La morale de cet exemple est qu'un compilateur sait mieux qu'un développeur quand il est intéressant d'utiliser un bit trick. Si tu commences à essayer de faire des bit tricks en code C alors tu n'es même pas certain que le compilateur va bien faire ce que tu demandes.
Pire, tu vas introduire de la confusion aussi bien au niveau de la lisibilité de ton code qu'au niveau de compréhension de l'intention que le compilateur va déduire. En essayant de gagner quelques microsecondes tu vas en fait en perdre plusieurs millisecondes … bad bet.

Ce qui est très important, en revanche, c'est de bien informer son compilateur sur ses intentions en écrivant un code clair et simple, en utilisant ces mots clés qui sont faits pour (const, restrict, … ou les extensions disponibles pour marquer des fonctions pures et/ou constantes).
Ce qui peut être intéressant est de demander à ton compilateur de paralléliser ton code en utilisant les instructions vectorielles type SIMD.

15/12/2016, 17h38
LEK

@ternel, effectivement je me base sur des fichiers avec fins de ligne windows like et je ne traite pas les autres cas.
@picodev : je comprends ta remarque, mais j'ai juste besoin d'apprendre par ce biais là, j'ai déjà essayé les approches au niveau avec de bonnes perfs mais pour le plaisir je voulais voir jusqu'où il est possible d'aller..
@Matt_houston, ok merci pour ton retour, c'est dommage, je me suis laissé à rêver pendant un moment qu'il devait y avoir un moyen pour rapidement mettre à 0 tous les bits différents de fin de ligne et caractère séparateur et qu'ensuite je pouvais les retouver plus rapidement sans passer en revue tous les élements mais par exemple en traitant par lot les bits... (je ne suis pas sûr que ce que je dis à un sens, j'entrevoyais une possibilité mais c'est un peut nouveau pour moi)

En tous cas merci pour vos retours, même si cela ne m'avance pas sur une méthode particulière à tester pour mesurer s'il y a ou non un gain.
15/12/2016, 17h54
Aurel-R

Citation:

Envoyé par picodev

nous sommes en 2016, nous ne sommes plus dans les années 1970/1980 où ce genre de micro optimisations avait son utilité ou son importance. Les compilateurs C sont plus évolués et souvent bien plus malins que ceux qui les utilisent. On ne peut plus s'attendre réellement «qu'à un ensemble d'instruction C correspondent un ensemble similaire d'instruction en code machine».

Évidemment que pour des opérations simples (+ - * / et d'autres) il vaut mieux laisser le compilo faire 'à sa manière'. En même temps quel est l'intérêt de faire des manipulations de bits dans ce cas ?

Pour le reste en revanche, il peut être beaucoup plus avantageux (quand ce n'est pas la seule solution possible) de manipuler des bits. C'est de l'optimisation (plus "haut niveau") qui s'opère sur des données à traiter. Par exemple pour optimiser la place que prend un tableau d'entiers (de taille n) en mémoire, et sachant qu'un entier représente 4 octets, on a donc 4*n octets, ce qui occupe beaucoup de mémoire sur un grand nombre d'entiers. Grâce à de l'optimisation (de la compression donc) avec des "bits hack", on peut réduire de façon assez importante la place occupée en mémoire (VLQ par ex). Aussi, Ce genre d'optimisation nécessite de manipuler et de jouer avec les octets/bits.

Donc je trouve que c'est une démarche intéressante de chercher à optimiser le traitement de données en passant (ou non) par des "bits hack".

Pour revenir au sujet, comme dit plus haut, tu devras comparer octet par octet. Après ça dépendra de ce que tu fais avec ton fichier. Si c'est de la lecture seule (mais j'imagine que non), tu n'auras besoin de le parser qu'une seule et unique fois en entier.

Après tu peux analyser plusieurs fichiers cvs et essayer d'y trouver des similarités (genre si les octets '\n' sont sur un offset multiple de 2 ou non, padding, etc)
15/12/2016, 18h37
Obsidian

Citation:

Envoyé par LEK

Bonjour,
Cette question aurait pu être posée pour tout autres langagues car je crois que les opérateurs de traitements de bits et concepts doivent être les mêmes...
Mais voilà, je suis en train de m'exercer en C, sur la lecture et le parsing d'un fichier CSV, et je voulais expérimenter une manière innovante qui ne m'oblige pas à tester octet par octet le contenu du fichier chargé en mémoire pour repérer les saut de ligne et l'utilisation du caractère séparateur (virgule dans mon cas)... Je me demandais donc s'il était possible d'optimiser ce parsing de manière à repérer avec le moins d'instructions possible la position des caractères "\n" et "," dans mon buffer à l'aide de Xor+bit shifting ?

Comme indiqué plus haut, le XOR/bit shifting implique tout de même que tu lises d'abord ces valeurs en mémoire. Donc, effectivement, un XOR sera équivalent à une égalité. C'est d'ailleurs bien souvent comme cela que celle-ci est établie par le micro-processeur : une soustraction des deux valeurs en mettant à jour les bits de condition (les flags), et notamment le bit Z, correspondant en fait à une sorte de non-OU câblé et qui indique automatiquement si un registre donné ou un résultat d'opération est nul.

En revanche, il est possible de suivre certaines approches heuristiques sur les gros fichiers. Voir par exemple « Why GNU grep is so fast ».

Citation:

Envoyé par picodev

nous sommes en 2016, nous ne sommes plus dans les années 1970/1980 où ce genre de micro optimisations avait son utilité ou son importance. Les compilateurs C sont plus évolués et souvent bien plus malins que ceux qui les utilisent. On ne peut plus s'attendre réellement «qu'à un ensemble d'instruction C correspondent un ensemble similaire d'instruction en code machine».

C'est vrai, mais ces dernières années, nous avons atteint un point où nous sommes en train de basculer vers l'extrême inverse : tout ce qui touche de près ou de loin à la rédaction de code optimisé « doit être laissé à l'appréciation du compilateur ». C'est pertinent d'un point de vue technique, mais cela implique que tous les programmeurs devraient s'attacher à écrire un compilateur pour savoir optimiser le code correctement. Et sans aller jusque là, cela veut surtout dire que tout programmeur devrait savoir jusqu'à quel point le compilateur qu'il utilise va optimiser le code qu'il produit et, surtout, à quel stade il va cesser de le faire.

Ça signifie aussi que la production d'un exécutable décent va être intimement lié à la qualité du compilateur utilisé, celle-là même que pratiquement personne ne sait estimer avec précision. L'exemple-type est le « x & 1 » que l'on applique sur les entiers pour en extraire le bit de poids faible. Lorsque l'on cherche en fait à en déterminer la parité, on nous oblige aujourd'hui à le remplacer par « x % 2 »… en partant du principe que tout compilateur retraduira forcément cette expression en « x & 1 ». Si on utilise un compilateur qui prenne le programmeur au mot et qui fasse en fin de compte — exactement — ce qu'il lui a demandé, il va appliquer un coûteux DIV, voire appellera la routine dédiée à cette charge (car les processeurs proposant DIV sont rares). Opération à comparer à un ET logique qui fait partie des fondamentaux, avant même les opérations arithmétiques, et qui peut souvent s'exécuter en un cycle.

Certes, les considérations liées à l'optimisation trop précoce sont toujours justifiées. Mais je maintiens que l'optimisation en soi doit rester une préoccupation du programmeur qui doit s'y entraîner, quitte à déporter cela vers une plateforme et/ou un langage dédié à cela, ou à pratiquer sérieusement la théorie de la compilation.
15/12/2016, 19h22
picodev

Citation:

Envoyé par Aurel-R

Évidemment que pour des opérations simples (+ - * / et d'autres) il vaut mieux laisser le compilo faire 'à sa manière'. En même temps quel est l'intérêt de faire des manipulations de bits dans ce cas ?

Et pas que pour les opérations simples. Il y a un tas de «savoirs ancestraux» qui n'ont plus lieu d'être de nos jours (je parle de plateformes modernes utilisant des outils modernes, évidemment, je mets l'embarqué à part) et le problème est que certains de ces savoirs ont la vie dure et ont parfois l'effet inverse. Parmi ces «savoirs ancestraux» je mets en vrac : il faut créer des variables pour sortir les expressions qu'on serait amené à calculer plusieurs fois, il faut préférer un ++i à un i++ ou à un i+=1, …, les bit tricks améliorent automatiquement les performances.

Citation:

Envoyé par Aurel-R

Pour le reste en revanche, il peut être beaucoup plus avantageux (quand ce n'est pas la seule solution possible) de manipuler des bits. C'est de l'optimisation (plus "haut niveau") qui s'opère sur des données à traiter. Par exemple pour optimiser la place que prend un tableau d'entiers (de taille n) en mémoire, et sachant qu'un entier représente 4 octets, on a donc 4*n octets, ce qui occupe beaucoup de mémoire sur un grand nombre d'entiers. Grâce à de l'optimisation (de la compression donc) avec des "bits hack", on peut réduire de façon assez importante la place occupée en mémoire (VLQ par ex). Aussi, Ce genre d'optimisation nécessite de manipuler et de jouer avec les octets/bits.

Donc je trouve que c'est une démarche intéressante de chercher à optimiser le traitement de données en passant (ou non) par des "bits hack".

Je ne parlais que de code, pas de structure de données. On utilise d'ailleurs couramment «des bits tricks» pour ça sans aller très loin → utf8.

Citation:

Envoyé par Aurel-R

Pour revenir au sujet, comme dit plus haut, tu devras comparer octet par octet. Après ça dépendra de ce que tu fais avec ton fichier. Si c'est de la lecture seule (mais j'imagine que non), tu n'auras besoin de le parser qu'une seule et unique fois en entier.

Après tu peux analyser plusieurs fichiers cvs et essayer d'y trouver des similarités (genre si les octets '\n' sont sur un offset multiple de 2 ou non, padding, etc)

Dans le genre «trucs et astuces», pourquoi ne pas simplement faire un type punning → un uint64_t pour 8 chars (à partir du moment où CHAR_BIT vaut 8), un xor, une négation et d'un coup on compare 8 octets …
Mais dans ce cas, pourquoi ne pas directement demander au compilo de vectoriser les accès ?

Citation:

Envoyé par Obsidian

C'est vrai, mais ces dernières années, nous avons atteint un point où nous sommes en train de basculer vers l'extrême inverse : tout ce qui touche de près ou de loin à la rédaction de code optimisé « doit être laissé à l'appréciation du compilateur ». C'est pertinent d'un point de vue technique, mais cela implique que tous les programmeurs devraient s'attacher à écrire un compilateur pour savoir optimiser le code correctement. Et sans aller jusque là, cela veut surtout dire que tout programmeur devrait savoir jusqu'à quel point le compilateur qu'il utilise va optimiser le code qu'il produit et, surtout, à quel stade il va cesser de le faire.

Normalement, avant d'écrire du code on passe par plusieurs phases de réflexion. Entre autre on choisit (du moins on devrait choisir) les structures de données et les algos qu'on va utiliser pour résoudre un problème, implémenter un modèle, … La première optimisation se fait à ce niveau.
Ensuite on implémente nos choix sans chercher à faire des micro optimisations, le but premier est d'obtenir une version fonctionnelle.
Au final, on peut éventuellement profiler son produit optimisé par le compilateur pour savoir où d'éventuelles optimisations pourraient apporter le plus gain.
On n'a pas, a priori, à savoir où quand ni comment le compilateur va optimiser notre code. Par contre, l'aider à le faire est très important.
Oui, pour bien utiliser son compilateur il faut bien connaître son compilateur. Ça n'a pas changé depuis 40 ans → mieux on connaît ses outils mieux on les utilise.
Le programmeur n'a plus à connaître les arcanes de son compilateur pour produire un code optimisé, et heureusement.

Citation:

Envoyé par Obsidian

Ça signifie aussi que la production d'un exécutable décent va être intimement lié à la qualité du compilateur utilisé, celle-là même que pratiquement personne ne sait estimer avec précision. L'exemple-type est le « x & 1 » que l'on applique sur les entiers pour en extraire le bit de poids faible. Lorsque l'on cherche en fait à en déterminer la parité, on nous oblige aujourd'hui à le remplacer par « x % 2 »… en partant du principe que tout compilateur retraduira forcément cette expression en « x & 1 ». Si on utilise un compilateur qui prenne le programmeur au mot et qui fasse en fin de compte — exactement — ce qu'il lui a demandé, il va appliquer un coûteux DIV, voire appellera la routine dédiée à cette charge (car les processeurs proposant DIV sont rares). Opération à comparer à un ET logique qui fait partie des fondamentaux, avant même les opérations arithmétiques, et qui peut souvent s'exécuter en un cycle.

Pourquoi donc voudrais-tu remplacer un x & 1 par un x % 2 ? L'important est de noter l'intention plus que de penser à optimiser ce genre de code.
A priori, le compilateur choisira de produire un code approprié à l'utilisation que ce soit avec un % ou un &. Il pourra même ne pas produire de code du tout s'il arrive à prouver qu'à l'endroit où cette instruction est appelée la valeur peut être connue …
C'est lui qui choisira, suivant les infos que tu lui auras donné, si cette expression est «traduite» en compare et jump ou en conditional move. Ce n'est pas, ça ne devrait plus être une considération du programmeur.
Les processeurs sont devenus trop complexes et trop nombreux pour qu'un programmeur puisse programmer en émettant des hypothèses, c'est le job du compilo.

Citation:

Envoyé par Obsidian

Certes, les considérations liées à l'optimisation trop précoce sont toujours justifiées. Mais je maintiens que l'optimisation en soi doit rester une préoccupation du programmeur qui doit s'y entraîner, quitte à déporter cela vers une plateforme et/ou un langage dédié à cela, ou à pratiquer sérieusement la théorie de la compilation.

Quand on commence à coder la majorités des optimisations ont déjà du avoir lieu. La seconde phase d'optimisation vient (parfois) ensuite s'il le faut et si c'est nécessaire.

Ce que je dis ici est surtout destiné aux développement sur des plateformes modernes, en utilisant des outils modernes. Cela ne concerne pas par exemple le domaine de l'embarqué.
16/12/2016, 10h00
Matt_Houston

Citation:

Envoyé par Obsidian

En revanche, il est possible de suivre certaines approches heuristiques sur les gros fichiers. Voir par exemple « Why GNU grep is so fast ».

À noter que cela est applicable seulement lorsque l'entrée fait plus d'un caractère, je cite un extrait du très instructif propos en lien ci-dessus en rapport direct avec la question de l'OP (emphase mienne) :

Citation:

Moreover, GNU grep AVOIDS BREAKING THE INPUT INTO LINES. Looking
for newlines would slow grep down by a factor of several times,
because to find the newlines it would have to look at every byte!

Bonjour,
je pense avoir trouvé ce que je cherchais a exprimer ici dans la fonction *find_hdr_value_end :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #if defined(__x86_64__) || \ 844 defined(__i386__) || defined(__i486__) || defined(__i586__) || defined(__i686__) || \ 845 defined(__ARM_ARCH_7A__) 846 /* speedup: skip everything not a comma nor a double quote */ 847 for (; s <= e - sizeof(int); s += sizeof(int)) { 848 unsigned int c = *(int *)s; // comma 849 unsigned int q = c; // quote 850 851 c ^= 0x2c2c2c2c; // contains one zero on a comma 852 q ^= 0x22222222; // contains one zero on a quote 853 854 c = (c - 0x01010101) & ~c; // contains 0x80 below a comma 855 q = (q - 0x01010101) & ~q; // contains 0x80 below a quote 856 857 if ((c | q) & 0x80808080) 858 break; // found a comma or a quote 859 } 860 #endif
Il me reste à l'adapter à la recherche des virgules et fins de ligne...
Je ne sais pas si c'est effectivement la méthode du type punning citée plus haut ni si le gain sera énorme, voir même si cela ne marchera pas sur toutes les architectures.... Mais bon c'est un début et cela me rassure, il y avait bien un moyen de considérer les bytes par blocs pour ne pas avoir à passer en revue chaque char de manière indépendante si non nécessaire...