Jump to content

  • Log In with Google      Sign In   
  • Create Account

Attempting to create a pool allocator


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
16 replies to this topic

#1 Jeffreyp   Members   -  Reputation: 178

Like
0Likes
Like

Posted 07 March 2013 - 06:53 AM

Hello,

 

Today I decided that I want to gain some knowledge about memory management.

I don't know much about memory management so i thought it would be a nice "exercise" to try to create a pool allocator.

Actually everything is working as expected but I think I did something wrong.

 

Here's the code :

 

PoolAllocator.h

#pragma once



class PoolAllocator

{

public:

    PoolAllocator(void);

    ~PoolAllocator(void);


    void allocate(const size_t amount);

    char *obtain(const size_t amount);

    void free(void *mem);


private:


    char *memory;

    char *at;

    int atAmount;

    int size;


};

 

 

PoolAllocator.cpp

#include "PoolAllocator.h"



PoolAllocator::PoolAllocator(void)

{

}



PoolAllocator::~PoolAllocator(void)

{

    delete[] memory;
    delete[] at;

}



void PoolAllocator::allocate(const size_t maxSize)

{

    memory = new char[maxSize];

    at = &memory[0];

    atAmount = 0;

    size = maxSize;

}


char *PoolAllocator::obtain(const size_t amount)

{

    if(atAmount + amount     > size - 1)

        return nullptr;


    at += amount;


    return at;

}


void PoolAllocator::free(void *mem)

{


}

 

main.cpp

#include <Windows.h>

#include <iostream>


#include "PoolAllocator.h"


class A

{

public:

    int val;


};


class B

{

public:

    int val;


};


int main()

{

    PoolAllocator allocator;

    allocator.allocate(1000);


    A *a = (A*)allocator.obtain(sizeof(A));


    a->val = 10;


    std::cout << "A : " << a->val << std::endl;


    B *b = (B*)allocator.obtain(sizeof(B));


    b->val = 20;


    std::cout << "A : " << a->val << std::endl << "B : " << b->val << std::endl;

    

    system("pause");

    return 0;

}

 

My knowledge in memory management is really limited, so it could be that I made some 'horrible' mistake or something.

Basically I just want someone to check this code.

 

Thanks in advance !



Sponsor:

#2 Hodgman   Moderators   -  Reputation: 31800

Like
6Likes
Like

Posted 07 March 2013 - 07:02 AM

That's not a pool allocator, it's a stack allocator.

 

In the destructor you shouldn't be deleting both memory and at. at is inside memory (and at wasn't created with new), it's already deleted when you delete memory.

The atAmount variable is always zero. What's it for?
Instead of "atAmount + amount > size - 1", you should be using "at + amount > memory + size".
 
You should merge the allocate method into the constructor, so it's created like:
PoolAllocator allocator(1000);
At the moment, someone could call allocate twice, and your class would cause a memory leak. 


The allocator should probably be non-copyable, because at the moment if I write PoolAllocator other = allocator; your code will crash.
e.g.

class PoolAllocator
{
public:
...
private:
    PoolAllocator(const PoolAllocator&);//not implemented
    PoolAllocator& operator=(const PoolAllocator&);//prevents accidentally copying
...
};

 

If the free method does nothing, it shouldn't exist. At the moment, it will only fool your users into thinking that it's necessary, or that they are actually freeing memory.

 

The obtain function does not take alignment into account. If someone obtains a char and then an int, the int will be misaligned.


Edited by Hodgman, 07 March 2013 - 07:06 AM.


#3 tivolo   Members   -  Reputation: 989

Like
3Likes
Like

Posted 07 March 2013 - 07:21 AM

If you're interested in creating a pool allocator (not a stack allocator, like Hodgman noted), I've written about that on my blog



#4 Jeffreyp   Members   -  Reputation: 178

Like
0Likes
Like

Posted 07 March 2013 - 07:25 AM

That's not a pool allocator, it's a stack allocator.

 

In the destructor you shouldn't be deleting both memory and at. at is inside memory (and at wasn't created with new), it's already deleted when you delete memory.

