Se connecter

Informatique

Programmation

Sujet : C++ - Optimisation de la recherche dans un dictionnaire
1
PillsDispenser
Niveau 51
05 mars 2021 à 17:34:07

Hello,

Code : https://hatebin.com/weplfpqojq

Je voudrais optimiser le programme suivant en utilisant un « pool » de Texture-s afin d’éviter les allocations mémoires à chaque insertion lors de l’initialisation et pouvoir aussi supprimer les destructions dans la fonction Shutdown().

Quelqu un peut il m'aider, je ne sais pas comment faire ?

godrik
Niveau 21
05 mars 2021 à 17:55:13

Toute les textures sont de la meme taille?

PillsDispenser
Niveau 51
05 mars 2021 à 20:44:29

Le 05 mars 2021 à 17:55:13 godrik a écrit :
Toute les textures sont de la meme taille?

Non pas forcément.
Texture.h
https://hatebin.com/pgdsoojzia

godrik
Niveau 21
06 mars 2021 à 02:22:42

Tu dis que les texturers n'ont pas la meme taille,mais tous les objets ont juste des donnees de meme taille... Qu'est ce que tu cherches a faire et pourquoi tu pense que c'est necessaire?

Optimiser un benchmark comme tu as fais n'est probablement pas representatif de performance dans une application pour un million de raison. Au pif:

1/ le code est sequentiel: tout ce genre de chose serait fait en parallel dans une vraie application.
2/ pourquoi est ce que le dictionnaire est stocke par un std::map? Les arbres sont plus lent que les tables de hashage
3/ pourquoi est ce que le dictionnaire est associe des chaines de caracteres a une texture? Certainement, ce que l'on veut est donne un identifiant unique aux textures. Probablement un entier 32bit suffira parceque je doute que tu aura plus de 4 milliard de texture.
4/ Pourquoi est ce que les texture n'ont que 32 octets de donnees? Une texture fait typiquement au moins 2 octet par pixel (et probablment 4), donc ca, ca fait des textures de 16 pixels.
5/ Une texture est typiquement lue du disque ou genere proceduralement. Donc mesurer le cout de creation de l'objet texture ne represente pas le cout de chargement d'une texture.

PillsDispenser
Niveau 51
06 mars 2021 à 10:53:24

C'est pour apprendre et après faire d'autre truc.
Utilisez une valeur de hachage uint32_t à la place de std::string pour le type Name
Utiliser une recherche dichotomique (binary search) afin de trouver plus rapidement les éléments

godrik
Niveau 21
06 mars 2021 à 18:15:05

Je vois.

Des conseils:

-Ne t'inquiete pas des questions de placement memoire a ce niveau la. En pratique les allocateurs memoires font un boulot pas trop mauvais. Et c'est plus une optimisation fine qu'autre chose.
-Si tu n'a pas un bouquin de structure de donnee. Tu peux regarder https://people.cs.vt.edu/shaffer/Book/ Le livre est un peu vieux, mais toujours tres utilisables pour comprendre ce qu'il se passe.
-C'est bien d'apprendre a ecrire ces trucs la (genre binary search) parceqeu ca fait comprendre plein de chose.
-Mais la en pratique tu utilises std::map qui est un genre d'arbre binaire de recherche. Du fait, tu as deja une recherche en temps logarithmique. Et si tu utilisais std::unordered_map, tu aurais une table de hashage et des operations en O(1).

PillsDispenser
Niveau 51
06 mars 2021 à 19:36:36

Mais du coup là j'aimerais

  • Optimiser le programme suivant en utilisant un « pool » de Texture-s afin d’éviter les allocations mémoires à chaque insertion lors de l’initialisation et pouvoir aussi supprimer les destructions dans la fonction Shutdown().
  • Utilisez une valeur de hachage uint32_t à la place de std::string pour le type Name
  • Utiliser une recherche dichotomique (binary search) afin de trouver plus rapidement les éléments

Mais je sais pas comment le faire.

godrik
Niveau 21
06 mars 2021 à 20:05:52
  • Optimiser le programme suivant en utilisant un « pool » de Texture-s afin d’éviter les allocations mémoires à chaque insertion lors de l’initialisation et pouvoir aussi supprimer les destructions dans la fonction Shutdown().

Tu utilise un vecteur pour stocker les textures et ta map pointe dans le vecteur.

  • Utilisez une valeur de hachage uint32_t à la place de std::string pour le type Name

bah, voila, tu fais ca... (Je ne comprends pas le probleme)

  • Utiliser une recherche dichotomique (binary search) afin de trouver plus rapidement les éléments

Lis un cours de structure de donne pour comprendre pourquoi ca n'a pas de sense de faire recherche dichotomique dans un std::map.

PillsDispenser
Niveau 51
06 mars 2021 à 21:38:33

Le 06 mars 2021 à 20:05:52 godrik a écrit :

  • Optimiser le programme suivant en utilisant un « pool » de Texture-s afin d’éviter les allocations mémoires à chaque insertion lors de l’initialisation et pouvoir aussi supprimer les destructions dans la fonction Shutdown().

Tu utilise un vecteur pour stocker les textures et ta map pointe dans le vecteur.

  • Utilisez une valeur de hachage uint32_t à la place de std::string pour le type Name

bah, voila, tu fais ca... (Je ne comprends pas le probleme)

  • Utiliser une recherche dichotomique (binary search) afin de trouver plus rapidement les éléments

Lis un cours de structure de donne pour comprendre pourquoi ca n'a pas de sense de faire recherche dichotomique dans un std::map.

Oui mais justement je ne sais pas comment faire

PillsDispenser
Niveau 51
20 mars 2021 à 17:45:26

:up:

89ron
Niveau 10
20 mars 2021 à 19:54:17

Le 06 mars 2021 à 21:38:33 PillsDispenser a écrit :

Le 06 mars 2021 à 20:05:52 godrik a écrit :

  • Optimiser le programme suivant en utilisant un « pool » de Texture-s afin d’éviter les allocations mémoires à chaque insertion lors de l’initialisation et pouvoir aussi supprimer les destructions dans la fonction Shutdown().

Tu utilise un vecteur pour stocker les textures et ta map pointe dans le vecteur.

  • Utilisez une valeur de hachage uint32_t à la place de std::string pour le type Name

bah, voila, tu fais ca... (Je ne comprends pas le probleme)

  • Utiliser une recherche dichotomique (binary search) afin de trouver plus rapidement les éléments

Lis un cours de structure de donne pour comprendre pourquoi ca n'a pas de sense de faire recherche dichotomique dans un std::map.

Oui mais justement je ne sais pas comment faire

Pour faire une recherche dichotomique, il faut que tu construises un conteneur, exemple un tableau de string qui soit ordonner. Les elements doivent etre trier au moment de l'insertion.

Seulement une recherche dichotomique c'est plus lent meme dans les meilleurs des cas qu'un std::map ou std::unordered_map ou un std::vec

Le plus rapide serait un std::unordered_map<uint32_t, *Texture> et pour garder le nom de tes differentes textures tu faits un enum.

Pour ton pool tu fait un mempool de N elements pour un seul type de texture. Et tu alloues la memoire de tout les elements a la construction du niveau et les desalloues a sa destruction dans le cas d'un jeu, par exemples.

1
Sujet : C++ - Optimisation de la recherche dans un dictionnaire
   Retour haut de page
Consulter la version web de cette page