why my vector class is alot slower than default vector class.

[Gyiove]

my vector:http://pastebin.com/5q7scy2k

LARGE_INTEGER t_start_counter, t_current_counter;
void tstart()
{
	QueryPerformanceCounter(&t_start_counter);
}

double tend()
{
	QueryPerformanceCounter(&t_current_counter);
	double out;
	out = (double)(t_current_counter.QuadPart - t_start_counter.QuadPart);
	out *= 0.000001;
	return out;
}

int main() {
	int a = 0;
	spvec<int> v;
	vector<int> i;
	double t1 = 0.0, t2 = 0.0;

	tstart();
	for (a = 0; a < 83886; a++) v.push(a + 100);
	t1 = tend();

	tstart();
	for (a = 0; a < 83886; a++) i.push_back(a + 100);
	t2 = tend();

	cout << "times:" << t1 << "/" << t2 << " ration:" << t2 / t1 << endl;
	return 0;
}

I think i have alot of learning to do before i start creating something at all.
results:
times:3.61922/0.003251 ration:0.00089826

I really need some help...
2 version, I'm just too stupid or i have to do some reading.
I read the code of default vector and now im trying to understand
everything what there is going on.
( its in progress right now ... still learning those new unknown stuff from there )


To be honest i don't understand what is going on there.
I thought that the only way of increasing dynamic array size is to
create new array with new size, copy old elements and delete old array and replace pointer but thats just horrible as my inside feeling told me.

Question to senior programmers.
Do i have hope to jump from this hopeless condition to condition where
i can actually do something what is better or same when it comes to
performance and effectiveness?

Any advice how i can improve myself?
( anything is welcome, even those big boring articles )

Perhaps my problem here is that im using really old methods.
I hope thats the case, it seems obvious.

( also please don't mind my re inventing wheel thing, i just really like to waste my time on that. )
Thank you.

[Ceset]

Dont reinvent wheel, why?

Wheel is around for 6000 years. You think starting from zero makes you smart or better? Take the current wheel and go further with it.

As for your class, you would get surprised to know what kind of tricks are used inside vector class.

I can guarantee that this won't improve you. Only thing it did is to show you that how incapable a human is alone.

Think about this, Bjaurne Strasstrup, creator of c++, get help from many people and although he is the creator he didn't even do the half job. I can guarantee he couldn't even if he tried to do so.

Use what is provided and create your own only when you have to.

[Peter87]

First of all I hope you have turned on optimizations (Release mode) because you don't really care about the performance of unoptimized code.

You should not have to create a new array each time you call push. The way std::vector does it is that when it runs out of space it allocates a larger array that is some percentage of the old size (often 200%, but I think VC++ uses 150%). If you double the size each time you only have to allocate a new array 18 times while adding all 83886 elements.

http://en.wikipedia.org/wiki/Dynamic_array

[cire]

Running the following might give you some insight.

// http://ideone.com/BrqbmZ
#include <iostream>
#include <vector>

bool reallocation_check(const int*& data, const std::vector<int>& v)
{
    if (data != v.data())
    {
        std::cout << "Reallocation at size: " << v.size() << "\nNew capacity: " << v.capacity() << '\n';
        data = v.data();
        return true;
    }

    return false;
}

int main()
{
    const unsigned limit = 83886;

    std::vector<int> v;
    const int* data = v.data();
    unsigned reallocations = 0;


    for (unsigned i = 0; i < limit; ++i)
    {
        v.push_back(i + 100);
        if (reallocation_check(data, v))
            ++reallocations;
    }

    std::cout << "Reallocations: " << reallocations << '\n';
}

How many allocations does your custom vector make?

[ne555]

> why my vector class is alot slower than default vector class.

> Perhaps my problem here is that im using really old methods.
> I hope thats the case, it seems obvious.

my mind reading cat is not with me right now.
If you want advice about how to improve your vector implementation, then you ought to show your vector implementation.

Also, you may want to learn to use a profiler
http://sourceware.org/binutils/docs-2.25/gprof/index.html

[Gamer2015]

I implemented one and it is faster on my mashine. (only implemented push_back)
I think i cheated a little bit at the part where std::vector invokes the move-constructor for all "old" elements in case of reallocation, i just did memcopy there.
(Is it possible for an object to be copyable but not moveable? does that concept make sense anywhere?)

You should show us your code so we can help you.

[Ceset]

Does noone agrees with me on reinventing wheel?

[Gamer2015]

I think you should do it if you want to spend your time with it.

Is it a good idea?
Who knows, you'll find out after you're through with that topic.
You'll learn some things like placement new, move constructors and perfect forwarding if you are very motivated.

Show us your code and we can help you! ;)

