Jak snadno a rychle umocnit složitost vykonávání programu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
KIIV+42
God of flame
25. 9. 2008   #1
-
0
-

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

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

// neco s pismenama retezce
}


předpokládejme že to bude třeba 512MB dlouhý řetězec... aby se netroškařilo

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Reklama
Reklama
25. 9. 2008   #2
-
0
-

Pokazde to bude znova pocitat to strlen()?

Nahlásit jako SPAM
IP: 78.102.164.–
Prosím, jestli potřebujete s něčím poradit,zeptejte se na fóru. Jakýkoliv bezdůvodný pokus mě kontaktovat skončí okamžitým přidáním do ignore listu![br][br] Současný počet osob, které to nepochopily: 7
Zelenáč0
Posthunter
25. 9. 2008   #3
-
0
-

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

Nahlásit jako SPAM
IP: 89.176.254.–
KIIV+42
God of flame
25. 9. 2008   #4
-
0
-

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 :)

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
dannyk0
Věrný člen
25. 9. 2008   #5
-
0
-

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.

Nahlásit jako SPAM
IP: 158.196.67.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
KIIV+42
God of flame
25. 9. 2008   #6
-
0
-

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;
}

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Zelenáč0
Posthunter
26. 9. 2008   #7
-
0
-

Tak premyslim nad jednim problemem:
Mam-li cyklus

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

nasobi se to pri kazde iteraci, nebo to GCC spocita jiz pri kompilaci?

Nahlásit jako SPAM
IP: 89.176.254.–
dannyk0
Věrný člen
26. 9. 2008   #8
-
0
-

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;


a vypis v asm:


.text:00436700 cmp [ebp+var_8], 4B000h
.text:00436707 jge short loc_43671D


Ocividne z toho vyplyva,ze kompiler uz to automaticky optimalizuje.

Udelal sem jeste jeste jeden maly pokus.



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


Z tohoto jasne vyplyva,ze se to vzdy znovu nasobi.
Ovsem pri nastaveni kompilace s optimalizaci na Maximal speed jiz mame kod takovyto:


.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

Konkretne si vsimnete registru esi,do ktereho se prevede vysledek nasobeni.Ten se pak pouze dekrementuje a na nule se pokracuje v kodu.

Takze jde videt,ze prekladac je dost chytry na tyhle zakladni zaludnosti :)

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
tmi0
Věrný člen
26. 9. 2008   #9
-
0
-

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)

Nahlásit jako SPAM
IP: 213.226.230.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
dannyk0
Věrný člen
26. 9. 2008   #10
-
0
-

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

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
KIIV+42
God of flame
26. 9. 2008   #11
-
0
-

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

Nahlásit jako SPAM
IP: 77.237.136.–
Program vždy dělá to co naprogramujete, ne to co chcete...
KIIV+42
God of flame
1. 10. 2008   #12
-
0
-

tak doufam ze to aspon nekomu neco dalo :D

Nahlásit jako SPAM
IP: 80.188.94.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Quiark0
Věrný člen
27. 2. 2009   #13
-
0
-

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;

Nahlásit jako SPAM
IP: 193.86.140.–
Quiark0
Věrný člen
27. 2. 2009   #14
-
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);
}


Příslušný asm:
00401000  push        178BD50h 

00401005 push offset ___xi_z+34h (4020F4h)
0040100A call dword ptr [__imp__printf (4020A0h)]
00401010 add esp,8

Nahlásit jako SPAM
IP: 193.86.140.–
KIIV+42
God of flame
28. 2. 2009   #15
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
tmi0
Věrný člen
28. 2. 2009   #16
-
0
-

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... ).

Nahlásit jako SPAM
IP: 213.226.226.–
ksp.mff.cuni.cz -- doporučuje 5 z 0 přetečených bufferů!
KIIV+42
God of flame
28. 2. 2009   #17
-
0
-

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