The atAmount variable is always zero. What's it for?
Instead of "atAmount + amount > size - 1", you should be using "at + amount > memory + size".
 
You should merge the allocate method into the constructor, so it's created like:
PoolAllocator allocator(1000);
At the moment, someone could call allocate twice, and your class would cause a memory leak. 


The allocator should probably be non-copyable, because at the moment if I write PoolAllocator other = allocator; your code will crash.
e.g.

class PoolAllocator
{
public:
...
private:
    PoolAllocator(const PoolAllocator&);//not implemented
    PoolAllocator& operator=(const PoolAllocator&);//prevents accidentally copying
...
};

 

If the free method does nothing, it shouldn't exist. At the moment, it will only fool your users into thinking that it's necessary, or that they are actually freeing memory.

 

The obtain function does not take alignment into account. If someone obtains a char and then an int, the int will be misaligned.

 

Thanks for the response!

Some really informative things in there.

 

 

That's not a pool allocator, it's a stack allocator.

 

Yes you're right. I read it up on wikipedia and understand it now.

 

 

The atAmount variable is always zero. What's it for?
Instead of "atAmount + amount > size - 1", you should be using "at + amount > memory + size".

 

atAmount actually does the same as

at + amount > memory + size

 

But shouldn't be

at + amount > memory + size - 1

 

Because if

at + amount == memory + size

it would crash at

at+= amount
right?

 

 

If the free method does nothing, it shouldn't exist. At the moment, it will only fool your users into thinking that it's necessary, or that they are actually freeing memory.

 

Actually I don't know how I should implement this method. Can you give me some tips?

 

Thanks.


Edited by Jeffreyp, 07 March 2013 - 07:28 AM.


#5 Jeffreyp   Members   -  Reputation: 178

Like
0Likes
Like

Posted 07 March 2013 - 07:26 AM

If you're interested in creating a pool allocator (not a stack allocator, like Hodgman noted), I've written about that on my blog

 

Thanks I will check it out!



#6 EWClay   Members   -  Reputation: 659

Like
1Likes
Like

Posted 07 March 2013 - 09:13 AM

You should not have the -1 in the comparison. For example, if you allocate 1000 bytes and then attempt to obtain 1000 bytes, it should succeed. But as it is you can only obtain 999 bytes.

More importantly, you should be returning the value of 'at' before adding 'amount' to it, or you will overrun the end of the buffer.

#7 Jeffreyp   Members   -  Reputation: 178

Like
0Likes
Like

Posted 07 March 2013 - 09:28 AM

You should not have the -1 in the comparison. For example, if you allocate 1000 bytes and then attempt to obtain 1000 bytes, it should succeed. But as it is you can only obtain 999 bytes.

More importantly, you should be returning the value of 'at' before adding 'amount' to it, or you will overrun the end of the buffer.

 

Oké, thanks for the explanation


Edited by Jeffreyp, 07 March 2013 - 09:34 AM.


#8 dpadam450   Members   -  Reputation: 946

Like
1Likes
Like

Posted 07 March 2013 - 10:58 AM

Your use of class member variables should take note of being a member variable by either:

 

this->at
or naming it

m_at; (m_ noting it is a 'member' variable)



You may also want to return a void* instead of char* since you are technically return a pointer to not a char but a random object (could be a GameObject*, int*, Texture*)


Edited by dpadam450, 07 March 2013 - 11:01 AM.


#9 Jeffreyp   Members   -  Reputation: 178

Like
0Likes
Like

Posted 07 March 2013 - 02:42 PM

Your use of class member variables should take note of being a member variable by either:

 

this->at
or naming it

m_at; (m_ noting it is a 'member' variable)



You may also want to return a void* instead of char* since you are technically return a pointer to not a char but a random object (could be a GameObject*, int*, Texture*)

 

Thanks for your response.

 

Your use of class member variables should take note of being a member variable by either:
 
this->at
or naming it
m_at; (m_ noting it is a 'member' variable)

 

Isn't naming class members with m_ a bad habit? The reason I'm saying this is because a few months ago I had an internship and

