BGAFC Vendégkönyv

Σ: 1 post

TCH (statz)

#1, Főfasz (10466)

8792 | #2d09 | ^ | Idézet | Tue, 03 Jun 2014 03:16:16 +02

188.36.*.*

*.catv.pool.telekom.hu

Jegesmedvementes jó estét kívánok retkes hallgatóinknak, ez itten a basszunk lovat optimalizállyunk rovat, mai témánk a stringtömbök egyberagasztása; melyik módszer lassú, vagy nem gyors, avagy kurjunk kecskét minden pénteken fogászati célból bencsmárkollyunk. Van ugye a lóbaszó folyamatosan allokálós fajta, ami azt csinálja, hogy egy ciklusban végigmegy a stringtömbön és minden körben újraallokálja a célbuffert, hogy beleférjen a következő adag is.

char *implode_ac(char *separator, char *strings[], long long int count)
{
	unsigned long long int retlen, lpos, tmp;
	long long int i;
	unsigned int seplen;
	char *result;

	if ((separator == NULL) || (strings == NULL))
	{
		return NULL;
	}
	retlen = 0;
	result = malloc(retlen);
	if (result == NULL)
	{
		return NULL;
	}
	seplen = strlen(separator);
	--count;
	lpos = 0;
	for (i = 0; i < count; ++i)
	{
		tmp = strlen(strings[i]);
		retlen += tmp + seplen;
		result = realloc(result, retlen);
		if (result == NULL)
		{
			return NULL;
		}
		strcpy((char *)(result + lpos), strings[i]);
		strcpy((char *)(result + lpos + tmp), separator);
		lpos = retlen;
	}
	retlen += strlen(strings[i]) + 1;
	result = realloc(result, retlen);
	if (result == NULL)
	{
		return NULL;
	}
	strcpy((char *)(result + lpos), strings[i]);
	return result;
}

Alapiskola, semmi extra nem szükséges hozzá.

Aztán van a csirkés egyszer allokálós módszer, amiben két ciklus van, az egyik előbb összeszámolja a szükséges helyet, majd egyszer allokál, aztán másol.

#define loccpy_ao \
/* BEGIN LOCCPY */\
	while (*src)\
	{\
		*dst++ = *src++;\
	}\
/* END LOCCPY */\
\

char *implode_ao(char *separator, char *strings[], long long int count)
{
	unsigned long long int retlen;
	long long int i;
	unsigned int seplen;
	char *result;
	char *src;
	char *dst;

	if ((separator == NULL) || (strings == NULL))
	{
		return NULL;
	}
	retlen = 0;
	seplen = strlen(separator);
	--count;
	for (i = 0; i < count; ++i)
	{
		retlen += strlen(strings[i]) + seplen;
	}
	retlen += strlen(strings[i]);
	result = malloc(retlen + 1);
	if (result == NULL)
	{
		return NULL;
	}
	dst = result;
	for (i = 0; i < count; ++i)
	{
		src = strings[i];
		loccpy_ao;
		src = separator;
		loccpy_ao;
	}
	src = strings[i];
	loccpy_ao;
	*dst = 0;
	return result;
}

Ez már egy birkafasznyit rázósabb, mert a másolásnál akad egy kis gond: ha a strcat()-tal másolunk, az mindig megkeresi a terminátort a cél végén, tehát a célnak újra és újra megméri a hosszát, ráadásul a cél egyre hosszabb ugye. Ha strcpy-val másolunk, akkor pedig nekünk kéne megmondani, hogy hova másoljon, vagyis kéne egy másodlagos pointer, hogy tudjuk, hogy épp hol a cél vége, amit viszont kézzel kell inkrementálgatni a források hosszával, vagyis itt újból végig kéne strlen()-elni másodjára is a tömböt, ami egyértelműen marhaság lenne; tehát fogjuk a célt és írunk mi custom inline strcpy-t, ahol a pointer mindig a cél végére mutat. Így csak egyszer kell végigszámolni a tömböt.

Nosza, akkor teszteljünk. Tesztprogramnak ennyi is elég

void main(int argc, char *argv[])
{
	int i;
	for (i = 0; i < 50000000; ++i)
	{
		free(implode_ac(":::", argv, argc));
	}
}

majd mi adunk nekik elég szemetet, amit összefűzhetnek. Először teszteljük le a folyamatosan allokálót:

root@Csabi:~# gcc -O2 test.c
root@Csabi:~# time a.out kecske macska anyad buzi lo tehen kurwa picsa geci fasz mocskosmikrofos apicsaba retkes fos fos fos fos kecske geci anyad hulye buzerans takony teve foskobold szar fos hugy

real    1m35.576s
user    1m35.604s
sys     0m0.000s

Írjuk át a meghívást az egyszer allokálósra (implode_ac => implode_ao) és teszteljük újra:

root@Csabi:~# gcc -O2 test.c
root@Csabi:~# time a.out kecske macska anyad buzi lo tehen kurwa picsa geci fasz mocskosmikrofos apicsaba retkes fos fos fos fos kecske geci anyad hulye buzerans takony teve foskobold szar fos hugy

real    0m42.211s
user    0m42.220s
sys     0m0.000s

Hoppá, több mint kétszer olyan gyors. Mondjuk nem csoda, a sok allokálgatás ezzel jár.

