QList vs List de STL

[alpha_one_x86]

Bonjour, j'ai des gros probléme de performance sur les QList, ça me prends 80% de mon temps cpu sur les QList::at() ou operator[].
J'aimerai donc passé sur les list de la STL pour gagner en performance. Quelqu'un as déjà fait des testes sur le sujet?
Je fait des .at(), insertion en fin de list, size, et clear.

Merci d'avance.

[dourouc05]

Les conteneurs Qt sont déjà pas mal optimisés, en général, bien que ce ne soit pas l'objectif premier. Les utilises-tu bien ? Tu forces peut-être la copie avec l'appel à at(), ce qui ralentirait déjà pas mal (principe du COW).

[alpha_one_x86]

Code: http://pastebin.com/y58rgEi6
Ligne 390, et surtout 460, c'est la ou les profiler me dise que c'est long.
Ensuite l'operateur[] semble appeller at() de QDataList ...

Je sais pas pourquoi, j'ai eu une grosse perte de performance de l'ordre de 1000 d'un coup.

[nosleduc]

La fonction at, il me semble vérifie à chaque fois si l'indice est correct.

Si vous utilisez QList avec l'opérateur [], vous pouvez donc utiliser un QVector.
Vous pouvez s'il vous voulez éviter les appels de fonction faire une énumération rapide du style

Code :

1
2
3
4
5
6
 
 
T * ptr = (myVector.count() ? myVector.data() : 0);
for(int i = 0, end = myVector.count(); i < end; ++i){
     ....
}

[alpha_one_x86]

Qt semble en interne beaucoup faire appelle à la glibc (un maj ne change rien), 80% de l'appelle à [] ou at est dans mcount et _mcount_internal de libc (packet glibc ici), libc-2.14.1.so _mcount.S et mount.c

[nosleduc]

ptr est donc un tableau, l'accès avec [] doit être plus rapide

[alpha_one_x86]

Je ne sais pas comment rajouté rapidement un entrée à la fin d'un tableau de pointeur (faut l'élargir dynamiquement? comment?).

EDIT: ça semble être realloc, bon je vais faire 3 implémentation, une en Qt, une en C++ avec liste, une en C.

Vous me conseillé quoi en C++, stl::vector, stl::list?

[Mat.M]

Envoyé par alpha_one_x86

Je sais pas pourquoi, j'ai eu une grosse perte de performance de l'ordre de 1000 d'un coup.

je ne connais pas Qt mais ce qu'il faut essayer c'est de fixer la taille de la liste à une taille initiale....parce que sinon la classe va réallouer de manière fréquente et la mémoire va se fragmenter.
Par exemple pour les classes MFC qui sont un peu équivalentes à Qt mais spécifiques à Microsoft le MSDN conseille explicitement de fixer une taille initiale pour les conteneurs comme CArray ou CList.
Donc je suggérrais dans faire autant pour QList

Before using an array, use SetSize to establish its size and allocate memory for it. If you do not use SetSize, adding elements to your array causes it to be frequently reallocated and copied. Frequent reallocation and copying are inefficient and can fragment memory.

Avec std::vector ou std::list tu risques d'avoir le même problème...

[alpha_one_x86]

Même probléme en préallouant, mais ça semble pas venir qu'un probléme de fragmentation mémoire.

En plus linux défragemente assez bien la mémoire, et j'ai pas de pression mémoire sur mon systéme.

[Jerome S]

http://qt.developpez.com/doc/4.7/qlist.html

const T & QList::at ( int i ) const

Returns the item at index position i in the list. i must be a valid index position in the list (i.e., 0 <= i < size()).

This function is very fast (constant time).

T & QList::operator[] ( int i )

Returns the item at index position i as a modifiable reference. i must be a valid index position in the list (i.e., 0 <= i < size()).

This function is very fast (constant time).

Les fonctions at et l'opérateur [] effectuent les mêmes choses. De plus, ils disent que la fonction est censée être rapide...

[alpha_one_x86]

Oui, c'est cencé étre rapide. Hors c'est pas le cas.

[ness522]

Ligne 460 :

Code :

to_send_map_management_move[moveClient_index].movement_list << moveClient_tempMov;

Si je comprend bien tu ajoutes "moveClient_tempMov" en fin d'une liste.
Je ne sais pas ce qu'est ce "moveClient_tempMov", mais ça ressemble à une structure qui va être recopiée dans la liste. Le temps à cet endroit dépend certainement plus de la copie de la structure (ou classe) que de l'ajout en fin de liste.

Peux-tu peut-être donner aussi la définition de tes structures et listes qui posent problème ?

[alpha_one_x86]

http://pastebin.com/ahWtC9Ni
et
http://pastebin.com/54YUXpXc
Mais la d'aprés le profiler c'est vraiment pour 75% du temps cpu le operator[] qui fait chier.

[Troudhyl]

Ça ne répondra pas à ta question (tu peux faire du profiling, profites-en pour nous éclairer ), mais :
- pourquoi utiliser QList au lieu de QMap ou QHash pour stocker des éléments avec un id, qui pourrait servir de clef ?
- tu dis que l'operateur[] est lent, mais tu l'utilises deux fois de suite pour attraper le même élément, au lieu de créer une seule fois une référence à cet élément.

Ensuite peut-être que tu peux étudier les autres possibilités offertes par Qt pour boucler (je ne peux pas t'en dire plus, peut-être QMutableListIterator ?).

Sinon, les résultats de vos recherches m'intéressent aussi, car je faisais confiance aux classes Qt pour être bien optimisées.

[ness522]

J'ai pas d'idée, l'opérateur [] te renvoie une référence modifiable, et travaille en temps constant, ce qui veut dire que le temps est le même quel que soit la taille de la liste !

Ca ne me semble donc pas être là que le bât blesse, j'ai pas d'expérience des profilers, sont-ils toujours précis pour ce genre de trucs (descendre si bas dans le raffinement des fonctions qui usent le CPU). J'aurais tendance à regarder à un plus haut niveau...

[alpha_one_x86]

Sous linux, apprement il compte le nombre d'entrée, 1) utilisation de mcount de libc, 2) le temps semble proportionnel à la taille de la liste
Je me trompe peu étre.

[Jerome S]

Ils disent que l'index doit être dans un range valide, donc ca signifie qu'ils ne le vérifient pas. Il n'y a donc pas de raison qu'il compte le nombre d'entrées...

[yan]

Question bête. Tu est bien en release?
Autre question, tu dit que ça prend 80%, mais si tu l'utilise partout, ce résultat n'est il pas logique?
Ne faut il pas plutôt regarder l’occupation CPU des méthodes qui l'appel?
Que fait ton bout de code qui pose problème?

Ca me semble être surtout un problème d’algorithme qui te génère trop de boucle sur ta liste.

[alpha_one_x86]

Je suis en debug. La suppression du flag: -pg améliore grandement les choses, passage de l'utilisation du cpu, de 100% à 10%, 7% en mode release, -march=native ne change rien

80% car dans l'algo c'est sur ces point que ça passe le plus.
Les grossees fonction sont: ClientMapManagement::moveThePlayer() et ClientMapManagement::moveClient(), maintenant passé à 90% de temps cpu

Le code qui pose probléme à un compléxité carré (je peu rien y faire, c'est la mise des déplacements des autres joueurs dans la liste du joueurs, et comme il faut le faire pour chaque joueurs...).
Mais bon, déjà viré 80% du temps cpu, aprés j'optimiserai le reste...
Et vu que la complexité et carré juste à cette endroit, j'aimerai optimisé un max ce bout de code.

[ness522]

Envoyé par alpha_one_x86

Je suis en debug.

...

bah oui là alors ça chaque accès au tableau est potentiellement vérifié par des Q_ASSERT, c'est donc beaucoup plus lent et pas très représentatif.