Optimisation divisions : opérations 64 bits
Posté le 24/07/2018 15:25
Bonjour à tous,
Pour optimiser
Windmill, j'ai besoin d'optimiser deux divisions situées dans la boucle la plus profonde (celle qui se répète le plus). Elles monopolisent à elles seules environ 70% du processeur !
Voici le code que je cherche à optimiser :
int x, y, z
...
int a = x/z;
int b = y/z;
Alors j'ai fait mes recherches et j'ai trouvé
Libdivide, qui permet de faire des divisions rapides.
Le seul problème, c'est que pour optimiser ces divisions, l'algo de Libdivide utilise une multiplication et une division sur 64 bits :
static inline int libdivide__mullhi_s32(int x, int y)
{
uint64_t xl = x, yl = y;
uint64_t rl = xl * yl;
return (uint32_t)(rl >> 32);
}
static unsigned int libdivide_64_div_32_to_32(unsigned int u1, unsigned int u0, unsigned int v, unsigned int *r)
{
uint64_t n = (((uint64_t)u1) << 32) | u0;
unsigned int result = (unsigned int)(n / v);
*r = (unsigned int)(n - result * (unsigned int64)v);
return result;
}
Seulement on est limité sur casio, les types int et long faisant 32 bits...
J'ai trouvé dans le
doc Renesas page 357 (indice en bas de page)
Renesas a écrit :
long dmuls_h(long data1, long data2)
Description: Multiplies a pair of signed 32-bit data to produce a signed 64-bit data, and
refers to the upper 32 bits of the product.
Header: <machine.h> or <umachine.h>
Example: #include <machine.h>
extern long data1, data2;
extern long result;
void main(void)
{
result = dmuls_h(data1, data2);
}
Remarks: This function is invalid when cpu= sh1 is specified.
Donc ça c'est ok ! (ouf ! j'avais lu que c'était valid QUE pour SH1...
)
Mais je n'ai aucune piste pour le division 64 bits...
Est-ce que que vous auriez des pistes, des conseils, est-ce bricolable à la main ?
Citer : Posté le 24/07/2018 16:15 | #
J'ai trouvé une autre lib qui n'utilise pas de division 64 bits.
Je vais voir ce que ça donne
Citer : Posté le 24/07/2018 17:02 | #
Y'avait un tweak du sdk pour gérer les nombres 64 bit (nécessaires pour eigenmath). Sinon essaie de n'utiliser que des int32, en copiant l'algo de la division 64 bit par exemple (à moins que celui de la division 64 bit utilise des 128 bits...)
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 24/07/2018 18:09 | #
hmm intéressant cette piste, merci.
Là je viens d'essayer, en mettant #include <machine.h> puis dmulu_h(a, b) mais le compilateur ne reconnait pas la fonction "is undefined"...
J'ai vu qu'il faut être en "privilege mode", en quoi ça consiste et comment être dans ce mode ?
Citer : Posté le 24/07/2018 18:12 | #
L'application est en mode privilégiée (et c'est mal mais c'est la faute de CASIOWIN donc bon), tu n'as pas à te soucier de ça. Aussi, dmulu_h est une macro normalement, mais devrait être définie si tu as inclus <machine.h>…
Du moins si tu utilises le compilateur de Renesas (SHC). À ce moment-là, ces macros sont des alias aux built-ins correspondants :
#define dmulu_l(data1, data2) _builtin_dmulu_l(data1, data2)
#define dmuls_h(data1, data2) _builtin_dmuls_h(data1, data2)
#define dmuls_l(data1, data2) _builtin_dmuls_l(data1, data2)
Si tu utilises GCC, ce code devrait permettre de définir les macros (extrait de la libcarrot) :
uint32_t __result; __asm("dmulu.l %1, %2\r\n" "lds.l MACH, %0"
:"=r"(__result) :"r"(__data1), "r"(__data2));
return (__result); }
static __attribute__((always_inline, unused)) uint32_t __dmulu_l(uint32_t __data1, uint32_t __data2) {
uint32_t __result; __asm("dmulu.l %1, %2\r\n" "lds.l MACL, %0"
:"=r"(__result) :"r"(__data1), "r"(__data2));
return (__result); }
static __attribute__((always_inline, unused)) int32_t __dmuls_h(int32_t __data1, int32_t __data2) {
int32_t __result; __asm("dmuls.l %1, %2\r\n" "lds.l MACH, %0"
:"=r"(__result) :"r"(__data1), "r"(__data2));
return (__result); }
static __attribute__((always_inline, unused)) int32_t __dmuls_l(int32_t __data1, int32_t __data2) {
int32_t __result; __asm("dmuls.l %1, %2\r\n" "lds.l MACL, %0"
:"=r"(__result) :"r"(__data1), "r"(__data2));
return (__result); }
#define dmulu_h(_DATA1, _DATA2) __dmulu_h(_DATA1, _DATA2)
#define dmulu_l(_DATA1, _DATA2) __dmulu_l(_DATA1, _DATA2)
#define dmuls_h(_DATA1, _DATA2) __dmuls_h(_DATA1, _DATA2)
#define dmuls_l(_DATA1, _DATA2) __dmuls_l(_DATA1, _DATA2)
Ce code te demandera d'inclure <stdint.h> pour utiliser les types int32_t et uint32_t, ou de les définir toi-même en tant que signed long et unsigned long respectivement.
Mon blog ⋅ Mes autres projets
Citer : Posté le 24/07/2018 18:46 | #
Ok c'est un bon point.
Je compile avec le SDK et ça ne fonctionne pas. Le SDK n'utilise pas le compilateur Renesas ?
Merci pour le code, si ça ne fonctionne pas avec le SDk je me mettrai à gcc, je sais que Lephé n'avait pas réussi à compiler Windmill dessus par contre.
Citer : Posté le 24/07/2018 19:15 | #
Le SDK utilise le compilateur de Renesas (nommé « SHC »), si. Je viens de m'aperçevoir qu'en fait, le SDK de base utilise la version 6.00 du compilateur alors que je regardais les headers de la version 9.04, installée dans les SDK tweakés. Essaies de voir ce que ça donne avec ce SDK par exemple, c'est le même avec la version 9.04 du compilateur (et pas besoin de mon code du coup).
Si ça ne marche pas, il faut demander à des gens plus experts dans ce qui se fait sur Windows. Peut-être Zezombye s'il n'a pas la flemme
Mon blog ⋅ Mes autres projets
Citer : Posté le 24/07/2018 19:44 | #
Hmm intéressant je ne connaissais pas cette version du SDK !
Et ça fonctionne !
Ajouté le 24/07/2018 à 19:47 :
Par contre j'ai une autre erreur (peu importe la version du SDK), je n'arrive pas à cerner son origine
** L2300 (E) Duplicate symbol "ilog(unsigned int)" in "C:\Casio Projets\Render 3D V2\Debug\Main.obj"
Est-ce que quelqu'un saurait pourquoi ?
#define FASTDIV
#include <machine.h>
unsigned char ilog(unsigned int i);
static inline void init_fastdivctx(struct fastdivctx *ctx, unsigned int divisor);
static inline unsigned int fastdiv(struct fastdivctx *ctx, unsigned int eax);
struct fastdivctx {
unsigned int mult;
unsigned int mod;
unsigned char shift1:1;
unsigned char shift2:7;
};
#endif
unsigned char ilog(unsigned int i)
{
unsigned char result = 0;
while (i >>= 1)
{
result++;
}
return result;
}
static inline void init_fastdivctx(struct fastdivctx *ctx, unsigned int divisor)
{
unsigned char ilogd = 3;//ilog(divisor);
int power_of_2 = (divisor & (divisor - 1)) == 0;
if (divisor == 0 || divisor >= (1U<<31))
{
}
if (power_of_2)
{
ctx->shift1 = 0;
}
else
{
ctx->shift1 = 1;
}
ctx->shift2 = ilogd;
ctx->mod = divisor;
ctx->mult = (1ULL<<(32+ctx->shift1+ctx->shift2)) / divisor + 1;
}
/*
static inline unsigned int fastmod(struct fastdivctx *ctx, unsigned int eax)
{
uint64_t edxeax = ((uint64_t)eax) * ctx->mult;
unsigned int edx = edxeax>>32;
unsigned int eaxorig = eax;
eax -= edx;
eax >>= (ctx->shift1);
eax += edx;
eax >>= (ctx->shift2);
edx = ctx->mod*eax;
return eaxorig - edx;
}
*/
static inline unsigned int fastdiv(struct fastdivctx *ctx, unsigned int eax)
{
unsigned int edx = dmulu_h(eax, ctx->mult);
eax -= edx;
eax >>= (ctx->shift1);
eax += edx;
eax >>= (ctx->shift2);
return eax;
}
Citer : Posté le 24/07/2018 23:51 | #
Regarde si tu n'as pas déclaré le ilog dans un autre fichier de ton projet. Sinon, essaie d'enlever le prototype pour voir.
Selon le site de Renesas (https://www.renesas.com/en-eu/products/software-tools/tools/compiler-assembler/compiler-package-for-superh-family.html) le compilo 9.04 supporte le C89 et le C99 (ce qui fait que je peux déclarer une variable après une fonction, entre autres) mais quand je teste avec le nouveau sdk, déclarer une variable avec une fonction provoque toujours une erreur. Il y a un truc à faire pour compiler en C99 ?
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 25/07/2018 00:00 | #
J'ai vérifié et je ne déclare ilog nul part ailleurs. J'ai changé le nom de la fonction en ilogerzayteqy et c'est la même.
Si je retire le proto et la fonction ça marche, mais avec non
Vraiment je comprends pas pour le coup...
Ah c'est cool si on a le C99, ça prend en charge les vector non ?
Citer : Posté le 25/07/2018 11:51 | #
C89 et C99 sont des standards de C, pas de C++. Faut voir si d'autres standards de C++ sont pris en compte.
Pour la gestion du standard C99, Zezombye, ne lis pas de travers : seules certaines fonctionnalités du C99 sont supportées, à savoir les commentaires en // (qui étaient, de toute façon, supportés avant je crois) et le type long long (entier 64-bit). Le manuel ne cite pas d'option pour switcher de standard, tout est donc considéré comme « C99 » par défaut, puisque les standards C (ISO 9899) sont pensés pour être rétrocompatibles avec les standards précédents (ils se contentes de les étendre généralement).
Et concernant ton souci d'ilog, Ninestars, aucune idée avec seulement cet extrait… essaie éventuellement de définir cette fonction en static si tu ne l'utilises que dans ce fichier, ça ne devrait plus poser de souci de symbole au niveau du linker (puisque ça devient une fonction interne au fichier).
Mon blog ⋅ Mes autres projets
Citer : Posté le 25/07/2018 21:01 | #
Juste quelques mots sur ce sujet, même si j'arrive un peu après la bataille.
D'abord, la multiplication 64 bits existe bien sûr dans le processeur et est gérée par deux instructions nommées dmuls.l et dmulu.l, la première multipliant en signé et la seconde en non-signé. Le résultat est stocké dans le registre abstrait 64-bit mac qui est en fait deux registres de contrôle de 32 bits, mach et macl.
dmuls_h() renvoie la valeur de mach après exécution de dmuls.l. Si tu utilise à la fois dmuls_h() et dmuls_l(), vu le niveau d'optimisation qu'on connaît à ce compilateur, il est peut-être capable de faire la multiplication deux fois. N'hésite pas à écrire quelques lignes d'assembleur si tu peux, quitte à programmer une fonction dans un fichier src à part.
Ensuite, j'ai déjà utilisé pour gint un trickz assez puissant qui transforme une division 32 bits (~70 cycles) par une multiplication 64 bits (~7 cycles) quand le diviseur est connu à la compilation. Ça ne t'intéresse pas, c'est sûr, mais pour tous ceux qui ont besoin de diviser à répétition par 10 pour afficher du décimal, ça aide vraiment. De mémoire je crois que ma preuve de l'opération est un peu faite avec les mains.
Le mode privilégié c'est un peu le mode admin du processeur. Celui dans lequel on peut exécuter les instructions de contrôle et adresser toute la mémoire, discuter avec les périphériques... dans un OS bien fait on n'aurait pas droit mais CASIOWIN est comme ça. gint abuse du mode privilégié toutes les trois lignes
Je découvre aussi cette histoire de version du compilo, merci Cake !
Je vais être un peu pédant peut-être, mais de mémoire le standard ne dit pas que long long fait 64 bits, seulement qu'il faut au moins autant qu'un int, ce qui n'aide pas vraiment.
Pour apporter ma petite contribution, j'ai dumpé la table de symboles de tous les objets de fxlib ; aucune trace de ilog. Ninestars, essaie de compiler un projet vide (ajoutes-y toutefois toutes les bibliothèques que tu utilises dans Windmill et que tu n'as pas écrites toi-même) avec un appel à ilog() pour voir si la fonction n'existerait pas déjà. As-tu également fait la recherche textuelle dans l'ensemble de ton dossier de projet ?
Citer : Posté le 25/07/2018 21:17 | #
@Lephenixnoir Pour le standard (ici ISO C99) et le type long long :
@Ninestars Est-ce que ce problème de symboles ne serait pas parce que le fichier est inséré deux fois dans le projet ?
Mon blog ⋅ Mes autres projets
Citer : Posté le 27/07/2018 08:01 | #
Merci pour vos précisions
@Lephé : Pour revenir sur l'exemple de la division par 10, c'est ce que j'utilise mais dynamiquement pour n'importe quel dénominateur en fait.
Je vais essayer de le compiler dans un nouveau fichier. Ce qui est étrange c'est que même en changenant le nom de la fonction avec un truc absurde style ilogkfhqskfbskfb(...) c'est pareil. Alors soit j'ai vraiment pas de chance avec le nom soit il y a un truc étrange haha !
Je pense que ça doit être ça Cake, pourtant j'ai un #ifndef LIVDIVIDE et je l'inclue qu'une fois. De plus j'ai ce problème que sur cette fonction et pas les autres...
Citer : Posté le 28/07/2018 17:30 | #
Donc tu réimplémentes la division... c'est ce que je vois.
Citer : Posté le 28/07/2018 23:20 | #
Bon j'ai essayé mon truc sur un projet vierge, ça compile bien, mais par contre l'algo renvoie le mauvais résultat...
Je vais tenter avec l'autre algo de division rapide que j'ai trouvé sur le net
Citer : Posté le 29/07/2018 13:10 | #
T'as regardé du coté de fixed ? Il me semble que y'a un algo pour faire de la division assez rapide dedans.