Help with C++ style



  • Hello there.
    I'm trying to re-learn C++ after not touching it for several years. So I figured I'll post some code here and you could help me with general "style" hints. If you spot any errors I'd apreciate you pointing them out as well, of course!


    It's a memory pool manager.
    It allocates large blocks of memory, say 100 elements at a time (customisible). And then treats the first sizeof(void*) bytes as a pointer to the next free slot. This means that I can just hook up a free'd element to this "free list". I originally had a union of the type and a pointer to the next union, but that didn't work out well since unions can't contain classes with default constructors. So now I do a fair bit of casting magic instead.


    It's a template class so that's why it's all in one header (I couldn't get it to work with the definitions in a .cpp file - if I understand correctly you're supposed to write something like "export template<typename T>" and then it should work, but it didn't. I use VS2003)

    So it's all inline right there in the header (too ugly? how do I solve this?).

    Tell me what you think!

    <FONT color=#0000ff size=1>

    #pragma</FONT><FONT size=1> </FONT><FONT color=#0000ff size=1>once

    #include</FONT><FONT size=1> <cassert>

    </FONT><FONT color=#0000ff size=1>

    namespace</FONT><FONT size=1> MEM

    {

    </FONT><FONT color=#008000 size=1>/**

    An enum describing the two block size behaviours.

    */

    </FONT><FONT size=1>

    </FONT><FONT color=#0000ff size=1>enum</FONT><FONT size=1> BlockSizeBehaviour {    CONSTANT </FONT><FONT color=#008000 size=1>/**< Double the block size after each allocation*/

    </FONT><FONT size=1>

                                           ,  DOUBLE </FONT><FONT color=#008000 size=1>/**< Leave the block size constant */

    </FONT><FONT size=1>

                                        };

    </FONT><FONT color=#008000 size=1>/**

    This class alocates memory more efficiently than the standard 'new' and 'delete'.

    This is done by allocating large "blocks" of data at a time, and then handing out small

    pieces of these blocks as data is requested. When a block runs out of free space, a new

    one is allocated. Free'd space is reused in subsequent allocations.

    It is recommended that classes using a MemoryPool re-implement 'operator new' and

    'operator delete' using a namespace-scoped MemoryPool to handle the allocation and deallocation.

    NOTE:

    This class exploits the allocated space which hasn't been requested by the client yet to hide

    the structure of a linked list of free "slots". In order for this to work each slot needs to

    be at least as large as a pointer. So, the following condition must hold if you want to use

    this class:

    sizeof(T) >= sizeof(void*)

    */

    </FONT><FONT size=1>

    </FONT><FONT color=#0000ff size=1>template</FONT><FONT size=1> <</FONT><FONT color=#0000ff size=1>typename</FONT><FONT size=1> T>

    </FONT><FONT color=#0000ff size=1>class</FONT><FONT size=1> MemoryPool

    {

    </FONT><FONT color=#0000ff size=1>private</FONT><FONT size=1>:

    </FONT><FONT color=#008000 size=1>// Pointer to the next free 'slot'.

    </FONT><FONT size=1>

    </FONT><FONT color=#008000 size=1>// The first sizeof(void*) bytes of this slot represents a pointer to the next slot after that, and so on.

    </FONT><FONT size=1>

    T *nextFree;

    size_t blockSize;

    BlockSizeBehaviour behaviour;

    </FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> updateBlockSize()

    {

    </FONT><FONT color=#0000ff size=1>if</FONT><FONT size=1> (behaviour == DOUBLE)

    {

    blockSize *= 2;

    }

    }

    </FONT><FONT color=#008000 size=1>// Some stats

    </FONT><FONT size=1>

    size_t totalAllocated;

    size_t totalUsed;

    </FONT><FONT color=#008000 size=1>// A simple singly-linked list.

    </FONT><FONT size=1>

    </FONT><FONT color=#0000ff size=1>struct</FONT><FONT size=1> node

    {

    T* block; </FONT><FONT color=#008000 size=1>//pointer to buffer of T's

    </FONT><FONT size=1>

    node * next;

    };

    </FONT><FONT color=#008000 size=1>// Used for storing up blocks. Needed so we can delete them in the destructor.

    </FONT><FONT size=1>

    node * blockList;

    </FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> saveBlock(T *block)</FONT>

    <FONT size=1>{

    node * n = </FONT><FONT color=#0000ff size=1>new</FONT><FONT size=1> node;

    n->block = block;

    n->next = blockList;

    blockList = n;

    }

    </FONT><FONT color=#008000 size=1>// Keep these private to prevent autogenerated versions being exposed

    </FONT><FONT size=1>

    MemoryPool(</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1>);

    MemoryPool(MemoryPool &p);

    MemoryPool & </FONT><FONT color=#0000ff size=1>operator</FONT><FONT size=1>=(</FONT><FONT color=#0000ff size=1>const</FONT><FONT size=1> MemoryPool & bs);

     

    </FONT><FONT color=#0000ff size=1>public</FONT><FONT size=1>:

    </FONT><FONT color=#008000 size=1>/**

    Initialise the memory pool.

    @param initalBlockSize the initial number of "slots" to allocate at a time

    @param b the behaviour of the block size. 'CONSTANT' indicates that the same block size is

    used every time, 'DOUBLE' indicates that the block size will be doubled each time a new block

    is allocated.

    */

    </FONT><FONT size=1>

    MemoryPool(size_t initialBlockSize, BlockSizeBehaviour b = CONSTANT)

    : nextFree(0),

    blockSize(initialBlockSize > 0 ? initialBlockSize : 1),

    behaviour(b),

    totalAllocated(0),

    totalUsed(0),

    blockList(0)

    {};

    ~MemoryPool(</FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1>)

    {

    </FONT><FONT color=#008000 size=1>//Go through all allocated blocks and delete them

    </FONT><FONT size=1>

    node *n = blockList;

    node *tmp;

    </FONT><FONT color=#0000ff size=1>while</FONT><FONT size=1> (n != 0)

    {

    </FONT><FONT color=#0000ff size=1>operator</FONT><FONT size=1> </FONT><FONT color=#0000ff size=1>delete</FONT><FONT size=1>(n->block);

    tmp = n;

    n = n->next;

    </FONT><FONT color=#0000ff size=1>delete</FONT><FONT size=1> tmp;

    }

    };

     

    </FONT><FONT color=#008000 size=1>/**

    Allocates space for a single element of type T.

    @return A pointer to the allocated space, the contents of which should be considered undefined.

    */

    </FONT><FONT size=1>

    T* Allocate()

    {

    </FONT><FONT color=#0000ff size=1>if</FONT><FONT size=1> (nextFree != 0)

    {

    assert(totalAllocated > totalUsed);

    </FONT><FONT color=#008000 size=1>// We have space left in the last block

    </FONT><FONT size=1>

    T *p = nextFree;

    </FONT><FONT color=#008000 size=1>// The value at the location of nextFree is a pointer pointing to the next free slot

    </FONT><FONT size=1>

    nextFree = *(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(nextFree));

    totalUsed ++;

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> p;

    }

    </FONT><FONT color=#0000ff size=1>else

    </FONT><FONT size=1>

    {

    </FONT><FONT color=#008000 size=1>// We need to allocate another block

    </FONT><FONT size=1>

    assert(totalAllocated == totalUsed);

    T * block = </FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T*>(</FONT><FONT color=#0000ff size=1>operator</FONT><FONT size=1> </FONT><FONT color=#0000ff size=1>new</FONT><FONT size=1> (</FONT><FONT color=#0000ff size=1>sizeof</FONT><FONT size=1>(T) * blockSize));

    saveBlock(block);

    totalAllocated += blockSize;

     

    </FONT><FONT color=#008000 size=1>// Make the first sizeof(void*) bytes of each slot

    </FONT><FONT size=1>

    </FONT><FONT color=#008000 size=1>// represent a pointer which points to the next slot

    </FONT><FONT size=1>

    </FONT><FONT color=#0000ff size=1>for</FONT><FONT size=1> (size_t i = 0; i < blockSize -1; ++i)

    {

    *(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(&block[i])) = &block[i+1];

    }

    *(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(&block[blockSize-1])) = 0;

    nextFree = blockSize >= 2 ? &block[1] : 0;

    updateBlockSize();

    totalUsed++;

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> block;

    }

    }

    </FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> Free(T* p)

    {

    </FONT><FONT color=#008000 size=1>// Hook this element on to the front of the "free list"

    </FONT><FONT size=1>

    *(</FONT><FONT color=#0000ff size=1>reinterpret_cast</FONT><FONT size=1><T**>(p)) = nextFree;

    nextFree = p;

    totalUsed--;

    }

    </FONT><FONT color=#008000 size=1>/**

    @return total number of used 'slots'.

    */

    </FONT><FONT size=1>

    size_t GetTotalUsed()

    {

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> totalUsed;

    }

    </FONT><FONT color=#008000 size=1>/**

    @return total number of allocated 'slots'.

    */

    </FONT><FONT size=1>

    size_t GetTotalAllocated()

    {

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> totalAllocated;

    }

    </FONT><FONT color=#008000 size=1>/**

    @return the overhead fraction.

    */

    </FONT><FONT size=1>

    </FONT><FONT color=#0000ff size=1>float</FONT><FONT size=1> GetOverhead()

    {

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> 1.0f - </FONT><FONT color=#0000ff size=1>static_cast</FONT><FONT size=1><</FONT><FONT color=#0000ff size=1>float</FONT><FONT size=1>> (totalUsed) / totalAllocated;

    }

    BlockSizeBehaviour GetBlockSizeBehaviour()

    {

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> behaviour;

    }

    </FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> SetBlockSizeBehaviour(BlockSizeBehaviour b)

    {

    behaviour = b;

    }

    size_t GetBlockSize()

    {

    </FONT><FONT color=#0000ff size=1>return</FONT><FONT size=1> blockSize;

    }

    </FONT><FONT color=#0000ff size=1>void</FONT><FONT size=1> SetBlockSize(size_t sz)

    {

    blockSize = sz;

    }

    };

    };

    </FONT>


  • Damn, that formatting didn't work out.

     

    The header file is here:

     

    http://www.dtek.chalmers.se/~sylvan/MemoryPool.h


  • The code looks pretty clean, and is easy to read. But I do have a few comments/suggestions:



    Careful with your copy constructor. It should be declared Foo( const Foo& ), you have declared it Foo( Foo& ).

    Also, you probably should not be returning T* from Allocate and giving
    T* to free. These methods are dealing with raw memory (not a
    constructed T) and their signatures should reflect that. Use void*
    instead.



    The question you have about cleaning up the code is one of the biggest
    problems in C++ with regard to templates. Any code that wishes to use a
    template class must have access to the method definitions, so as to
    implement the specifics. The only exception to this is if you
    explicitly instantiate a template inside a source file; in your
    example, if you knew that the only template parameters that would be
    used are ints and strings, you could write:



    template class MemoryPool<int>;

    template class MemoryPool<std::string>;



    In this case, you could move the implementation details to the source
    file that contained these explicit instantiations. If a memory pool of
    another type was used, it will generate a link error.



    The only other solution to cleaning up templatized code is to define
    the methods inline outside of the class definition. This is the same as
    defining a method in a source file, except it is required that you use
    the inline function specifier either in the declaration or the
    definition of the method. After that, you can move the implementation
    to a separate file and just #include it after the class definition.



    Be aware that memory pools, while speeding up allocation, can
    potentially cause memory fragmentation. In your implementation, the
    blocks the class allocates will not be free'd until the program ends,
    assuming the pool is defined as a namespace-scoped global variable, as
    you suggest. Because the program could potentially allocate a new block
    at any time, this block could end up almost anywhere in memory.



    A final suggestion: take a look at <a
    href="http://www.boost.org/libs/pool/doc/index.html">boost's
    pool</a>. It doesn't do exactly what yours does, but on the other
    hand, there are many varieties to choose from, and they will all be
    extensively tested.



  • Thank you very much for your help!



  • The only thing I noticed was the inconsistent case for names.

    eg.

    The first 3 declared types:

    enum BlockSizeBehaviour
    class MemoryPool
    struct node

    The code is laid out clearly though and easy enough to read, well
    commented etc.


    The real reason why I'm replying though, is to write an essay about this statement in the comments;

    <font><b>This class alocates memory more efficiently than the standard 'new' and 'delete'.</font></b>


    How do you know this?

    By the looks of things, this class will not be significantly better (faster/efficient)
    than new/delete (which are usually just wrappers around malloc/free). 
    Most systems allocate memory in large chunks to the
    application heap and then the library (malloc/free) divver it up into
    smaller more appropriate bits - just like your code.  Unless you are
    wrting this as an actual implementation of new/delete for a target
    system I'd have to question why? (perhaps you're doing it as a learning
    exercise?).

    The one place where you stand to gain some performance (and slightly
    less wastage) is knowing the type size ahead of time and being able to
    arrange the elements contiguously, but since the whole premise binds to
    a specific type, that class might as well inherit from it instead, and
    thus immediately inherit the required new/delete operators.

    Your class will be faster than a standard implementation but much of that comes from compromises.

    eg.

    Deleting the same object twice would be almost impossible to debug,
    since it might not show up until 2 unrelated "new" objects are
    allocated over the top of each other, something that no commerical
    library would let slip.

    A memory overrun elsewhere that happens to touch the singly linked list
    would be catastrophic yet inexplicably difficult to locate during
    debugging.  malloc/free on the other hand usually allocate their
    own "scratch pad" memory
    in separate pages that are unlikely to be nuked by an application
    overrun and thus can usually detect AND recover  from the situation.



    One big reason why this kind of class/library is seen around the place
    is to provide exactly these kinds of protections a little closer to the
    source instead of the generally "lazy detection" seen in most
    commercial libraries.



    If you do want to prove it's worth, make sure you create test cases
    which might actually occur, like lots of allocations, lots of
    deallocations and lots of interleaving in-between.



    If the existing functionality is exactly what you are after, the
    equivalent can be achieved with a simple "free pool" implementation, of
    which, I believe a template already exists in STL.



    Hmmm, I didn't intend this to be a slag-off, the code itself is good, I just hope you have your reasons well thought out.



  • @Xarium said:


    <font>This class alocates memory more efficiently than the standard 'new' and 'delete'.</font>


    How do you know this?



    Well the usage case I had in mind is allocating tons of small objects where the space overhead of new/malloc would get kind of large percentage-wise (I get around it because I know the size of the objects so I wont' have to store that information like new does). If the objects are short lived (many allocations/deallocations) then I suppose I would get a considerable speed win as well.

    @Xarium said:

    but since the whole premise binds to
    a specific type, that class might as well inherit from it instead, and
    thus immediately inherit the required new/delete operators.


    That is a good point. I didn't really think about this since I'm used to single-inheritance only. What's the best "style" here in your opinion? Having a template for the type, or just using "sizeof(this)" everywhere I need to know the size? Does the latter even work (will sizeof(this) return the size of the allocator part of the class, or indeed the size of the entire class?).
    On the other hand I think that basically every single use case for this class would need custom behaviour in the new/delete operators anyway, so it may be easier to just give an explicit interface to the allocator and let each class use it internally, rather than pretend that just inheriting from it will "do the trick".

    @Xarium said:
    Your class will be faster than a standard implementation but much of that comes from compromises.


    Yes of course, that's the point. I didn't mean to claim it was generally faster. It's faster when you know you're going to need a large amount of objects of the same size be allocated and deallocated often. So you could use it for your "bullet" class in an action game, say.



  • @Xarium said:

    The only thing I noticed was the inconsistent case for names.

    eg.

    The first 3 declared types:

    enum BlockSizeBehaviour
    class MemoryPool
    struct node


    Ah, the idea was that private and local data starts with a lower case letter, while public stuff starts with an upper case letter.


  • Just a few superficial comments...  One thing you might want to consider is look into the allocators that the STL uses (std::alloc) and rewrite your class to fit that interface, then you can use your allocator with any container in the STL.  Also, I wonder what the purpose of your allocator is? Usually when I decide I need to do my own custom memory management it's for a very specific purpose, and so tend to tailor the class to that purpose rather than being so generic.

    (Also, apologies if the forum software ends up mangling this post, there is on preview and no edit, as far as I can tell).

    @sylvan said:

    <font color="#0000ff" size="1">
    </font>

    <font color="#0000ff" size="1">#pragma</font><font size="1"> </font><font color="#0000ff" size="1">once</font>

    <font color="#0000ff" size="1">


    </font>

    <font color="#0000ff" size="1">What does this do?  Whatever it does, it's not portable.</font>

    <font color="#0000ff" size="1">


    </font>

    <font color="#0000ff" size="1">#include</font><font size="1"> <cassert></cassert></font>

    <font color="#0000ff" size="1">
    </font>

    <font color="#0000ff" size="1">namespace</font><font size="1"> MEM</font>


    <font size="1">I name my namespaces in camel case like classes: "Mem".  This is a more personal style choice though, no big deal.
    </font>

    <font size="1">


    </font>

    <font size="1">{</font>

    <font color="#008000" size="1">/**</font>

    <font color="#008000" size="1">An enum describing the two block size behaviours.</font>

    <font color="#008000" size="1">*/</font>



    It looks like you are going to use doxygen or a similar documentation thing.  Don't say "An enum", since that will be obvious in the output. Don't say "two", since you might add something to the enum later. Simply say "Describe a block size behavior).
    <font size="1"> </font>

    <font color="#0000ff" size="1">


    </font>

    <font color="#0000ff" size="1">enum</font><font size="1"> BlockSizeBehaviour {    CONSTANT </font><font color="#008000" size="1">/**< Double the block size after each allocation*/</font>

    <font size="1"> </font>

    <font size="1">                                       ,  DOUBLE </font><font color="#008000" size="1">/**< Leave the block size constant */</font>

    <font size="1"> </font>

    <font size="1">                                    };</font>

    <font color="#008000" size="1">/**</font>

    <font color="#008000" size="1">This class alocates memory more efficiently than the standard 'new' and 'delete'.</font>


    <font color="#008000" size="1">Don't say "This class".  It's obvious that it's a class. 
    </font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">This is done by allocating large "blocks" of data at a time, and then handing out small</font>

    <font color="#008000" size="1">pieces of these blocks as data is requested. When a block runs out of free space, a new</font>

    <font color="#008000" size="1">one is allocated. Free'd space is reused in subsequent allocations.</font>

    <font color="#008000" size="1">It is recommended that classes using a MemoryPool re-implement 'operator new' and </font>

    <font color="#008000" size="1">'operator delete' using a namespace-scoped MemoryPool to handle the allocation and deallocation.</font>

    <font color="#008000" size="1">NOTE: </font>


    <font color="#008000" size="1">In doxygen you can say @note
    </font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">This class exploits the allocated space which hasn't been requested by the client yet to hide</font>

    <font color="#008000" size="1">the structure of a linked list of free "slots". In order for this to work each slot needs to </font>

    <font color="#008000" size="1">be at least as large as a pointer. So, the following condition must hold if you want to use </font>

    <font color="#008000" size="1">this class:</font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">@code</font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">sizeof(T) >= sizeof(void*)</font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">@endcode</font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">*/</font>

    <font size="1"> </font>

    <font color="#0000ff" size="1">template</font><font size="1"> <</font><font color="#0000ff" size="1">typename</font><font size="1"> T></font>

    <font color="#0000ff" size="1">class</font><font size="1"> MemoryPool</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">private</font><font size="1">:</font>

    <font color="#008000" size="1">// Pointer to the next free 'slot'.</font>

    <font size="1"> </font>

    <font color="#008000" size="1">// The first sizeof(void*) bytes of this slot represents a pointer to the next slot after that, and so on.</font>

    <font size="1"> </font>

    <font size="1">T *nextFree;</font>

    <font size="1">

    </font>

    <font size="1">So this is an array of pointers then? If so, just make it an array (T nextFree[]) or a std::vector or something, and then you don't need to explain what an array is in your comment.</font>

    <font size="1">


    </font>

    <font size="1">size_t blockSize;</font>

    <font size="1">BlockSizeBehaviour behaviour;</font>

    <font size="1">

    </font>

    <font size="1">Some people like to distinguish instance member variables from variables that are local to methods, by a prefix like "m", "my" or "_".  Again this is a more personal choice, though.</font>

    <font size="1">


    </font>

    <font color="#0000ff" size="1">void</font><font size="1"> updateBlockSize()</font>

    <font size="1">{ </font>

    <font color="#0000ff" size="1">if</font><font size="1"> (behaviour == DOUBLE)</font>

    <font size="1">{</font>

    <font size="1">blockSize *= 2;</font>

    <font size="1">}</font>

    <font size="1">}</font>

    <font color="#008000" size="1">// Some stats</font>

    <font size="1"> </font>

    <font size="1">size_t totalAllocated;</font>

    <font size="1">size_t totalUsed;</font>

    <font color="#008000" size="1">// A simple singly-linked list.</font>

    <font color="#008000" size="1">

    </font>

    <font color="#008000" size="1">You could also just use std::list<T*>, I think.
    </font>

    <font color="#008000" size="1">


    </font>

    <font size="1"> </font>

    <font color="#0000ff" size="1">struct</font><font size="1"> node</font>

    <font size="1">{</font>

    <font size="1">T* block; </font><font color="#008000" size="1">//pointer to buffer of T's</font>

    <font size="1"> </font>

    <font size="1">node * next;</font>

    <font size="1">};</font>

    <font color="#008000" size="1">// Used for storing up blocks. Needed so we can delete them in the destructor.</font>

    <font size="1"> </font>

    <font size="1">node * blockList;</font>

    <font color="#0000ff" size="1">void</font><font size="1"> saveBlock(T *block)</font>

    <font size="1">{</font>

    <font size="1">node * n = </font><font color="#0000ff" size="1">new</font><font size="1"> node;</font>

    <font size="1">n->block = block;</font>

    <font size="1">n->next = blockList;</font>

    <font size="1">blockList = n;</font>

    <font size="1">}</font>

    <font color="#008000" size="1">// Keep these private to prevent autogenerated versions being exposed</font>

    <font size="1"> </font>

    <font size="1">MemoryPool(</font><font color="#0000ff" size="1">void</font><font size="1">);</font>

    <font size="1">MemoryPool(MemoryPool &p);</font>

    <font size="1">MemoryPool & </font><font color="#0000ff" size="1">operator</font><font size="1">=(</font><font color="#0000ff" size="1">const</font><font size="1"> MemoryPool & bs);</font>

    <font size="1"> </font>

    <font color="#0000ff" size="1">public</font><font size="1">:</font>

    <font color="#008000" size="1">/**</font>

    <font color="#008000" size="1">Initialise the memory pool.</font>

    <font color="#008000" size="1">@param initalBlockSize the initial number of "slots" to allocate at a time</font>

    <font color="#008000" size="1">@param b the behaviour of the block size. 'CONSTANT' indicates that the same block size is</font>

    <font color="#008000" size="1">used every time, 'DOUBLE' indicates that the block size will be doubled each time a new block</font>

    <font color="#008000" size="1">is allocated.</font>

    <font color="#008000" size="1">

    </font>

    <font color="#008000" size="1">In doxygen you can say "@a CONSTANT" and "@a DOUBLE" for pretty formatting.</font>

    <font color="#008000" size="1">


    </font>

    <font color="#008000" size="1">*/</font>

    <font size="1"> </font>

    <font size="1">MemoryPool(size_t initialBlockSize, BlockSizeBehaviour b = CONSTANT)</font>

    <font size="1">: nextFree(0), </font>

    <font size="1">blockSize(initialBlockSize > 0 ? initialBlockSize : 1), </font>

    <font size="1">behaviour(b), </font>

    <font size="1">totalAllocated(0), </font>

    <font size="1">totalUsed(0),</font>

    <font size="1">blockList(0)</font>

    <font size="1">{};</font>

    <font size="1">~MemoryPool(</font><font color="#0000ff" size="1">void</font><font size="1">)</font>

    <font size="1">{</font>

    <font color="#008000" size="1">//Go through all allocated blocks and delete them</font>

    <font size="1"> </font>

    <font size="1">node *n = blockList;</font>

    <font size="1">node *tmp;</font>

    <font color="#0000ff" size="1">while</font><font size="1"> (n != 0)</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">operator</font><font size="1"> </font><font color="#0000ff" size="1">delete</font><font size="1">(n->block);</font>

    <font size="1">tmp = n;</font>

    <font size="1">n = n->next;</font>

    <font color="#0000ff" size="1">delete</font><font size="1"> tmp;</font>

    <font size="1">}</font>

    <font size="1">};</font>

    <font size="1"> </font>

    <font color="#008000" size="1">/** </font>

    <font color="#008000" size="1">Allocates space for a single element of type T.</font>

    <font color="#008000" size="1">@return A pointer to the allocated space, the contents of which should be considered undefined.</font>

    <font color="#008000" size="1">*/</font>

    <font size="1"> </font>

    <font size="1">T* Allocate()</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">if</font><font size="1"> (nextFree != 0) </font>

    <font size="1">{ </font>

    <font size="1">assert(totalAllocated > totalUsed);</font>

    <font size="1">

    </font>

    <font size="1">You didn't #include <assert.h>.  This will be an annoyance when porting to a platform whose standard headers don't coincidentally include it.
    </font>

    <font size="1">


    </font>

    <font color="#008000" size="1">// We have space left in the last block</font>

    <font size="1"> </font>

    <font size="1">T *p = nextFree;</font>

    <font color="#008000" size="1">// The value at the location of nextFree is a pointer pointing to the next free slot</font>

    <font size="1"> </font>

    <font size="1">nextFree = *(</font><font color="#0000ff" size="1">reinterpret_cast</font><font size="1"><t**>(nextFree));</t**></font>

    <font size="1">totalUsed ++;</font>

    <font color="#0000ff" size="1">return</font><font size="1"> p;</font>

    <font size="1">}</font>

    <font color="#0000ff" size="1">else</font>

    <font size="1"> </font>

    <font size="1">{</font>

    <font color="#008000" size="1">// We need to allocate another block</font>

    <font size="1"> </font>

    <font size="1">assert(totalAllocated == totalUsed);</font>

    <font size="1">T * block = </font><font color="#0000ff" size="1">reinterpret_cast</font><font size="1"><t*>(</t*></font><font color="#0000ff" size="1">operator</font><font size="1"> </font><font color="#0000ff" size="1">new</font><font size="1"> (</font><font color="#0000ff" size="1">sizeof</font><font size="1">(T) * blockSize));</font>

    <font size="1">saveBlock(block);</font>

    <font size="1">totalAllocated += blockSize;</font>

    <font size="1"> </font>

    <font color="#008000" size="1">// Make the first sizeof(void*) bytes of each slot </font>

    <font size="1"> </font>

    <font color="#008000" size="1">// represent a pointer which points to the next slot</font>

    <font size="1"> </font>

    <font color="#0000ff" size="1">for</font><font size="1"> (size_t i = 0; i < blockSize -1; ++i)</font>

    <font size="1">{</font>

    <font size="1">*(</font><font color="#0000ff" size="1">reinterpret_cast</font><font size="1"><t**>(&block[i])) = &block[i+1];</t**></font>

    <font size="1">}</font>

    <font size="1">*(</font><font color="#0000ff" size="1">reinterpret_cast</font><font size="1"><t**>(&block[blockSize-1])) = 0;</t**></font>

    <font size="1">nextFree = blockSize >= 2 ? &block[1] : 0; </font>

    <font size="1">updateBlockSize();</font>

    <font size="1">totalUsed++;</font>

    <font color="#0000ff" size="1">return</font><font size="1"> block;</font>

    <font size="1">}</font>

    <font size="1">}</font>

    <font color="#0000ff" size="1">void</font><font size="1"> Free(T* p)</font>

    <font size="1">{</font>

    <font color="#008000" size="1">// Hook this element on to the front of the "free list"</font>

    <font size="1"> </font>

    <font size="1">*(</font><font color="#0000ff" size="1">reinterpret_cast</font><font size="1"><t**>(p)) = nextFree;</t**></font>

    <font size="1">nextFree = p;</font>

    <font size="1">totalUsed--;</font>

    <font size="1">}</font>

    <font color="#008000" size="1">/**</font>

    <font color="#008000" size="1">@return total number of used 'slots'.</font>

    <font color="#008000" size="1">*/</font>

    <font size="1"> </font>

    <font size="1">size_t GetTotalUsed()</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">return</font><font size="1"> totalUsed;</font>

    <font size="1">}</font>

    <font color="#008000" size="1">/**</font>

    <font color="#008000" size="1">@return total number of allocated 'slots'.</font>

    <font color="#008000" size="1">*/</font>

    <font size="1"> </font>

    <font size="1">size_t GetTotalAllocated()</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">return</font><font size="1"> totalAllocated;</font>

    <font size="1">}</font>

    <font color="#008000" size="1">/**</font>

    <font color="#008000" size="1">@return the overhead fraction.</font>

    <font color="#008000" size="1">*/</font>

    <font size="1"> </font>

    <font color="#0000ff" size="1">float</font><font size="1"> GetOverhead()</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">return</font><font size="1"> 1.0f - </font><font color="#0000ff" size="1">static_cast</font><font size="1"><</font><font color="#0000ff" size="1">float</font><font size="1">> (totalUsed) / totalAllocated; </font>

    <font size="1">}</font>

    <font size="1">BlockSizeBehaviour GetBlockSizeBehaviour()</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">return</font><font size="1"> behaviour;</font>

    <font size="1">}</font>

    <font color="#0000ff" size="1">void</font><font size="1"> SetBlockSizeBehaviour(BlockSizeBehaviour b)</font>

    <font size="1">{</font>

    <font size="1">behaviour = b;</font>

    <font size="1">}</font>

    <font size="1">size_t GetBlockSize()</font>

    <font size="1">{</font>

    <font color="#0000ff" size="1">return</font><font size="1"> blockSize;</font>

    <font size="1">}</font>

    <font color="#0000ff" size="1">void</font><font size="1"> SetBlockSize(size_t sz)</font>

    <font size="1">{</font>

    <font size="1">blockSize = sz;</font>

    <font size="1">}</font>

    <font size="1">};</font>

    <font size="1">};</font>



  • Thank you for your comments. Just two quick clarifications:

    @reed said:


    <font size="1">So
    this is an array of pointers then? If so, just make it an array (T
    nextFree[]) or a std::vector or something, and then you don't need to
    explain what an array is in your comment.</font>

    Actually it isn't. It's a pointer to a single T. This memory area also contains a pointer to another T (and so on). I.e. the first 4 bytes of this T is overwritten with a pointer (which is OK since it's a free list - those slots aren't used). The idea is to save memory when you want to allocate tons of small objects by hiding the pointers inside the unused "slots".

    @reed said:

    <font size="1">Some
    people like to distinguish instance member variables from variables
    that are local to methods, by a prefix like "m", "my" or "_".  Again
    this is a more personal choice, though.</font>



    I actually did distinguish between local and non-local members. Public members start in upper case (just a habit from C# I suppose)...



  • the first 4 bytes of this T is overwritten with a pointer


    Oh, so the pointer could *either* be pointing at a T, or, at a T* (another pointer)?

    In this case use a union.  (Or you could define two classes (T and T-holder that contains a T*) with a common base class and use a dynamic_cast).

    Don't assume that a pointer is 4 bytes! 

    It won't be on a 64-bit machine, and it will be pretty mysterious why your pointers go completely wrong and the program crashes (or data starts getting corrupted).



    I actually did distinguish between local and non-local members. Public members start in upper case (just a habit from C# I suppose)...


    Ah, OK. This is not standard C++ style then (where only classes and maybe constants start with upper case letters).




  • Don't assume that a pointer is 4 bytes!


    Nevermind, looking at the code I see you specfiy sizeof(void*).  Still, it's weird, and C provides a tool to do this explicitly (union).




  • enum BlockSizeBehaviour {    CONSTANT /**< Double the block size after each allocation*/

                                           ,  DOUBLE /**< Leave the block size constant */

                                        };


    Comment/Code mismatch.

    --

    This board software is seriously broken.



  • @sylvan said:

    It's a template class so that's why it's all in
    one header (I couldn't get it to work with the definitions in a .cpp
    file - if I understand correctly you're supposed to write something
    like "export template" and then it should work, but it didn't. I use
    VS2003)




    'export' is to date only implemented in a single compiler (Comeau). And
    the actual benefits are not as large as expected. So I don't think we
    will see widespread support for export in several years.



  • A memory allocator of the type you've showed us is more of a C
    construct than a C++ one.  On the whole, C++ developers change
    memory allocation primarily in 2 ways:

    • Writing a custom allocator for STL classes
    • Overloading new.

    An allocator like yours will likely work well for an array of ints or chars, but may work poorly for classes.


    Consider an array of std::strings alloacted using your allocator.


    Firstly, the constructor will not be called, so the objects will be left in an uninitialised state. 

    Secondly, if you modify your allocator to use "placement new" so that the constructor works, you might find that the basic object
    uses relatively little memory, and that the object will, itself,
    allocate a big buffer (without using your allocator).



    Such is life



    Michael J




  • @reed said:

    Don't assume that a pointer is 4 bytes!

     Still, it's weird, and C provides a tool to do this explicitly (union).


    Actually unions won't work here (you'd think they would, but they won't). Members of unions can't have copy constructors. I tried unions first, this is the work-around.



  • Ah, OK. This is not standard C++ style then (where only classes and maybe constants start with upper case letters).

    What, like the standard library, you mean?

    What's that you say?

     

    It doesn't use upper case letters for class names or constants?

    Well, would you look at that.

    Standard C++ style is, if anything, all-lower-case with underscores between words.

     



  • We've all had the template headaches at one time or another, especially when you are dealing with large quantities of templates, and being forced to define them in header files.  There are rumors of C++0x supporting template function- and member-function prototypes to place in headers, and have their definitions defined in source code files, but have them properly associated, however its still just rumors for the moment.

    One thing you do want to avoid whenever possible is the use of reinterpret_cast, as many can tell you it tends to be considered 'dangerous' because of its C'ness in allowing unsafe casts.  If anything use static_cast or dynamic_cast wherever possible.

    Your coding style looks tolerable, though I do agree with others as far as using some more common way of distinguishing members from non members (I personally use mFoo for members, gFoo for globals (Where all globals are put in a Globals struct, and tFoo for anything declared within the scope of a function)).

    The Standard C++ Library uses the naming scheme of 'foo', '_Foo', and '__foo', where anything starting with _ and __ is generally kept within the library, anything such as class names, algorithm names, etc, are lowercase, some with underscores, anything that starts with one underscore is immediately followed by atleast one uppercase character, and anything starting with two underscores is immediately followed by atleast one lowercase letter.

    You may also want to consider using boost::shared_ptr to manage your freestore allocated pointers, its a great and safe way of ensuring your pointers are properly getting deleted at the right time.  Note that shared_ptr is part of C++0x and sill be standardized.

    As kind of a side note seeing as how you are getting back into it just remember, a lot of people and a lot of books and tutorials and so forth have a habit of telling you it is ok to do things like 'using namespace std;' ... Never do this in a header ... You really should never do this at all, no matter what scope.  The whole purpose of the 'std' namespace is to keep everything in the standards in its own namespace, eliminating the potential for naming conflicts, and making them easily distinguished from any proprietary code.  For some reason a lot of people seem to be terrified of writing things such as std::vector, std::string, etc, in their code, they think it makes them less of a person or something, who knows.  If it REALLY bothers you that much, do things like 'using std::string;' or 'using std::vector;' at function scope or if you are really annoyed, at .cpp file scope, but trust me you get used to the std::'s and after awhile your eyes will ignore them to the point of knowing they are there, but not allowing them to be a hinderance at all.



  • @sylvan said:

    @Xarium said:

    <font>This class alocates memory more efficiently than the standard 'new' and 'delete'.</font>

    How do you know this?


    Well the usage case I had in mind is allocating tons of small objects...
    Oops, sorry, my question was ambiguous, I meant; have you explicitly tested that your system is actually more efficient in a real-world setting?
    The standard memory routines might surprise you.

    @sylvan said:
    Having a template for the type, or just using "sizeof(this)" everywhere I need to know the size?

    sizeof(this) will return the size of the system word (say 4 or 8 bytes) because "this" is a pointer.
    sizeof(*this) is legal but is unreliable because it is resolved by the compiler at the point it is seen and will return the size of the local (aka definition scope) class rather than the super-class that you actually want.
    The prototype of the "new" operator is specifically given a size parameter for these reasons.  The value is consistent for the caller not the sub-class, thus you can store this value in the sub-class and always know the size of the super-class that it represents (if you need the size outside the new operator).
    A template does much the same thing, but I don't think it is necessary since the underlying code for your class need not change no matter what derives from it.

    @sylvan said:
    On the other hand I think that basically every single use case for this class would need custom behaviour in the new/delete operators anyway...

    Why custom behaviour?  A new/delete operator should not get involved in how an object is constructed - the constructor has not been called inside "new" (the object does not exist yet) and the destructor has already been called when inside "delete" (the object is now just a lump of unpredictable memory).  Custom behaviour of new/delete should be limited solely to where and how it manipulates memory - it should not use any class level property (other than intrinsics).

    @sylvan said:
    It's faster when you know you're going to need a large amount of objects of the same size be allocated and deallocated often. So you could use it for your "bullet" class in an action game, say.

    Have you considered a simple pool of "free objects" allocated the normal way?  ie. freed objects are recycled into the pool - new objects are taken from the pool (unless the pool is empty in which case they are allocated the normal way).
    Such a system would have all the same virtues as yours and be much simpler to implement and also be much faster at runtime.  The one thing yours might be better at is memory proximity at the start - all objects would be naturally close in proximity getting a small boost through reduction of CPU cache misses (don't read much into this - the difference is likely to be academic).

    Bascially, I guess I'm saying that you have used a generic kind of approach (the new/delete approach) to a problem you were seeking a specialised solution for (to avoid the overheads of a general new/delete).
    It's a good attempt but I think you either need to generalise your problem domain (allow a true random access memory model) or specialise the implementation more (don't re-implement  functionality, like paging, that new/delete already has and is probably better at).



  • @Raider said:

    There are rumors of C++0x supporting template function- and member-function prototypes to place in headers, and have their definitions defined in source code files, but have them properly associated, however its still just rumors for the moment.



    It's already in the Standard. The problem is that separating the template implementation from the definition is apparently a real hassle for the compiler writers. This will likely not change with the introduction of C++0x, which is why I ask you to titlt your head 90 degrees and parse this internet idiom: " :-( "


Log in to reply