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.
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
You'll just love to hear that this is the first class I'm writing.
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. I was fascinated by the idea. See, I'm writing a small game now. Yes, yes, premature optimization is the devil. I just thought it'd be interesting.
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.
It's bad habit to actually do delete on pointers which you've changed their original type from (exception for polymorphism, if you use virtual destructors). And you really shouldn't have to change type. With templates in C++, you have a lot of power to keep the type all the time.
Remember, the best way to avoid memory errors is simply to delete what you get from new. Don't change pointer type and call delete.
If you keep that in mind, the compiler will do the rest.
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:
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.Code:union { void *mMemory ObjectType *mObjects; };
Ah, right, I wanted to ask something too:
Any particular reason for going in the reverse direction? Well I guess objects are usually deleted in the reverse order of creation... Hm, I suppose that's reason enough.
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.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.
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.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.
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.
Last edited by VirtualAce; 11-17-2007 at 04:45 PM.
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
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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; }
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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; }
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
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.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
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:
This works just as well, and no memory leaks.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);
Last edited by Elysia; 11-18-2007 at 12:22 AM.
You're right.
I realise the problems with messing around with memory management. If the class proves to be too much trouble, I'll eject it. But until then, I'll see it to a somewhat finished state.
Some more background: I've had a long break from programming. The main point of me programming right now is to get into the groove and improve my skills. I can afford trying magic tricks.
Right, remembered this after a good night's sleep. But things should be fine if I have separate pointers for void *mMemory and Object *mObjects, right? Every time allocation is done to mMemory, mMemory is also cast into mObjects.
That's a thought. Might be a very good tradeoff.
I suppose. Access will basically be "Loop through the list and update each element".
Is std::tr1::unordered_set some kind of hash table?
I'm not following you. I don't want to construct an entire array of objects prematurely.
Eh, well, not being familiar with allocators I wouldn't know.
Basically, if you want char, allocate a char array, then delete it.
If you want my_object, then allocate an array of my_object, then delete it.
Don't go allocating something and casting it to void*. You don't need to do :perator new either if you just stick to your objects. Don't mess around with them - just use them as you would, without changing the type. Then delete will work just fine.
No, I don't want char. I don't even want an array of my_object. I want a region of memory where I can put my objects. CornedBee made a good post on how this is possible. I'd only be casting from void*, and only when new memory is allocated.
I understand that it would be faster to use swapping, if the swap function was more efficient than assignment.
However, the references say:
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)?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.
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?
Last edited by CornedBee; 11-18-2007 at 05:31 AM.
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.