Kilka pytań o optymalizację

Odpowiedz Nowy wątek
2011-08-26 13:00
Pętlarz
0

1)
czy jest różnica wydajnościowa między

 
for(int i =0; i < 1000; i++){
     //jakieś operacje
}

a

 
int i;
for( i = 0; i < 1000; i++){
     //jakieś operacje
}

Kiedyś na pewnym teście otrzymałem pierwszy kod z pytaniem "jak tą pętlę zoptymalizować", byłem w szoku bo nie miałem pojęcia.

2)
mam powiedzmy 2000 obiektów przetrzymywanych w vectorze vectorów (taka sobie macierz/ tablica dwuwymiarowa), jak zwał tak zwał, i w programie wykonuje się pętla while (non stop), w której są wyoknywane jakieś operacje na tych obiektach i teraz które rozwiązanie jest lepsze:
a) przetrzymywać pozycję x i y każdego z elementów (czyli zajmowanie pamięci)
b) czy może w kazdej petli while wyliczac pozycje na podstawie mnożenia dwoch liczb (mam taką możliwość)

chodzi o to co lepsze a (zajmowanie pamięci) , b (mnożenie dla każdego obiektu w każdej pętli by szukaną wartość otrzymać)

Dzięki za wszelkie sugestie.

Pozostało 580 znaków

2011-08-26 13:15
0

te dwa kody roznia sie tylko tym ze w przypadku drugiego kodu zmienna i jest widoczna poza pętlą. w większości przypadków optymalizacje kompilatora zoptymalizują ten kod do najlepszej postaci. w przypadku wyłączonych optymalizacji, jeśli zmienna i nie jest nigdzie w kodzie używana można zrobić np tak:

int i=1000;
while (i--)
{
//jakies operacje
}

teoretycznie wpływ na szybkość ma też zapis:
i++ <==> zapamietuje wartosc i do zmiennej tymczasowej, "wrzuca" ja w wyrazenie. po zakonczeniu tej operacji inkrementuje i
++i <==> inkrementuje i, zwraca i
w przypadku takich pętli kompilator na pewno to zoptymalizuje. jeśli w jakiś operacjach używasz przykładowo:
vector<int> v;
... // tutaj mu ustawiasz rozmiar na 1000, wrzucasz jakeis elementy itd
to pętle można zapisać tak:

for (vector<int>::iterator i = v.begin(); i!=v.end(); ++i)
  {
   // jakies operacje
  }

i w tym wypadku mozesz odczuc znaczaca roznice na wykonaniu.

w przypadku tablicy np takiej którą używasz w pętli można zrobić tak:

int tab[1000];
//tutaj jakies zainicjowanie elementów
int* end = tab+1000;
for (int* i = tab; i!=end; ++i)
  {
   // jakies operacje
  }

zauważ jak ten kod wygląda podobnie do kodu z vector<int>

  1. nie wiem o co chodzi o_O

░█░█░█░█░█░█░█░█░█░█░█░
edytowany 1x, ostatnio: krwq, 2011-08-26 13:16

Pozostało 580 znaków

2011-08-26 13:24
msm
0

Kiedyś na pewnym teście otrzymałem pierwszy kod z pytaniem "jak tą pętlę zoptymalizować", byłem w szoku bo nie miałem pojęcia.

Współczuję nauczyciela/wykładowcy :( Te dwa kody być może różniły się pod względem wydajności - jakieś 20 lat temu. Teraz nie ma żadnej różnicy.

Podobnie mitem jest że for(;;++i) jest szybsze od for(;;i++) - różnica istnieje tylko w teorii, ale skoro mamy zasadę as-if to każdy kompilator to przetworzy tak samo, nawet przy wyłączonej optymalizacji.

2.

a) przetrzymywać pozycję x i y każdego z elementów (czyli zajmowanie pamięci)
b) czy może w kazdej petli while wyliczac pozycje na podstawie mnożenia dwoch liczb (mam taką możliwość)

Znaczy że chcesz zrobić wektor wektorów i tylko w niektórych miejscach znajdują się faktyczne obiekty? Lepiej byłoby przetrzymywać je w pojedynczym wektorze który zawierałby dane w rodzaju
struct s { int pozycjaX; int pozycjaY; obiekt faktycznyObiekt; } albo użyć jakiejś http://en.wikipedia.org/wiki/Sparse_array

chodzi o to co lepsze a (zajmowanie pamięci) , b (mnożenie dla każdego obiektu w każdej pętli by szukaną wartość otrzymać)

Jako że nie rozumiem do końca poprzedniego pytania (zgadywałem) to odpowiem na to oddzielnie - wybierz b.

edytowany 1x, ostatnio: msm, 2011-08-26 13:25

Pozostało 580 znaków

2011-08-26 13:27
Pętlarz
0

1) dzięki :)
2) chodzi o to że masz np obiekt klasy
class Kwadrat{
public:
int x,y,w,h;
}
masz macierz takich obiektów
i teraz wykonujesz pętlę while, ktora sie wykonuje caly czas dzialania programu, do momentu wyjscia. W kazdym wywolaniu petli potrzebujesz zrobic cos na polu x tego obiektu.
I teraz pytanie:
a) czy w klasie powinno być tak jak teraz przetrzymywane x dla każdego z tych 2000 obiektów czy
b) nie trzymać x i y (czyli nie zajmowac pamięci) tylko przelatując przez macierz dwoma pętlami for wyliczać np

x = i*kwadrat.w;
y = j*kwadrat.h
 

czyli pamięć jest niezajęta do przetrzymywania x i y ale za to zeby te pola wyliczyc trzeba wykonac w kazdej petli mnozenie dla kazdego obiektu (czyli wydajnosc za pewne spada)

