Moja implementacja stosu jest szybsza?!

Question

Witam

zrobiłem sobie ostatnio implementacje stosu, kolejki i listy w C++ i wszystko działa fajnie, ale postanowiłem porównać szybkość mojego stosu ze stosem z C++ (z biblioteki stack). I wyszły mi zaskakujące wyniki bowiem mój jest ponad 6 razy szybszy!

Mój stos:

template<class T>
class Stack
{
	class Component
	{
	public:
		T value;
		Component *next_component = nullptr;
		Component(T &value)
		{
			this->value = value;
		}
	};
	Component *c = nullptr;
	std::size_t _size = 0;

public:
	const bool is_empty() const { return c == nullptr; }
	const std::size_t size() const { return _size; }
	void push(T value)
	{
		_size++;
		if (c == nullptr)
		{
			c = new Component(value);
		}
		else
		{
			Component *temp = new Component(value);
			temp->next_component = c;
			c = temp;
		}
	}
	T pop()
	{
		if (c == nullptr) throw std::out_of_range("Cannot pop from the stack - it is empty!");
		_size--;
		Component *temp = c->next_component;
		T value = c->value;
		delete c;
		c = temp;
		return value;
	}
	T& peek() const
	{
        if (c == nullptr) throw std::out_of_range("Cannot peek the stack - it is empty!");
		return c->value;
	}
	void clear()
	{
		std::size_t *_ptr = &_size;
		while (*_ptr) {
			(*_ptr)--;
			Component *temp = c->next_component;
			delete c;
			c = temp;
		}
	}
	~Stack()
	{
		clear();
	}
};

Metoda porównania:

#define SIZE 1000
#define TESTS 100
long long tab[SIZE];

void test()
{
	clock_t begin_time;
	float time;
	begin_time = clock();
	for (int i = 0; i < TESTS; i++)
	{
		std::stack<long long> s;
		for (int j = 0; j < SIZE; j++)
			s.push(tab[j]);
		for (int j = 0; j < SIZE; j++)
			s.top() += 50;
		while (!s.empty())
			s.pop();
	}
	time = float(clock() - begin_time) / CLOCKS_PER_SEC;
	std::cout << "System's stack: " << time << endl;

	begin_time = clock();
	for (int i = 0; i < TESTS; i++)
	{
		Stack<long long> s;
		for (int j = 0; j < SIZE; j++)
			s.push(tab[j]);
		for (int j = 0; j < SIZE; j++)
			s.peek() += 50;
		while (!s.is_empty())
			s.pop();
	}
	time = float(clock() - begin_time) / CLOCKS_PER_SEC;
	std::cout << "My stack: \t" << time << endl;
}
int main() {
	srand(time(nullptr));

	for (int j = 0; j < SIZE; j++)
		tab[j] = rand();

	for (int i = 0; i < 10; i++)
		test();//10 testów dla pewności

	getchar();
	return 0;
}

Oraz wyniki:

Moje pytanie brzmi: dlaczego? przecież domyślny stos powinien być lepiej zrobiony i powinien być szybszy

Pozdrawiam

Comments

A optymalizacje kompilatora włączyłeś? Bez nich nie ma co mierzyć.

---

Wszystko domyślnie ustawione mam, ale już wiem - tryb debug jest wolniejszy...

Answer 1

Skompiluj to w trybie release zanim zabierzesz się kiedyś znowu za pomiary. 

System's stack: 0.000465
My stack:     0.002924
System's stack: 0.000459
My stack:     0.002844
System's stack: 0.000447
My stack:     0.002841
System's stack: 0.000446
My stack:     0.002845
System's stack: 0.000449
My stack:     0.002861
System's stack: 0.000456
My stack:     0.002915
System's stack: 0.000445
My stack:     0.002834
System's stack: 0.000441
My stack:     0.002856
System's stack: 0.000444
My stack:     0.002785
System's stack: 0.000442
My stack:     0.002754

Btw twoja implementacja stosu jest pod wieloma względami upośledzona (brak iteratorów, możliwości użycia własnego alokatora, nie da się go porpawnie skopiować / przypisać), więc użyłbym std::stack nawet gdyby rzeczywiście był 6 razy wolniejszy.

Comments

Tak, to ma teraz sens :D Wiele wyjaśnia, ale na to nie wpadłem:)