I showed some c++ source code and they said that naming c++ class members with m_ is a bad habit from the C language. Just curious : )

 

You may also want to return a void* instead of char* since you are technically return a pointer to not a char but a random object (could be a GameObject*, int*, Texture*)

 

Oké, any other reasons I should use void* instead of char *? I saw both when I was googling around so I'm not really sure.

 

Thanks !



#10 Tasche   Members   -  Reputation: 222

Like
1Likes
Like

Posted 07 March 2013 - 04:13 PM

I showed some c++ source code and they said that naming c++ class members with m_ is a bad habit from the C language. Just curious : )

read the posts on this stackoverflow page for a discussion:

http://stackoverflow.com/questions/1228161/why-use-prefixes-on-member-variables-in-c-classes

i personally go for Jason Williams approach, have yet to see the bad side of prefixing.



#11 wintertime   Members   -  Reputation: 1876

Like
1Likes
Like

Posted 07 March 2013 - 05:16 PM

The bad side is its just useless clutter.

Everyone knows globals are "bad" right, so there are nearly none? Function arguments and local variables you instantly see right? Functions should also be kept short and often dont even have local variables? So the only kind of variable left are member variables, that means you can just assume if its not local its a member variable, even if you avoid all distracting hungarian namemangling.



#12 EWClay   Members   -  Reputation: 659

Like
1Likes
Like

Posted 07 March 2013 - 08:01 PM

Using m_ is not a bad habit. Some people don't like it, but it's certainly useful.

Parameter names should be uncluttered and free to be called wherever they need to be because readability of the interface is the most important. Member names should not be allowed to clash with parameter names and the easiest way to ensure that is to use a naming convention.

I see you have mem and memory above. That's not really better.

#13 tivolo   Members   -  Reputation: 989

Like
2Likes
Like

Posted 08 March 2013 - 06:58 AM

Using prefixed member variables (e.g. m_) is useful for writing optimized code.

 

You may or may not know it, but all member variables alias other pointer variables (e.g. function arguments and other members) because of the implicit this-pointer. This affects code optimization and often leads to less optimal code because of redundant loads. Therefore I like all member variables to clearly stand out by using a prefix, so they aren't used in e.g. tight inner loops, but moved to a local variable first. Aliasing basically happens all over the place.

 

Google for "pointer aliasing", "strict aliasing rule", "type punning" and "restricted pointers" if you're interested.



#14 King Mir   Members   -  Reputation: 2050

Like
0Likes
Like

Posted 08 March 2013 - 08:31 AM

T

Using prefixed member variables (e.g. m_) is useful for writing optimized code.
 
You may or may not know it, but all member variables alias other pointer variables (e.g. function arguments and other members) because of the implicit this-pointer. This affects code optimization and often leads to less optimal code because of redundant loads. Therefore I like all member variables to clearly stand out by using a prefix, so they aren't used in e.g. tight inner loops, but moved to a local variable first. Aliasing basically happens all over the place.
 
Google for "pointer aliasing", "strict aliasing rule", "type punning" and "restricted pointers" if you're interested.

That's something that the compiler should be able to optimize on its own. Accessing a member of a struct can trivially be proven not to alias with another member of the struct. Also, member variables will be moved to registers if they are used in tight inner loops, so there wouldn't be redundant loads.

#15 Jeffreyp   Members   -  Reputation: 178

Like
0Likes
Like

Posted 08 March 2013 - 09:00 AM

Thanks for all the responses !

A lot of useful information : )



#16 tivolo   Members   -  Reputation: 989

Like
0Likes
Like

Posted 08 March 2013 - 04:00 PM

T

Using prefixed member variables (e.g. m_) is useful for writing optimized code.
 
You may or may not know it, but all member variables alias other pointer variables (e.g. function arguments and other members) because of the implicit this-pointer. This affects code optimization and often leads to less optimal code because of redundant loads. Therefore I like all member variables to clearly stand out by using a prefix, so they aren't used in e.g. tight inner loops, but moved to a local variable first. Aliasing basically happens all over the place.
 
