logo Homepage
Pages: [1]
  Imprimer  
Auteur Fil de discussion: Optimiser un programme C dont les variables ne comportent qu'un seul bit  (Lu 8365 fois)
BAAL

Profil challenge

Classement : 13/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« le: 10 Mars 2015 à 01:31:03 »

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 ?
Journalisée
Asteriksme
Modérateur Global

Profil challenge

Classement : 37/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 785

.


Voir le profil WWW
« #1 le: 10 Mars 2015 à 01:47:51 »

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...
Journalisée

"It's a funny thing about some mathematicians. We often don't care if the results have applications because the results are themselves so pretty."
S0410N3
Administrateur

Profil challenge

Classement : 10/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 1260


Voir le profil WWW
« #2 le: 10 Mars 2015 à 02:01:48 »

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

Enjoy (copyleft de quelqu'un qui a trop parlé)

S0410N3

-------------------------------------------------------------------------------------
La folie est le prix à payer pour le temps passé à être trop lucide.
-------------------------------------------------------------------------------------
http://forum.hardware.fr/hfr/Discussions/Societe/francais-repere-repaire-sujet_19265_1.htm
Asteriksme
Modérateur Global

Profil challenge

Classement : 37/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 785

.


Voir le profil WWW
« #3 le: 10 Mars 2015 à 02:06:25 »

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)
Journalisée

"It's a funny thing about some mathematicians. We often don't care if the results have applications because the results are themselves so pretty."
S0410N3
Administrateur

Profil challenge

Classement : 10/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 1260


Voir le profil WWW
« #4 le: 10 Mars 2015 à 02:09:16 »

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 ?
Journalisée

Enjoy (copyleft de quelqu'un qui a trop parlé)

S0410N3

-------------------------------------------------------------------------------------
La folie est le prix à payer pour le temps passé à être trop lucide.
-------------------------------------------------------------------------------------
http://forum.hardware.fr/hfr/Discussions/Societe/francais-repere-repaire-sujet_19265_1.htm
BAAL

Profil challenge

Classement : 13/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #5 le: 10 Mars 2015 à 02:09:47 »

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).
Journalisée
S0410N3
Administrateur

Profil challenge

Classement : 10/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 1260


Voir le profil WWW
« #6 le: 10 Mars 2015 à 02:49:15 »

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

Enjoy (copyleft de quelqu'un qui a trop parlé)

S0410N3

-------------------------------------------------------------------------------------
La folie est le prix à payer pour le temps passé à être trop lucide.
-------------------------------------------------------------------------------------
http://forum.hardware.fr/hfr/Discussions/Societe/francais-repere-repaire-sujet_19265_1.htm
Celelibi
Profil challenge

Classement : 298/54363

Néophyte
*
Hors ligne Hors ligne
Messages: 24


Voir le profil
« #7 le: 10 Mars 2015 à 03:05:35 »

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.
Journalisée
BAAL

Profil challenge

Classement : 13/54363

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #8 le: 10 Mars 2015 à 03:12:14 »

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.
Journalisée
ferbos

Profil challenge

Classement : 11/54363

Membre Senior
****
Hors ligne Hors ligne
Messages: 356

The Godfather is back....


Voir le profil WWW
« #9 le: 10 Mars 2015 à 07:23:52 »

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
« Dernière édition: 10 Mars 2015 à 12:58:57 par ferbos » Journalisée

"Les seules limites sont les fautes."
Celelibi
Profil challenge

Classement : 298/54363

Néophyte
*
Hors ligne Hors ligne
Messages: 24


Voir le profil
« #10 le: 10 Mars 2015 à 09:16:35 »

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.
Journalisée
Pages: [1]
  Imprimer  
 
Aller à: