Version imprimable
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.
:salut:
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).
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.
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:
2
3
4
5
6
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
ptr est donc un tableau, l'accès avec [] doit être plus rapide
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?
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.Citation:
Envoyé par alpha_one_x86
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
Avec std::vector ou std::list tu risques d'avoir le même problème...Citation:
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.
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.
http://qt.developpez.com/doc/4.7/qlist.html
Citation:
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).
Les fonctions at et l'opérateur [] effectuent les mêmes choses. De plus, ils disent que la fonction est censée être rapide...Citation:
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).
Oui, c'est cencé étre rapide. Hors c'est pas le cas.
Ligne 460 :
Si je comprend bien tu ajoutes "moveClient_tempMov" en fin d'une liste.Code:to_send_map_management_move[moveClient_index].movement_list << moveClient_tempMov;
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 ?
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.
Ç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.
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...
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.
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...
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.
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.
...Citation:
Envoyé par alpha_one_x86
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.
La différence entre debug et release est de 30%...
Donc, ce n'est pas le at ou [] qui pose problème. C'est ton algo en lui même qu'il faut optimiser. La mesure est biaisé par un grand nombre d'appel a ces méthodes en debug.
Il fait quoi ton algo?
Comme dit plus haut. C'est les déplacment joueur.
Quand le joueur X bouge, l'info est transmise aux joueur prêt de lui. Et si un joueur prêt de lui bouge, l'info lui est transmise. Alors si tout le monde bouge...
EDIT: Avec QHash j'ai 50% de performance en plus!Je me suis apperçu tardivement qu'il supporté de multiple vableur pour la même clef, je vais donc tout refaire...
Voila avec la multi-implementation:
http://pastebin.com/6kHh5wen
Il fait un segfaultne version C (macro POKECRAFT_SERVER_MAP_MANAGEMENT_LIST_TYPE_C_MALLOC), pas moyen de comprendre pourquoi.
Et la version C++/STL me bloque sur:
Code:../pokecraft-server-gui-2/pokecraft-server/ClientMapManagement.cpp:521:50: error: no match for 'operator[]' in '((ClientMapManagement*)this)->ClientMapManagement::to_send_map_management_move[((ClientMapManagement*)this)->ClientMapManagement::moveClient_index]'
Peux tu expliquer le contexte de ton jeux?
mmorpg, 2D tiled, type pokemon...
Pourquoi ne pas utiliser un tableau 2D?Citation:
Envoyé par alpha_one_x86
Pour savoir si un joueur est à côté il suffira de regarder dans le tableau.
Rapport avec le probléme?Citation:
Envoyé par yan
1) j'ai utilisé un algo plus efficace qui n'utilise pas de float (j'ai découpé en sous map), et pour une map de 100 000 par 100 000 ça fait 10Go de ram si je compte 8Bits (1octect) par case, j'ai prévu un algo plus évoluer plus tard
2) le problème ce situe sur la répartition des déplacements entres tout les joueurs, pas sur la détection de la proximité, j'aimerai calculer 1000 joueurs qui ce vois, ça ferai environs 33 000 joueur supporté à 30 joueur par sous map.
Aprés teste: QHash = C = C++/STL, soit beaucoup moins de cpu que QList
C'est quoi l'équivalent de QList en STL, car vector ne permet pas la suppression d'une entrée à un index.
c'est a dire ?Citation:
Envoyé par alpha_one_x86
Si tu as testé avec d'autre conteneur, pourquoi utiliser QList??Citation:
Envoyé par alpha_one_x86
16% du cpu pour mon implementation en QHash
20% pour l'implémentation en C/C++
33% en QList
J'ai tester avec un certain nombre de container, QList n'est que l'implementation de base que j'ai faite.
Si QHash correspond mieux à tes besoins, pourquoi vouloir continuer avec QList?Citation:
Envoyé par alpha_one_x86
J'ai justement supprimé la QList.