• 10
• 10
• 12
• 12
• 14
• entries
17
22
• views
7024

# Dumb Pointers made Smarter... AND MORE

201 views

Journal Entry for 8/23/05 12:30 A.M.
Well, if you're reading this, then you've most likely noticed that I am almost at the bottom of the journal page. Oh well, I'm sure they'll get around to reactivating it soon.

Anyway, I accomplished some more on memory management tonight. I implemented a heap tracer so I will know if something doesn't get deallocated before the app dies. I decided against overloading the new/delete operators as I have found that my overloaded delete may not always get called in the event a constructor throws an exception. Instead I went with inline macros again. It all worked out great. It will tell you which file/function/namespace/line number that the pointer was allocated in on both creation and deletion. If a pointer is never freed, the tracer will output where it was originally created so you can track it down quickly.

Next on the menu is implementing all of this into my old engine! I'm finally moving on! It will all have been worth it in the long run I'm sure.

Journal Entry for 8/22/05
Well, last friday I sent a request to the GD.Net Gods for a name-change from JohnMMena to NoMonkey. Unfortunatelly when they switched the name it deactived my GD.Net service.

So for the meantime, I am just going to update my last entry until things get straightened out.

I got the Smart pointers within 1 second of the standard new/delete. I really think I finally got them where I want them... maybe :).

I also implemeneted freelist's which turned out to be a pain all because of one very weird problem. When I would use the freelist on a simple base class, it worked fine, but for shits and giggles I decided to use it on my smart pointer class. When I did this, I would get a user breakpoint somewhere in the heap debugger stating that some memory had moved blah, blah, blah and I think there was something about my momma being fat in there too. Anyway, after beating my head over the problem for hours, I found that if I didn't initialize one variable in the default constructor of the smart pointer class, it would run okay, but had memory leaks.

So after wanting to grab my shot gun, load my computer up onto a launcher and yell "PUUUUULLL!", I decided to let some fresh eyes take a look at it and sent it over to Visage.

He and I went back and forth on the possible problems and after mulling it all over we came to the conclusion that there couldn't be anything wrong with the code whatsoever. Then, out of desperation, I changed my initial variable allocation of the freelist from new to malloc and to he and I's surprise, it worked. I think his exact quote was "I feel worthless as a programmer right now."

Anyway, problem solved and everything seems to be working okay. I think I'm going to look into overloading new/delete for memory tracing next. Then once this is complete, I might be able to move on to the actual engine work! But I doubt it. :)

Keep it real!

Journal Entry for 8/19/05
Well, after consulting with Eberly (3D Game Engine Architecture) on the whole slow pointer issue, I finally got these things to run at a reasonable speed.

My new numbers at n=10,000,000 loops is now:

Empty test loop took 0.031000 seconds

Standard new/delete took 44.860000 seconds

mem_ptr new/release took 99.985000 seconds

The last one of course being my smart pointer. I ran this on a different, slower machine which is why the numbers are larger in general. The cool thing is that the spread between the standard new/delete vs. mem_ptr new/release is only 55 seconds whereas on the other machine w/ the older code it was 173 seconds. That's only ~0.00001 seconds of overhead per alloc/dealloc pair. Not to mention the time for the smart pointers is faster with the newer code on the slower machine than the older code on the faster machine. (Say that 10 times fast!)

To gain this speed, I implemented Eberly's hash table.

Given how fast I can allocate 10 million objects, I think I can finally wrap these babies up and move on!

Next up: Free Lists!

I've already found a pretty kick ass free list example that runs the above loop in less than a second. I'm also debating on memory pools, but I'm getting mixed reviews on what people think about their reliability/performance.

[UPDATE]
I made some more optimizations to the code, my numbers are now:

Empty test loop took 0.047000 seconds
Standard new/delete took 45.844000 seconds
mem_ptr new/release took 51.968000 seconds

How do you like them apples? I'm much happier with these results!
[/UPDATE]

Thanks again for looking!

Woah. Woah. I think I am going to go read Eberly again.

EDIT: Okay, I ran my own tests. Here they are:
TimerPtr t("Timer");
double starttime = t->getCurTime();
for(int i = 10000000; i > 0; --i)
{
}
cout << "Empty loop: " << (t->getCurTime() - starttime) / 1000.0f << endl;

starttime = t->getCurTime();
for(int i = 10000000; i > 0; --i)
{
Scale *s = new Scale();
delete s;
}
cout << "Standard new/delete: " << (t->getCurTime() - starttime) / 1000.0f << endl;

starttime = t->getCurTime();
for(int i = 10000000; i > 0; --i)
{
ScalePtr s;
}
cout << "Smart pointer with free list: " << (t->getCurTime() - starttime) / 1000.0f << endl;



There is the code. Here is the output:
Empty loop: 0.063
Standard new/delete: 6.246
Smart pointer with free list: 0.744


That was a lot faster than I expected. Anyway, the ScalePtr is my smart pointer tied into my object factory, which upon creation requests a Scale object (creates one if none exist), and adds a reference. Upon destruction, it removes a reference. If references equal zero, it returns its memory to the free list as "available" memory.