Nahlásit jako SPAM
IP: 80.250.1.–
Program vždy dělá to co naprogramujete, ne to co chcete...
dannyk0
Věrný člen
28. 2. 2009   #18
-
0
-

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

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
Vojtěch Havel
~ Anonymní uživatel
20 příspěvků
8. 3. 2009   #19
-
0
-

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
}


nemůžeme s jistotou tvrdit, že lze dosadit místo strlen() konstantu. A to ani když se jí předá const char * (sledovaná paměťová oblast se změnit teoreticky může). Konstantu dosadit může snad jen kompilátor s nastavenou vysokou úrovní optimalizace, protože v manuálech se jistě dočtete, že třeba při -O3 se neručí za správnost výsledků :-)

btw k původní otázce threadu:


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

// neco s pismenama retezce

}


my chceme provést akci uvnitř cyklu pro každý znak? tak to potom vím odpověď na otázku, co je na tom kódu špatně :-)

Nahlásit jako SPAM
IP: 213.211.34.–
KIIV+42
God of flame
8. 3. 2009   #20
-
0
-

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

Nahlásit jako SPAM
IP: 77.237.136.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Quiark0
Věrný člen
8. 3. 2009   #21
-
0
-

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.

Nahlásit jako SPAM
IP: 193.86.140.–
dannyk0
Věrný člen
8. 3. 2009   #22
-
0
-

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



No tu jistotu bereme u konstatnich stringu :D
Jinak u klasicky stringu tu jistotu nemame nikdy,jenze prekladac je mazany a provede predpocet delky stringu predem a tu predpoctenou hodnotu pak pouziva pro cyklus, takze znova delku opravdu dokola nepocita (pri standartnim nastaveni VS2008).

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
Vojtěch Havel
~ Anonymní uživatel
20 příspěvků
9. 3. 2009   #23
-
0
-

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!

Nahlásit jako SPAM
IP: 213.211.53.–
KIIV+42
God of flame
9. 3. 2009   #24
-
0
-

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:

Nahlásit jako SPAM
IP: 77.237.136.–
Program vždy dělá to co naprogramujete, ne to co chcete...
joe
~ Anonymní uživatel
62 příspěvků
10. 3. 2009   #25
-
0
-

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.



Nesmysl, nic takového Ti překladač pro takovou konstrukci udělat nesmí a neudělá. Nejen, že je to ve standardu, ale je to snad i logické.

Nahlásit jako SPAM
IP: 213.211.51.–
joe
~ Anonymní uživatel
62 příspěvků
10. 3. 2009   #26
-
0
-

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



Podmínka ve foru se prostě vyhodnocuje vždy a úplně, včetně volání funkcí. Jiné chování je nepřípustně a nelogické.

Nahlásit jako SPAM
IP: 213.211.51.–
joe
~ Anonymní uživatel
62 příspěvků
10. 3. 2009   #27
-
0
-

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

Nahlásit jako SPAM
IP: 213.211.51.–
dannyk0
Věrný člen
11. 3. 2009   #28
-
0
-

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


Samozrejme muzou byt vyjimky, ale tuhle pribliznou kontrukci sem uz nekolikrat videl a nevidim duvod, proc by to kompiler nemohl udelat.

Nahlásit jako SPAM
IP: 85.135.97.–
Jedu v c++,c#,assembler,ASP.NET,PHP,databaze,bezpecnost softwaru[br] -----------------------------------------------------------[br] Muj blog o programovani,hudbe a vsem moznem,co najdu na netu :) [br] http://dannyk.aspone.cz[br] -----------------------------------------------------------[br] Na foru mam nejake prispevky pod nickem Master,tak jen pro upresneni :)
joe
~ Anonymní uživatel
62 příspěvků
11. 3. 2009   #29
-
0
-

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.


Unáhlil jsem se. Jak už jsem napsal, tak mě hned napadl případ, kdy by to tak mohlo být bez porušení pravidel.

Nahlásit jako SPAM
IP: 213.211.51.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 105 hostů

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý