Sur les courbes de Bézier et la vitesse Arduino, deuxième partie

Nous passerons - et plus loin

Dans mon post précédent, j'ai montré comment vous pouvez améliorer la vitesse de calcul des points sur une courbe de Bézier (KB) en:

1. Transformations des formules de calcul - accélération ~ 3 fois.
2. Il n'y a presque pas d'accélération de PT à FT - mais cela permet 3.
3. L'opération de remplacement de la division par multiplication et décalage est une accélération de 40% supplémentaires.

À la fin du message mentionné, j'ai dit que les calculs peuvent être faits encore plus rapidement, mais ce que "le garçon a dit - le garçon l'a fait".

Permettez-moi de vous rappeler encore une fois la formule obtenue pour calculer le point sur la base de connaissances

$$

$$P = (A1 * et + B1) * et + C (=> 2 * 2 +)$$

La prochaine augmentation de la vitesse est liée à la particularité du problème - nous devons non seulement calculer la valeur de KB à différentes valeurs du paramètre "et", mais trouver une série de valeurs lors de la modification (dans ce cas, l'augmentation) de ce paramètre par une valeur fixe connue (en outre, dans notre case unit), qui vous permet d'utiliser la technique décrite ci-dessous. À mon époque, cela s'appelait la méthode de calcul de la différence (si la mémoire est bonne, du moins c'était ce qu'on appelait dans les cours), tout Internet est à votre disposition, peut-être (même avec certitude), il y a un autre nom.

Nous considérons le cas P = A * et (=> 1 *), et supposons que nous connaissons la valeur de P0 avec un argument u0. La valeur avec l'argument suivant u0 + 1 peut alors être calculée comme P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+). Sans perdre de précision, nous avons pu remplacer l'opération de multiplication par l'opération d'addition, qui est beaucoup plus rapide.

Maintenant un exemple plus complexe P = A * et * et (=> 2 *), nous considérons par analogie P = A * (et + 1) * (et + 1) = A * (et * et + 2 * et + 1) = A * et * et + 2 * A * et + A = P0 + 2 * A * et + A (=> 2 * 2 +). À première vue, nous n'avons rien gagné, mais si nous calculons A '= 2 * A à l'avance, nous obtenons (=> 1 * 2 +), une victoire est tout à fait possible. Mais nous ne nous arrêterons pas sur ce qui a été réalisé et sur l'expression obtenue A '* et appliquerons la technique déjà connue de nous, alors nous aurons deux opérations sur deux variables: P = P + A' + A; A '= A' + A (=> 3+). Si nous tenons compte du fait que la valeur initiale de A 'peut être effectuée davantage par A, alors en général il n'y a que deux additions au lieu de deux multiplications. Oui, nous avons dû obtenir deux variables supplémentaires, mais c'est un échange classique - nous payons avec de la mémoire pour le moment.

Il ne reste plus qu'à calculer les valeurs initiales correctes, mais cela n'est fait qu'une seule fois au début des itérations, et si la valeur initiale du paramètre est u = 0, alors c'est généralement trivial P = 0, A '= A. Nous allons tester notre méthode sur plusieurs itérations (c'est complètement inutile, les mathématiques correctement appliquées ne peuvent pas donner la mauvaise réponse), mais cela nous permettra de mieux comprendre ce qui se passe. Alors
itération 0: et = 0; P = 0 (vrai); A '= A; A '' = 2 * A;
itération 1: et = 1; P = 0 + A '= 0 + A = A (vrai); A '= A' + A '' = A + 2 * A = 3 * A;
itération 2: et = 2; P = A + 3 * A = 4 * A (vrai); A '= 3 * A + 2 * A = 5 * A;
itération 3: et = 3; P = 9 * A (vrai); A '= 7 * A et ainsi de suite.

On note le lien entre les formules obtenues et la méthode de Newton pour calculer la valeur d'une fonction au voisinage d'un point de valeur connue. De plus, étant donné que notre fonction est du second ordre et que toutes les dérivées, à partir du troisième, sont égales à zéro, nous pouvons remplacer en toute sécurité le signe égal approximatif par le signe exact. La seule différence avec cette méthode est que nous déplaçons constamment le point par rapport auquel nous construisons un nouveau voisinage afin d'éviter d'effectuer des opérations de multiplication dans la formulation d'origine.

Réécrivez notre expression originale pour KB sous forme développée

$$

$$P = A1 * et * et + B1 * et + C$$

