Un gros malloc par rapport à plusieurs reallocs plus petits

Désolé si cela a déjà été demandé, je n’ai pas pu trouver exactement ce que je cherchais.

Je lis des champs d’une liste et les écris dans un bloc de mémoire. je pouvais

  • Parcourez toute la liste, trouvez la taille totale requirejse, faites un malloc puis parcourez à nouveau la liste et copiez chaque champ;
  • Parcourez toute la liste et realloc le bloc de mémoire au fur et à mesure que j’écris les valeurs;

À l’heure actuelle, le premier me semble le plus efficace (le plus petit nombre d’appels). Quels sont les avantages et les inconvénients de l’une ou l’autre approche?

Merci pour votre temps.

Vous ferez probablement mieux d’allouer une quantité décente d’espace au départ, en fonction de ce que vous pensez être le maximum probable.

Ensuite, si vous trouvez que vous avez besoin de plus d’espace, ne vous contentez pas d’allouer suffisamment d’argent supplémentaire, allouez un gros morceau supplémentaire.

Cela minimisera le nombre de réallocations tout en ne traitant qu’une fois la liste.

À titre d’exemple, allouez initialement 100 Ko. Si vous vous rendez compte que vous avez besoin de plus d’argent, réaffectez 200 Ko, même si vous n’avez besoin que de 101 Ko.

La première approche est presque toujours meilleure. Realloc () fonctionne généralement en copiant l’intégralité du contenu d’un bloc de mémoire dans le bloc plus grand, récemment alloué. Donc, n reallocs peut signifier n copies, chacune plus grande que la dernière. (Si vous ajoutez chaque fois m octets à votre allocation, le premier realloc doit copier m octets, le suivant 2m, les 3m suivants, …).

La réponse pédante serait que les implications internes de realloc () sur les performances sont spécifiques à l’implémentation, elles ne sont pas définies explicitement par la norme. Dans certains cas, cela pourrait fonctionner avec des fées magiques déplaçant instantanément les octets, etc., etc. realloc () signifie une copie.

Ne réinventez pas la roue et utilisez le darray de CCAN qui met en œuvre une approche similaire à celle décrite par paxdiablo. Voir darray sur GitHub