Jak snadno a rychle umocnit složitost vykonávání programu – C / C++ – Fórum – Programujte.com

tak schválně - co je na tomto úseku kódu špatně:

for ( i=0 ; i<strlen(retezec)-1; i++ ) {

  // neco s pismenama retezce

}

Pokazde to bude znova pocitat to strlen()?

To KIIV : To nas zkousis, nebo to nevis? :-D

To CommanderZ : presne tak :D ale todle delaj lidi i v jinejch jazycich... pocitani poctu prvku pole v php a samo to daj zase do podminky v cyklu...


To Zelenáč : vim :) je to nazornej priklad :D

u malejch veci je to jedno ale jak sem uz rekl, zkuste to na pul GB a uvidite ten rozdil :)

Zalezi na kompileru.Ja videl i kod v asm,kdy se to vypocitajo jednou a ulozilo do docasne promenne.Takze je to docela sporne.Ale musi se na to davat bacha no.

mimochodem udelal sem jednu zajimavou verzi... nedal sem tam ani 512MB string ale jen 1MB

#include <stdio.h>

#include <stdlib.h>



// velikost pole

#define VEL (1024*1024)

// jak casto budu vypisovat

#define OUT (1024*32-1)



int main(int argc, char *argv[])

{

  char * test = malloc(VEL+1);

  int i,j;  

  printf("zacinam\n");

  for ( i=0; i< VEL; i++ ) {

    test[i]='x';    

  }

  test[VEL]='\n';

  printf("nahrano do pameti\n");





  printf("zacinam test rychlosti - spravne udelany cyklus\n");  

  j=strlen(test);

  for(i=0; i<j; i++) {

    if ( (i & OUT)==0 ) {

      printf("%d ",i);    

    }             

  }

  printf("\nkonec konec spravneho cyklu\n");





  printf("zacinam test rychlosti strlen uvnitr cyklu\n");

  for(i=0; i<strlen(test); i++) {

    if ( (i & OUT)==0 ) {

      printf("%d ",i);    

    }             

  }

  printf("\nkonec spatneho\n");  



  free(test);

  

  // system("PAUSE"); // pokud je potreba:)	

  return 0;

}

Tak premyslim nad jednim problemem:
Mam-li cyklus

for(i=0; i<640*480; i++)

tot otazka.Zkompiluj si to a protahni nejaky disassemblerem.

EDIT: Tak sem to vyzkousel.VC++ ve VS2008.Defaultni nastaveni.Vypnute CRT knihovny.Empty projekt.
Kod je:

        int i;

	for (i = 0;i < 640*480;i++)

	{

		cout << "test";

	}



	return 0;

.text:00436700                 cmp     [ebp+var_8], 4B000h

.text:00436707                 jge     short loc_43671D

int main(char* argc,int argv)

{

	int i;

	int x = atoi((const char*)argc[1]);

	int y = atoi((const char*)argc[2]);

	for (i = 0;i < x*y;i++)

	{

		cout << "test";

	}



	return 0;

}

.text:0043700D loc_43700D:                             ; CODE XREF: _main+74j

.text:0043700D                 mov     eax, [ebp+var_8]

.text:00437010                 add     eax, 1

.text:00437013                 mov     [ebp+var_8], eax

.text:00437016

.text:00437016 loc_437016:                             ; CODE XREF: _main+4Bj

.text:00437016                 mov     eax, [ebp+var_14]

.text:00437019                 imul    eax, [ebp+var_20]

.text:0043701D                 cmp     [ebp+var_8], eax

.text:00437020                 jge     short loc_437036

.text:00437022                 push    offset aTest    ; "test"

.text:00437027                 push    offset std__cout

.text:0043702C                 call    j_??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char>>(std::basic_ostream<char,std::char_traits<char>> &,char const *)

.text:00437031                 add     esp, 8

.text:00437034                 jmp     short loc_43700D

.text:00402D1C                 imul    eax, edi

.text:00402D1F                 add     esp, 8

.text:00402D22                 test    eax, eax

.text:00402D24                 jle     short loc_402D47

.text:00402D26                 mov     esi, eax

.text:00402D28                 jmp     short loc_402D30

.text:00402D28 ; ---------------------------------------------------------------------------

.text:00402D2A                 align 10h

.text:00402D30

.text:00402D30 loc_402D30:                             ; CODE XREF: _main+28j

.text:00402D30                                         ; _main+45j

.text:00402D30                 push    offset aTest    ; "test"

.text:00402D35                 push    offset std__cout

.text:00402D3A                 call    j_??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char>>(std::basic_ostream<char,std::char_traits<char>> &,char const *)

.text:00402D3F                 add     esp, 8

.text:00402D42                 sub     esi, 1

.text:00402D45                 jnz     short loc_402D30

gcc je na optimalizace docela dost chytre a rekl bych ze na tohle by prislo. level optimalizace se nastavuje prepinacem -On, kde n je z <0,3>, pripadne -Os pro co nejmensi kod. a abys videl vysledek optimalizace, nevim proc by si to mel kompilovat a zpetne disassit, kdyz staci prepinac -S aby ti gcc-cko hodilo rovnou vystup v assembler code).
ale ackoli se rika ze kompilator rozumi optimalizaci daleko lepe nez programator (cemuz dosti verim), ve vyhodnocovaci podmince bych se snazil vyraz nevyhodnocovat (a co se tyce podminek a jejich optimalizaci obecne, docela dobra je treba funkce __builtin_expect, ac ji pokud se nemylim ma pouze gcc)

