Go Down

Topic: Multiplier par 1024 (Read 561 times) previous topic - next topic

Dec 23, 2020, 09:59 am Last Edit: Dec 30, 2020, 10:48 pm by vileroi
Bonjour,

J'ai une multiplication à faire par 1024. Il s'agit (ma bêtise a quand même ses limites) d'un entier long non signé. J'ai plusieurs solutions avec mon compilateur optimisé, resultat et valeur sont des uint16_t uint32_t:
A) resultat = valeur * 1024;
B) resultat = valeur << 10;
C) resultat = valeur *1023 +valeur;
Bien sûr il y en a d'autres, mon esprit inventif ne va pas vous faire la liste.

D'emblée comme ça, j'aurais tendance à dire que A est plus explicatif, mais que B est meilleur. Quand à C, c'est l'idée la plus stupide du jour (il n'est que 8h du matin).

MAIS, comme tout shadock qui se respecte, j'ai mesuré les temps de ces instructions (Maman m'a dit que si je mets la main dans une casserole d'eau bouillante, je vais me brûler. C'est vrai, j'ai vérifié). J'ai mesuré sur une Uno.
Pour B je trouve 86 cycles d'horloges. Comme mon entier long est coupé en 4 octets, on  doit faire 10 fois un décalage de 1 case pour profiter de la retenue que l'on va passer au poids d'après. Il doit faire pour mon entier long non signé sur 4 octets A-B-C-D
Répéter 10 fois:
   a) décale D de 1 case vers la gauche, ce qui dépasse va dans la retenue
   b) décale C avec la retenue de 1 case vers la gauche, ce qui dépasse va dans la retenue
   b) décale B avec la retenue de 1 case vers la gauche, ce qui dépasse va dans la retenue
   b) décale A avec la retenue de 1 case vers la gauche
C'est tout à fait conforme à ce que j'attendais.
Pour A: faut pas prendre le compilateur pour un ministre, il voit bien que c'est une puissance de 2 et il va faire des décalages. On a donc aussi 86 cycles.
Pour C: rien que pour l'embêter, j'ai caché qu'on pouvait faire des décalages, et du coup il fait vraiment la multiplication. Ce qui durerait 64 cycles si il n'y avait pas l'addition, et ce qui fait 68 cycles avec
Conclusion: C'est bien la solution C la meilleure avec l'optimisation par défaut. Et si dans ma bibliothèque j'ai une multiplication par 1024 à faire, il vaut mieux cette formule.

Question: peut-on ne pas optimiser le code que pour une seule instruction?
Grand jeu concours: avec l'optimisation par défaut, trouvez la formule pour multiplier valeur par 1024 et mettre ceci dans resultat en utilisant le moins de cycles possible. Le gagnant gagne un karma.



Après cet exercice, j'ai quand même voulu en savoir plus. j'ai testé:
resultat = valeur << 32;

Il a pris 16 cycles. Je l'ai bien eu, il lui suffisait de faire
resultat = 0;

c'était pareil, et cela lui aurait coûté que 8 cycles.



Et si je testais les autres décalages pour resultat = valeur << N;
Ncycles   remarques
0  16c'est juste une copie
1  20un seul décalage, pas de boucle
2  30à partir d'ici, on fait des boucles et cela coûte 16+7N cycles
3  37
4   44
...   ...
7   65
8   72
...   ...
15   121
16   19pas idiot, c'est un décalage d'un seul octet
17   135on reprend 16+7N cycles
...   ...
22   171à partir d'ici 17+7N cycles; le cycle en plus vient-il d'une erreur de chronométrage?
23   178
24   20normal, c'est un décalage d'octets
25   192reprise du 17+7N cycles
...   ...
30   22717+7N cycles
31   22jun petit décalage à gauche pour récupérer le bit de poids fort...
32   16peux mieux faire


Je ne m'explique pas vraiment le 16+7N cycles qui passe à 17+7N cycles. Si je faisais une erreur de chronométrage sur les temps longs, pour N=24, je devrais retrouver 19 comme pour N=16!

Ils ont quand même optimisé pour N=16 et N=24, mais pas pour N=8.

