9 replies to this topic

[roboticforest]

So, I've overloaded the global new and delete operators, and now I have a nifty, pointer tracking, memory leak detector, yet this doesn't really help me in preventing memory fragmentation of the heap.

I would ask how to -undo- memory fragmentation, but this is looking more or less impossible. Instead, does anyone have any tips on how prevent, or limit fragmentation?

[dargueta]

Create separate heaps for different types, so there won't be any wasted space when items are freed. I only know how to do this in Windows, if that's what you're developing for.

EDIT: You could also just malloc your entire heap and implement a garbage collector / defragmenter yourself, but it'd make your program slow.

[roboticforest]

dargueta said:

Create separate heaps for different types, so there won't be any wasted space when items are freed.

That sounds good. I'm already doing something like this with special resources. (Images, for example.) Because of this I can have special manager classes that give out handles while swapping memory behind the scenes.

dargueta said:

You could also just malloc your entire heap and implement a garbage collector / defragmenter yourself...

That would be cool, except that the reason I've given up on making a defragmenter is as follows:

Someone calls new.
New returns a pointer.
Where is that pointer in memory?

Since the pointer itself is not created on the heap using new I have no idea where it is, or how many times the user has copied it. Also, because it's just a plain old pointer I can't tell it that I've moved the data that it's pointing to. In short, I can't safely rearrange the heap.

Smart pointers would be good, but as far as I know there is no way I can guarantee that they get used, and I'd have to use them everywhere which doesn't seem possible.

Any other ideas on how to manage memory fragmentation?

Heh... Since we're on the topic, anyone know how to make a defragmenter?

[Lance]

No you don't. I did not read really carefully but I believe essentially darguta advised you to use memory pool(do a search on memory pool), that's a technique commonly used by programmers who have same concerns.

Memory defragmentation in C/C++ will be extremely difficult as the virtual memory location has been exposed to the programmer. Let's say, void * p1, *p2, *p3 points to consecutive virutal memory blocks, and p2 was subsequently freed(deleted), now you want to combine p1 block and p3 block by either move p2 to the beginning or the end. Now the address of p1 and/or p2 will be changed and there is no way the defragmentor can know how many pointers are pointing to p1 block and p3 block and change their value accordingly. You can probably achieve that with one additional level of indirection, i.e. in all places you use
T *, you'll use T **, and maintain a map internally. I don't see any benefit of doing it this way over the more common memory pool approach.

[roboticforest]

Lance said:

...I believe essentially darguta advised you to use memory pool...

Memory defragmentation in C/C++ will be extremely difficult as the virtual memory location has been exposed to the programmer. ...

Ah, well... My design already uses a pool, and the exposure programmers have to the global heap is what's causing my problems.

Here's an example that with hopefully clarify why I can't shuffle around and defragment the memory.

Lets say that I use the memory pool to allocate, a tree, or list of some kind. Well, the memory pool gives me back a smart pointer, and it's safe for the memory pool to move around the list as much as it wants. The problem here is that the nodes within the list are not allocated using the memory pool, but by using good old operator new.

The catch is that, regardless of where the memory comes from, new gives back raw pointers to the nodes, not smart pointers to the nodes.

This brings us back to being unable to shuffle around the memory, because we can't tell raw pointers, created with operator new, that the memory they point to just moved.

Interesting problem, eh?

Even if I could have operator new return smart pointers -without- having the calling code know that it doesn't have a normal raw pointer, that wouldn't stop people from copying pointers around, thus bypassing that little trick.

[dargueta]

What you could do is have new return a pointer to a smart pointer. However, a defragmenter wouldn't be necessary if you created a separate heap for each type of object.

For example, let's say that we have two types of objects, type A which takes 10 bytes, and type B which takes up 5 bytes. If we allocate two objects of type B and one of type A, our heap might look like this:

[<-B-><----A---><-B->]

Now say we free both B objects:

[.....<----A--->.....]

There are currently 10 bytes free in our heap - enough to allocate another A object, right? Wrong. Those 10 bytes aren't contiguous. Although there's enough space, it's not all in one block. We can't move objects on the heap around without smart pointers, so we're stuck. However...

