Pętla skanująca std::vector i jej optymalizacje

Witam.

Od jakiegoś czasu zastanawiam się nad czymś co może jest szczegółem, ale może mieć duże znaczenie.

typedef unsigned int UINT

std::vector<Object> objects;

I pętla:

for(UINT i = 0; i < objects.size(); i++)
{
    
}

II pętla:

for(UINT i = 0, iEnd = objects.size(); i < iEnd; i++)
{
    
}

Jak widać:

• W I pętli co każdy krok jest wywoływana funkcja objects.size()
• W II pętli co każdy krok jest odczytywana zmienna iEnd

Co tak naprawdę robi funkcja size() w vector? Dokonuje obliczeń w celu sprawdzenia rozmiaru vector'a czy po prostu pobiera prywatne pole obiektu?

I pętla jest zdecydowanie przejrzystsza, II wydaje się być szybsza.

Czy opłaca się tak kombinować jak w II pętli czy nie zyska się na tyle na szybkości żeby psuć przejrzystość kodu?

Pozdrawiam

vector<T>::size() jest inline tak wiec nie ma roznicy, czy uzywasz .size() czy nie. Najbardziej nieefektywnym krokiem w twoim rogramowanie jest skladowanie objektow. Generalnie powinienes kladowac shared_ptr<Object>
Pozdrawiam serdecznie

Dzięki.

PS. Popieram twoje zdanie nad wyższością C++ przed C#, Java w temacie "Programista C++" : P

tak wiec nie ma roznicy, czy uzywasz .size() czy nie.
Pod warunkiem, że kompilujesz z włączoną optymalizacją. W buildach debugowych typowo wszystko jest wywoływane.

Swoją drogą dlaczego używanie std::vector miałoby być błędem do przechowywania obiektów?
Wg. mnie nie ma różnicy czy przechowuje się tam wskaźniki do obiektów czy całe obiekty, bo vector sam zaalokuje pamięć na nie

żeby nie było wątpliwości, std::vector<objects> używam jako "singleton", jest w jednym miejscu jako jedna kopia

Gokor napisał(a)

Swoją drogą dlaczego używanie std::vector miałoby być błędem do przechowywania obiektów?
Wg. mnie nie ma różnicy czy przechowuje się tam wskaźniki do obiektów czy całe obiekty, bo vector sam zaalokuje pamięć na nie

żeby nie było wątpliwości, std::vector<objects> używam jako "singleton", jest w jednym miejscu jako jedna kopia

Pomysl, jakie masz zyski z optymalizacji, jesli kopiujesz maly obiekt taki jak boost_shared_ptr<T> a T. Pamietaj, ze kazde wywolanie push_back wywojuje copy constructor i zysk jest widoczny nawet przy malych klasach.

Pozdrawiam serdecznie

a tak a propos to iterowanie mozna najszybciej tak zrobic:

std::vector<Object> objects;
for (std::vector<Object>::iterator i = objects.begin(); i!=objects.end(); ++i)
{
 // *i <-- aktualny obiekt
}

szybsze iterowanie od tego udalo mi sie osiagnac tylko jak zrobilem sobie prosta implementacje tablicy i zrobilem w zasadzie to co wyzej tylko bezposrednio na wskaznikach

@krwq:

Niestety to twoje "szybsze" iterowanie jest ok. 10 razy wolniejsze od tego co użyłem w pierwszym poście :)

Swoją drogą, jest w ktoś stanie wyjaśnić następującą rzecz?

Pierwszy przykład:

class Position
{
   UINT16 x;
   UINT16 y;
   BYTE z;
};

std::vector<Position> vector;

// Inicjacja vector'a
for(int i = 0; i < 10000000; i++)
{
    vector.push_back(Position(0,0,0));
}
 

Czas wykonywania: 350 ms

for(int i = 0; i < vector.size(); i++)
{
	Position pos = vector[i];

	if(pos.x == 0 && pos.y == 0 && pos.z == 0)
		pos.x = 1;
}

Czas wykonywania: 3600 ms

for(std::vector<Position>::iterator i = vector.begin(); i != vector.end(); i++)
{
      Position pos = *i;

      if(pos.x == 0 && pos.y == 0 && pos.z == 0)
            pos.x = 0;
}

Wyżej został użyty std::vector<Position>, teraz użyję std::vector<Position*>

Drugi przykład:

class Position
{
   UINT16 x;
   UINT16 y;
   BYTE z;
};

std::vector<Position*> vector;

// Inicjacja vector'a
for(int i = 0; i < 10000000; i++)
{
    vector.push_back(new Position(0,0,0));
}
 

Czas wykonywania: 14000 ms (??!!)

for(int i = 0; i < vector.size(); i++)
{
	Position* pos = vector[i];

	if(pos->x == 0 && pos->y == 0 && pos->z == 0)
		pos->x = 1;
}

Czas wykonywania: 17000 ms (??!!)

for(std::vector<Position*>::iterator i = vector.begin(); i != vector.end(); i++)
{
      Position* pos = *i;

      if(pos->x == 0 && pos->y == 0 && pos->z == 0)
            pos->x = 0;
}

Jak widać w pierwszym przykładzie został użyty czysty obiekt Position (5 bajtowy)
W drugim został użyty wskaźnik na ten obiekt (4 bajtowy)