Conclusion A partir de 8 décalages, il vaut mieux la solution C. Comme quoi il y a des idées saugrenues à garder.


lesept

Proposition :
Code: [Select]
  uint16_t valeur = 12; // prise au pif...
  uint16_t resultat = 0;
  for (int i = 0; i < 1024; i++)
    for (int j = 0; j < valeur; j++)
      ++ resultat;
  Serial.println(resultat);


J'ai bon ?  :D
A force d'essayer on finit par réussir... Donc, plus ça rate, plus on a de chances que ça marche (proverbe Sharduinok).

#2
Dec 23, 2020, 11:37 am Last Edit: Dec 23, 2020, 11:46 am by vileroi
!mumixam el sap ,ehcrehc ej euq muminim el tse'C .srevne'l à emèlborp el sirp sa ut euq siorc eJ
<--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <--  <-- <--  <--   <--

Ils ne m'ont pas écoutés.Je lis ceci:
unsigned long micros() {
    unsigned long m;
    uint8_t oldSREG = SREG, t;
    
    cli();
    m = timer0_overflow_count;
#if defined(TCNT0)
    t = TCNT0;
#elif defined(TCNT0L)
    t = TCNT0L;
#else
    #error TIMER 0 not defined
#endif

#ifdef TIFR0
    if ((TIFR0 & _BV(TOV0)) && (t < 255))
        m++;
#else
    if ((TIFR & _BV(TOV0)) && (t < 255))
        m++;
#endif

    SREG = oldSREG;
    
    return ((m << 8) + t) * (64 / clockCyclesPerMicrosecond());
}


Décidément, je suis fâché avec l'horloge système

MarsaMatruh

Faudrait voir le code assembleur généré. Il n'y a pas cette option du côté d'arduino?

L'ATmega328 doit pas bien aimer les décalages qui dépassent sa largeur de registre  :) .

68tjs

#5
Dec 23, 2020, 06:19 pm Last Edit: Dec 23, 2020, 06:19 pm by 68tjs
Et en plus il y a des tonnes d'options de gcc que l'IDE a fixé pour nous et que l'on ne peut pas (simplement) modifier.
Bon comme je n'y connais et n'y comprend rien je ne suis pas frustré.
Ceux qui savent qu'ils ne savent rien en connaisse autant que ceux qui croient tout savoir et qui n'en connaissent pas plus qu'eux.
Pierre DAC.


Quote
Faudrait voir le code assembleur généré. Il n'y a pas cette option du côté d'arduino?
Si, mais en connaissant un peu l'assembleur et ce que l'on peut faire avec et en regardant le temps d'exécution d'une instruction, on a quasiment la méthode. Un jour, j'irais regarder le code. Je l'avais déjà fait il y a 15 ans avec une interface différente sur des AVR.

Quote
L'ATmega328 doit pas bien aimer les décalages qui dépassent sa largeur de registre
Les AVR qui bossent pour moi  n'ont pas le droit à la parole, et que cela leur plaise ou non, il doivent obéissance.
Mais en langage machine AVR, les seuls décalages possibles sont sur 8 bits. le reste est une suite d'instructions

Quote
Et en plus il y a des tonnes d'options de gcc que l'IDE a fixé pour nous et que l'on ne peut pas (simplement) modifier.
Tant que l'on écrit pour soi, on peut faire ce que l'on veut, mais si on s'amuse à faire un bibliothèque, il vaut mieux l'optimiser pour la configuration par défaut. On ne peut pas demander à une tierce personne de modifier la configuration du compilateur.

lesept

Une question au passage : comment mesurer le nombre de cycles pour l'exécution d'une instruction ou d'un ensemble d'instructions ? 
A force d'essayer on finit par réussir... Donc, plus ça rate, plus on a de chances que ça marche (proverbe Sharduinok).

Même réponse que comment fait-on pour faire clignotter la LED_BUILTIN? C'est selon chacun, il y a plein de solutions. La mienne c'est de définir le step d'un moteur pas à pas sur la broche de la led et de demander un rotation.

 Pour la mesure du temps d'un code, j'ai ma méthode, elle fonctionne, et par paresse si j'en trouve une meilleure, il est probable que je n'en change pas.

