4
\$\begingroup\$

While thinking about this question it struck me that one problem of linked data structures always seems to be loss of memory locality and performance could possibly be improved if all allocated nodes are in a contiguous block of memory. So hacked together an object pool implementation in C.

The code compiles with gcc -std=c99 -pedantic -Wall -Werror -O3 without any warnings.

Things I'd like to draw review attention to:

  • Standard conformance
  • Portability
  • Performance improvements
  • C best practices

All other reviews are welcome as well of course.

Header

#ifndef OBJECT_POOL_H
#define OBJECT_POOL_H

#include <stddef.h>

/*
 * This is an implementation of a generic pre-allocated object pool with automatic growth. It pre-allocates
 * storage for a number of objects of a defined size (a single object pool can only hold objects which are
 * all of the same size). If the pool runs out of storage it will double its capacity automatically but adding
 * an additional buffer with double the capacity of the previous buffer. It will try smaller capacity increases
 * if the doubling fails.
 * By default a maximum of OBJECT_POOL_MAX_NUM_BUFFERS will be created yielding at most 31 doubling steps (first
 * buffer will hold initial_capacity items).
 * So the default number of items it can hold at most is initial_capacity * (2^33 - 1)
 * The pre-allocated objects are padded to the next multiple of 4 bytes.
 */

/*
 * Maximum number of buffers. #define yourself if you want something different
 */
#ifndef OBJECT_POOL_MAX_NUM_BUFFERS
#define OBJECT_POOL_MAX_NUM_BUFFERS 32
#endif /* OBJECT_POOL_MAX_NUM_BUFFERS */

/*
 * Default initial capacity. #define yourself if you want something different
 */
#ifndef OBJECT_POOL_DEFAULT_INITIAL_CAPACITY
#define OBJECT_POOL_DEFAULT_INITIAL_CAPACITY 64
#endif /* OBJECT_POOL_DEFAULT_INITIAL_CAPACITY */

/*
 * Type to represent an object_pool object.
 */
typedef struct _object_pool object_pool;

/*
 * Creates an new object_pool object. item_size will be rounded up to the nearest
 * multiple of 4.
 * Returns a pointer to the created object pool object.
 * Returns NULL under when at least one of the following conditions are detected:
 *  - item_size is 0
 *  - initial_capacity is 0
 *  - failure to allocate memory for the pool
 */
object_pool *object_pool_create(size_t item_size, size_t initial_capacity);

/*
 * Initializes an object_pool object with capacity of OBJECT_POOL_DEFAULT_INITIAL_CAPACITY items. Otherwise see above.
 */
object_pool *object_pool_create_default(size_t item_size);

/*
 * Obtains a pointer to an item from the object pool. This may result the object pool in increasing it's capacity.
 * Previously obtained pointers via object_pool_get will remain valid when the pool grows. The initialization state
 * of the object pointed to by the pointer is not defined (e.g. it may contain random data). The caller of this method
 * is required to properly initialize the object before using it.
 *
 * Returns NULL if it failed to obtain an item which can be caused by:
 *  - pool is NULL
 *  - failed to grow the pool due to memory exhaustion
 *  - maximum number of buffers has been allocated and they are all depleted
 */
void *object_pool_get(object_pool *pool);

/*
 * Returns an item back to the object pool so it can be used again.
 * Returns true if the item was put back into the pool and false otherwise.
 *
 * Specifically false will be returned when at least one of the following conditions are detected:
 *  - pool is NULL
 *  - item is NULL
 *  - item does not point to an object held within the internal buffers
 */
bool object_pool_put(object_pool *pool, void *item);

/*
 * Releases all memory associated with the object pool. Accessing objects through pointers obtained via object_pool_get
 * after this method has been called will invoke undefined behaviour (e.g. most likely will crash but that's not guaranteed)!
 * It is safe to call this on a NULL pointer (in which case this is a noop)
 */
void object_pool_free(object_pool *pool);

#endif /* OBJECT_POOL_H */

Implementation

#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include "object_pool.h"

