PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : [C] realloc() und performance


The_Invisible
2008-09-08, 21:43:29
hallo,

hätte eine frage an die profis hier. und zwar habe ich eine funktion geschrieben die eine datei zeilenweise in eine stringtabelle einliest, beispiel:


char **read2chararr()
{
FILE *fp;
char buf[1024], **con = NULL;
int i = 1;

fp = fopen("C:\\Windows\\System32\\drivers\\etc\\services", "r");

while(fgets(buf, 1024, fp) != NULL)
{
//printf("%i", i);

if(con == NULL)
{
con = (char **) malloc(sizeof(char *));
con[0] = (char *) malloc(sizeof(char) * (strlen(buf)+1));
strcpy(con[0], buf);
}
else
{
//printf("%i = %s\n", strlen(buf), buf);
con = (char **) realloc(con, sizeof(char *) * i);
con[i-1] = (char *) malloc(sizeof(char) * (strlen(buf)+1));
strcpy(con[i-1], buf);
}

i++;
}

con = (char **) realloc(con, sizeof(char *) * i);
con[i-1] = NULL;

fclose(fp);

return con;
}


funktioniert auch alles wunderbar und ohne probleme. mir stellt sich aber die frage ob die malloc() und realloc() funktionen nicht zu viel kosten da sie quasi für jede zeile aufgerufen werden und ob man das vielleicht besser machen könnte. irgendwelche tipps oder tricks in dieser art?

aja, und die funktion ist noch stark prototyp bevor sich einige beschweren kommen. ;)

mfg

Trap
2008-09-08, 21:51:31
Realloc muss alles bisher gelesene umkopieren, bei n-facher Textmenge müssen also n²/2 kopiert werden.

Gute Performance geht nur wenn man zuerst nachguckt wieviel Speicher man braucht oder zuviel Speicher anfordert (immer aktuelle Größe *1.5 wäre eine Möglichkeit).

Gast
2008-09-08, 22:05:14
1.) Du solltest dir zuerst einmal überlegen, wie groß deine Datei wird. Falls es nur 20-30 Zeilen sind, dann ist so so wahrscheinlich die schnellste Lösung. Falls es jedoch 1 Mio. Zeilen werden, dann ist es eine Katastrophe, weil die Zeit ca. quadratisch mit der Anzahl der Zeilen wächst und 1 Mio. Mal ein paar MB anfordern und wieder freigeben ist ziemlich mühsam. Hier würde ich lieber eine verkettete Liste nehmen und die dann nachher bei Bedarf in eine verkettete Liste umwandeln.
In dem Fall der services Datei wird es denke ich einmal nicht die schnellste Lösung sein, aber so wirklich kritisch sollte es nicht sein. Du kannst ja auch gleich auf Vorrat immer 10 Zeilen mehr anlegen. Das tut niemandem weh und ist gleich wesentlich schneller.

2.) Vergiss nicht bei deinem Programm, dass der Pfad bei Windows nicht immer gleich ist. Ein Windows kann z.B. auch D liegen und die meisten Pfade können auch anders heißen z.B. nicht Windows usw.

3.) Wenn die Datei groß ist (ein paar 100MB aufwärts) und die Zeilen kurz sind (z.B. 20 Bytes), dann kann fgets auch bremsen. Da ist nämlich jedes Mal ein Kontext Switch notwendig, was ca. 100K Aufrufe pro Sekunde ergibt. Bei schnellen Platten um die 100MB/s ist das eventuell zu wenig.

Ectoplasma
2008-09-11, 12:30:54
Realloc muss alles bisher gelesene umkopieren, bei n-facher Textmenge müssen also n²/2 kopiert werden.

Ja und nein. Realloc muss nicht unbedingt alles umkopieren, denn realloc kann auch die gleiche Adresse zurückgeben. Allerdings sollte man sich darauf nicht verlassen.

The_Invisible
2008-09-24, 14:13:15
und ich dachte immer speicher verschwenden ist pöse ;)

da die dateien aber 100k nicht übersteigen sollte meine lösung also kein problem sein.

andere frage die eigentlich mit dieser nichts gemein hat:
ist es möglich eine funktion zu schreiben die zB ein char* zurückgibt aber nicht selber mit free() löschen muss? static kenne ich, weiß aber nicht ob das ein guter ansatz ist. mir kommt zudem vor in der standardbibliothek gibt es einige solche funktionen, sehe da aber nur die header.

edit:
zb eine funktion wo das wünschenswert wäre

/* Replace first occurrence of search in string with repl */
char *replace(char *string, char *search, char *repl)
{
char *newstr = (char *) malloc(sizeof(char) * (strlen(string) + strlen(repl)));
char *found;
ptrdiff_t ptrd = 0;

memset(newstr, 0, sizeof(char) * (strlen(string) + strlen(repl)));

if((found = strstr(string, search)) != NULL)
{
ptrd = found - string;
strncpy(newstr, string, (int)ptrd);

strncat(newstr, repl, strlen(repl));

strncat(newstr, found + strlen(search), strlen(string) - ptrd - strlen(search));

return newstr;
}
else
{
return string;
}
}


mfg

Coda
2008-09-24, 15:23:04
Jede Speicherallozierung ist extrem langsam. In nem Inner-Loop ist das tödlich.

Außerdem gibst du überhaupt keinen Speicher wieder frei.

The_Invisible
2008-09-24, 18:03:22
der speicher wird "draußen" dann wieder freigegeben, siehe dazu auch meine letzte frage wie man das eleganter machen könnte.

aber danke für den hinweis mit "extrem langsam". da die dateien meistens nur ein paar kb haben ist das hoffentlich nicht so "tödlich", habe zumindest noch nichts bemerkt.

mfg