I can send you my code for both my object factory, my free list, and my smart pointers if you want. However, my smart pointers rely on a base Object class. Though, mine is different than Eberly's. I didn't like the idea of having all objects be forced as instances (because RemoveRef() called delete this;) -- so I have the objects handle reference counting, but the smart pointers deal with verifying the count.

Holy crap! your numbers a lot better than mine! Even for the standard new/delete. I wonder why they are so slow on my machine?

My specs on the slower machine are:
AMD 2700
512 RAM

and on the faster machine:
Intel HT 2.8GHz
2GB RAM

Even on the faster machine the numbers are a lot worse than yours. When I get home, I'm going to redo my test in the same fashion as yours to get a better comparison.

[EDIT]
Did you by chance overload new/delete for the Scale object? I just ran this test again but in the same manner you did, and the numbers for new/delete were still terrible.
[/EDIT]

Also, I'm not sure exactly which results you were going for, but if you subtract the time it took to run the empty loop from the others, you can get just the time analysis of the actual allocations/deallocations.

I'd definitely like to look over your free list. The one I found is basically a singly linked list. It is very fast, but I'd like to look at some other examples.

Thanks for the constructive response!

Nope, no overloading. I have a 1.67 GHz powerbook G4 with 2 gigs of RAM.

Here is the code, with comments to tell what each file does

ObjectFactory.h
The global class -- It is a singleton. It has the ability to pre-register a class with specific chunk sizes.
#ifndef __OBJECT_FACTORY_H__
#define __OBJECT_FACTORY_H__

//Memory protected (cache missing prevention) free lists are not finished
#define MEMORYPROTECTEDFREELISTS

#include "precompiled.h"

#include "Object.h"

#include "FreeList.h"
#include "MemoryProtectedFreeList.h"
#include "ListFreeList.h"

#include "Singleton.h"

namespace Symphony
{

//templated for Base Class
class ObjectFactory : public Singleton<ObjectFactory>
{
private:
//Built in helper classes.  Ew.
class BaseFreeListWrapper
{
public:
virtual ~BaseFreeListWrapper(){};
//virtual FreeList<BC> operator -> ()=0;
virtual Object * getInstance() = 0;
virtual void FreeInstance(Object *instance) = 0;
};

template <typename T>
class DerivedFreeListWrapper : public BaseFreeListWrapper
{
public:
DerivedFreeListWrapper(int iInitialSize, string className)
{
myFreeList = NULL;
#ifdef MEMORYPROTECTEDFREELISTS
myFreeList = new MemoryProtectedFreeList<T>(iInitialSize, className);
#else
myFreeList = new ListFreeList<T>(iInitialSize, className);
#endif
}

~DerivedFreeListWrapper()
{
if(myFreeList)
delete myFreeList;
}

/*
inline FreeList<BC> operator -> () {
return *myFreeList;
};
*/

inline Object * getInstance()
{
if(myFreeList)
return myFreeList->getInstance();
return NULL;
}

inline void FreeInstance(Object *instance)
{
if(myFreeList)
myFreeList->FreeInstance((T*)instance);
return;
}
private:
FreeList<T> *myFreeList;
};

typedef BaseFreeListWrapper free_list;
typedef std::map<std::string, free_list*> obj_map;
typedef obj_map::iterator obj_iterator;
typedef obj_map::const_iterator const_obj_iterator;

private:
obj_map registered;
public:
enum CREATION_EXPECTANCY
{
ONCE = 1,
ALMOST_NEVER = 5,
LOW = 20,
MEDIUM = 50,
HIGH = 500,
EXTREMELY_HIGH = 2000
};

ObjectFactory()
{
DEBUG_LOG(Logger::INFO, "Initializing Object Factory");
}

~ObjectFactory()
{
destroyAll();
}

void destroyAll()
{
DEBUG_LOG(Logger::INFO, "Deconstructing Object Factory");
//we must iterate through the map and destroy the FreeLists
obj_iterator cur = registered.begin();
//they are stored in std::pairs, so we have to delete the .second
//since .first is the key
for(; cur != registered.end(); ++cur)
delete cur->second;
registered.clear();
}

template <class T>
inline bool registerClass(const char *className, int ce)
{
DEBUG_LOG(Logger::INFO, "Registering class: " << className << " with " << ce << " in the FreeList");
//here, we must register the class

//obj_iterator cur  = registered.find(className);
//if(cur != registered.end()) //its already registered
//	return false;

switch(ce)
{
case ONCE:
{
registered[className] = new DerivedFreeListWrapper<T>(ONCE, className);
} break;
case ALMOST_NEVER:
{
registered[className] = new DerivedFreeListWrapper<T>(ALMOST_NEVER, className);
} break;
case LOW:
{
registered[className] = new DerivedFreeListWrapper<T>(LOW, className);
} break;
case MEDIUM:
{
registered[className] = new DerivedFreeListWrapper<T>(MEDIUM, className);
} break;
case HIGH:
{
registered[className] =

0