Discussion :

[buzzkaido]

Bonjour,

Dans un soft que je developpe actuellement, j'ai une section de code qui doit pouvoir s'excuter le plus rapidement possible.

Il s'agit d'un sequenceur musical.

Dans mon architecture, il y a un objet cSequencer qui contient :
- un buffer avec les evenements à traiter
- les parametres de timing
- un vecteur de "patterns" qui sont en cours de lecture, qui contient un vecteur des différentes pistes de ce pattern
- une fonction appellée très souvent qui sert à calculer le contenu du buffer.

Voici mon code (à peu près, je passe les détails)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class cSequencer
{
    void *buffer;
    int  paramTiming1;
    int  paramTiming2;
    int  paramTiming3;
    std::vector<cPattern*> vPatterns;
 
    void remplirBuffer();
}
 
class cPattern
{
    std::vector<cPiste*> vPistes;
    cSequencer *sequencer;           // pointeur vers le sequenceur
    void remplirBuffer();
}
 
class cPiste
{
    cPattern *pattern;           // pointeur vers le pattern
    void remplirBuffer();
}

Actuellement, j'ai ceci comme implémentation :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
void cSequencer::remplirBuffer()
{
    std::vector<cPattern*>::const_iterator It;
    for(It=vPatterns.begin();It!=vPatterns.end();It++)
        (*It)->remplirBuffer();
}
 
void cPattern::remplirBuffer()
{
    std::vector<cPiste*>::const_iterator It;
    for(It=vPistes.begin();It!=vPistes.end();It++)
        (*It)->remplirBuffer();
}
 
void cPiste::remplirBuffer()
{
    // On calcule le contenu du buffer, en utilisant les infos de timing :
 
    pattern->sequencer->paramTiming1;
    pattern->sequencer->paramTiming2;
    pattern->sequencer->paramTiming3;
 
    // Et on remplit le buffer situé à l'adresse pointée par :
    pattern->sequencer->buffer;
}

Questions :
-----------

1/ Est-il plus efficace de passer les variables paramTiming1,paramTiming2,paramTiming3,*buffer à chaque fonction remplirBuffer ou est-ce plus rapide de récuperer ces valeurs par pointeur comme je le fait actuellement ?

2/ Quel conteneur STL est le plus rapide pour parcourir toute sa liste par un itérateur ?

Merci !

[smashy]

je ne suis pas sure que tu constates des ameliorations quelconques en :

-changeant l acces au paramTiming (passage comme parametre de fonction ou acces par indirection)

-changeant le type de container.





Le type vector<> est le plus rapide pour l acces, mais l insertion peut forcer une reallocation+une recopie du contenu.

Le type list<> a un acces un peu plus lent (car l'indirection par pointeur next -> destruction du cache memoire), mais les insertion peuvent etre plus rapide :

La encore, ca depend :

-quand on ajoute un element dans une liste, il y a allocation d un nouveau maillon

-quand on ajoute un element dans un vecteur, et que le vecteur n est pas assez grand , il y a allocation de deux fois la memoire deja alloue (donc , plus le vecteur grandit , moins les allocations sont nombreuses)

Au final, le choix entre vector<> et list<> depend de l usage , et du cout d une recopie d un element (cas du vecteur)

Cependant, tu parcours tous les elements d un container en effectuant une operation a chaque fois, si cette operation est longue, ca ne sert pas a grand chose de chercher quelques pouillemes de microsecondes par le choix d un container.

Enfin, si au total tu n as que 3 entiers a utiliser (param...) , ca ne te coute pas forcement plus cher de les passer en parametres

note : dans ton code, quand tu fais

pattern->sequencer->paramTiming???

tu fais un deferencement qui va peut etre impliquer la destruction du cache memoire mais comme tu fais cet appels 3x sur des zones adjacentes, le cout est amortie.

donc meme remarque que les pouillemes de scondes

[poukill]

2/ Quel conteneur STL est le plus rapide pour parcourir toute sa liste par un itérateur ?

Merci !

Le vecteur... Mémoire contigüe, pas de liste chaînée...
Accès par un forward iterator est ce qu'il y aura de plus rapide je pense.
A vérifier avec d'autres avis...

[smashy]

absolument d accord

cependant, pour un cas plus general, si tu inseres souvent des elements tu risques de multiplier les allocations + recopie. Si tu en retires aussi, au bout d un moment tu n auras plus du tout de recopie (quand le buffer sera suffisamment grand pour absorber un flot d ajouts + suppressions)

Enfin, l ajout dans un vecteur<> invalide tout iterateur (pas pour une list<> normalement) donc attention :

class A { ... }

vector<A> v;

...

A * pa = &v[5];

v.push(A()); // <- le pointeur pa ne doit plus etre utilise !!!

[loufoque]

Pourquoi tu stockes des pointeurs et non des objets dans tes vecteurs ?

[buzzkaido]

Merci pour les nombreuses réponses !

Donc je garde mon système actuel...

Pour répondre à 2-3 choses :

- je fais essentiellement de la lecture (peu d'insertion/suppression)
- je stocke des pointeurs et non les objets directement car ces objets sont créés ailleurs (par un autre objet) et ne doivent pas necessairement etre detruits lorsqu'ils sont retirés du vecteur. Ca me parraissait donc plus logique de ne stocker que les pointeurs sur les objets qui m'interessent.

Autre question :
---------------

Le buffer que j'envoie est un tableau du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
sEvenement *buffer[n];

Cette structure m'est imposée par le SDK avec lequel je travaille.

Existe-t-il un moyen rapide et efficace de trier ce tableau ?
Je connait les algos du type QuickSort, mais je ne sais pas trop comment optimiser la deplacement d'un ou plusieurs éléments du tableau (pour en insérer un autre au milieu)

Vaut-il mieux utiliser une bête copie genre buffer[n] = buffer[n-1]; ?
Ou un appel à memcpy ?
Ou un container STL permet de faire ça (récuperer les données sous forme de tableau contigü ?

Je precise que sEvenement est une structure de 32 octets qui m'est imposée, elle aussi, par le SDK.

Encore merci !

[smashy]

en regle general, ne pas utiliser memcpy si c est pour copier autre chose que des buffers d'octets (i.e des objets par exemple) car la copie d un objet n est pas necessaire une copie octet par octet (redefinition de l operateur d affectation).

L insertion d un element au milieu d un buffer est une tres mauvaise idee : mieux vaut utiliser une liste dans ce cas.

sinon, dans la STL tu as quelquechose comme:

struct mycompare {

int operator(const sEvenement & src1,const sEvenement & src2){

...
}
};

std::sort(buffer,buffer + n,mycompare());

qui va faire un quick sort sur le buffer.

Si la copie d element est lourde, tu peux passer par un tableau temporaire qui contiendra les indices ..


int indices[] = { 0 ... n }; /* a initialiser proprement en C++ */

struct mycompare2 {

mycompare2(const sEvenement * e) : buf(e){}

int operator(int src1,int src2){

return compare(buf[src1],buf[src2]);
}

const sEvenement * buf
};

sort(indices,indices + n,mycompare2(buffer));
maintenant indices contient l ordre des elements dans buffer pour qu ils soient tries ... a toi de reordonne le buffer (tu a eviter un nombre de copie consequent de sEvenement))