Na logikę drugi przykład powinien być znacznie szybszy, a jest niesamowicie mniej wydajny.

Mógłby ktoś to wyjaśnić?

Czy jechales z tym w release czy debug?
Nie chce mi sie zbytnio w to wierzyc, poza tym to przy inkrementowaniu iteratorow powinienes uzywaz ++i a nie i++.

Pozdrawiam serdecznie

Tryb był ustawiony cały czas na Release i optymalizacje na Max speed.

Zmieniłem z it++ na ++it, obiekt dałem zamiast 5 bajtowego na kilka razy większy.

Wyniki są następujące:

2500 ms dla pętli z odwoływaniem się do vector'a za pomocą vector[i]
3600 ms dla pętli z iteratorem [begin(), end()]

I bardzo podobne czasy dla użycia vector'a z wskaźnikiem na obiekt zamiast bezpośrednio obiektu.

Tylko, że teraz obiekt zajmuje z kilkadziesiąt bajtów, a wskaźnik 4.
Więc jakim cudem podobne są czasy?

A co do iteratora to może po prostu jest wolniejszy od odwoływania się za pomocą [] ?

Pozdrawiam, mam nadzieje, że ktoś rozwiąże tę zagadkę.

Dziwne jest to, że rozmiar obiektu Object ma wpływ na czas dostępu do std::vector<Object*>

Przecież w tym kontenerze są przechowywane wskaźniki więc nie powinno mieć to wpływu?

Może się jakiś wypowie ekspert od znajomości std::vector?

Prawdopodobnie na długość wykonywania się kodu 3 i 4 wpłynęło środowisko lub wewnętrzna implementacja vector'a, na którą i tak nie masz wpływu.

Rożnicę między 1 i 2 oraz 3 i 4(choć ten pominąłem) masz tu mniej więcej widoczną - mogłem gdzieś się pomylić w ocenie co jest co, ale kody 1, 3 nie różnią się praktycznie w ogóle, więc 3 nawet nie opisałem.

Natomiast główny wpływ na dłuższe wykonywanie iteracji przykładu 2 w stosunku do 1 ma wykorzystanie iteratora i liczba wywołań funkcji w każdym obiegu pętli, które spisałem w podsumowaniu na 220 linijce.

Kod był kompilowany bez optymalizacji, ale optymalizację większej różnicy raczej nie zrobią poza tym o czym @Azarien napisał wcześniej.

Morał z tego taki, że nie masz odpowiedniego środowiska do robienia pomiarów oraz optymalizacji powinieneś szukać w algorytmach, a nie w takich głupotach jak iteracje.

Jeszcze do tego pytania z początku jak działa vector.size(). Otóż wektor przechowuje adres początku danych oraz adres elementu następnego po nich. vector.size() na podstawie tych wartości oblicza rozmiar wektora. Wzór jest taki:
(end - start) / sizeof(element), z tym że dzielenie jest wykonywane za pomocą przesunięcia binarnego w prawo.

Czas wykonywania: 350 ms
Czas wykonywania: 3600 ms
Czas wykonywania: 14000 ms (??!!)
Czas wykonywania: 17000 ms (??!!)

Pomiar czasu wykonania czegoś jest rzeczą trudną. Niektóre kompilatory (jak GCC) stosują bardzo agresywną optymalizację, w wyniku której np. takie coś

#include <stdio.h>
int main()
{
  int a=0;
  for (int i=1;i<=10;i++)
    a+=i;
  printf("%i\n",a);
}

kompilator gcc przy -O3 zamieni ci na

#include <stdio.h>
int main()
{
  printf("%i\n",55);
}

i całe mierzenie pętli diabli wzięli — gdyż została wykonana w czasie kompilacji, a a staje się po prostu stałą. Bez printfa

int main()
{
  int a=0;
  for (int i=1;i<=10;i++)
    a+=i;
}

jest jeszcze gorzej:

int main()
{
}

Ups! kompilator wywalił wszystko, skoro program i tak nic nie robi…

Dokładnie. Azarien dobrze naświetlił sprawę.

Kod:

for(int i = 0; i < vector.size(); i++)
{
        Position pos = vector[i];
 
        if(pos.x == 0 && pos.y == 0 && pos.z == 0)
                pos.x = 1;
}

w rzeczywistości nic nie robi - zmienna lokalna pos jest niby modyfikowana, ale jej stan w ogóle nie jest przesyłany dalej, więc kompilator w ogóle wycina całe ciało pętli. Natomiast w kodzie:

for(int i = 0; i < vector.size(); i++)
{
        Position* pos = vector[i];
 
        if(pos->x == 0 && pos->y == 0 && pos->z == 0)
                pos->x = 1;
}

następuje już modyfikacja wektora. Niby ten wektor już potem nie jest używany i nie wpływa na działanie programu, ale tego już kompilator nie dostrzega i nie optymalizuje.

Przy włączonych optymalizacjach nie widzę żadnych różnic pomiędzy wersjami (jeżeli brać pod uwagę tylko te co modyfikują wektor) :P Tzn różnice są w zakresie błędu pomiarowego: http://www.ideone.com/77WzE

Dzięki wielkie za wszystkie odpowiedzi.

Pozdrawiam