This blog will hopefully be a place where I can share code with friends, talk about programming and technology related stuff, and serve as a repository for my past stuff when I need it later...
To start off, here's something I worked on a while back: A memory allocator that implements the C functions nmalloc and nfree (which basically do the same thing as malloc and free in malloc.h).
nmalloc.c : http://pastebin.com/f72460c04
nmalloc.h : http://pastebin.com/f4a8b27bc
Memory is divided into many partitions by the function nmalloc_init. Each partition has an associated block size. All blocks within one partition have the same length. While this leads to internal fragmentation, it avoids the overhead involved in managing blocks of variable length. The blocks within a partition are chained into 2 linked lists – the Used list and the Free list. Each partition has it’s own pair of linked lists. (The layout of the partitions is provided by the calling program)
If you already know the sizes of objects that will be used in your program, it speeds up allocation considerably. Unfortunately it has considerable space overhead, and isn't exactly thread friendly. I haven't optimised it because the performance was good enough for my purposes :-
O(1) allocation and deallocation when memory partitions are empty, since operations are more or less independent of number of blocks etc. (Typical delay: 2-6 µs)
O(n) allocation and deallocation when partitions start filling up, since smaller blocks must be merged. Time taken becomes proportional to size requested.
No comments:
Post a Comment