stack-based allocation

This is a discussion on stack-based allocation within the C++ Programming forums, part of the General Programming Boards category; Hi, I'm making an allocator with different allocation strategies. One of these strategies is a stack allocation. I want to ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    4

    Question stack-based allocation

    Hi,

    I'm making an allocator with different allocation strategies. One of these strategies is a stack allocation.

    I want to preallocate a large block of memory and pick from this space when allocating memory. The picking would be sequential so it would resemble to a stack.

    In theory it seems fine. But how can I return chunks of such a memory block?

    Suppose a quick draft (see comment in allocate):

    Code:
    init()
    {
        myMemory = ::operator new(LOTS);
    }
    
    void* allocate(int size)
    {
        // what i'm trying is this
        // problem is, compiler doesn't know the size of void*
        // i'm sure there's a way to do this, but i don't know any
        void* result = myMemory + index;
        index += size;
    
        return result;
    }
    
    void* myMemory;
    int index;
    So, any idea how I could return the address in myMemory that happens to be at the given index?

    Any way to do this without templating (allocator relies on an abstract strategy that can be stack, heap, etc)?

    Thanks!
    Last edited by eXodus31337; 01-04-2009 at 10:47 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,962
    Quote Originally Posted by eXodus31337
    Any way to do this without templating (allocator relies on an abstract strategy that can be stack, heap, etc)?
    I am not sure what you mean here: making it into a class template should not pose a problem to your allocation strategy. I have not tried this myself, but you could define a class template with the exact same interface as std::allocator, and even implement the class template by keeping a std::allocator member and forwarding all function calls except allocate, deallocate and max_size to that std::allocator member (since the allocate member function effectively is where you implement your allocation strategy, and this must be matched in deallocation).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jan 2009
    Posts
    4
    Forwarding all calls except allocate/deallocate/max_size could be a great idea, thanks.

    Still, anyone knows how to return the address at the top of the stack? That is, base myMemory pointer plus a given index? Compiler wants to know the size of the data when I would only want to offset it manually.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,962
    Quote Originally Posted by eXodus31337
    Still, anyone knows how to return the address at the top of the stack? That is, base myMemory pointer plus a given index? Compiler wants to know the size of the data when I would only want to offset it manually.
    One way that you could try is to make myMemory a char* instead of a void*.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,607
    Keep in mind that, due to alignment requirements of a particular object, you can only safely use the returned memory for objects of type T where sizeof(T) == sizeof(char).

    gg

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,962
    Quote Originally Posted by Codeplug
    Keep in mind that, due to alignment requirements of a particular object, you can only safely use the returned memory for objects of type T where sizeof(T) == sizeof(char).
    Mind elaborating? I note that the allocate() function in eXodus31337's example differs from the allocate() function in an allocator using the interface of std::allocator since eXodus31337's version presumably allocates size number of bytes, not size * sizeof(T) number of bytes (since there is no template parameter T to begin with).

    EDIT:
    I went back to read an article I bookmarked on allocators, and the relevant portion is:
    The standard does not guarantee that 'mem_' will have a correct alignment for something else than 'char'. And this is deadly. There are rumors that the next revision of the standard will address this problem, but until then...

    To avoid the second issue, we could dynamically allocate 'mem_' (the standard guarantees correct alignment for dynamically allocated memory).
    Consequently, it seems like your concern is misplaced.
    Last edited by laserlight; 01-05-2009 at 08:03 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I think what codeplug is referring to is this:
    Code:
    char *p1 = allocate(sizeof(char)*3);
    double *p2 =allocate(sizeof(double));
    If we assume that myMemory is aligned to a nice 8-byte boundary when init() is finished, what is the address given to p2? It will not be aligned to a nice 8-byte boundary, I can promise. Since some processors do not "agree with" reading data at unaligned addresses, this would cause an "unaligned access" error. Sure, x86 would gladly accept this sort of thing (with a 1 clock penalty if read from L1 cache, potentially more if reading from L2 cache or external memory).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,962
    Quote Originally Posted by matsp
    If we assume that myMemory is aligned to a nice 8-byte boundary when init() is finished, what is the address given to p2? It will not be aligned to a nice 8-byte boundary, I can promise. Since some processors do not "agree with" reading data at unaligned addresses, this would cause an "unaligned access" error.
    That makes sense, assuming that the memory pool was supposed to be used by objects of different types. Unfortunately eXodus31337 is rather vague about that, and in fact I am a little confused as to whether eXodus31337 intends to follow my suggestion of copying the default allocator's interface.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Jan 2009
    Posts
    4

    Thumbs up

    I guess at this point, copying -or not- the standard allocator wouldn't solve the alignment problem since it would redefine de/allocate to pick from a given block anyway.

    The target is x86, but then again I'd prefer doing something portable rather than a frail implementation.

    Can I assume that solving this problem would be allocating a large linear block of memory to pick from. Then picking from the top of it. Finally placing the current index at the nearest 8byte multiple?

    Thanks again for the help, nice arguing there people

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yes, rounding the size up to the next 8- or 16-byte boundary will do the trick - and you can do that with a couple of simple math/logic operations.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Jan 2009
    Posts
    4
    it works like a charm now
    even runs on my psp without alignment problems. thanks all of you.
    Last edited by eXodus31337; 01-06-2009 at 06:12 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack Based Array?
    By suckerpunch678 in forum C++ Programming
    Replies: 11
    Last Post: 04-01-2005, 01:23 AM
  2. Rough cut stack manipulation
    By Thantos in forum C Programming
    Replies: 7
    Last Post: 04-02-2004, 11:49 AM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 09:12 PM
  4. Stack problem
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 11-11-2003, 03:30 PM
  5. HEap and stack, I'm confused
    By indigo0086 in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 10-31-2002, 09:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21