Multiplier par 1024

International Français Le bar
1

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;

N cycles remarques
0 16 c'est juste une copie
1 20 un 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 19 pas idiot, c'est un décalage d'un seul octet
17 135 on 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 20 normal, c'est un décalage d'octets
25 192 reprise du 17+7N cycles
... ...
30 227 17+7N cycles
31 22 jun petit décalage à gauche pour récupérer le bit de poids fort...
32 16 peux 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.

2

Proposition :

  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 ? :smiley:

3

!mumixam el sap ,ehcrehc ej euq muminim el tse'C .srevne'l à emèlborp el sirp sa ut euq siorc eJ
<-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <-- <--

4

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

5

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 :slight_smile: .

6

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

7

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.

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

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.

8

Une question au passage : comment mesurer le nombre de cycles pour l'exécution d'une instruction ou d'un ensemble d'instructions ?

9

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
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()
{
}
10

lesept:
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.

11

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

12

lesept:
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
13

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....

14

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

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

15

Salut Vileroi,

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) :slight_smile:
avec:

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

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:

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.

16

Je suppose que tu voulais écrire uint32_t

Effectivement (en fait j'utilise unsigned long).

Serial.println(t1); // afficher le compteur

Je dirais plutôt

Serial.println(t1-1); // afficher le compteur

Cela donne le valeur juste. En effet si on ne mesure rien, t1 vaut 1, et si on mesure _NOP( ), on trouve 2.

J'ai aussi une erreur de chronométrage de 1 que j'avais plus ou moins signalé. Je ne retrouve pas les 72 pour un décalage de 8 positions, j'ai dû me tromper. Pour les autres résultats, les mesures ont l'air d'être les mêmes.

J'ai refait les tests avec le timer. J'ai bien une erreur de chronométrage de 1 à partir d'un certain nombre.

Vu que ma méthode donne un résultat faux, je vais me pencher dessus. Quand je l'ai faite, je ne savais pas programmer les timers. Mais je crois que je vais m'orienter avec plusieurs chronométrages en fonction de ce que j'ai à mesurer. Je pense que passer par un timer est une meilleure solution pour les temps courts, limité à 255 cycles avec un timer 8 bits, 65535 avec un timer 16 bits. Pour des instructions plus lente (copie d'une image sur un écran par exemple) le timer ne fonctionne plus, je reprned mon ancienne version. Et une troisième méthode avec un analyseur en ayant une succession de PORTB=0; PORTB=FF; pour mesurer des choses qui ne passent pas par les deux premières méthodes, comme par exemple la durée de la remise à l'heure de l'horloge système.

D'un point de vue philosophique et pour les instructions longues, faut-il mesurer en tenant compte de l'horloge système ou pas? Ma méthode est fausse pour avoir le nombre de cycles, mais pas pour le temps moyen que va durer réellement l'instruction. Si elle dure exactement 1018µs, je suis sûr qu'elle prendre 1024µs car il y aura les 6µs perdus pendant la remise à l'heure.