Thread: Quick question about memory allocation

I'm going to assume that your program is finished, and that you've profiled the code with some real-world data to see where the real hot spots are, and found that this is indeed a problem.

Use std::vector instead. It's a dynamic array and can work as a buffer instead and you won't have to worry about allocating/deallocating data.

I'm not sure I understand this correctly. I'm assuming you mean you don't have to concern yourself with the details of resizing the vector. If you store pointers to objects in the vector then you must call delete on those objects or your entire vector will leak memory.

Right, some background then. I had a chat with a professional game developer some time back where he told me he sped up their game by 40% by replacing all linked lists with dynamic arrays.

This does not mean you will get the same speed increase. The results of that could change significantly if you do not have the exact same engine structure or app structure as the fella you talked to. Linked lists are fine if you use them correctly but will be slow if you try to do 50 inserts and removes in a frame. The fundamental idea is to use the right data structure for the job. At work if I went in and changed all our linked lists to arrays and claimed it was purely for a 40% speed increase I probably wouldn't be too popular. I would hold what the fella said in the context it was said in. It does not mean since he got those results in situation A that you will get the same results in situation B.

It is far simpler to rely on easy simple straightforward code that doesn't use magic tricks to get the job done. Magic tricks cause code to become obfuscated, hard to maintain, and very error-prone. And if you are doing all of this just to see if you get the same increase I hope you have a copy of Araxis merge or some other merge program that you can use to 'undo' your handy work.

Kludge is right, for it is an assumption on your part that all pointer types have the same representation. This is not guaranteed.
http://www.c-faq.com/null/machexamp.html

Basically, are you saying you are reinventing std::vector which already does almost exactly what you want so that you can have a different erase method?

I think there might be easier solutions, such as simply writing your special erase function for a vector. May-be something along these lines:

Code:

template <class T>
typename std::vector<T>::iterator 
fast_erase(std::vector<T>& vec, typename std::vector<T>::iterator it)
{
    assert(it != vec.end());
    *it = *vec.rbegin();
    vec.pop_back();
    return it;
}

Possibly even faster, especially for member types like std::string:

Code:

template <typename T>
typename std::vector<T>::iterator
fast_erase(std::vector<T> &vec, typename std::vector<T>::iterator it)
{
  assert(it != vec.end());
  std::iter_swap(it, vec.rbegin());
  vec.pop_back();
  return it;
}

Originally Posted by Araanor

A linked list would imply links.

The class uses an array so the objects can be stored in sequence and not be fragmented across memory.
O(1) is achieved for insertion by inserting items at the end of the list.
O(1) is achieved for deletion by replacing the deleted item with the last one in the list.

This stuff with me looking to allocate memory without constructors and other fun headaches is just some smaller optimizations for the heck of it.

Ah, in that case since order is obviously unimportant, the container interface is really that of an unordered set or unordered multiset. The difference being that e.g. an std::tr1::unordered_set has about constant time operations on insert, delete AND lookup, whereas you have O(n) lookup.
Well that can certainly be acceptable if you don't use lookup very often.

Originally Posted by Araanor

That's good advice, but I wanted deletion in constant time.

I'll keep the original type of the pointers - I just thought of a new kludge instead! Which is:

Code:

union
{
	void *mMemory
	ObjectType *mObjects;
};

So allocation and deletion is done with mMemory, and objecty stuff is done with mObjects. It's the first time I found a use for unions! Go me.

Erm...
If anything, it should be the other way around. Allocate in mObjects and assign the address to mMemory later. Allocate and delete the same variable.
But all this is irrevant if you use std::vector.
All you can do is:

Code:

class MyClass
{
	int mem1;
	int mem2;
	float mem3;
	struct grr
	{
		UINT64 a, b, c;
	} grr;
};

	MyClass c1, c2, c3, c4;
	std::vector<MyClass> v;
	v.push_back(c1);
	v.push_back(c2);
	v.push_back(c3);
	v.push_back(c4);

This works just as well, and no memory leaks.

I understand that it would be faster to use swapping, if the swap function was more efficient than assignment.

However, the references say:

A call to iter_swap() exchanges the values of two elements exactly as a call to swap( *a, *b );

The swap() function swaps the values of a and b.
swap() expects that its arguments will conform to the Assignable model; that is, they should have a copy constructor and work with the = operator. This function performs one copy and two assignments.

So, to gain anything from it I would have to overload the swap function for my type (and use using std::swap to make it choose the overload)?
However, then there would be unnecessary overhead for types that don't / cannot implement swap efficiently. Is there a way to make fast_erase choose swapping automatically if there is a swap method present for the type and use assignment otherwise?