//////////////////////////////////////////////////////////////////////////
/// STACK structure, for internal use - used to manage use and free lists
//////////////////////////////////////////////////////////////////////////

typedef struct _stack
{
    char **items;
    size_t top;
    size_t size;
} stack;

static bool stack_init(stack *s, size_t size)
{
    if (!s)
    {
        return false;
    }

    s->items = malloc(size * sizeof(*s->items));
    if (!s->items)
    {
        return false;
    }

    s->top = 0;
    s->size = size;

    return true;
}

static void stack_destroy(stack *s)
{
    if (s)
    {
        free(s->items);
    }
}

static bool stack_isfull(stack *s)
{
    return s && (s->top == s->size);
}

static bool stack_isempty(stack *s)
{
    return s && (s->top == 0);
}

static bool stack_push(stack *s, char *item)
{
    if (!s || stack_isfull(s))
    {
        return false;
    }
    s->items[s->top] = item;
    s->top += 1;
    return true;
}

static char *stack_pop(stack *s)
{
    if (!s || stack_isempty(s))
    {
        return NULL;
    }
    s->top -= 1;
    return s->items[s->top];
}


///////////////////////////////////////////////////////////////////////////
/// BUFFER structure, for internal use - represents a single object buffer
///////////////////////////////////////////////////////////////////////////

typedef struct _buffer
{
    char *buffer;
    char *virgin_element;
    char * const last_element;
    stack reuse_list;
    stack inuse_list;
    const size_t capacity;
    const size_t item_size;
} buffer;

static bool buffer_init(buffer *buf, size_t item_size, size_t capacity, size_t *actual_capacity)
{
    if (!buf)
    {
        return false;
    }

    char *b = NULL;
    do
    {
        // in case memory allocation fails, we try smaller sizes until minimum size
        b = malloc(item_size * capacity);
    } while (!b && (capacity >>= 2) > OBJECT_POOL_DEFAULT_INITIAL_CAPACITY);

    if (!b)
    {
        return false;
    }

    buffer local_init = 
    { 
        .buffer = b, 
        .virgin_element = b, 
        .last_element = b + (capacity - 1) * item_size,
        .reuse_list = { 0 },
        .inuse_list = { 0 },
        .capacity = capacity,
        .item_size = item_size 
    };
    memcpy(buf, &local_init, sizeof(local_init));

    *actual_capacity = capacity;

    if (!stack_init(&buf->reuse_list, capacity))
    {
        free(buf->buffer);
        return false;
    }

    if (!stack_init(&buf->inuse_list, capacity))
    {
        stack_destroy(&buf->reuse_list);
        free(buf->buffer);
        return false;
    }

    return true;
}

static void buffer_destroy(buffer *buf)
{
    if (buf)
    {
        stack_destroy(&buf->reuse_list);
        stack_destroy(&buf->inuse_list);
        free(buf->buffer);
    }
}

static bool buffer_isempty(buffer *buf)
{
    // if the inuse list is full then all items have been handed out so the buffer is considered empty
    return buf && stack_isfull(&buf->inuse_list);
}

static void *buffer_get_item(buffer *buf)
{
    if (!buf || buffer_isempty(buf))
    {
        return NULL;
    }

    char *item = stack_pop(&buf->reuse_list);
    if (!item)
    {
        // no item for re-use available > get a fresh one
        item = buf->virgin_element;
        buf->virgin_element += buf->item_size;
    }

    return stack_push(&buf->inuse_list, item) ? item : NULL;
}

static bool buffer_put_item(buffer *buf, void *item)
{
    char *ptr = item;
    if (ptr >= buf->buffer && ptr <= buf->last_element)
    {
        return stack_push(&buf->reuse_list, item);
    }
    return false;
}

////////////////////////////
/// The actual object pool
////////////////////////////

struct _object_pool
{
    buffer buffers[OBJECT_POOL_MAX_NUM_BUFFERS];
    size_t num_buffers;
    size_t last_buffer_size;
    size_t item_size;
};

