en l'occurence, c'est un "traitement de donnees massif". et le probleme en lui meme n'est pas particulierement bas-niveau, non...
pour un grand nombre 'n' d'elements, on doit sampler une spline qui comporte 'k' control-points.
n est entre le millier et la centaine de millier, mais pourrait etre plus grand.
k est >= 2, la plupart du temps, tourne autour de 3 ou 4, mais peut monter dans quelques rares cas a 10, 20, etc..
pour sampler cette spline, chaque element a un parametre 't' compris dans l'intervalle de temps des control-points de la spline.
en gros, pour chaque element, on doit trouver les deux control-points consecutifs de la spline dont l'intervalle contient 't'
chaque control-point a un parametre de temps 't' propre, une valeur associee, (et deux tangentes, mais c'est un detail).
en gros, on peut decomposer le probleme en deux parties, pour chaque element:
1- trouver les deux control-points
2- interpoler la spline entre ces deux control-points au niveau du parametre 't' de l'element, pour recuperer la bonne valeur.
sachant que les control-points de la spline ne sont pas espaces regulierement (leurs 't' consecutifs sont strictement croissants, mais d'intervalles differents.. genre { 0.0, 0.1, 0.8, 1.5, 1.51, 2.0 }
la solution algorithmiquement seduisante serait de faire un lower_bound sur le tableau de 't' des control-points (bon une recherche dichotomique quoi), qui donne O(log2(n)) en complexite.
tiens d'ailleurs, parenthese: pour les notations O(), on ignore les constantes, ok. est-ce que pour les log on ignore aussi la base? genre O(log2(n)) == O(log(n)) ?
bref or donc..
1- recherche rapide dans le tableau de 't' qui est trie, via un lower_bound -> recuperation des deux control-points, 'cp0' et 'cp1'
2- element.value = interpolate(cp0, cp1, (element.t - cp0.t) / (cp1.t - cp0.t));
ok. en connaissant mieux les donnees du probleme (notamment la distribution de 'k', le nombre de control-points), on peut supposer que pour de faibles valeurs (3 ou 4), ca sera plus performant d'utiliser une recherche lineaire simple. mais bon, c'est flou. et si on implemente a la main le lower_bound pour ce cas specifique, directement dans la boucle principale de traitement, on peut arriver a de meilleures perfs que la recherche lineaire a partir de k=4.. bref
sur x86, c'etait deja pas mal rapide. passage a une optim "bas niveau" sans changer d'algo: utiliser les intrinsics SSE pour faire un lower_bound qui cherche 4 elements a la fois -> de memoire (c'est ptet pas exactement ca, ca date d'il y a genre un an quand meme...) x3 en perfs pour la recherche seule (noye dans l'algo global, ca devait faire un poil moins de x2, genre x1.8, qqch comme ca.
bref. c'etait cool.
sauf que.. recemment, portage sur cell (PS3 / archi PPC) de la dite chose. architecture radicalement differente. tres mauvaise prediction de branchement. trash dramatique du pipeline fp et int, branches tres couteuses comparees a x86, dependances d'instructions a la pelle du au faible nombre de pipelines compare aux core2 et autres archis plus recentes.
la recherche des deux control-points seule prend PLUS DE 90% du temps, alors que sur x86 c'est l'inverse.
repasser a une recherche lineaire ameliore deja pas mal les perfs. mais c'est toujours assez lamentable.
u32 id = k - 2;
for (u32 i = 0; i < k - 1; i++)
{
if (cptimes[i + 1] > t)
break;
}
(bon le for d'au dessus, aussi anodin soit-il est a peu pres 2 fois plus lent sur l'archi cible qu'un autre for fait differemment avec un goto et sans l'init de 'id', mais, on va oublier ca, c'est du detail)
tu sais ce qui a bien fonctionne?
en epargnant les details et cas particuliers bas niveau, les PPC ont notamment une instruction fsel, qui fonctionne comme ca:
fsel(float x, float a, float b)
{
return (x >= 0) ? a : b;
}
et qui fait que ce genre d'expressions:
float y = (x >= 0) ? a : b;
se fait compiler (sous GCC en tout cas), en une seule instruction fsel.
si jamais a et b sont des int, ca casse tout, vu que ca genere des branches.
comment avoir un x60 sur les perfs de l'algo au dessus dans les cas les plus utilises ?
reponse:
4 versions du code, qui specialise 2, 3, 4, et n control-points. (rien n'empeche de specialiser pour 5 ou 6, evidemment, a part que dans ce cas precis, c'est des valeurs de 'k' assez rares, et la plateforme cible a pas non plus trop de memoire a perdre).
et ne pas faire de recherche, mais tester absolument _tous_ les control-points. meme ceux qui sont superieurs a t. pas d'early-out, rien:
exemple de ce que donnerait une version a 5 control points de l'algo:
float k0 = (t - cptimes[1]) >= 0 ? 1.0f : 0.0f;
float k1 = (t - cptimes[2]) >= 0 ? 1.0f : 0.0f;
float k2 = (t - cptimes[3]) >= 0 ? 1.0f : 0.0f;
u32 id = u32(k0 + k1 + k2);
const ControlPoint &cp0 = cp[id];
const ControlPoint &cp1 = cp[id + 1];
(bon en fait j'avoue avoir triche dans les chiffres...
le x60 en perfs, c'est pour la version a 2 control-points, ou il n'y a pas besoin de faire de recherche du tout
, le "vrai" gain pour la version a 4 control-points (la plus frequemment rencontree), n'est "que" de x18
)
le x60 en perfs, c'est pour la version a 2 control-points, ou il n'y a pas besoin de faire de recherche du tout 
, le "vrai" gain pour la version a 4 control-points (la plus frequemment rencontree), n'est "que" de x18 
)
et meme pas te rendre compte que ca pourrait etre largement mieux, juste parceque tu t'arrettes a "je vois pas comment ameliorer cet algo, c'est le mieux que je puisse trouver d'un point de vue haut niveau, sur le papier, il a la meilleure complexite". (le "tu" de la phrase precedente n'est pas a prendre comme "toi, bob", c'est un "tu" general 
)
)
)