Ma méthode qui vaut ce qu'elle vaut:
Je fais 1000 boucles contenant un nop avec un micros() devant et un micros() derrière
Je fais 1000 boucles contenant un nop et mon code à tester, encadré par deux micros()
Je calcule la différence de temps qui représente en µs le temps de 1000 code ou bien le temps en ns d'un code
J'ai mis des variables pour ne pas avoir à les définir à chaque fois.
Pour que cela fonctionne
- il faut faire des multiples de 1024 boucles car sinon on peut avoir le temps supplémentaire du timer qui peut se rajouter ans une boucle et pas dans l'autre. Solution que j'ai choisi, je fais 100000 boucles, il peut y avoir une différence d'une interruption timer (8µs environ) qui est ignorée par la division par 100
- il faut utiliser des variables volatiles ou pas suivant ce que l'on veut faire.
- il ne faut pas que le compilateur vire le code. Pour cela j'initialise mes variables avec random() avant les boucles et je fais un Serial.print() après (pour que l'affichage ne se fasse pas il est soumis à la condition "quand les poules auront des dents".
- si le code est long, je fais 100 boucles, je n'ai plus besoin d'une grande précision, voir une seule boucle dans certains cas (combien de temps je met à afficher une image sur mon écran).
Cela donne
Code: [Select]

volatile boolean o, o2;
volatile byte b, b2, b3;
volatile word w, w2, w3;
volatile unsigned long ul, ul2;
volatile float f, f2;
volatile double d;
volatile byte tb[256];
//volatile word tw[256];

void setup()
{
  randomSeed(analogRead(0));
  o = random(2);
  //  o=!o;
  o2 = random(2);
  b = random(2);
  b2 = random(2);
  b3 = random(2);
  w = random(0x10000);
  w2 = random(0x10000);
  w3 = random(0x10000);
  ul = random(0x10000);
  ul2 = random(0x10000);
  f = random(0x10000);
  f2 = random(0x10000);
  d = random(0x10000);
  for (byte i = 0; i < 255; i++) tb[i] = random(256);
//  for (word i = 0; i < 255; i++) tw[i] = random(0x10000);


  Serial.begin(115200);
  unsigned long t1, t2, t3; // Chronomètres
  t1 = micros();
  for (unsigned long x = 100000ul; x > 0; x--) _NOP(); // Tarer le temps d'une boucle
  t2 = micros();
  for (unsigned long x = 100000ul; x > 0; x--) // Boucle de mesure
  {
    _NOP();


    // Mettre ici le code à tester
    ul2 = 0; // Par exemple




  }
  t3 = micros();
  t1 = t3 + t1 - 2 * t2;
  Serial.println();
  Serial.println(String(t1 / 100ul) + "ns");
  Serial.println(String(t1 / 6250ul) + "cycle(s)\n");
  if (t1 > 1000000000l)
  {
    Serial.print(o);
    Serial.print(o2);
    Serial.print(b);
    Serial.print(b2);
    Serial.print(b3);
    Serial.print(w);
    Serial.print(w2);
    Serial.print(w3);
    Serial.print(ul);
    Serial.print(ul2);
    Serial.print(f);
    Serial.print(f2);
    Serial.print(d);
    for (byte i = 0; i < 255; i++) Serial.print(tb[i]);
//    for (byte i = 0; i < 255; i++) Serial.print(tw[i]);
  }
}

void loop()
{
}

68tjs

Une question au passage : comment mesurer le nombre de cycles pour l'exécution d'une instruction ou d'un ensemble d'instructions ?
Simple et efficace.
Tu modifies les réglages d'un timer pour mettre le prédiviseur à 1. Le compteur du timer (TCNTx) donne alors directement des cycles horloges.
Comme le compteur du timer peut être lu et écrit, pour éviter les débordements, je le mets systématiquement à 0 avant la mesure et je ne fait que le lire après la suite d'instruction.

Une fois la mesure faite tu remets  (ou pas) le réglage par défaut du timer.
Perso sur un avr 8 bits j'ai toujours utilisé un timer 8bit pour être sur que la lecture se fait en 1 cycle d'horloge.

