C memory management

Hey /prog, I'm teaching myself C by writing a roguelike and I noticed that C uses manual memory management for creating objects in the heap. I was wondering if the C-gods could lend me some advice on how to proceed with this:

I want to write a roguelike with thousands of NPCs, every NPC is a really small piece of data which does not contain any pointers (position, stats, behavior... probably ends up being a few bytes). NPCs would spawn and die constantly. How would I go about managing the memory for this?

• malloc and free individual NPCs
• Boehm-Demers-Weiser conservative garbage collector
• malloc a big chunk of memory and build some kind of memory manager on top of it (are there techniques for this?)

Please advice.

>>38
No, really. Starcraft(1st one, I never played 2nd) can calculate at least thousand of units in real time without faking. You are doing turn based game.

>>41
OP asked for "thousands of". Not "a thousand".

>>41
While we're on the subject, how many MHz is the processor you are anticipating, OP?

>>39
fuck you faggot

>>31
does contain horrible, misleading code,
How many times have we been over this? The whole point of the post was that misleading code is a problem, of course it contains an example of exactly that. I've explained that a few times already, including the very same post the code appears in.

>>42
FWIW, I had a simulator running ~300,000 object simulations/sec., executing transcendental computations on about 16 different attributes plus branching code running on an ARM chip clocked at 66MHz with no FPU. Unless you plan to do something obscene like solve path finding completely each frame for each entity or get into very high numbers of entities I don't see a problem brewing if you are targeting desktop typical systems with 1920x1080 displays.

• while it's true that you can only ever see a screenful at a time, i'm going for a DWARF FORTRESS-like game (or simulation), where you command multiple hundreds of @'s. i want to see how far i can take this without faking things.

• the terrain will be saved as a two dimensional array and accessed through a map_(x,y) macro so that later on we can add support for an infinite world.


static tile map[MAP_W][MAP_H];
#define map_(x,y) map[x][y];

• a tile is a single byte, and holds all information necessary for path-finding: 4 bits for terrain type, 1 bit for walkable, etc...

• i can update the code in >>12 to use a bona fide memory pool that allows indices to data (as per >>19 and wikipedia).

• i'll write a quadtree for a mapping of position -> game object index. i'll probably end up using another memory pool for the nodes inside the tree.

>>45
The whole point of the post was that misleading code is a problem, of course it contains an example of exactly that. I've explained that a few times already, including the very same post the code appears in.
You still don't get it.

The code itself is not the problem. It is a consequence.

The moment you decide to pass a pointer to some kind of nul-terminated array because that's "C style", you get horrible code ridden with problems that you can heroically overcome and discuss with other brain damaged people.

The moment you decide to pass a proper array with length and an index, you are practically destined to write good code. At least you are guaranteed to avoid every problem of the documented in >>7.

Look:
since code like this is a little unclear about intentions
Miss.

It's better to use a struct member to indicate that it's the last item
Miss.

but you'll have to guard against exhausting the list.
Miss.

There's also a subtle bug: if you do not null terminate the list, it will continue searching past the end of the array whenever the list is full.
Miss.

I'd sooner use a nonserial format for this kind of thing because of the possibility of errors above. Alternatively you could just mark individual NPCs as "free" when deleting and skip them when walking the list.
I can't imagine what did you mean by "nonserial format", but it's a miss anyway.

When I say that you are an awful programmer I mean "programmer", not "coder". As a coder you did a good job: wrote some code, then demonstrated its various flaws. No questions about that.

Your brain damage manifested itself and doomed your efforts before even one line of code was written. And it seems that not only you are a terrible braindamaged programmer, but what's even worse, you don't realize there are decisions to be made before coding, which could produce all the difference in the world!


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

#define MEM_SIZE 1024
#define MEM_TYPE int

MEM_TYPE* mem = NULL;
int mem_chunks = 0;
int mem_free = 0;
int mem_index = 0;

typedef union mem_block
{
    int next_block;
    MEM_TYPE value;
} mem_block;

void grow_pool()
{
    // printf( "chunks: %d\n", mem_chunks);
    mem_chunks++;
    mem_free = MEM_SIZE;
    mem = realloc(mem,mem_chunks * MEM_SIZE * sizeof(MEM_TYPE));
   
    if(mem == NULL)
    {
        fprintf(stderr, "Out of memory, exiting\n");
        exit(1);
    }
   
        memset(mem + (mem_chunks-1) * MEM_SIZE * sizeof(MEM_TYPE),
        0xFF,
        MEM_SIZE * sizeof(MEM_TYPE));
}