object_pool *object_pool_create(size_t item_size, size_t initial_capacity)
{
    if (!item_size || !initial_capacity)
    {
        return NULL;
    }

    object_pool *pool = calloc(1, sizeof(*pool));
    if (!pool)
    {
        return NULL;
    }

    // round up to next multiple of 4
    item_size = ((item_size + 3) / 4) * 4;

    size_t actual_capacity;
    if (!buffer_init(&pool->buffers[0], item_size, initial_capacity, &actual_capacity))
    {
        free(pool);
        return NULL;
    }

    pool->item_size = item_size;
    pool->num_buffers = 1;
    pool->last_buffer_size = actual_capacity;

    return pool;
}

object_pool *object_pool_create_default(size_t item_size)
{
    return object_pool_create(item_size, OBJECT_POOL_DEFAULT_INITIAL_CAPACITY);
}

void *object_pool_get(object_pool *pool)
{
    if (!pool)
    {
        return NULL;
    }

    // find a buffer which still has some items left to hand out
    buffer *buf = NULL;
    for (int i = 0; i < pool->num_buffers; ++i)
    {
        if (!buffer_isempty(&pool->buffers[i]))
        {
            buf = &pool->buffers[i];
            break;
        }
    }

    // all buffers are depleted -> need to create a new one
    if (!buf)
    {
        if (pool->num_buffers == OBJECT_POOL_MAX_NUM_BUFFERS)
        {
            // too bad, no space left
            return NULL;
        }

        buf = &pool->buffers[pool->num_buffers];
        size_t actual_capacity;
        if (!buffer_init(buf, pool->item_size, pool->last_buffer_size * 2, &actual_capacity))
        {
            return NULL;
        }
        pool->num_buffers += 1;
        pool->last_buffer_size = actual_capacity;
    }

    return buffer_get_item(buf);
}

bool object_pool_put(object_pool *pool, void *item)
{
    if (!pool || !item)
    {
        return false;
    }

    // find the buffer the item belongs to
    for (int i = 0; i < pool->num_buffers; ++i)
    {
        if (buffer_put_item(&pool->buffers[i], item))
        {
            return true;
        }
    }

    return false;
}

void object_pool_free(object_pool *pool)
{
    if (!pool)
    {
        return;
    }

    for (int i = 0; i < pool->num_buffers; ++i)
    {
        buffer_destroy(&pool->buffers[i]);
    }

    free(pool);
}

Test

#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdio.h>
#include <time.h>

#include "object_pool.h"

typedef struct _test_t
{
    int val;
    bool pad1;
    bool pad2;
    bool pad3;
    bool really;
} test_t;

#define ASSERT(x, msg) do { if (!(x)) { printf("%s\n", msg); exit(-1); } } while(0)

static void test_object_pool_returns_null_with_invalid_parameters()
{
    ASSERT(!object_pool_create(0, 1), "unexpected object returned");
    ASSERT(!object_pool_create(1, 0), "unexpected object returned");
    ASSERT(!object_pool_create(0, 0), "unexpected object returned");
    ASSERT(!object_pool_create_default(0), "unexpected object returned");
}

static void test_object_pool_free_null_doesnt_crash()
{
    object_pool_free(NULL);
}

static void test_object_pool_invalid_put_doesnt_crash()
{
    test_t t;
    object_pool *pool = object_pool_create(sizeof(test_t), 1);
    ASSERT(pool, "init failed");
    ASSERT(!object_pool_put(pool, &t), "invalid item put succeeded");
    ASSERT(!object_pool_put(pool, NULL), "invalid NULL put succeeded");
    object_pool_free(pool);
}

static void test_object_pool_get_and_put()
{
    object_pool *pool = object_pool_create(sizeof(test_t), 1);
    ASSERT(pool, "init failed");

    const int num_items = 1000;
    test_t **objects = malloc(sizeof(test_t *) * num_items);

    for (int i = 0; i < num_items; ++i)
    {
        test_t *o = object_pool_get(pool);
        ASSERT(o, "failed to get object");
        o->val = i;
        o->really = true;
        objects[i] = o;
    }
    for (int j = 0; j < num_items; ++j)
    {
        ASSERT(objects[j]->really, "not really?");
        ASSERT(objects[j]->val == j, "value failed");
        ASSERT(object_pool_put(pool, objects[j]), "failed to put");
    }

    free(objects);
    object_pool_free(pool);
}

static void test_object_pool_performance(bool with_free)
{
    int num_iterations = with_free ? 10000 : 1;
    int num_items = with_free ? 10000 : 100000000;
    unsigned long long total = num_iterations * num_items;

    test_t **items = calloc(num_items, sizeof(test_t *));

    object_pool *pool = object_pool_create(sizeof(test_t), num_items);
    ASSERT(pool, "init failed");

    clock_t start, end;
    double elapsed;

    start = clock();
    for (int i = 0; i < num_iterations; ++i)
    {
        for (int j = 0; j < num_items; ++j)
        {
            items[j] = malloc(sizeof(test_t));
            items[j]->really = true;
        }
        if (with_free)
        {
            for (int j = 0; j < num_items; ++j)
            {
                free(items[j]);
            }
        }
    }
    end = clock();
    elapsed = (end - start) / (double)CLOCKS_PER_SEC;
    printf("malloc%s of %llu items took %f sec (%u items/sec)\n", with_free ? " and free" : "", total, elapsed, (unsigned int)(total / elapsed));

    if (!with_free)
    {
        for (int j = 0; j < num_items; ++j)
        {
            free(items[j]);
        }
    }

    start = clock();
    for (int i = 0; i < num_iterations; ++i)
    {
        for (int j = 0; j < num_items; ++j)
        {
            items[j] = object_pool_get(pool);
            items[j]->really = true;
        }
        if (with_free)
        {
            for (int j = 0; j < num_items; ++j)
            {
                object_pool_put(pool, items[j]);
            }
        }
    }
    end = clock();
    elapsed = (end - start) / (double)CLOCKS_PER_SEC;
    printf("get%s of %llu items took %f sec (%u items/sec)\n", with_free ? " and put" : "", total, elapsed, (unsigned int)(total / elapsed));
    free(items);
    object_pool_free(pool);
}


int main(void)
{
    test_object_pool_returns_null_with_invalid_parameters();
    test_object_pool_free_null_doesnt_crash();
    test_object_pool_invalid_put_doesnt_crash();
    test_object_pool_get_and_put();

    test_object_pool_performance(false);
    test_object_pool_performance(true);
}

Test Output

Compiled with gcc -std=c99 -Wall -Werror -pedantic -O3 and gcc 4.9.2 on cygwin 2.5.0

malloc of 100000000 items took 7.875000 sec (12698412 items/sec)
get of 100000000 items took 0.984000 sec (101626016 items/sec)
malloc and free of 100000000 items took 13.938000 sec (7174630 items/sec)
get and put of 100000000 items took 2.750000 sec (36363636 items/sec)

clang 3.5.1 on the same platform and same build options yields almost identical results.


Update: With the inuse_list replaced with an inuse_counter the performance improves somewhat:

malloc of 100000000 items took 7.797000 sec (12825445 items/sec)
get of 100000000 items took 0.547000 sec (182815356 items/sec)
malloc and free of 100000000 items took 13.906000 sec (7191140 items/sec)
get and put of 100000000 items took 0.594000 sec (168350168 items/sec)
\$\endgroup\$
1
\$\begingroup\$

Inuse stack purpose?

I'm not sure what purpose your inuse stack serves. If you create a pool of 100 items, and then call get() followed by put(), you will have put one item on the inuse stack which also appears on the reuse stack. If you do this again, you will put the same item on the inuse stack a second time (a duplicate). Repeat 100 times and the inuse stack will become full and you won't be able to allocate any more items, even though there are actually all 100 items left to allocate.

The inuse stack should be replaced by a simple counter of how many items are in use. You can increment the counter on each get and decrement it on each put.

\$\endgroup\$
  • \$\begingroup\$ Good point, I missed that. I guess I need to add a check to make sure the object pool is a big as I expect it to be (the tests all pass since the object pool will simply expand). Also I agree that an inuse counter would suffice. \$\endgroup\$ – ChrisWue Feb 5 '16 at 5:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.