[BAAL]

Les processeurs d’aujourd’hui ont généralement 32 ou 64 bit.
Ce qui veut dire qu’en ce qui concerne le temps d’exécution, quand je programme en C, je n’ai pas le choix que d’écrire:
int a = 0;
int b = 1;
int c = a^b;
Même si je sais que a, b, c ne sont en fait que des variables de 1 bit.

J’ai un programme plein de telles variables, et je me demandais s’il y’avait un outil ou une libraire C qui pouvait faire du packing intelligent et potentiellement améliorer le temps d’exécution par 32x ou 64x.

J’imagine que non, mais qui sait, peut-être que quelqu’un a une idée ?

[Asteriksme]

Tu peux utiliser le type char (ou unsigned char) qui sera a priori codé sur (au moins) 8 bits, mais il me semble que c'est la plus petite unité adressable...

[S0410N3]

C'est une question qui appelle au troll en tout cas.
Et je me doute que tu connais déjà la réponse BAAL.

[Asteriksme]

ou alors tu compactes toi même tes variables dans 8 (ou plus selon l'architecture et le type) fois moins de variables : chaque bit de chaque variable représente une variable indépendante (oui désolé c'est pas clair mais il est tard)

[S0410N3]

Pour les compacter comme tu dis a priori tu perds du temps cpu à le faire et des octets intemédiaires, donc ça ne sert à rien non ?
Ou alors tu ne parles pas d'un cpu d'ordi ?

[BAAL]

C'est une question qui appelle au troll en tout cas.
Et je me doute que tu connais déjà la réponse BAAL.

Pas du tout, à moins que la réponse soit que c’est impossible.

Tu peux utiliser le type char (ou unsigned char) qui sera a priori codé sur (au moins) 8 bits, mais il me semble que c'est la plus petite unité adressable...

Je viens d'essayer, et comme prévu, ça n’a rien changé.
Même avec un type char, le processeur utilise le même ALU de 32 ou 64 bit,
il ne peut pas faire 4 opérations char en même temps qu’une opération int.
L’idée ça serait de packer 32 variables ensemble dans un int s’ils ont la même opération.
Du coup ça prend autant de temps à faire une opération qu’il en faut pour en faire 32.
Le catch c’est qu’il faut payer un prix pour les combiner puis les décombiner.
Je me demandais donc s’il y’avait une lib qui faisait ce genre de chose automatiquement et essayait de minimiser les coûts?

Pour les compacter comme tu dis a priori tu perds du temps cpu à le faire et des octets intemédiaires, donc ça ne sert à rien non ?
Ou alors tu ne parles pas d'un cpu d'ordi ?

Voilà c'est ça le problème. Je parle bien d’un cpu d’ordi (pour simuler un circuit de logique).

[S0410N3]

Tu fais quoi des retenues en combinant tes bits dans la même opération ?

[Celelibi]

Tu veux peut-être un bit field.
Si tu veux être sûr de faire des opérations sur des mots de 32 ou 64 bits, il va te falloir un union aussi, mais ce comportement n'est pas standard.
Tu peux même aller plus loin avec les instructions vectorielles type SSE.

Mais avant d'optimiser à la main, vérifie que ton compilateur n'optimise pas déjà tes opérations.

[BAAL]

Tu fais quoi des retenues en combinant tes bits dans la même opération ?

Il n'y a pas d'addition entre deux bits, juste des &, |, ~ (and, or, not).

Tu veux peut-être un bit field.
Si tu veux être sûr de faire des opérations sur des mots de 32 ou 64 bits, il va te falloir un union aussi, mais ce comportement n'est pas standard.
Tu peux même aller plus loin avec les instructions vectorielles type SSE.

Mais avant d'optimiser à la main, vérifie que ton compilateur n'optimise pas déjà tes opérations.

Je crois que les bit field sont quand même implémentés avec des int, et on n’échappe pas aux shifts et aux masks. Je ne crois pas que le compilateur optimise ça tout seul, mais je vais vérifier.

[ferbos]

Salut,

Je répondrais ce que répondait mon professeur de langage C qui ne nous regardait jamais dans les yeux:
"Ce que vous gagnez en mémoire, vous risquez de le perdre en flops. Il faut trouver l'équilibre entre les deux" (très métaphysique )

Et pour l'instant, je n'ai jamais été déçu par cette phrase et pourtant j'ai essayé.

Même en faisant des "struct" pour obtenir des bits fields, tout dépend des opérations (leur type, leur nombre, leurs combinaisons) qui vont être effectuées et dans ce cas du nombre de bits utilisées.

Edit du 10/03/2015 à 12:40:
Par rapport au bits dont je connais mal l'accès en mémoire, je fais l'analogie aux matrices et au calcul à effectuer dessus. On remarque que suivant le nombre de zéros présents dans la matrice mais aussi la taille de cette dernière, on restructure la matrice en triangle, en ligne par indexation ou encore des solutions hybrides par bloc. Mais cela a des conséquences sur les opérations et en général face aux opérations d'un problème donné, on reprogramme lesdites opérations classiques suivant si on se trouve devant une matrice quasiment vide ou pas. Ceci correspondrait ici à réécrire des fonctions en assembleur (?). Donc plutôt que de voir le problème de l'opération posé sur un bit, il s'agirait de mettre en masse les bits, de les restructurer et d'effectuer des opérations de masse dédiées à la structure choisie.

Du coup, je pense à un truc bête si on met "bool" à la place de "int", est-ce que les opérations ne vont pas plus vite même si cela est stocké en "char"? Je suis persuadé de la réponse

ferbos

[Celelibi]

Je crois que les bit field sont quand même implémentés avec des int, et on n’échappe pas aux shifts et aux masks. Je ne crois pas que le compilateur optimise ça tout seul, mais je vais vérifier.

Si tu veux packer plusieurs bits dans un byte, tu n'échapperas pas aux shift+mask. Avec un bit field ils seront simplement générés par le compilateur.
La pertinence des opérations groupés comme tu cherches à le faire dépend fortement du ratio entre tes opérations groupées et tes accès aux bits.

Dans l'idée je dirais de commencer par compiler l'implémentation naïve avec -O2 ou -O3 et désassembler pour voir le code généré.
Faire de même avec un simple bit field. (gcc reconnaîtra peut-être plus facilement l'optimisation sur un bit field que sur des char.)
Recommencer avec un union qui englobe le bit field et un uint*_t en faisant à la main l'opération sur l'entier. (Note: vérifier que sizeof de l'union est égal au sizeof de l'entier. Si le bit field est plus large que l'entier, ça va chier.)
Tu pourrais aussi tenter de mettre tes bits dans des char et simplement remplacer le bit field par un tableau ou une struct de 4 ou 8 char. Pas de shift, mais seulement 4 ou 8 opérations groupées. (À moins d'aller taper dans le MMX/SSE pour jouer avec des mots plus grands.)

Et si le but c'est d'optimiser le temps d'exécution, la seule bonne stratégie c'est de faire des benchmarks.