malloc alternative for memory allocation as a stack

Question

I am looking for a malloc alternative for c that will only ever be used as a stack. Something more like alloca but not limited in space by the stack size. It is for coding a math algorithm.

• I will work with large amounts of memory (possibly hundreds of megabytes in use in the middle of the algorithm)
• memory is accessed in a stack-like order. What I mean is that the next memory to be freed is always the memory that was most recently allocated.
• would like to be able to run an a variety of systems (Windows and Unix-like)
• as an extra, something that can be used with threading, where the stack-like allocate and free order applies just to individual threads. (ie ideally each thread has its own "pool" for memory allocation)

My question is, is there anything like this, or is this something that would be easy to implement?

Answer 1

As you already found out, as long as it works with malloc you should use it and only come back when you need to squeeze out the last bit of performance.

An idea fit that case: You could use a list of blocks, that you allocate when needed. Using a list makes it possible to eventually swap out data in case you hit the virtual memory limit.

struct block {
  size_t size;
  void * memory;
  struct block * next;
};
struct stacklike {
  struct block * top;
  void * last_alloc;
};
void * allocate (struct stacklike * a, size_t s) {
  // add null check for top
  if (a->top->size - (a->next_alloc - a->top->memory) < s + sizeof(size_t)) {
    // not enough memory left in top block, allocate new one
    struct block * nb = malloc(sizeof(*nb));
    nb->next = a->top;
    a->top = nb;
    nb->memory = malloc(/* some size large enough to hold multiple data entities */);
    // also set nb size to that size
    a->next_alloc = nb->memory;
  }
  void * place = a->next_alloc;
  a->next_alloc += s;
  *((size_t *) a->next_alloc) = s; // store size to be able to free
  a->next_alloc += sizeof (size_t);
  return place;
}

I hope this shows the general idea, for an actual implementation there's much more to consider.

To swap out stuff you change that to a doubly linked list an keep track of the total allocated bytes. If you hit a limit, write the end to some file.