No, hát akkor ez a helyzet, hogy a két ciklust használó, egyszer allokáló verzió gyorsabb, mint az egy ciklust használó, folyamatosan allokálgató.
Máshogy meg nem lehet csinálni, hiszen vagy végignézzük előre az összeset, hogy tudjuk mennyi az annyi és utána hosszmérés nélkül másolhassunk, vagy menetközben számolgatjuk hozzá folyamatosan. A kettőt nem lehet kombinálni, hogy hosszmérés és allokálgatás nélkül csak másolunk, pedig az lenne az igazi...

Vagy esetleg mégis lehetne? Mi is gátolja meg, hogy ezt tegyük? Mármint azonkívül, hogy ahhoz, hogy másolhassunk, előbb allokálni kéne, ahhoz meg a hosszt kéne tudni, hogy tudjuk mennyit kell allokálni? De, ha jobban végiggondoljuk: vajon tényleg kell nekünk tudni a stringek hosszát, hogy allokálhassunk? Miért nem allokálunk hasraütésszerűen, aztán írunk bele, majd alkalomadtán kitoldván a puffert, ha elfogyott? Lássuk csak a kecskét!

#define prealloc \
/* BEGIN PREALLOC */\
	if (++ssize == asize)\
	{\
		asize += alloc_buffer;\
		result = realloc(result, asize);\
		if (result == NULL)\
		{\
			return NULL;\
		}\
	}\
/* END PREALLOC */\
\

#define loccpy_pa \
/* BEGIN LOCCPY_PA */\
	while (*src)\
	{\
		prealloc;\
		*dst++ = *src++;\
	}\
/* END LOCCPY_PA */\
\

char *implode_pa(char *separator, char *strings[], long long int count, unsigned long int alloc_buffer)
{
	char *result;
	char *dst;
	char *src;
	unsigned long long int asize, ssize;
	long long int i;

	if ((separator == NULL) || (strings == NULL))
	{
		return NULL;
	}
	asize = alloc_buffer;
	ssize = 0;
	result = malloc(asize);
	if (result == NULL)
	{
		return NULL;
	}
	--count;
	dst = result;
	for (i = 0; i < count; ++i)
	{
		src = strings[i];
		loccpy_pa;
		src = separator;
		loccpy_pa;
	}
	src = strings[i];
	loccpy_pa;
	prealloc;
	*dst = 0;
	return realloc(result, ssize);
}

Voila. A custom inline copyban használunk még két változót, az egyik az allokált memória méretét, a másik a valódi, kihasznált memória méretét tárolja. A cél és forráspointerek inkrementálása mellett így kell inkrementálni egy másik változót, valamint figyelni, hogy a következő körben overflow lenne-e már és ha igen, akkor allokálni egy újabb porciót. Így 100%-ig kiszűrünk mindenféle hosszmérést és az allokálások elsöprő többségétől is megszabadultunk; kettő db. tuti allokálás van, a többi már attól függ, hogy a stringtömb teljes hossza belefér-e az alapból allokált bufferbe, vagy sem; a bufferchunkok méretét pedig mi szabályozzuk. Már csak az a kérdés, hogy vajon jó-e az ötlet és ez tényleg gyorsabb-e, mint a folyamatosan allokálgató?

void main(int argc, char *argv[])
{
	int i;
	for (i = 0; i < 50000000; ++i)
	{
		free(implode_pa(":::", argv, argc, 256));
	}
}

Kicsit változtattunk a kódon, kell a bufferchunk mérete is. Teszt:

root@Csabi:~# gcc -O2 test.c
root@Csabi:~# time a.out kecske macska anyad buzi lo tehen kurwa picsa geci fasz mocskosmikrofos apicsaba retkes fos fos fos fos kecske geci anyad hulye buzerans takony teve foskobold szar fos hugy

real    0m37.332s
user    0m37.336s
sys     0m0.004s

A válasz egyértelmű igen. Az egyszer allokálgatós módszer gyenge pontjai, a két ciklus és a hosszméregetés így megszűnt, ez cca. 13%-os sebességnövekedést hozott. Itt a cucc egybe, kulcsrakészen (implode.c)

#ifndef _IMPLODE_C
#define _IMPLODE_C 1

#include <stdlib.h>

#define prealloc \
/* BEGIN PREALLOC */\
	if (++ssize == asize)\
	{\
		asize += alloc_buffer;\
		result = realloc(result, asize);\
		if (result == NULL)\
		{\
			return NULL;\
		}\
	}\
/* END PREALLOC */\
\

#define loccpy \
/* BEGIN LOCCPY */\
	while (*src)\
	{\
		prealloc;\
		*dst++ = *src++;\
	}\
/* END LOCCPY */\
\

char *implode(char *separator, char *strings[], long long int count, unsigned long int alloc_buffer)
{
	char *result;
	char *dst;
	char *src;
	unsigned long long int asize, ssize;
	long long int i;

	if ((separator == NULL) || (strings == NULL))
	{
		return NULL;
	}
	asize = alloc_buffer;
	ssize = 0;
	result = malloc(asize);
	if (result == NULL)
	{
		return NULL;
	}
	--count;
	dst = result;
	for (i = 0; i < count; ++i)
	{
		src = strings[i];
		loccpy;
		src = separator;
		loccpy;
	}
	src = strings[i];
	loccpy;
	prealloc;
	*dst = 0;
	return realloc(result, ssize);
}

#endif

Köszönöm a figyelmetlen segget, bikacsököt bilgécnek és a kurwa anyját a mikrofosnak.