Pozostało 580 znaków

2011-08-26 13:41
0

dla 2000 obiektów to nie myśl o czymś takim jak pamięć. chyba że postanowisz w środku klasy zrobić coś w stylu char pole[1000000].

lepiej mieć w tym wyopadku pamięciożerny szybki kod (jeśli pamięciożernością można nazwać zabranie 1MB ram)


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 1x, ostatnio: krwq, 2011-08-26 13:42

Pozostało 580 znaków

2011-08-26 14:22
msm
0

1 MB? 2000 (obiektów) x 2 (pola) * 4 (sizeof int) = 16 kb. To się nawet spokojnie zmieści w L2 Cache. W takim razie prawdopodobnie wersja 'pamięciożerna' będzie szybsza.
Z drugiej strony mnożenie jest szybkie a ładowanie danych, nawet z cache, wolne... Zrób benchmark, sam jestem ciekawy ;)

Btw. skoro klasa nazywa się kwadrat to wysokość i szerokość każdego kwadratu jest równa? A może wszystkie kwadraty mają taką samą wysokość i szerokość? :P

edytowany 2x, ostatnio: msm, 2011-08-26 14:22
na nazwę klasy nawet nie zwróciłem uwagi :P - krwq 2011-08-26 14:24

Pozostało 580 znaków

2011-08-26 15:01
nnn
1

przed chwilą zrobiłem mały eksperyment:

napisałem taki kod:

 
#include <stdio.h>
 
void bla()
{
    int i = 0;
    for( i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - i poza petla \n");
    }
}
 
void ola()
{
    for( int  i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - w  petli \n");
    }
}
 
int main()
{
    ola();
    bla();
}

po czym skompilowałem w Visual Studio w trybie Release.

Odpaliłem exeka w IDA i oto co dostałem:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  signed int v3; // [email protected]
  signed int v4; // [email protected]
 
  v3 = 1000;
  do
  {
    _puts("Funkcja - w  petli \n");
    --v3;
  }
  while ( v3 );
  v4 = 1000;
  do
  {
    _puts("Funkcja - i poza petla \n");
    --v4;
  }
  while ( v4 );
  return 0;
}

Pozostało 580 znaków

2011-08-26 15:02
nnn
0

przed chwilą zrobiłem mały eksperyment:

napisałem taki kod:

 
#include <stdio.h>
 
void bla()
{
    int i = 0;
    for( i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - i poza petla \n");
    }
}
 
void ola()
{
    for( int  i = 0 ;i <  1000 ;i++ )
    {
        puts("Funkcja - w  petli \n");
    }
}
 
int main()
{
    ola();
    bla();
}

po czym skompilowałem w Visual Studio w trybie Release.

Odpaliłem exeka w IDA i oto co dostałem:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  signed int v3; // [email protected]
  signed int v4; // [email protected]
 
  v3 = 1000;
  do
  {
    _puts("Funkcja - w  petli \n");
    --v3;
  }
  while ( v3 );
  v4 = 1000;
  do
  {
    _puts("Funkcja - i poza petla \n");
    --v4;
  }
  while ( v4 );
  return 0;
}

Pozostało 580 znaków

2011-08-26 15:03
nnn
0

w tym przykładzie dokładnie można zobaczyć na jakim poziomie są współczesne kompilatory.

Pozostało 580 znaków

2011-08-26 15:05
0

Pętlarz a jesteś pewien że chodzi o taki przykład jak w pierwszym poście, a nie przypadkiem:

for (int i=0; i < lista.getKoniecListy(); i++)
{...}

i nie chodziło żeby o to żeby za każdym razem nie pobierać getKoniecListy() tylko zapamiętać tą zwracaną wartość przed pętlą?

Pozostało 580 znaków

2011-08-26 15:13
nnn
0

a co ciekawe kompilatory zmieniają wszystkie pętle for na while

Nie ma to jak spec od RE który nigdy w życiu nie napisał linijki w asemblerze (bo wiedziałby że tam pętli nie uświadczy...) - Shalom 2011-08-26 15:40
@Shalom - ale akurat nnn ma rację, while() {} i do { } while() mają dość oczywisty sposób konwersji na kod asemblera więc można powiedzieć że kompilator zamienia 'for' i 'while' na 'do {} while' (do while a nie while). Może i uproszczenie, ale wszyscy wiedzą o co chodzi (btw. faktycznie ładnie ta optymalizacja wyszła) - msm 2011-08-26 15:51
Hmmmm na upartego pętlę w asemblerze uświadczy-jest w końcu instrukcja loop dekrementująca ECXa i wykonująca się,gdy ECX!=0. - MasterBLB 2011-08-26 18:26
Ale LOOP jest odpowiednikiem (dec exc; jnz <x>) (nawet nie jestem pewien czy nie aliasem). Nie wiem czy to można nazwać pętlą. - msm 2011-08-26 18:53
Toteż mówię,że na upartego jedynie.Co do aliasu to przynajmniej do pentium 2 miała swój własny kod hex,ale czy w nowszych prockach jej nie wyrzucili to już się nie orientuję.Generalnie każda pętla opiera się na przerwaniu ciągłego strumienia instrukcji dla procesora i skok w inne miejsce-to min jest powodem czemu nie uważam goto za instrukcję wyklętą i jak mi jakoś w kodzie wyjdzie jej użycie to nie rzucam się jak głupi do koniecznego jej zastępowania pętlami.A że jej użycie wychodzi jakoś tak z raz na rok,może pół,to już inna inszość ;P - MasterBLB 2011-08-26 19:06

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0