[Gyiove]

i forgot to post my class code
here it is:http://pastebin.com/5q7scy2k

@Peter87
Thanks for you my vector is almost at the same speed as default vector
here was the result:
> You should not have to create a new array each time you call push. The way std::vector does > it is that when it runs out of space it allocates a larger array that is some percentage of the
> old size (often 200%, but I think VC++ uses 150%)

but i think its just an horrible way to do it, allocating so much more memory.
I have reserv_step variable what allocates reserv_step + 1 + oldsize.
But i think i might at that feature of default vector to mine.

[Gamer2015]

but i think its just an horrible way to do it, allocating so much more memory.

Why do you think that?
If you don't want that overhead you can just shrink_to_fit (in C++11).
If you don't want to use C++11 you can use a little trick:
std::vector<T>(vec).swap(vec);

I think this is a great way to do it because it increases the performance by a large factor.

[Peter87]

Note std::vector has the reserve function, so if you know how many elements you are going to have you can avoid reallocations and extra memory usage all together.

vector<int> i;
i.reserve(83886);
for (a = 0; a < 83886; a++) i.push_back(a + 100); // no reallocations 

http://www.cplusplus.com/reference/vector/vector/reserve/

[Peter87]

but i think its just an horrible way to do it, allocating so much more memory.

Are you sure 50% extra memory usage on average (if you use the doubling strategy) is such a big deal? If you think so, then you should also care about what types you are storing in your vector. Do you really need an int, is a short enough, or maybe a char? Maybe use float instead of double? If you are able to use a smaller datatype in your vector that will save at least as much memory as is wasted by the doubling array size strategy.

[Gyiove]

@Peter87
> Are you sure 50% extra memory usage on average (if you use the doubling strategy) is such a big deal?

Yes and no.
It depends on many thing.

Anyways, how's my costom vector code?
Is there something you would do differently ?
Code:http://pastebin.com/5q7scy2k

[Gamer2015]

Yes and no.
It depends on many thing.

It's a performance gain for a little bit memory.
You can deallocate that memory if you want to so you still have that gigantic performance gain and no memory overhead.

Anyways, how's my costom vector code?
Is there something you would do differently ?

Yeah here are a few things:

1.) I'd try to name the functions like those in std::vector
2.) I'd make the data private and use other names.
3.) I'd pass a const-reference instead of a pointer to push
4.) I'd use an allocater for allocation and deallocation
5.) I'd add a copy- and move-constructor

[Gyiove]

@Gamer2015
Can you also tell me why you prefer to use that instead of this?

Updated code:
http://pastebin.com/EYQqZmDT

My vector is now 1.8(almost 2x!) faster than default vector.
testing code:

LARGE_INTEGER t_start_counter, t_current_counter;
void tstart()
{
	QueryPerformanceCounter(&t_start_counter);
}

double tend()
{
	QueryPerformanceCounter(&t_current_counter);
	double out;
	out = (double)(t_current_counter.QuadPart - t_start_counter.QuadPart);
	out *= 0.000001;
	return out;
}

int main()
{
	int a = 0, b = 0;
	spvec<int> v;
	vector<int> i;
	double t1 = 0.0, t2 = 0.0;
	v.reservstep_grow = 1.5f; // increased reserved spot 150% of size


	tstart();
	for (a = 0; a < 16777216; a++) v.push(a + 100);
	t1 = tend();

	tstart();
	for (a = 0; a < 16777216; a++) i.push_back(a + 100);
	t2 = tend();
	

	cout << "times:" << t1 << "/" << t2 << " ration:" << t2 / t1 << endl;
}

results:
times:0.17494/0.321027 ration:1.83507

I haven't tested other functions yet but the question is
how does default vector clear function works?
Does it do:
delete [] data
size = 0

or it does the same like my clear() function?

[andywestken]

Does it do:
delete [] data
size = 0

No - it's rather more involved than that.

I've posted some of the code from the version of <vector> which comes with Microsoft Visual Studio below.

The destructor function is called explicitly (not something you should normally do) which allows the object to be 'destroyed' without deallocating the storage.

The reason that the destructor is called explicitly is because the objects were originally contructed using placement new, which was done so the lifetime of the memory storage could be decoupled from that of the objects stored in the vector.

Andy

From the Visual Studio version of <vector>

	void clear()
		{	// erase all
		erase(begin(), end());
		}