Google for "pointer aliasing", "strict aliasing rule", "type punning" and "restricted pointers" if you're interested.

That's something that the compiler should be able to optimize on its own. Accessing a member of a struct can trivially be proven not to alias with another member of the struct. Also, member variables will be moved to registers if they are used in tight inner loops, so there wouldn't be redundant loads.

 

In the case of aliasing, you couldn't be more wrong.

You should not assume what the compiler can and should do, but rather check the facts about what it is allowed to do.

 

First and foremost, the compiler needs to generate correct code. Only then can it create optimized code.

In the case of aliasing, the compiler must be very conservative in order to generate code that behaves correctly in all situations.

 

It cannot be trivially proven that two members don't alias each other. Consider a class with two int* members - if they both point to the same address, they alias each other. And because they are both of type "pointer to int", they are allowed to do so, per the standard. So-called compatible types are allowed to alias, and that also includes signed/unsigned, and cv-qualified types, e.g. a int* is allowed to alias an unsigned int*. In addition, there is a special case for char*, which is allowed to alias everything. You need that to correctly implement certain functionality in case your compiler adheres to the strict aliasing rule (the PS3 compiler does, trust me).

 

You also stated that "member variables will be moved to registers if they are used in tight inner loops, so there wouldn't be redundant loads", and again, this is wrong in case of aliasing.

 

Consider the following simple example:

 

void XorCypher::Encrypt(char* buffer, size_t size)
{
  for (size_t i=0; i<size; ++i)
  {
    buffer[i] ^= m_key;
  }
}

Assume this is a member function of a class XorCypher that has a member named char m_key. In this case, char* buffer aliases char XorCypher::m_key because of the implicit this-pointer (m_key actually becomes a pointer to char). Therefore, the compiler has to generate code that reloads m_key on each and every loop iteration because it might have changed in a store-operation to buffer[i]!

 

Aliasing happens for member variables, function arguments, pointer types, and also reference types. That's why I said "aliasing basically happens all over the place", and you have to be aware of that.

 

What can you do against it? Use local variables, or restricted pointers (using the C99 restrict keyword, supported by all major C++ compilers).

After all, there is a reason why free functions can be faster than member functions, and why the above can be a performance penalty on Xbox360/PS3 platforms.

 

Recommended reading material if you want to know more details:


http://cellperformance.beyond3d.com/articles/2006/06/understanding-strict-aliasing.html

http://cellperformance.beyond3d.com/articles/2006/05/demystifying-the-restrict-keyword.html

http://assemblyrequired.crashworks.org/2008/07/08/load-hit-stores-and-the-__restrict-keyword/


Edited by tivolo, 08 March 2013 - 04:05 PM.


#17 dpadam450   Members   -  Reputation: 946

Like
0Likes
Like

Posted 08 March 2013 - 04:15 PM

The bad side is its just useless clutter.

Everyone knows globals are "bad" right, so there are nearly none? Function arguments and local variables you instantly see right? Functions should also be kept short and often dont even have local variables? So the only kind of variable left are member variables, that means you can just assume if its not local its a member variable, even if you avoid all distracting hungarian namemangling.



Not useless clutter, the reason I posted this in the first place is I was like "where is 'at' coming from" and for each variable I have to go find it. Remember in the real world files can get 1-2K lines long, so the idea you want to go back to a header to see if the variable is local or not is horrible. You could have 5 func parameters + 10 local variables in a given function that you didn't write.

The two companies (game) I have worked at use mVariableName. At home I use this-> because I like reading code and saying "this objects speed is 20" instead of "mSpeed is 20".

Oké, any other reasons I should use void* instead of char *? I saw both when I was googling around so I'm not really sure.


Convention. You took a piece of raw memory and casted it to a char and then to a GameObject (example below). So you are denoting the memory you are returning is going to be a char, but really it's not really going to be a char, just a pointer to raw memory that the user of the class will cast to something they want. I just searched the EA base, and they are all void* as well.
GameObject* gameObject = allocate();




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS