Sign in to follow this  
MENTAL

List container with free list.

Recommended Posts

For the purposes of "fun" and "education", I'm having a go at writing my own list container. The functionality of the container is complete, and now I want to go about improving the speed of it. The area that instantly stood out for me was memory management. The list container is node-based, so when you add an item to the list it allocates a new node and copies the value to be inserted into it, before linking it to the list. When removing the node, it is unlinked from the list and deleted (which will also destruct the value contained in it). What I was looking to do was instead of deleting the node, I would destruct its value (i.e. placement delete) and then move the node into a free list. The next time a new value is added into the list, it can check the free list to see if there are any unused nodes. If so, it pulls it off and inserts it into the main list, thus saving an allocation (the node's value would need to be reconstructed using placement new). The problem I come to is this. When the time comes for the container to release all of its memory, I will call delete on every node created by the list. For the ones in use this will be fine, but for the nodes in the free list, this will cause the compiler to trigger the destructor for an already destructed member, causing a wonderful cascade of errors. The solution I came up with was to stop using new and delete and instead switch over to malloc and free. When creating a new node, I would allocate the memory needed for the node's values and pointers. The only thing that would need constructing is the value itself, so I could call placement new on that member. When deleting the nodes during the list's destruction, I would call placement delete on the values on the main list, and then call free () on the node itself. This would just release the memory without any destructors being called. Here's an example:
template <typename T> struct ListNode
{
    T value;
    ListNode<T> *next;
    ListNode<T> *previous;
};

// The list needs a new node. Pull one from the free list or allocate a new one.
ListNode<T> *List<T>::CreateNode (const T &value)
{
    ListNode<T> *created_node = NULL;

    if (!m_free_nodes)
    {
        // I know I need to cast this properly.
        created_node = malloc (sizeof (T));
    }

    else
    {
        created_node = m_free_nodes;
        m_free_nodes = m_free_nodes->next;
    }

    if (!created_node)
    {
        // Throw exception
    }

    new (&created_node->value) T (value);
    // Next and previous are filled out by CreateNode's caller.

    return created_node;
}

// Put a node onto the free list. It has already been unlinked from the main list.
void List<T>::RecycleNode (ListNode<T> *node)
{
    node->value.~T ();

    node->next = m_free_nodes;
    m_free_nodes = node;
}

void List<T>::~List ()
{
    DestroyList (m_main_list, true);
    DestroyList (m_free_list, false);
}

void List<T>::DestroyList (ListNode<T> *list_start, bool destruct_value)
{
    while (list_start)
    {
        ListNode<T> *next_node = list_start->next;

        if (destruct_value)
            list_start->value.~T ();

        free (list_start);
    }
}

This this make any sense, and is it the right way to go about solving the problem? Thanks in advance for any help :)

Share this post


Link to post
Share on other sites
Option 1:
1. Implement std::allocator, let's say MyAllocator
2. std::list<T, MyAllocator>
3. Profit?

Option 2:
1. use boost intrusive library.

Option 3:
1. use boost pool


With each of the above, you can expect up to 50 times reduced run-times, without any modifications to the code.

Quote:
The solution I came up with was to stop using new and delete and instead switch over to malloc and free.


These don't really save anything. With free list, it's customary to use appropriate overloads of new to (de)allocate the objects.

And not calling destructors is just bad mojo, enough to make such implementation literally worthless. If destructor is trivial, no code will be generated for it anyway, it won't even result in function call, thanks to templates. If it's non-trivial, it needs to be called.

Quote:
This this make any sense, and is it the right way to go about solving the problem?


The problem is trivial to solve by not abandoning sanity, and using text-book examples of bad practices, such as malloc/free in combination with class instances.

Share this post


Link to post
Share on other sites
Quote:
Option 1:
1. Implement std::allocator, let's say MyAllocator
2. std::list<T, MyAllocator>
3. Profit?


No, as the opening sentence quite clearly states that I'm creating my own containers as a learning experience. And even so, your answer gave no insight into how to create an allocator that handles lots of small objects being created and destroyed frequently, which was the point of this post.

Quote:
Option 2:
1. use boost intrusive library.


See the above reply.

Quote:
Option 3:
1. use boost pool


See the above reply.

Quote:
These don't really save anything. With free list, it's customary to use appropriate overloads of new to (de)allocate the objects.

And not calling destructors is just bad mojo, enough to make such implementation literally worthless. If destructor is trivial, no code will be generated for it anyway, it won't even result in function call, thanks to templates. If it's non-trivial, it needs to be called.


Oh my goodness...

Switching to malloc and free (AFAIK you can't mix new and free, but I could be wrong on that) allows me to control exactly when I want memory constructed and destructed. While every call to malloc will be followed up by a placement new on the allocated node, when it comes to switching the node into the free-list, I should only destruct the value stored by the node - not the entire node itself (hence, calling the stored value's destructor). This is then constructed with a new value should the node be pulled off the free-list.

Now, when it comes to deleting (from memory) a node on the free-list, calling "delete" on it would result in an error. "delete" will call the node's destructor (which is fine). This destructor will call the stored value's destructor, which isn't fine as it has already been destructed. Hence, errors. So, you use memory allocation routines that allow you total control over which and when the destructors are called.

Quote:
The problem is trivial to solve by not abandoning sanity, and using text-book examples of bad practices, such as malloc/free in combination with class instances.


What a fantastic way of finishing an unhelpful post. If the sight of malloc and free upset you so much, replace them with calls to new and delete with arrays of bytes instead.

Share this post


Link to post
Share on other sites
Quote:
Original post by MENTAL
Quote:
These don't really save anything. With free list, it's customary to use appropriate overloads of new to (de)allocate the objects.

And not calling destructors is just bad mojo, enough to make such implementation literally worthless. If destructor is trivial, no code will be generated for it anyway, it won't even result in function call, thanks to templates. If it's non-trivial, it needs to be called.


Oh my goodness...

Switching to malloc and free (AFAIK you can't mix new and free, but I could be wrong on that) allows me to control exactly when I want memory constructed and destructed. While every call to malloc will be followed up by a placement new on the allocated node, when it comes to switching the node into the free-list, I should only destruct the value stored by the node - not the entire node itself (hence, calling the stored value's destructor). This is then constructed with a new value should the node be pulled off the free-list.

Now, when it comes to deleting (from memory) a node on the free-list, calling "delete" on it would result in an error. "delete" will call the node's destructor (which is fine). This destructor will call the stored value's destructor, which isn't fine as it has already been destructed. Hence, errors. So, you use memory allocation routines that allow you total control over which and when the destructors are called.

Quote:
The problem is trivial to solve by not abandoning sanity, and using text-book examples of bad practices, such as malloc/free in combination with class instances.


What a fantastic way of finishing an unhelpful post. If the sight of malloc and free upset you so much, replace them with calls to new and delete with arrays of bytes instead.

Just wanted to make you aware of, unless you already knew, that you can call operator new and operator delete directly to allocate memory. Allocation (calling operator new for memory) and calling the constructor are two separate steps performed by the new-operator (same for delete and destructors of course), and you can peform them manually also. Since you already use placement new and explicit destructor calls, I suggest you stick with the C++-way all the way.

Examples from your code:

if (!m_free_nodes)
{
created_node = operator new(sizeof (T));
}


operator delete(list_start);

Share this post


Link to post
Share on other sites
Quote:
Original post by MENTAL
Quote:
Option 1:
1. Implement std::allocator, let's say MyAllocator
2. std::list<T, MyAllocator>
3. Profit?


No, as the opening sentence quite clearly states that I'm creating my own containers as a learning experience. And even so, your answer gave no insight into how to create an allocator that handles lots of small objects being created and destroyed frequently, which was the point of this post.


Did you even bother to look at those examples? Such as pool:
Quote:
When should I use Pool?

Pools are generally used when there is a lot of allocation and deallocation of small objects. Another common usage is the situation above, where many objects may be dropped out of memory.
Or perhaps the concepts used?

Quote:
What a fantastic way of finishing an unhelpful post.


So the examples I gave that deal with that very problem, and provide professional implementation wasn't helpful? If learning is involved, doesn't it make sense to look at 3 different approaches to the very problem you mention?

Your post doesn't mention that you've found existing allocators unsuitable, that you've looked at any other problem, the problems you've encountered, or what in particular you want to learn.

Boost in particular always lists design rationale, as well as implementation choices they've made, and is invaluable learning experience, or at least foundation for further questions.

Learning primarily involves "standing on shoulders of giants". Effective one at least. What else than point the examples of how people considerably more experienced than me have solved this problem is there to give?

Share this post


Link to post
Share on other sites
Quote:
Original post by MENTAL
Oh my goodness...

Switching to malloc and free (AFAIK you can't mix new and free, but I could be wrong on that)


You are correct that far.

Quote:
allows me to control exactly when I want memory constructed and destructed.


Except that (a) memory is allocated and deallocated; and (b) you can do the same with the global operator new and operator delete.

Quote:
While every call to malloc will be followed up by a placement new on the allocated node,


and (c) I'm pretty sure this is technically undefined behaviour, since malloc allocates from "the heap" while new allocates from "the freestore", and these aren't guaranteed to be the same memory spaces.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this