where

	iterator erase(const_iterator _First_arg,
		const_iterator _Last_arg)
		{	// erase [_First, _Last)
		iterator _First = _Make_iter(_First_arg);
		iterator _Last = _Make_iter(_Last_arg);

		if (_First != _Last)
			{	// worth doing, copy down over hole

 #if _HAS_ITERATOR_DEBUGGING
			if (_Last < _First || _First._Mycont != this
				|| _First._Myptr < _Myfirst || _Mylast < _Last._Myptr)
				_DEBUG_ERROR("vector erase iterator outside range");
			pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
				_VEC_ITER_BASE(_First));
			_Orphan_range(_First._Myptr, _Mylast);

 #else /* _HAS_ITERATOR_DEBUGGING */
			pointer _Ptr = _STDEXT unchecked_copy(_VEC_ITER_BASE(_Last), _Mylast,
				_VEC_ITER_BASE(_First));
 #endif /* _HAS_ITERATOR_DEBUGGING */

			_Destroy(_Ptr, _Mylast);
			_Mylast = _Ptr;
			}
#if _HAS_ITERATOR_DEBUGGING
        return (iterator(_First._Myptr, this));
#else
		return (_First);
#endif
		}

which, a few calls later, calls a different version of _Destroy

		// TEMPLATE FUNCTION _Destroy
template<class _Ty> inline
	void _Destroy(_Ty _FARQ *_Ptr)
	{	// destroy object at _Ptr
	_DESTRUCTOR(_Ty, _Ptr);
	}

where the macro _DESTRUCTOR is

#define _DESTRUCTOR(ty, ptr) (ptr)->~ty()

which you can see calls the destructor function explicitly. This is not somethign you normally do, but has to be done here as the objects were originally contructed using placement new.

You have a copy of <vector> somewhere on your machine if you want to dig down further.

[ne555]

> My vector is now 1.8(almost 2x!) faster than default vector.
I'm not seeing such a thing

times:0.133755/0.081817 ration:0.611693

¿are you compiling with optimizations?

By the way, your ratio is backwards


> Can you also tell me why you prefer to use that instead of this?
¿what are «that» and «this»?


> how does default vector clear function works?
my implementation does something like this->erase( this->begin(), this->end() )
That will ask the allocator to destroy every element. No memory is released (capacity remains the same).

I suppose that for POD it may change to make it constant time like yours.

[JLBorges]

> how does default vector clear function works?
> or it does the same like my clear() function?

Prior to C++11, clear() was defined in terms of erase().

C++11 specified that clear() should
a. remove all elements from the container (post condition: empty() == true)
b. leave the capacity() unchanged
c. must not throw exceptions (must be adorned with a noexcept)

C++14 added that the time complexity is linear (unintended omission in C++11).

For a vector which is not allocator-aware, but is otherwise like the standard vector, the implementation of clear() could be something like this:

#include <type_traits>

template < typename T > struct my_vector
{
    // ...

    void clear() noexcept
    {
        // note: the condition is a constexpr; we can safely expect the compiler to
        // optimise away dead code. ie. for trivially_destructible types, clear() is just sz = 0 ;
        if( !std::is_trivially_destructible<T>::value )
            for( std::size_t i = 0 ; i < sz ; ++i ) buffer[i].~T() ;

        // note: the standard requires that the destructor of T must not throw

        sz = 0 ;
    }

    private:
        T* buffer ;
        std::size_t sz ; // size
        // ...
};

Tip: test your code with non-trivial, moveable types (for instance, elements of type std::string)

[Gyiove]

I'm not seeing such a thing
times:0.133755/0.081817 ration:0.611693
¿are you compiling with optimizations?

Yes, Here's my options:
http://www.upload.ee/image/4716800/op.png

To be honest, i want to know what happens with my code after it compiles with
optimizations.

I hope g++ includes same thing, haven't tested things on linux yet.
I'm prepared for surprises.

Can you also tell me why you prefer to use that instead of this?
¿what are «that» and «this»?

Read the post before me, post that @Gamer2015 posted.

Now i have new question.
Does those new c++ versions like c++11 or c++14 includes something i can't do
with old versions?

Do they include new ways what are faster and replacement for old ways?

[JLBorges]

> Does those new c++ versions like c++11 or c++14 includes something i can't do with old versions?
> Do they include new ways what are faster and replacement for old ways?

Yes.
See: https://en.wikipedia.org/wiki/C%2B%2B11#Core_language_runtime_performance_enhancements