MAYLIB 0.7.5 / Thread - Page 1

Pour info, la 0.7.4 / 0.7.3 est disponible sur le site de la T3 : t3?id=2&d=archives/Librairies/Maylib/
(Si je ne fais plus de news, c'est que la page admin est cassée).

Sinon, revenons à la version 0.7.5 qui est en cours de développement. Elle apporte son lot de nouveauté (petite extension ROOTOF - très naive, mais sympa : ROOTOF(4,-x^3+x^2+x-1,x)^15 = -15+30*ROOTOF(4,-1+x^2-x^3+x,x)-10*ROOTOF(4,-1+x^2-x^3+x,x)^3-12*ROOTOF(4,-1+x^2-x^3+x,x)^2, implanté de façon super naïve et pas du tout optimisée).

Mais la principale nouveauté est le support des thread dans le moteur de calcul symbolique.
Pour ce faire, je me suis inspiré de cilk plus (site: http://www.cilkplus.org/ ) pour faire mon interface ( http://en.wikipedia.org/wiki/Cilk_Plus )
Les contraintes que j'avais :
* pas de regression du temps de calcul en mode Single-Thread.
* simple à gérer : le code MT ne doit pas rendre le code moins lisible et le même code doit pouvoir fonctionner en mode ST ou en mode MT.
L'interface cilk plus répondait à ces conditions. Prenons l'exemple classique de Fibonacci: int fib(int n) { if (n < 2) return n; int x = fib(n-1); int y = fib(n-2); return x + y; }
en version parallélisée, cela donne : int fib(int n) { if (n < 2) return n; int x = cilk_spawn fib(n-1); int y = fib(n-2); cilk_sync; return x + y; }
Juste deux mot clés (cilk_spawn et cilk_sync en plus) mais le code reste le même (exemple complet disponible à https://www.cilkplus.org/fibcpp )
Pour compiler, il faut utiliser GCC /clang /icc dernière version :
gcc fib.c -O3 -fcilkplus
On execute:
./a.out

./a.out: error while loading shared libraries: libcilkrts.so.5: cannot open shared object file: No such file or directory

Arg ! Ca ajoute une dépendance à un runtime
Une fois corrigé:

Fibonacci number #39 is 63245986.
Calculated in 6.059 seconds using 2 workers.

Comme l'interface est simple, je me suis dit que ca serait un bon entrainement de voir comme faire avec pthread seulement (pas encore porter le for).
Bon, j'ai paumé le source de test... (je dois pouvoir facilement le refaire cependant), mais les résultats étaient sans appel. Ce test de code vite fait était 10 fois plus rapide que cilk !
[EDIT] Bon finalement, j'ai refait le source pour être crédible. Les résultats:

Fibonacci number #39 is 63245986.
Calculated in 0.702 seconds using 2 workers.

Le code est cependant moins joli: int fib(int n); struct fib2_s { int x, n; }; static void subfunc_1 (void *data) { struct fib2_s *f = data; f->x = fib (f->n ); } /* Compute Fibonacci number using thread systems. */ int fib(int n) { if (n < 2) return n; struct fib2_s f; may_spawn_block_t b; may_spawn_start(b); f.n = n - 2; may_spawn (b, subfunc_1, &f); int y = fib (n-1); may_spawn_sync(b); return f.x + y; }

M'enfin bon, un facteur 10... je ne sais pas comment est faite l'implémentation de cilk plus ans gcc 4.9, mais à mon avis, y'a un insecte qui traine !
Considérant en plus qu'il me faut contrôler les variables globales lors d'un nouveau thread, je suis donc parti sur mon interface qui me permet de contrôler les variables globales spécifiques au thread lors de la création d'un nouveau thread (c'est hallucinant qu'ils n'aient pas prévu une fonction de construction / destruction à enregistrer lors de la création / destruction d'un thread mais qu'ils aient ajouté un quickexit dans le standard C11 - fin disgression).

L'interface de MAYLIB pour les thread worker devient donc:

int       may_kernel_worker(int nb_core,size_t stack_size);
==> Définit le nomber de worker (= thread additionel que MAYLIB utilisera "automatiquement" pour ces calculs) et la taille de la pile des objets algébriques pour chaque thread. 
Note: 1==> 1 thread, pas de worker. 0 ==> Auto detect number of core / Auto detect stack_size. 

void may_spawn_start(may_spawn_block_t block, may_mark_t mark);
==> Démarre et initialise un block // dont tous les calculs seront garbage collecté lors du prochain compactage impliquant mark.

void may_spawn (may_spawn_block_t block, void (*func)(void *), void *data);
==>Exécute (potentiellement) la fonction func(data) dans le block // block (s'il y a un worker de libre), où l’exécute de lui même sinon.

void may_spawn_sync(may_spawn_block_t block);
==> Attend que tous les worker aient finis.

(Je sais, ce n'est pas une interface complète et elle ne permet pas tout).

Comme c'est pas très user friendly (limite du C...), j'ai donc fait un pool de macros supplémentaire dont voici l'usage:

    MAY_SPAWN_BLOCK(block);
    MAY_SPAWN(block,(b,c,d), {
      a = add(b,c);
      a = add (a, d);
    }, (a));
    z = add(r, t);
    MAY_SPAWN_SYNC(block);

Ca rend la lecture plus simple en stockant le coeur de l'algorithme à coté des autres calculs (et accessoirement avec des bons define, de générer le code sans multi-thread directement dans le cœur de la fonction)
La seule macro complexe est MAY_SPAWN dont le prototype est :
MAY_SPAWN(block, (list of input), { core of computation }, (list of output) );
qui encapsule l'appel à may_spawn ci-dessus.
Elle a un inconvénient : elle génère une nested function (comme ont dit dans le milieu) qui n'est supporté que par GCC et ICC (clang ne le supporte pas) et utilise l'extension typeof.
Par contre, elle ne génère pas de trampoline (ce qui fait que la stack n'est pas marquée comme exécutable, donc pas de faille de sécurité) car toutes les variables locales sont recopiés dans une structure interne permettant de passer en paramètre les données à la fonction.

Vous me direz :
* les nested function, c'est mal, c'est pas standard. C'est un gnuisme. Oui, mais ne faisant pas de C++ (et les fonctions lambda), j'ai pas le choix si je ne veux pas détruire le flot de l'algorithme de calcul. Les fonctions lambda en C existent (point zerosquare inside) mais nécessitent de mettre tout le code dans une macro... Ca marche... mais c'est super chiant lorsque ton code a une erreur et qu'il te dit que c'est tout le temps à la ligne 10 (ligne de début de la fonction). J'ai limité la casse en faisant en sorte d'éviter le trampoline.

* Pourquoi te compliques tu la vie à éviter le trampoline si c'est pour quand même utiliser les nested function ? Parce que les trampoline, c'est leeeeennnnnnnt !
Si je reprend mon exemple de fibonnacci avec pthread, en le modifiant pour faire utiliser une nested function: int fib(int n) { if (n < 2) return n; struct fib2_s f; may_spawn_block_t b; may_spawn_start(b); f.n = n - 2; #if 0 may_spawn (b, subfunc_1, &f); #else void subfunc_2 (void *data) { f.x = fib(f.n); } may_spawn (b, subfunc_2, &f); #endif int y = fib (n-1); may_spawn_sync(b); return f.x + y; }
j'obtiens:

Fibonacci number #39 is 63245986.
Calculated in 21.206 seconds using 2 workers.

Et oui, faire un saut indirect récursif vers une fonction dont l'adresse change tout le temps est super couteux !

Donc, c'est bon j'ai décidé, et je pars implanter çà proprement dans MAYLIB... ce fut la galère

Il me reste à savoir comment gérer la pile algébrique de MAYLIB. Pour mes tests, j'ai modifié la fonction karatsuba de maylib: MAY_SPAWN_BLOCK(block, mark); MAY_SPAWN(block, (a,i,n), { /* A(X_i) = A1(X_i^2)*X_i+A2(X_i^2) */ split (&a1, &a2, a, i); /* (A1+A2)*(B1+B2) with j */ a1pa2 = add (a1, a2, n); }, (a1, a2, a1pa2)); /* B(X_i) = B1(X_i^2)*X_i+B2(X_i^2) */ split (&b1, &b2, b, i); /* B(X_i) = B1(X_i^2)*X_i+B2(X_i^2) */ b1pb2 = add (b1, b2, n); MAY_SPAWN_SYNC(block); MAY_SPAWN(block, (a1pa2, b1pb2, j, n), { a1pa2fb1pb2 = karatsuba(a1pa2, b1pb2, j, n, mark); }, (a1pa2fb1pb2)); MAY_SPAWN(block, (a1, b1, j, n), { /* A1*B1 with j */ a1fb1 = karatsuba (a1, b1, j, n, mark); }, (a1fb1)); /* A2*B2 with j */ a2fb2 = karatsuba (a2, b2, j, n, mark); MAY_SPAWN_SYNC(block);
(Ok, ca rend le code un poil plus difficile à lire. Mais pas trop).

1) première version:
pour la première version, j'ai décidé de couper le restant de la pile algébrique en deux lors d'un spawn, et que chaque thread se la partage en deux (chaque thread à ainsi sa propre heap qu'il accède via une variable globale définit par l'attribut __thread). Tout est créée dans la même pile et tout se compacte à la fin d'un coup.
Le GC (Garbash Collector) est désactivé lors d'un block paralléle.
Simple, pas très élégant, ... et ne fonctionne pas du tout !

L’algorithme de divide & conquer épuise rapidement la pile de 10 Go (à chaque étape on perd la moitié du restant de la pile, ce qui fait que rapidement il ne reste rien).
On abandonne donc cette mauvaise idée.

2) seconde version.
Pour cette version, toutes les allocations se font au sein de la pile algébrique donc l'accès à plusieurs thread est autorisé. Afin d'optimiser les performances (et éviter le mutex !), j'ai utilisé le add atomic du C11 atomic_fetch_add (ou __sync_fetch_and_add pour les gnuismes). La pile est augmenté de facon atomique et chaque thread à son alloc qui va bien. Par contre, le free a été supprimé - seul un GC permet de récupérer les données - et le realloc modifié pour toujours réallouer de la mémoire.
Je suis arrivé à la faire fonctionner, mais elle a un défault : elle consomme 3x plus de mémoire qu'avant (et est bien plus lente) !

3) seconde version améliorée.
Pour celle-ci, j'ai modifié le realloc pour faire un spéculative realloc sur la pile (et si ca marche pas, on réalloue tout et on perd un peu de place pour rien), e qui donne: MAY_INLINE void *MAY_REALLOC(void *x, size_t o, size_t n) { size_t n_a = MAY_ALIGNED_SIZE (n); if (MAY_UNLIKELY (o >= n)) return x; size_t o_a = MAY_ALIGNED_SIZE (o), diff = n_a - o_a; char *old_top, *tmp; if (may_c.Heap.current_mark <= (char*) x && (old_top = may_c.Heap.top) == (char*)(x+o_a) && (tmp = MAY_ATOMIC_ADD (may_c.Heap.top, diff)) && tmp == old_top && tmp + diff < may_c.Heap.limit) return x; else return memcpy (MAY_ALLOC(n_a), x, o); }
Avec cette modification, la consommation mémoire revient à un niveau raisonnable et le MT aide bien les calculs :
Single Thread:

./t-pika "(1+(x+y+z+t+1)^20)*(1+x+y+z+t)^20" -oexpand > /dev/null
CPU time=6320ms  

Two Thread:

./t-pika "(1+(x+y+z+t+1)^20)*(1+x+y+z+t)^20" -oexpand > /dev/null
CPU time=4591ms  

Par contre, on a des régressions sur les temps sans MT du fait que l'allocation est bien plus lente (et oui un atomic_add nécessite de faire un flush cache...):

MAY V0.7.4 (GMP V5.0.5 MPFR V3.1.0 CC=gcc CFLAGS=-fexceptions -O3 -fomit-frame-pointer -funroll-loops -ffast-math -march=native -ffunction-sections -fdata-sections -static -flto -ffat-lto-objects -DMAY_USE_THREAD)
Start -- Base:0x24ea000 Top:0x24f2130 Used:33072 MaxUsed:33072 Max:10737418240
Construct (3*(a*x+b*y+c*z) with a=1/2, b=2/3 and c=4/5...0.00296ms [337837 execs/sec]
eval (sum ai*ai*ai) - quite different - N=100......0.01ms
eval (sum ai*ai*ai) -  quite similar  - N=100......0.01ms
eval (sum ai*ai*ai) - quite different - N=1000......0.08ms
eval (sum ai*ai*ai) -  quite similar  - N=1000......0.08ms
eval (sum ai*ai*ai) - quite different - N=10000......1.25ms
eval (sum ai*ai*ai) -  quite similar  - N=10000......1.50ms
eval (sum ai*ai*ai) - quite different - N=100000......56.00ms
eval (sum ai*ai*ai) -  quite similar  - N=100000......60.00ms
eval (sum ai*ai*ai) - quite different - N=1000000......687.00ms
eval (sum ai*ai*ai) -  quite similar  - N=1000000......831.00ms
eval(sum(i*x^i, n=0..20000)...14ms
eval(x+f(x)+f(f(x))+...+f(5000)(x)), subs f to id...532ms
eval(sum(i,i=0..20000)+x+sum(i,i=0..20000))...3ms
eval(sum(sin(n*PI/6), n=0..20000)...28ms
eval((2+3*I/4)^1000000)...191ms
evalf(sin(1+PI)^2+3^sqrt(1+PI^2)) to 100000 bits...139ms
expand ((a0+...a500)^2), replace a0, reeval...634ms
expand ((x0+...x2+1)^16*(1+(x0+...x2+1)^16))...40ms
expand ((x0+...x3+1)^20*(1+(x0+...x3+1)^20))...4427ms
expand ((x+y^400000000000+z)^20*(1+x+y+z^-1)^20)...830ms
expand ((1+x)^1000*(2+x)^1000)...304ms
expand ((17+x)^600*(42+x)^600)...250ms
expand ((1+sqrt(5))^65000)...3ms
expand ((1+x+y)^500)...562ms
expand (expand((1+x)^50*(1+y)^50) * expand((1-x)^50*(2-y)^50))...88ms
expand (expand((a+b+c+d+e+f+g+h)^5) * expand((a+b+c+d+e+f+g+h)^5))...622ms
expand ((1+x+...+x^65535)*(1+2*x+x^2+...+x^65535))...7897ms
divide ( (1+x)^1000+1 , (1-x)^500, x)...230ms
divide ( (1+x)^1000+1 , x^3-5*x+17, x)...3ms
divide ( (1+x+y^2)^50+1 , (1-x)^25+y, x)...23ms
divide ( (1+x+y^2)^25+1 , x^3*y-5*x*y^42+17*y+1, x)...3ms
divide ( (1+x+y^2)^50+1 , (1-x)^25+y, {x,y})...823ms
divide ( (1+x+y^2)^25+1 , x^3*y-5*x*y^42+17*y+1, {x,y})...1159ms
       gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...2ms
expand+gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...8ms
       gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...5ms
expand+gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...4ms
       gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...5ms
expand+gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...1750ms
       gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...0ms
expand+gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...2ms
       gcd ( (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^4*(3*x.. , (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^3*(3*x.. )...1ms
expand+gcd ( (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^4*(3*x.. , (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^3*(3*x.. )...58ms
       gcd ( (x^2-y^2)*(a+b)^10 , (x-y)*(a-c)^10 )...1ms
expand+gcd ( (x^2-y^2)*(a+b)^10 , (x-y)*(a-c)^10 )...1ms
       gcd ( (x-y)^50+a , (x+y)^50 )...1ms
expand+gcd ( (x-y)^50+a , (x+y)^50 )...0ms
       gcd ( -2107-7967*x+19271*x^50+551*x^49-39300*x^48+236.. , -2401-3773*x-9484*x^50-4086*x^49-31296*x^48-216.. )...2ms
       gcd ( -1368+2517*x-62928*x^500+126728*x^499-139637*x^.. , -6336-11784*x+4932*x^500+50975*x^499+97099*x^49.. )...193ms
       gcd ( 3772-5709*x-28359*x^500+38352*x^499-18303*x^498.. , -3680-4456*x+90816*x^500+35952*x^499+89870*x^49.. )...779ms
Compute GCD in Z/181Z
       gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...2ms
expand+gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...11ms
       gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...15ms
expand+gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...14ms
       gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...7ms
expand+gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...1926ms
       gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...2ms
expand+gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...27ms
Compute GCD in Z/43051Z
       gcd ( -936639990+26248623452*x^47-30174373832*x^46-19.. , 1882371920-30937311949*x^47+6616907060*x^46-742.. )...16ms
       gcd ( -96986421453*x^426-75230349764*x^425+1282023978.. , 13695560229*x^426+16181971852*x^425-90237548124.. )...1597ms
       gcd ( 138233755629*x^426-22168686741*x^425-6531403218.. , -12298243395*x^426-33246261919*x^425+1488121621.. )...6880ms
GCDFT1: gcd = 1 (n=14)...109ms
GCDFT2: gcd of linearly dense quartic inputs with quadratic GCDs (n=7)...63ms
GCDFT3: gcd of sparse inputs where degree // to #vars (n=4)...30ms
GCDFT4: gcd of sparse inputs where degree // to #vars (second) (n=4)...17ms
GCDFT5: gcd quadratic non-monic with other quadratic factors (n=6)...8ms
GCDFT7: gcd completly dense non-monic quadratic inputs (n=8)...1628ms
GCDFT8: gcd sparse non-monic quadratic inputs with linear gcds (n=10)...32ms
GCDFT9: trivariate inputs with increasing degrees (n=17)...1ms
GCDFT10: trivariate polynomials whose GCD has common factors with cofactors (j=7,k=11)...78ms
diff ( x/(1+sin(x^(y+x^2)))^2 , x)...0.00097ms
R1: f(f(...) with f(z)=sqrt(1/3)*z^2 + i/3 and n=17...462ms
R2: hermite(25,y)...899ms
R6: sum(((x+sin(i))/x+(x-sin(i))/x) for n=100000...1965ms
R7: 100000 random float eval of x^24+34*x^12+45*x^3+9*x^18 +34*x^10+ 32*x^21...772ms
R8:right(x^2,0,5,100000) ...168ms
S2:expand((x^sin(x) + y^cos(y) - z^(x+y))^500) ...626ms
S3:diff(expand((x^y + y^z + z^x)^500,x) ...2393ms
S4:series(sin(x)*cos(x),x=0,500) ...198ms
series(tan(2+x),x=0,100) ...2400ms
Rationalize nested expression 1 ...464ms
Rationalize sum((i*y*t^i)/(y+i*t)^i),i=1..10 ...625ms
Rationalize sum((i*y*t^i)/(y+abs(5-i)*t)^i),i=1..10 ...62ms
End -- Base:0x24ea000 Top:0x24f2170 Used:33136 MaxUsed:796873120 Max:10737418240
Total time 46709ms

alors qu'en classique on a:

MAY V0.7.4 (GMP V5.0.5 MPFR V3.1.0 CC=gcc CFLAGS=-fexceptions -O3 -fomit-frame-pointer -funroll-loops -ffast-math -march=native -ffunction-sections -fdata-sections -static -flto -ffat-lto-objects)
Start -- Base:0x1390000 Top:0x1398130 Used:33072 MaxUsed:33072 Max:10737418240
Construct (3*(a*x+b*y+c*z) with a=1/2, b=2/3 and c=4/5...0.00181ms [551470 execs/sec]
eval (sum ai*ai*ai) - quite different - N=100......0.01ms
eval (sum ai*ai*ai) -  quite similar  - N=100......0.01ms
eval (sum ai*ai*ai) - quite different - N=1000......0.10ms
eval (sum ai*ai*ai) -  quite similar  - N=1000......0.10ms
eval (sum ai*ai*ai) - quite different - N=10000......1.71ms
eval (sum ai*ai*ai) -  quite similar  - N=10000......1.50ms
eval (sum ai*ai*ai) - quite different - N=100000......56.00ms
eval (sum ai*ai*ai) -  quite similar  - N=100000......56.00ms
eval (sum ai*ai*ai) - quite different - N=1000000......692.00ms
eval (sum ai*ai*ai) -  quite similar  - N=1000000......792.00ms
eval(sum(i*x^i, n=0..20000)...4ms
eval(x+f(x)+f(f(x))+...+f(5000)(x)), subs f to id...516ms
eval(sum(i,i=0..20000)+x+sum(i,i=0..20000))...4ms
eval(sum(sin(n*PI/6), n=0..20000)...20ms
eval((2+3*I/4)^1000000)...184ms
evalf(sin(1+PI)^2+3^sqrt(1+PI^2)) to 100000 bits...140ms
expand ((a0+...a500)^2), replace a0, reeval...544ms
expand ((x0+...x2+1)^16*(1+(x0+...x2+1)^16))...52ms
expand ((x0+...x3+1)^20*(1+(x0+...x3+1)^20))...6388ms
expand ((x+y^400000000000+z)^20*(1+x+y+z^-1)^20)...724ms
expand ((1+x)^1000*(2+x)^1000)...304ms
expand ((17+x)^600*(42+x)^600)...248ms
expand ((1+sqrt(5))^65000)...0ms
expand ((1+x+y)^500)...500ms
expand (expand((1+x)^50*(1+y)^50) * expand((1-x)^50*(2-y)^50))...148ms
expand (expand((a+b+c+d+e+f+g+h)^5) * expand((a+b+c+d+e+f+g+h)^5))...492ms
expand ((1+x+...+x^65535)*(1+2*x+x^2+...+x^65535))...7737ms
divide ( (1+x)^1000+1 , (1-x)^500, x)...164ms
divide ( (1+x)^1000+1 , x^3-5*x+17, x)...0ms
divide ( (1+x+y^2)^50+1 , (1-x)^25+y, x)...16ms
divide ( (1+x+y^2)^25+1 , x^3*y-5*x*y^42+17*y+1, x)...4ms
divide ( (1+x+y^2)^50+1 , (1-x)^25+y, {x,y})...616ms
divide ( (1+x+y^2)^25+1 , x^3*y-5*x*y^42+17*y+1, {x,y})...916ms
       gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...0ms
expand+gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...8ms
       gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...4ms
expand+gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...8ms
       gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...0ms
expand+gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...1528ms
       gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...0ms
expand+gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...4ms
       gcd ( (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^4*(3*x.. , (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^3*(3*x.. )...0ms
expand+gcd ( (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^4*(3*x.. , (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^3*(3*x.. )...48ms
       gcd ( (x^2-y^2)*(a+b)^10 , (x-y)*(a-c)^10 )...0ms
expand+gcd ( (x^2-y^2)*(a+b)^10 , (x-y)*(a-c)^10 )...0ms
       gcd ( (x-y)^50+a , (x+y)^50 )...0ms
expand+gcd ( (x-y)^50+a , (x+y)^50 )...0ms
       gcd ( -2107-7967*x+19271*x^50+551*x^49-39300*x^48+236.. , -2401-3773*x-9484*x^50-4086*x^49-31296*x^48-216.. )...0ms
       gcd ( -1368+2517*x-62928*x^500+126728*x^499-139637*x^.. , -6336-11784*x+4932*x^500+50975*x^499+97099*x^49.. )...128ms
       gcd ( 3772-5709*x-28359*x^500+38352*x^499-18303*x^498.. , -3680-4456*x+90816*x^500+35952*x^499+89870*x^49.. )...500ms
Compute GCD in Z/181Z
       gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...4ms
expand+gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...8ms
       gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...12ms
expand+gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...12ms
       gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...4ms
expand+gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...1404ms
       gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...0ms
expand+gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...16ms
Compute GCD in Z/43051Z
       gcd ( -936639990+26248623452*x^47-30174373832*x^46-19.. , 1882371920-30937311949*x^47+6616907060*x^46-742.. )...12ms
       gcd ( -96986421453*x^426-75230349764*x^425+1282023978.. , 13695560229*x^426+16181971852*x^425-90237548124.. )...1128ms
       gcd ( 138233755629*x^426-22168686741*x^425-6531403218.. , -12298243395*x^426-33246261919*x^425+1488121621.. )...4816ms
GCDFT1: gcd = 1 (n=14)...108ms
GCDFT2: gcd of linearly dense quartic inputs with quadratic GCDs (n=7)...52ms
GCDFT3: gcd of sparse inputs where degree // to #vars (n=4)...24ms
GCDFT4: gcd of sparse inputs where degree // to #vars (second) (n=4)...16ms
GCDFT5: gcd quadratic non-monic with other quadratic factors (n=6)...4ms
GCDFT7: gcd completly dense non-monic quadratic inputs (n=8)...1357ms
GCDFT8: gcd sparse non-monic quadratic inputs with linear gcds (n=10)...28ms
GCDFT9: trivariate inputs with increasing degrees (n=17)...0ms
GCDFT10: trivariate polynomials whose GCD has common factors with cofactors (j=7,k=11)...60ms
diff ( x/(1+sin(x^(y+x^2)))^2 , x)...0.00066ms
R1: f(f(...) with f(z)=sqrt(1/3)*z^2 + i/3 and n=17...456ms
R2: hermite(25,y)...632ms
R6: sum(((x+sin(i))/x+(x-sin(i))/x) for n=100000...1772ms
R7: 100000 random float eval of x^24+34*x^12+45*x^3+9*x^18 +34*x^10+ 32*x^21...736ms
R8:right(x^2,0,5,100000) ...148ms
S2:expand((x^sin(x) + y^cos(y) - z^(x+y))^500) ...524ms
S3:diff(expand((x^y + y^z + z^x)^500,x) ...1916ms
S4:series(sin(x)*cos(x),x=0,500) ...192ms
series(tan(2+x),x=0,100) ...2900ms
Rationalize nested expression 1 ...364ms
Rationalize sum((i*y*t^i)/(y+i*t)^i),i=1..10 ...616ms
Rationalize sum((i*y*t^i)/(y+abs(5-i)*t)^i),i=1..10 ...56ms
End -- Base:0x1390000 Top:0x1398170 Used:33136 MaxUsed:983431120 Max:10737418240
Total time 42900ms

On a des régressions en performances... qui sont dommages et en plus le GC est toujours désactivé pendant le MT, ce qui fait que certains algorithmes peuvent prendre beaucoup plus de mémoire...
(J'ai oubliais de dire : si on compile sans le support MT, on a effectivement pas de regresssion et çà, c'est bien ).

J'aillais me dire merde, il me faut bien une heap séparée pour chaque thread, mais comment faire ?

4) Troisième version:
Chaque thread a sa heap séparée. Mais lorsqu'il a finit son travail, sa heap est donnée au GC pour qu'il la supprime en temps et en heure (au prochain GC impliquant la marque enregistrée lors du point de synchro), et il s'en créée une autre en attendant.
Cette méthode ne va pas consommer de mémoire réelle en plus, par contre, elle va consommer beaucoup plus de mémoires virtuelles...
Un autre problème est que le GC devient plus complexe: il doit déterminer si un bout de mémoire appartient à une heap qui va être libéré ou pas (ce n'est pas compliqué mais ca prend du temps!)
(Je vous passe tous les détails sordibes de mise au point, de bugs aléatoires, et de crise de nerf sur le débuggage du truc).
Passons au test:
Single Thread:

/t-pika "(1+(x+y+z+t+1)^20)*(1+x+y+z+t)^20" -oexpand > /dev/null
CPU time=6352ms  

Multi-Thread:

./t-pika "(1+(x+y+z+t+1)^20)*(1+x+y+z+t)^20" -oexpand > /dev/null
CPU time=4454ms  

Ok ca marche bien !
On consomme effectivement pas mal en virtuel: 395Go virtualisé mais seulement 84Mo alloué.

Et la campagne complète n'a pas de regression:

MAY V0.7.4 (GMP V5.0.5 MPFR V3.1.0 CC=gcc CFLAGS=-fexceptions -O3 -fomit-frame-pointer -funroll-loops -ffast-math -march=native -ffunction-sections -fdata-sections -static -flto -ffat-lto-objects -DMAY_WANT_THREAD)
Start -- Base:0x1ae3000 Top:0x1aeb130 Used:33072 MaxUsed:33072 Max:10737422335
Construct (3*(a*x+b*y+c*z) with a=1/2, b=2/3 and c=4/5...0.00232ms [430416 execs/sec]
eval (sum ai*ai*ai) - quite different - N=100......0.02ms
eval (sum ai*ai*ai) -  quite similar  - N=100......0.02ms
eval (sum ai*ai*ai) - quite different - N=1000......0.08ms
eval (sum ai*ai*ai) -  quite similar  - N=1000......0.08ms
eval (sum ai*ai*ai) - quite different - N=10000......1.25ms
eval (sum ai*ai*ai) -  quite similar  - N=10000......1.25ms
eval (sum ai*ai*ai) - quite different - N=100000......53.00ms
eval (sum ai*ai*ai) -  quite similar  - N=100000......56.00ms
eval (sum ai*ai*ai) - quite different - N=1000000......680.00ms
eval (sum ai*ai*ai) -  quite similar  - N=1000000......810.00ms
eval(sum(i*x^i, n=0..20000)...10ms
eval(x+f(x)+f(f(x))+...+f(5000)(x)), subs f to id...516ms
eval(sum(i,i=0..20000)+x+sum(i,i=0..20000))...2ms
eval(sum(sin(n*PI/6), n=0..20000)...24ms
eval((2+3*I/4)^1000000)...183ms
evalf(sin(1+PI)^2+3^sqrt(1+PI^2)) to 100000 bits...139ms
expand ((a0+...a500)^2), replace a0, reeval...554ms
expand ((x0+...x2+1)^16*(1+(x0+...x2+1)^16))...35ms
expand ((x0+...x3+1)^20*(1+(x0+...x3+1)^20))...4472ms
expand ((x+y^400000000000+z)^20*(1+x+y+z^-1)^20)...702ms
expand ((1+x)^1000*(2+x)^1000)...302ms
expand ((17+x)^600*(42+x)^600)...255ms
expand ((1+sqrt(5))^65000)...2ms
expand ((1+x+y)^500)...502ms
expand (expand((1+x)^50*(1+y)^50) * expand((1-x)^50*(2-y)^50))...115ms
expand (expand((a+b+c+d+e+f+g+h)^5) * expand((a+b+c+d+e+f+g+h)^5))...490ms
expand ((1+x+...+x^65535)*(1+2*x+x^2+...+x^65535))...7787ms
divide ( (1+x)^1000+1 , (1-x)^500, x)...151ms
divide ( (1+x)^1000+1 , x^3-5*x+17, x)...2ms
divide ( (1+x+y^2)^50+1 , (1-x)^25+y, x)...16ms
divide ( (1+x+y^2)^25+1 , x^3*y-5*x*y^42+17*y+1, x)...3ms
divide ( (1+x+y^2)^50+1 , (1-x)^25+y, {x,y})...597ms
divide ( (1+x+y^2)^25+1 , x^3*y-5*x*y^42+17*y+1, {x,y})...888ms
       gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...2ms
expand+gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...7ms
       gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...5ms
expand+gcd ( (1+2*x)^200*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...4ms
       gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...3ms
expand+gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...1533ms
       gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...0ms
expand+gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...2ms
       gcd ( (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^4*(3*x.. , (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^3*(3*x.. )...1ms
expand+gcd ( (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^4*(3*x.. , (7*y*x^2*z^2-3*x*y*z+11*(x+1)*y^2+5*z+1)^3*(3*x.. )...49ms
       gcd ( (x^2-y^2)*(a+b)^10 , (x-y)*(a-c)^10 )...2ms
expand+gcd ( (x^2-y^2)*(a+b)^10 , (x-y)*(a-c)^10 )...1ms
       gcd ( (x-y)^50+a , (x+y)^50 )...0ms
expand+gcd ( (x-y)^50+a , (x+y)^50 )...0ms
       gcd ( -2107-7967*x+19271*x^50+551*x^49-39300*x^48+236.. , -2401-3773*x-9484*x^50-4086*x^49-31296*x^48-216.. )...2ms
       gcd ( -1368+2517*x-62928*x^500+126728*x^499-139637*x^.. , -6336-11784*x+4932*x^500+50975*x^499+97099*x^49.. )...128ms
       gcd ( 3772-5709*x-28359*x^500+38352*x^499-18303*x^498.. , -3680-4456*x+90816*x^500+35952*x^499+89870*x^49.. )...506ms
Compute GCD in Z/181Z
       gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...3ms
expand+gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42) )...8ms
       gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...11ms
expand+gcd ( (1+2*x)^400*(x^3+2*x^2+1) , (1+2*x)^42*(x^3-2*x+42)+1 )...10ms
       gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...5ms
expand+gcd ( (1+2*x+y)^100*(x^3+2*x^2*y+1) , (1+2*x+y)^42*(x^3-2*x+42) )...1428ms
       gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...2ms
expand+gcd ( (x^2-3*x*y+y^2)^4*(3*x-7*y+2)^5 , (x^2-3*x*y+y^2)^3*(3*x-7*y-2)^6 )...20ms
Compute GCD in Z/43051Z
       gcd ( -936639990+26248623452*x^47-30174373832*x^46-19.. , 1882371920-30937311949*x^47+6616907060*x^46-742.. )...11ms
       gcd ( -96986421453*x^426-75230349764*x^425+1282023978.. , 13695560229*x^426+16181971852*x^425-90237548124.. )...1138ms
       gcd ( 138233755629*x^426-22168686741*x^425-6531403218.. , -12298243395*x^426-33246261919*x^425+1488121621.. )...4823ms
GCDFT1: gcd = 1 (n=14)...106ms
GCDFT2: gcd of linearly dense quartic inputs with quadratic GCDs (n=7)...55ms
GCDFT3: gcd of sparse inputs where degree // to #vars (n=4)...23ms
GCDFT4: gcd of sparse inputs where degree // to #vars (second) (n=4)...14ms
GCDFT5: gcd quadratic non-monic with other quadratic factors (n=6)...7ms
GCDFT7: gcd completly dense non-monic quadratic inputs (n=8)...1395ms
GCDFT8: gcd sparse non-monic quadratic inputs with linear gcds (n=10)...29ms
GCDFT9: trivariate inputs with increasing degrees (n=17)...1ms
GCDFT10: trivariate polynomials whose GCD has common factors with cofactors (j=7,k=11)...64ms
diff ( x/(1+sin(x^(y+x^2)))^2 , x)...0.00066ms
R1: f(f(...) with f(z)=sqrt(1/3)*z^2 + i/3 and n=17...457ms
R2: hermite(25,y)...669ms
R6: sum(((x+sin(i))/x+(x-sin(i))/x) for n=100000...1768ms
R7: 100000 random float eval of x^24+34*x^12+45*x^3+9*x^18 +34*x^10+ 32*x^21...663ms
R8:right(x^2,0,5,100000) ...150ms
S2:expand((x^sin(x) + y^cos(y) - z^(x+y))^500) ...523ms
S3:diff(expand((x^y + y^z + z^x)^500,x) ...2119ms
S4:series(sin(x)*cos(x),x=0,500) ...189ms
series(tan(2+x),x=0,100) ...2335ms
Rationalize nested expression 1 ...367ms
Rationalize sum((i*y*t^i)/(y+i*t)^i),i=1..10 ...619ms
Rationalize sum((i*y*t^i)/(y+abs(5-i)*t)^i),i=1..10 ...59ms
End -- Base:0x1ae3000 Top:0x1aeb170 Used:33136 MaxUsed:386605624 Max:10737422335
Total time 40630ms

C'est bien, pas de regression, et je vais plus vite.
Vous me direz, seulement 2s de gagner ? Oui mais j'ai pas converti grand chose en //. Seul expand dans certains cas, parallélise les données. Donc c'est encourangeant !
(Note: j'ai pas encore géré les exceptions dans le code // : je sens la prise de tête).

Quelle est la suite ?
- Trouver les endroits où je peux paralléliser.
- débugger le reste du code.

Merci de votre lecture !

Quelle est la licence de ton truc? J'aimerais bien le porter sur un RTOS.
Par contre ca me demandera de ruser niveau allocs, pas de MMU et pas moyen de reserver des gigas

(Mon post n'a pas été posté, je ne sais pas pourquoi. Donc je le retape).
Tu parles de quoi ? De MAYLIB ou juste du système de thread ? Les deux sont sous LGPLv3 mais le système de thread est trivial.
Pour info, je rappelle que MAYLIB compile pour PedroM sans problème, et sans fonctionne bien sous TI
Les tera de mémoire virtuelles sont nécessaires juste en multi-thread, pas en mode single-thread

Ah "dommage" le truc que je visais est BSD.

Mais pour une appli c'est pas grave, en fait.

Ce serait sur un stm32 avec 128k de ram et 512k de rom, une carte nucleo f411.

Je pense que ca pourrait etre bien fun effectivement

128 k de RAM devrait être suffisant pour faire des trucs.
J'ai peur pour 512K de ROM. C'est peu Je crois que ca passerait juste, mais très juste.

je prepare un module stm32 avec 2M de ROM.

Pas moyen de desactiver des routines ?

Fin bref c'est pas le sujet; ton machin de parallelisation est juste impressionnant.

squalyl (./7) :
Pas moyen de desactiver des routines ?

on peut toujours en désactiver.

squalyl (./7) :
Fin bref c'est pas le sujet; ton machin de parallelisation est juste impressionnant.

Merci.

Mais quel boulot de furax, bravo pour la persévérance et les améliorations ^^
Faut maitriser tout de bout en bout dans ce genre de projet : le langage, son préproc, les maths pures, la compilation, la gestion de la mémoire, l'OS, bref, chapeau pour la jolie combinaison de tout ça.
Si c'est pas indiscret, tu fais ça dans quel cadre ? Pro ou perso ?

Merci.
Mais c'est encore loin d'être parfait. Je ne suis pas encore satisfait de la structure de donnée, il me reste à implanter d'autres structures de données plus rapides, et tous les algorithmes qui manquent (matrice, factorisation, limite, ....)
Je fais çà perso. Pour le boulot, je fais des trucs bien moins poussé techniquement.

PpHd (./1) :
Elle a un inconvénient : elle génère une nested function (comme ont dit dans le milieu) qui n'est supporté que par GCC et ICC (clang ne le supporte pas) et utilise l'extension typeof.Par contre, elle ne génère pas de trampoline (ce qui fait que la stack n'est pas marquée comme exécutable, donc pas de faille de sécurité) car toutes les variables locales sont recopiés dans une structure interne permettant de passer en paramètre les données à la fonction.

C'est malheureusement faux. Si, ce code génère un trampoline! (J'ai vérifié, et au moins "gcc (GCC) 4.1.2 20060728 (prerelease) (TIGCC 4.1.2-pre9)" insère un appel à __trampoline_offset, comme attendu. Et le code crée bien un trampoline sur la pile:

	lea (12,%sp),%a2
	lea (16,%sp),%a3
	move.w #8316,(%a3)
	move.l %a2,18(%sp)
	move.w #20217,22(%sp)
	move.l #subfunc_2.3518,24(%sp)
[...]
	jbsr __trampoline_offset
	move.l %a2,-(%sp)
	pea (%a3,%d0.l)
	jbsr may_spawn

Il n'y a pas de push de b parce que j'en ai fait une structure vide pour le test.)

GCC crée toujours un trampoline quand tu prends l'adresse d'une "nested function", et ici la prise d'adresse est implicite par la conversion implicite en pointeur de fonction lors du passage d'argument. C'est ce trampoline qui passe l'emplacement de ta structure f (ou plus généralement des variables locales) à subfunc_2.

Et pour voir si un binaire GNU/Linux a besoin d'une pile exécutable:
readelf -l libfoo.so | grep GNU_STACK
ou:
eu-readelf -l libfoo.so | grep GNU_STACK
Regarde s'il y a la permission E là-dedans (RWE vs. RW).

J'ai essayé avec GCC 4.7 et GCC 4.9, et je n'obtiens pas de pile exécutable dans ce cas là: struct fib2_s { int n; int x; }; void may_spawn(void (*)(void*), void*); int fib(int n) { if (n < 2) return n; struct fib2_s f; f.n = n - 2; void subfunc_2 (void *data) { struct fib2_s *f = data; f->x = fib(f->n); } may_spawn (subfunc_2, &f); int y = fib (n-1); return f.x + y; }

Code ASM généré: .file "nested.c" .section .text.unlikely,"ax",@progbits .LCOLDB0: .text .LHOTB0: .p2align 4,,15 .globl fib .type fib, @function fib: .LFB0: .cfi_startproc cmpl $1, %edi jle .L2 jmp fib.part.0 .p2align 4,,10 .p2align 3 .L2: movl %edi, %eax ret .cfi_endproc .LFE0: .size fib, .-fib .section .text.unlikely .LCOLDE0: .text .LHOTE0: .section .text.unlikely .LCOLDB1: .text .LHOTB1: .p2align 4,,15 .type fib.part.0, @function fib.part.0: .LFB2: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 leal -2(%rdi), %eax movl %edi, %ebx movl $subfunc_2.1754, %edi subq $16, %rsp .cfi_def_cfa_offset 32 movq %rsp, %rsi movl %eax, (%rsp) call may_spawn leal -1(%rbx), %edi call fib addl 4(%rsp), %eax addq $16, %rsp .cfi_def_cfa_offset 16 popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE2: .size fib.part.0, .-fib.part.0 .section .text.unlikely .LCOLDE1: .text .LHOTE1: .section .text.unlikely .LCOLDB2: .text .LHOTB2: .p2align 4,,15 .type subfunc_2.1754, @function subfunc_2.1754: .LFB1: .cfi_startproc pushq %rbx .cfi_def_cfa_offset 16 .cfi_offset 3, -16 movl (%rdi), %eax movq %rdi, %rbx cmpl $1, %eax jle .L7 movl %eax, %edi call fib.part.0 .L7: movl %eax, 4(%rbx) popq %rbx .cfi_def_cfa_offset 8 ret .cfi_endproc .LFE1: .size subfunc_2.1754, .-subfunc_2.1754 .section .text.unlikely .LCOLDE2: .text .LHOTE2: .ident "GCC: (GNU) 4.9.1" .section .note.GNU-stack,"",@progbits
(Et GCC génère du code spécial pour ne pas créer de stack frame si on est dans le début de la fonction )

Ah, je n'étais pas sûr si GCC était suffisamment malin pour ça ou non, donc j'ai préféré te laisser essayer toi-même (connaissant ta curiosité ).

Là, la "nested function" n'accède pas aux variables locales de la fonction contenante parce que ta structure est passée en paramètre, donc du coup c'est comme si elle n'était pas "nested", et le trampoline n'est pas nécessaire.

Le vieux GCC de TIGCC fait de même (j'ai désactivé les informations de débogage pour avoir un .s plus propre):

	.section	.text.fib,"x"
	.even
	.globl	fib
fib:
	link.w %fp,#-4
	move.l %d3,-(%sp)
	move.w 8(%fp),%d3
	cmp.w #1,%d3
	jble .L4
	move.w %d3,%d0
	subq.w #2,%d0
	move.w %d0,-4(%fp)
	pea -4(%fp)
	pea subfunc_2.3518
	jbsr may_spawn
	subq.w #1,%d3
	move.w %d3,-(%sp)
	jbsr fib
	move.w %d0,%d3
	add.w -2(%fp),%d3
	lea (10,%sp),%sp
.L4:
	move.w %d3,%d0
	move.l -8(%fp),%d3
	unlk %fp
	rts
	.section	.text.subfunc_2.3518,"x"
	.even
subfunc_2.3518:
	move.l %a2,-(%sp)
	move.l 8(%sp),%a2
	move.w (%a2),-(%sp)
	jbsr fib
	move.w %d0,2(%a2)
	addq.l #2,%sp
	move.l (%sp)+,%a2
	rts

Kevin Kofler (./14) :
Le vieux GCC de TIGCC

Tiens d'ailleurs, il a pas été prévu un portage vers GCC 4.9, j'ai crû entendre parler de ça récemment, non ?

Théoriquement, mettre à jour le GCC de TIGCC est toujours sur mon TODO. En pratique, plus le temps passe, moins il est probable que ça se passe. Comme expliqué sur IRC, il faut compter environ 1-2 semaines de portage par version de GCC, de 4.1 à 4.9, ça fait 2 à 4 mois, temps que je n'ai actuellement pas, et de plus, ma motivation est limitée depuis l'écroulement de ma base d'utilisateurs et aussi le fameux fork.

À moins que ce ne soit ton projet à toi… Tu veux apprendre le C et le C++, avec GCC, tu apprendras forcément.