puis pour les calculs utilisant cette méthode, nous avons besoin de 2+ pour le premier terme (et deux variables), 1+ pour le deuxième terme (et une variable) et 2+ pour tout additionner (=> 5+). On peut s'attendre à ce que même cette (mauvaise) approche donne un gain par rapport à 2 * 2 +, mais tout va bien mieux. De toute évidence, l'opération d'addition est additive (merci, capitaine), vous pouvez donc regrouper les termes et remplacer les termes constants par de nouvelles expressions, ce qui donne l'algorithme suivant:

1. Les valeurs initiales de P = C; A '= A1 + B1; A '' = 2 * A1;
2. à l'étape suivante P = P + A '; A '= A' + A '' (=> 2+), ce qui est sans aucun doute plus rapide que le schéma de Horner.

Nous implémentons notre algorithme sous la forme d'un programme (ce n'est pas aussi trivial que cela puisse paraître, car pour des raisons de simplicité j'ai oublié le besoin de décalages, mais ce n'est pas trop difficile ... pendant 20 minutes), nous obtenons la complexité de calcul (=> 2 + 1 >>) et mesurons vitesse - il s'est avéré 140 (augmentation de la vitesse de 3 fois) cycles par cycle, mais c'est presque un résultat idéal. Ce que nous devons faire pour obtenir l'option idéale (dans un sens) est de prêter attention à la dimension des opérandes dans les formules. Maintenant, nous effectuons toutes les opérations sur des entiers longs (32 bits), et cela peut être inutile à certains endroits. Si nous réduisons la capacité des opérandes au minimum nécessaire, nous pouvons obtenir un gain de 20 à 25%, mais cela nous obligera à passer à l'assembleur (C n'a pas les moyens appropriés pour de telles opérations) et à analyser attentivement les données du problème d'origine. Que ce soit au lecteur de décider de le faire ou non, nous avons déjà accéléré les calculs de plus de 1900/140 = 13 fois par rapport à l'approche «naïve».

La dernière remarque sur la mise en œuvre de l'algorithme est que nous excluons toujours l'opération de division en la changeant par une multiplication constante, que nous prenons en compte lors de la génération des données initiales et du décalage par un multiple constant de 8. Cela peut être fait de différentes manières avec des temps d'exécution légèrement différents, laissant ces expériences à l'attention d'un lecteur curieux .

Cependant, un problème est survenu de manière totalement inattendue - nous voyons clairement deux opérations d'addition sur des nombres de 32 bits, qui devraient prendre 4 + 4 = 8 cycles d'horloge, mettre 8 * 3 * 2 = 48 cycles d'horloge supplémentaires pour l'envoi d'opérandes, 4 cycles d'horloge pour la réception du résultat du décalage, 4 un cycle d'horloge pour appeler la procédure de calcul et revenir, et 4 cycles d'horloge pour organiser le cycle - d'où 60 autres cycles d'horloge ne sont pas clairs. Auparavant, nous ne l'avions tout simplement pas remarqué dans le contexte de centaines de cycles d'horloge, mais vous pouvez maintenant faire attention. Des mesures excessives ont été facilement trouvées - au cours du cycle, il y a eu des opérations de débogage inutiles, si vous nettoyez tout soigneusement, il ne reste que 120 mesures et le but de chacune est tout à fait compréhensible (enfin, pas si clair, mais quand même). Ensuite, nous découvrons le temps d'exécution du cycle vide - 22 mesures, je me demande ce qu'ils font là tout ce temps, mais eh bien, et effacez le temps de calcul réel, qui sera de 98 cycles. Notez que l'évaluation de l'accélération de travail obtenue change: au lieu de 1900/140 = 13, nous obtenons (1900-50) / (140-40) = 19 fois, ce qui n'a aucun sens pratique, car le cycle est toujours nécessaire, mais il vous permet de l'augmenter encore plus l'estime de soi.

Et la dernière remarque - comme il est facile de le voir, nous avons commencé à rechercher et à éliminer les puces uniquement lorsque nous avons traité les grands coléoptères et leur (puces) existence est devenue évidente et, de plus, significative. Je recommande fortement exactement cette approche (et je ne suis pas le seul dans cette recommandation) lors de l'optimisation des programmes en termes de performances.

Eh bien, en conclusion, à propos de la note «dans un sens» - si nous parlons de calculer séquentiellement les coordonnées du point suivant sur la base de connaissances lors de la modification du paramètre (représentant le temps), alors l'algorithme proposé (après toutes les optimisations) n'est plus possible à améliorer. Mais si vous reformulez la tâche et, par exemple, fixez l'objectif de simplement construire un bureau d'études à l'écran (sans référence au temps), alors il existe une méthode très prometteuse, le mot-clé "Brezenheim", mais "c'est une histoire complètement différente", à laquelle je consacrerai un billet séparé (peut-être un jour si la sœur aînée ne s'en soucie pas).