Kouknete na aktualizovany prispevek nad tmi.Tam mate zajimavy vysledky.

To Zelenáč : no to nasobeni doufam ze ne :D o to by se mel postarat uz kompilator.. aspon pokud tam nemas nejakou promennou nasobenou necim jinym... by mel poznat ze to je proste konstanta

tak doufam ze to aspon nekomu neco dalo :D

Zkoušel jsem, jestli kompilátor vyoptimalizuje strlen z původního kódu. A nevyoptimalizuje :) Platí to pro VS2008. Zkoušel jsem i použít const char a na ten stringu vůbec nesahat, ale nic :) Viz kód:

	const size_t SIZE = 120*1000*1000;

	char *y = new char[SIZE];

	FILE *f = fopen("data.txt", "r");

	fread(y, 1000, SIZE/1000, f);

	y[SIZE-1] = 0;





	const char *x = y;



	size_t len = strlen(x);

	printf("nacteno, cas: %d, velikost: %d\n", clock(), len);



	unsigned int sum = 0;

	for (size_t i = 0; i < strlen(x); i++) {

		sum += x[i];

	}



	printf("cas: %d, hash: %d\n", clock(), sum);



	fclose(f);

	delete[] x;

	return 0;

Ale tohle už vyoptimalizuje (vypočítá konstantu) a to si myslím, že už je fakt slušný

class X {

public:

	int fn() const {

		return 12345*1000;

	}

};



void otherTest() {

	const X x;

	int sum = 0;

	for (int i = 0; i < 2*x.fn(); i++) {

		sum ++;

	}

	printf("vys: %d\n", sum);

}

00401000  push        178BD50h 

00401005  push        offset ___xi_z+34h (4020F4h) 

0040100A  call        dword ptr [__imp__printf (4020A0h)] 

00401010  add         esp,8 

To Quiark : je taky mozne ze si strlen nejak vynucuje ze ma byt pokazde provedeno...

To KIIV : urcite ne. zkousel jsem to s gcc, a s -O2 se dokonce strlen nevolal ani jednou (nevim jak presne se delka retezce zjistila, ale tusim ze toto bylo mozne proto ze tesne pred cyklem byla volana scanf naplnujici zmineny retezec... ).

kdo vi.. kazdopadne spolehat na "kompilator to udela sam" je cesta do pekel :D

Samozrejme neverit kompilatoru ve vsem, ale v techto trivialnich vecech se fakt vyplati mu verit :)

A kde by vzal kompilátor jistotu, že se velikost řetězce nezmění? Pokud se bavíme obecně o cyklu

for(i=0;i<strlen(s);i++){

	//cokoli

}

for ( i=0 ; i<strlen(retezec)-1; i++ ) {



  // neco s pismenama retezce



}

To Vojtěch Havel : no je pravda ze i ukoncovaci znak '\0' je formalne soucast retezce ale obykle se uz prilis zase nezpracovava ...
mimo to by se ten cyklus dal udelat snadneji pomoci ukazatele a dojit az k ukoncovaci \0 ... pokud vyslovene nepotrebuji tu delku jako takovou..
a pokud by se retezec menil mohl by to byt taky problem.. treba rozdelit retezec podle mezer.. misto mezer zapisovat \0 .. tak by to skoncilo po prvnim vlozeni 0 napriklad... ikdyz hodit by se to i mohlo

gcc ten strlen opravdu vyoptimalizuje pryč, ale když ho nahradím vlastní implementací, tak tam to volání nechá. Takže to asi má někde uložené, že strlen může.

Vojtěch Havel napsal:
A kde by vzal kompilátor jistotu, že se velikost řetězce nezmění?

To KIIV : máme řetězec "KIIV".
strlen("KIIV") = 4
cyklus for(i=0; i<4 -1; i++) proběhne třikrát - pro nultý znak, pro první znak, pro druhý znak. Trojka už není menší než 4-1. Pro 'V' se tedy cyklus neprovede!

To Vojtěch Havel : mas pravdu.. clovek ma v programu vzdy o jednu chybu vic nez mysli :)) a nejhorsi je, kdyz je presvedcen ze je to spravne ... to si tu cast pak ani nezkontroluje logicky.. jen tvrdi ze je to dobre :smile14:

dannyk napsal:
Zalezi na kompileru.Ja videl i kod v asm,kdy se to vypocitajo jednou a ulozilo do docasne promenne.Takze je to docela sporne.Ale musi se na to davat bacha no.

KIIV napsal:
To Quiark : je taky mozne ze si strlen nejak vynucuje ze ma byt pokazde provedeno...

Kecám, zrovna mě napadla optimalizační vyjímka :smile1:

2 joe: A proc by nesmel? Ja to tak videl, takze si nevymyslim.Proste to vypadalo nejak takhle:

push string

call strlen

mov ecx, eax

xor edx,edx

zpet:

nejake upravy

inc edx

cmp edx, ecx

jl zpet

dannyk napsal:
2 joe: A proc by nesmel? Ja to tak videl, takze si nevymyslim.
...
Samozrejme muzou byt vyjimky, ale tuhle pribliznou kontrukci sem uz nekolikrat videl a nevidim duvod, proc by to kompiler nemohl udelat.