Thread: portable alloca

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    7

    portable alloca

    alloca allocates memory on the stack frame. On my system I measure it to be about five times faster than malloc if allocation comes from the pool of available memory and several orders of magnitude faster if a system call is required. The disadvantage is that alloca is not portable and large allocations can overflow the stack. But the speed is desirable to me, so I have written the code below to use alloca if available and if making small allocations and use malloc otherwise. It still has the same restrictions on use as alloca. The advantage over C99 variable length arrays are that large allocations are still done on the heap to avoid overflowing the stack. In the code, xrealloc is an error wrapper for realloc and the other undefined macros can be found by google. I use GCC, so have included an extension that helps with type safety if GCC is included.

    I would appreciate any comments to improve this code for portability, safety, etc. while maintaining it's speed.

    Code:
    /* Find a good version of alloca. */
    #ifndef alloca
    # ifdef __GNUC__
    #  define alloca __builtin_alloca
    # else
    #  ifdef __DECC
    #   define alloca(x) __ALLOCA(x)
    #  else
    #   ifdef _MSC_VER
    #    include <malloc.h>
    #    define alloca _alloca
    #   endif
    #  endif
    # endif
    #endif
    
    /* Memory allocation below this threshold size is alloca'ed and above it is malloc'ed. */
    #define QALLOC_THRESHOLD ((size_t) 1000)
    
    #if defined (alloca)
    /* if GCC is used, then provide safer macros */
    # if __GNUC_PREREQ (2, 0)
    #  define qalloc(size)                                                        \
      __extension__ ({                                                            \
        size_t __qalloc_size = (size);                                            \
        void  *__qalloc_ret;                                                      \
                                                                                  \
        if (LIKELY ((__qalloc_size) < QALLOC_THRESHOLD)) {                        \
            __qalloc_ret = alloca (__qalloc_size);                                \
        } else {                                                                  \
            __qalloc_ret = xrealloc (NULL, __qalloc_size);                        \
        }                                                                         \
        __qalloc_ret;                                                             \
      })
    # else
    #  define qalloc(size) (((size) < QALLOC_THRESHOLD) ? (alloca (size)) : (xrealloc (NULL, size)))
    # endif
    # define qfree(ptr, size)                                                     \
      do {                                                                        \
        size_t __qfree_size = (size);                                             \
                                                                                  \
        if (UNLIKELY ((__qfree_size) >= QALLOC_THRESHOLD)) {                      \
            void  *__qfree_ptr  = (ptr);                                          \
            free (__qfree_ptr);                                                   \
        }                                                                         \
      } while (0)
    #else
    # define qalloc(size) xrealloc (NULL, size)
    # define qfree(ptr, size) free (ptr)
    #endif

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    You may want to take a peek at how PellesC does memory management... It's detailed in the help file, but in broad strokes he pre-allocates a block of heap memory on startup and then runs his own memory management in that block, up to a threshold size when it will switch to standard heap allocation... It's about 3x faster than standard malloc but isn't likely to crash the stack anytime soon.

    smorgasbordet - Pelles C
    Pelles C forum - Index

  3. #3
    Registered User
    Join Date
    Dec 2008
    Location
    Black River
    Posts
    128
    You should check for the alloca.h header (Maybe use a config script) since it usually provides a native implementation of alloca. From what I remember, glibc provides the header for many platforms.

    Also, you may want to increase the `QALLOC_THRESHOLD' a bit. Most OS usually guarantee a single guard page at the bottom of the stack, which can be as small as 4K. So at best you can allocate 4096 bytes (Probably a bit less since you have to account for possible compiler-allocated stack slots).
    Stick close to your desks and never program a thing,
    And you all may sit in the standards commitee!

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Yeah I was going to say that C99 variable length arrays are not specified as or requiring the use of alloca internally. They are fully allowed to use heap memory, so long as they ensure that no memory is leaked I imagine.
    Last edited by iMalc; 02-17-2011 at 12:30 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,398
    If the reason you like alloca() is because it's fast, you can be just as fast without putting things on the stack.

    If the reason you like alloca() is because you don't have to free the memory explicitly, then why not take that idea (not having to explicitly clean up things all over the place) to its logical conclusion, and switch to C++?

    Whether you like it because of speed or usability, there are better solutions.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. making it portable.....?
    By ShadeS_07 in forum C Programming
    Replies: 11
    Last Post: 12-24-2008, 09:38 AM
  2. C - Portable?
    By vb.bajpai in forum C Programming
    Replies: 2
    Last Post: 07-15-2007, 09:09 AM
  3. Replies: 3
    Last Post: 09-01-2005, 11:47 AM
  4. Portable Audio Library
    By CornedBee in forum C++ Programming
    Replies: 2
    Last Post: 05-19-2005, 02:09 AM
  5. which Portable mp3 player?
    By Raihana in forum A Brief History of Cprogramming.com
    Replies: 27
    Last Post: 01-09-2004, 07:58 AM