Custom Allocation

This is a discussion on Custom Allocation within the C Programming forums, part of the General Programming Boards category; Originally Posted by iMalc You'd probably be interested in this memory pool allocator I wrote a while ago: http://www.flipcode.com/cgi-bin/fcar...cgi?show=64152 Thanks, ...

  1. #16
    Registered User
    Join Date
    Apr 2007
    Posts
    129
    Quote Originally Posted by iMalc View Post
    You'd probably be interested in this memory pool allocator I wrote a while ago:
    http://www.flipcode.com/cgi-bin/fcar...cgi?show=64152
    Thanks, that's pretty darn clever. I like how you reuse the fixed object space (which has been padded a bit) to provide the infrastructure for your free pointer linked list. Thats pretty nifty. I think the C++ code actually hides the elegance of what you're doing however.

    I guess also there is no mechanism right now to grow your initial block of memory if it proves inadequate, though this can be easily fixed. Also there is one potential gotcha the way this is written. An important, though not often used compiler optimization is to rip apart structures and classes and treat their individual elements as atomic variables for register allocation and other standard optimizations. It has a name but it escapes me right now.


    Such an optimization could potentially nerf your initial allocation of the free list, since you may not be guaranteed that there is head room after the end of your class/structure. I am not sure, but ANSI C, for example, may not necessarily require structs to be held in contiguous memory. Though in this case you are probably safe since it seems to essentially be a recast of a pointer to the larger size pool. C++ is kind of weird though. I'm always surprised at what is really going on under the hood.

    For the technique I use, I basically want an allocation to pop the address off of a stack (an array) and return, whilst free pushes the address on to a stack. So which is faster, reading an entry from the top of an array and increment the array pointer, or simply returning the next entry in the linked list. The linked list approach has a slightly smaller instruction count I suppose. However if the stacked is used often it should be in cache memory, possibly reducing memory look up time, although perhaps that's true in your case as well since the data item itself should be contiguous to the next pointer.

    Freeing however requires looking up the data structure in the next pointer which may not be in the cache. One can never tell these things until one tries it however. It would be interesting to benchmark it.

  2. #17
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,852
    So you could have

    Create a pool of small objects
    smallObj *small = malloc( max * sizeof *small );

    Then to allocate
    return &small[count++];

    To free a block, one could simply abandon it, and carry on allocating quickly from the end of the array. But that would depend on whether the speed improvement was worth the acceptable losses.
    Or if you have a few more 'free', then perhaps create a free list which you allocate from when you get to count == max.

    When everything is done, just
    free( small );

    > I am not sure, but ANSI C, for example, may not necessarily require structs to be held in contiguous memory.
    Yes it does.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #18
    Registered User
    Join Date
    Apr 2007
    Posts
    129
    Quote Originally Posted by Salem View Post
    So you could have

    Create a pool of small objects
    smallObj *small = malloc( max * sizeof *small );

    Then to allocate
    return &small[count++];

    To free a block, one could simply abandon it, and carry on allocating quickly from the end of the array. But that would depend on whether the speed improvement was worth the acceptable losses.
    Or if you have a few more 'free', then perhaps create a free list which you allocate from when you get to count == max.

    When everything is done, just
    free( small );
    Yup simple and sweet for a lot of problems and I always prefers simplicity. This one however requires just a touch more flexibility. My ternary tree could hold anything from a few strings to run test cases or an enormous tree that fills up available memory. So in my code, when I exhaust the free list I load up another block of memory. When my free list gets too big, I grow the list using realloc, using the 50% growth trick, which grows the array in order n (n is the number of bytes needed.)

    However malloc on my linux distro is competitive with a simple decrement stack pointer and read off the free pointer trick. I'll venture a guess and suggests that MS's malloc is not this efficient.

    > I am not sure, but ANSI C, for example, may not necessarily require structs to be held in contiguous memory.
    Yes it does.
    I'm glad to hear it. My compiler optimization book was not so certain about this.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dynamic allocation from 1 instead of zero
    By cfdprogrammer in forum C Programming
    Replies: 27
    Last Post: 04-28-2009, 09:21 AM
  2. pointer to array with dynamic allocation
    By cfdprogrammer in forum C Programming
    Replies: 22
    Last Post: 04-07-2009, 10:56 AM
  3. redundant allocation
    By George2 in forum C++ Programming
    Replies: 22
    Last Post: 03-06-2008, 06:43 PM
  4. Stl sets and custom classes.
    By cunnus88 in forum C++ Programming
    Replies: 3
    Last Post: 05-13-2006, 12:58 AM
  5. Dynamic allocation (I thought it would crash)
    By Baaaah! in forum C Programming
    Replies: 16
    Last Post: 11-30-2005, 05:10 PM

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