int store(MEM_TYPE data)
{
    if ( mem_free-- == 0) grow_pool();
   
    int old_index = mem_index;
    int current = mem[mem_index];
   
    if ( current == 0xFFFFFFFF)
    {
        mem[mem_index++] = data;
        return (mem_index-1);
    }
    else
    {
        mem[mem_index] = data;
        mem_index = current;
        return old_index;
    }
}

void unstore(idx)
{
    mem[idx] = mem_index;
    mem_index = idx;
    mem_free++;
}

int main()
{
    grow_pool();
    store(345);
    int i = store(4038);
    store(12);
    printf( "%d\n", mem[i]);
    unstore(i);
    printf( "%d\n", mem_free);
   
    for ( i = 0; i < 1100; i++) store(i);
    // segfault... WTF!!!!
}


Program received signal SIGSEGV, Segmentation fault.
0x08048585 in store (data=4101) at mem.c:42
42              int current = mem[mem_index];

FUCKING C FUCK C FUCK FUCK FUCK FUUUUUCK FUCK C FUCKIT FUCK

install gentoo

>>48
Install valgrind. Fix all kind of errors(including race conditions) before they even corrupt your data.

>>21
>a freak of nature produced by overexposure to C and underexposure to other system languages.


OP, are you Tom in 316?
I know that's you

C++, deconstructors

i don't know any toms, but i did just figure out what the problem was. join me and come and learn something:

I wanted to grow the malloc memory in mem_pool by CHUNK_SIZE copies of mem_block, and have those new mem_block's initialized to 0xFF.


union mem_block
{
    unsigned int next_free;
    MEM_TYPE val;
    char d[100]; // for testing with sizeof(union mem_block) = 100
};

union mem_block* mem_pool;
mem_chunks++;
int size = mem_chunks * CHUNK_SIZE * sizeof(union mem_block);
mem_pool = realloc(mem_pool, size);

this works, ... but when i try to initialize the part i just added i get a segfault while calling memset:


int offset = (mem_chunks-1) * CHUNK_SIZE * sizeof(union mem_block);
int length = CHUNK_SIZE * sizeof(union mem_block);
memset(mem_pool + offset, 0xFF, length);

it seem the problem here is the * sizeof(union mem_block) part from the definition of offset. if i remove it, the code suddenly appears to work. at first i didn't understand this at all, but now i think it is because pointer arithmetic in C works like this:


huge_type* ptr = &foo;
huge_type* ptr2 = ptr+1;
ptr2 - ptr1 = sizeof(huge_type);

so, problem solved i hope? i'll post the source to memory manager as soon as i'm done with it.

no more segfaults!


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

#define MEM_TYPE char
#define CHUNK_SIZE 12

union mem_block
{
    unsigned int next_free;
    MEM_TYPE val;
};

union mem_block* mem_pool;

#define mem_(idx) mem_pool[idx].val

unsigned int mem_chunks = 0;
unsigned int mem_blocks_left = 0;
unsigned int mem_index = 0;

void grow_pool()
{
    mem_chunks++;
    mem_blocks_left = CHUNK_SIZE;
   
    mem_pool = realloc(mem_pool, mem_chunks * CHUNK_SIZE * sizeof(union mem_block));
   
    if(mem_pool == NULL)
    {
        fprintf(stderr, "Out of memory, exiting\n");
        exit(1);
    }
   
    memset(mem_pool + (mem_chunks-1) * CHUNK_SIZE,
        0xFF,
        CHUNK_SIZE * sizeof(union mem_block));
}


int store(MEM_TYPE data)
{
    if ( mem_blocks_left == 0) grow_pool();
    mem_blocks_left--;
   
    int old_index = mem_index;
    union mem_block current = mem_pool[mem_index];
   
    if ( current.next_free == 0xFFFFFFFF)
    {
        mem_pool[mem_index++] = (union mem_block) data;
        return (mem_index-1);
    }
    else
    {
        mem_pool[mem_index] = (union mem_block) data;
        mem_index = current.next_free;
        return old_index;
    }
}

void unstore(unsigned int idx)
{
    mem_pool[idx] = (union mem_block) mem_index;
    mem_index = idx;
    mem_blocks_left++;
}

int main()
{
    grow_pool();
    int i;
    for ( i = 0; i < CHUNK_SIZE * 30; i++) store(i*2);
    for ( i = 0; i < CHUNK_SIZE * 30; i++) unstore(i);
    for ( i = 0; i < CHUNK_SIZE * 30; i++) store(i*2);
    int d = store(123);
    printf( "%d\n", mem_(d));
    exit(1);
}

union mem_block* mem_pool = NULL;

Heheheh...

>>1
heap
Stopped reading right there.

funny to see your own dead threads resurrected... who the fuck is >>58? also, here's the lastest version of the code:

[#]
struct mem_pool
{
    unsigned int slot_size; // the size of each object in the pool
    unsigned int pool_size; // the number of objects in the pool
    unsigned int slots_left; // space left in the pool
    void* pool;
    void* ptr;
};

void mp_init(struct mem_pool* mp, unsigned int slot_size, unsigned int pool_size)
{
    mp->slots_left = pool_size;
    mp->slot_size = slot_size;
    mp->pool = malloc(pool_size*slot_size);
    if(mp->pool == NULL)
    {
        fprintf(stderr, "Out of memory, exiting\n");
        exit(1);
    }
    mp->ptr = mp->pool;
    memset(mp->pool, 0, pool_size*slot_size);
}

void* mp_alloc(struct mem_pool* mp)
{
    if (mp->slots_left == 0)
        return NULL;
   
    int* current = mp->ptr;
    if ( *current == 0)
        mp->ptr += mp->slot_size;
    else
        mp->ptr = (void*) *current;

    return (void*) current;
}

void mp_free(struct mem_pool* mp, void* slot)
{
    memcpy( slot, mp->ptr, sizeof(void*));
    mp->ptr = slot;
    mp->slots_left++;
}
[/#]

(Post truncated.)

(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)

(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
(Post truncated.)
FAGGOT.

8^2 get

RSA^key get

dubs

I CAN'T BELIEVE NONE OF YOU GUYS TOLD ME ABOUT OBSTACK

from http://www.ibm.com/developerworks/linux/library/l-memory/:

In pooled memory management, each allocation specifies a pool of memory from which it should be allocated. Each pool has a different lifespan. In Apache, there is a pool that lasts the lifetime of the server, one that lasts the lifetime of the connection, one that lasts the lifetime of the requests, and others as well. Therefore, if I have a series of functions that will not generate any data that lasts longer than the connection, I can just allocate it all from the connection pool, knowing that at the end of the connection, it will be freed automatically. Additionally, some implementations allow registering cleanup functions, which get called right before the memory pool is cleared, to do any additional tasks that need to be performed before the memory is cleared (similar to destructors, for you object-oriented folks).

To use pools in your own programs, you can either use GNU libc's obstack implementation or Apache's Apache Portable Runtime. GNU obstacks are nice, because they are included by default in GNU-based Linux distributions. The Apache Portable Runtime is nice because it has a lot of other utilities to handle all aspects of writing multiplatform server software. To learn more about GNU obstacks and Apache's pooled memory implementation, see the links to their documentation in the Resources section.

it seems no true c wizards exist on /prog/
i guess i'll become the first

>>67
Have you watched your SICP today?
http://thepiratebay.org/torrent/5765112/MIT_OpenCourseWare_6.001_Structure_and_Interpretation_of_Compute

>>67
Apache
Also Subversion uses that shit, and it didn't help it any: it's as bloated enterprise as possible, and then some.

I can't comprehend how you came to the conclusion that Apache-style memory pools are appropriate for a "roguelike with thousands of NPCs". Then again, I stopped reading the thread midway because it was physically hurting me.

>>67
it seems no true c wizards exist on /prog/
i guess i'll become the first
Let me tell you about my scheme fibs.

>>70
let me tell you
about my quoting skills

>>67
ffs why are dynamically allocating these things
array + freelist + 50x50 tiles for spatial indexing

>>69
i'm not going to use those after all, i think i'll stick with my >>60. thanks for the valuable input though, i'll be sure to include you as a character in my game: i've decided to make my dwarf fortress auschwitz themed.

you'll be in control of nazi camp guards (soldiers technicians etc...) and you have to build barracks, gaschambers, ovens, gallows, prisons, etc.... and kill and burn all the J's (and j's). there will also be pink J's.

first the j's arrive in trucks but after awhile you get to build a trainstation to continually ship 'em in. you also get to have higher nazi commanders in your camp. the game ends when you've killed all the jews.

>>72
motherfucker thanks

http://en.wikipedia.org/wiki/Free_list

A free list is a data structure used in a scheme for dynamic memory allocation. It operates by connecting unallocated regions of memory together in a linked list, using the first word of each unallocated region as a pointer to the next. It's most suitable for allocating from a memory pool, where all objects have the same size.
Free lists make the allocation and deallocation operations very simple. To free a region, one would just add it to the free list. To allocate a region, one would simply remove a single region from the end of the free list and use it. If the regions are variable-sized, one may have to search for a region of large enough size, which can be expensive.
Free lists have the disadvantage, inherited from linked lists, of poor locality of reference and so poor data cache utilization, and they provide no way of consolidating adjacent regions to fulfill allocation requests for large regions, unlike the buddy allocation system. Nevertheless, they're still useful in a variety of simple applications where a full-blown memory allocator is unnecessary or requires too much overhead.