Sinon  il y a la possibilité d'obtenir la suite d'instructions assembleur à partir de la compilation (utilitaire Atmel de l'avr-gcc dont j'ai oublié le nom ) et "pour ceux qui savent le lire", c'est à dire pas moi, compter le nombre d'instructions.
Ceux qui savent qu'ils ne savent rien en connaisse autant que ceux qui croient tout savoir et qui n'en connaissent pas plus qu'eux.
Pierre DAC.

lesept

Merci 68tjs (un rapport avec mai 68 dans ce pseudo ?)
Peux-tu compléter en donnant les instructions de réglage, mise à zéro et lecture ?

Est-ce que ça fonctionne sur ESP32 ? Sinon, comment le porter ? 

Merci
A force d'essayer on finit par réussir... Donc, plus ça rate, plus on a de chances que ça marche (proverbe Sharduinok).

trimarco232

Une question au passage : comment mesurer le nombre de cycles pour l'exécution d'une instruction ou d'un ensemble d'instructions ?
La méthode la + académique est de regarder le code en assembleur sur un simulateur (par ex atmel studio), et d'utiliser le stopwatch qui te permet d'avoir le nombre exact de cycles ;  tu peux même voir le temps pris par chaque petit bout en faisant du pas à pas
mais si c'est court, simplement compter les instructions, ça va aussi (standard = 1 cycle ; saut = 2 cycles ; aller ou retour sub = 4 cycles)
Pour l'ESP32, joker
- complexité des instructions
- RTOS
- doc lapidaire
donc je ne suis même pas certain d'avoir compris la question

Normalement tout ce que j'écris ne fonctionne que sur AVR (et des fois encore plus sectaire). Pour une fois que j'écris quelque chose de non spécifique et qui doit aussi tourner sur ESP32....

 
Quote
Une question au passage : comment mesurer le nombre de cycles pour l'exécution d'une instruction ou d'un ensemble d'instructions ?
Ça dépend des instructions, si c'est

Code: [Select]
ISR(TIMER2_OVF_vect)
{
  <instructions>
}

ni la méthode de @68tjs ni celle que j'ai indiquée ne fonctionne.

Une méthode qui a l'air de fonctionner est de donner une suite de
  digitalWrite(mesure, HIGH);
  digitalWrite(mesure, LOW);
et de mesurer l'écart supplémentaire dans le signal de sortie à l'ananlyseur. Cela fonctionne pour les instructions simples (comme une usine à gaz), mais fonctionne aussi pour les instructions ci-dessus

ChristopheFr

Salut Vileroi,

Quote
J'ai une multiplication à faire par 1024. Il s'agit (ma bêtise a quand même ses limites) d'un entier long non signé. J'ai plusieurs solutions avec mon compilateur optimisé, resultat et valeur sont des uint16_t:
Je suppose que tu voulais écrire uint32_t

J'ai 51 cycles (avec la vieille version 1.8.10) :)
avec:
Code: [Select]

  resultat = valeur<<2;
  resultat = resultat<<8;


Quote
Pour la mesure du temps d'un code, j'ai ma méthode, elle fonctionne, et par paresse si j'en trouve une meilleure, il est probable que je n'en change pas.
Pour mesurer le nombre de cycles, j'utilise le timer 1 16 bits (jusqu'à 65535 cycles) comme suit:
Code: [Select]

unsigned t1;
volatile uint32_t resultat = 0, valeur = 123;

void setup() {
  Serial.begin(115200);
  TCCR1A = 0; // timer 1 16 bits en mode compteur
  TCCR1B = 1; // prédiviseur du timer à 1 (compte les cycles d'horloge)
  cli(); // bloquer les interruptions
  TCNT1 = 0; // initialiser le compteur à 0
  // début du code à mesurer
  resultat = valeur<<2;
  resultat = resultat<<8;
  // fin du code à mesurer
  t1 = TCNT1;
  sei();
  Serial.print("t1: ");
  Serial.println(t1); // afficher le compteur
}

void loop() {
}


Simple et efficace.


Go Up