If we had two heaps, one from which we allocated only A objects and another from which we allocated only B objects, that would never happen. Because all objects in the heap are of the same size, whenever one is removed, it's guaranteed that another object of that same type will always fit in the space left behind.

All you have to do is keep your heaps separate, and you won't have to write a defragmenter, which would slow down performance a lot. Memory accesses would be slower because dereferencing smart pointers would require additional calculation to resolve the actual address, and defragmenting would hurt performance even more.

As for your tree problem, just overload new for the nodes too. What you could do is have new return a smart pointer class:

template <T>
template <K> //typecast type
class SmartPointer
{
    friend class HeapManager;
protected:
    T *data;
public:
    T *operator*(void) const; //overload dereference operator
    T& operator[](int index) const;  //array operator
    K *operator(K *)(void) const; //overload typecast
protected:
    void moveBlock(T *pnew);    //only accessible by heap manager
};

[roboticforest]

dargueta said:

What you could do is have new return a pointer to a smart pointer.

How would that work? Any place that expects to have direct access to the data being pointed to would need to be update to go through the extra layer of indirection. That won't be possible for anything I can't change the source code to.

dargueta said:

All you have to do is keep your heaps separate, and you won't have to write a defragmenter ...

I am doing that to an extent. There just isn't any way for me to make a new heap for -every- piece of data the program works with. Anything not covered by one of my many resource managers is falling to the global heap.

dargueta said:

As for your tree problem, just overload new for the nodes too.

I can't. I didn't design, nor do I have source for many things being used by my program. The tree was just a general example I made up.

dargueta said:

What you could do is have new return a smart pointer class

How? You can't overload a function by it's return type alone, and this would not work for anything not designed to use my smart pointers.

:-) Anyway, thank you for the code snippet, and the thorough response. Despite what it may look like, I'm not trying to be argumentative or shoot down -every- idea sent my way. It's a tricky problem.

So far, to sum things up so that we're all clear...
I'm using tools I did not design, and cannot change.
Those tools use operator new to allocate memory.
I can overload the global operator new and track memory leaks.
I cannot track the use and location of raw pointers being given to the libraries I use.
Due to that, I cannot defrag the memory the libraries use.

Hopefully you're all starting to see why I gave up on defragmenting memory for my current project, and only asked for tips on how to help prevent fragmentation. :-D

If anyone's got any more ideas I'd love to hear them. You've all been a lot of help just by getting me to explain the problem as we go.

Thank you all.

[Lance]

The answer is quite dependent on what classes you need to cope with and how frequently each will be new'd and delete'd.

The plan proposed below may be of no relevance in your situation though.

create memory pools according to size of objects to be allocated, eg.
1 for size ==1 (and all byte align'd objects)
2. size < = 4 except already included in 1
3. size <= x , etc, the fineness really depends on the objects you have, usually you do not need to use separate memory pool for really big objects

Then another question arise, how are you going to implete operator new [] () for each classes you intended to manage with a memory pool? I mean, where to put the cookies? You'll have to factor in this when you design you memory pools plan.


You'll have to accept there is no perfect solution to your problem unless intel and other major cpu vendors decide to support this extra level of indirection in their new cpus.

Go with memory pool, do a profiling, put your effort on those contribute to memory fragmentation the most. Every class should not be treated equally.

HTH.

[dargueta]

Oh, my bad. I thought this was some little project you were working on by yourself. What you could possibly do (provided you have the headers for the node classes) is insert extra entries for the operators and static variables, and then create another .cpp file that implements those functions. As long as you have the .lib or .obj files from the previous version, it should link properly.

[roboticforest]

dargueta said:

Oh, my bad. I thought this was some little project you were working on by yourself.

He he, yeah no.

I am by myself, but the project isn't even close to small.

dargueta said:

What you could possibly do (provided you have the headers for the node classes) is insert extra entries for the operators and static variables, and then create another .cpp file that implements those functions. As long as you have the .lib or .obj files from the previous version, it should link properly.

Now that's a nifty trick! I've never heard of that before.

I'm not sure off the top of my head if that will help with this particular project or not (I need to look into it), but I love knowing things like that regardless.