Menu
I have a program in which I want to be able to store certain data (dynamically allocated blocks), on disk for reduced memory usage and persistence.
My first thought was to write my own custom allocator which managed the content of files on the disk, but I want to see what alternatives there are too.
I've looked into custom memory allocators and topics on object serialization but there are subtle differences, both good and bad, when adapting those principles to managing the address space of a file.
In this situation:
Memory is accessed only through IO (read/write) functions rather than directly
No objects(methods/pointers) are stored, only data.
The size of a file is not static, so it should grow when needed rather than being large and static
For my uses, it is acceptable to re-map existing pointers after defragmentation
Because the data is not of a fixed size, most database implementations seem not well suited.
I ask, what is the best approach for this problem? Should I implement a simple memory allocator which treats a file as the heap?
For reference, im using C++ on embedded devices.
Edit: I've implemented my own memory manager which uses buddy memory allocation and block sizes of powers of two. I'm satisfied that it is correct and does not leak, coalesces free blocks, and can do a 'stop the world' defragmentation.
The problem is, as expected, there is quite a bit of internal and external fragmentation. I'm not an expert in this field and although I find it fascinating (I'm still a student), I wonder if there are any other implementations that have done the same or similar thing? Surely I cant be the only one?
Some helpful but so far incompatible topics are:
mmap tbh I havent used mmap but, it addresses the file IO, but not the management of the file address space.
BOOST:serialization I have a (probably unjustified) reluctance to use boost libraries at the moment.
STXXL Interesting but doesnt address variable size memory allocation
Doug Lea Memory Allocator Has very good insights into issues with memory allocators, but I'm not in a position to try and make my own implementation
743
Dynamic Memory Allocation is a process in which we allocate or deallocate a block of memory during the run-time of a program. There are four functions malloc(), calloc(), realloc() and free() present in <stdlib. h> header file that are used for Dynamic Memory Allocation in our system.
In C, dynamic memory is allocated from the heap using some standard library functions. The two key dynamic memory functions are malloc() and free(). The malloc() function takes a single parameter, which is the size of the requested memory area in bytes. It returns a pointer to the allocated memory.
Dynamic allocation can be handled in one of two general ways: • Stack allocation (hierarchical): restricted, but simple and efficient. Heap allocation: more general, but less efficient, more difficult to implement.
A way or organizing different types of data in the phone's memory. Also referred to as Shared memory. Dynamic memory means that all types of data are stored in the same memory (there is no separate memory for photos, ringtones etc.).
I've implemented my own memory manager which uses buddy memory allocation and block sizes of powers of two. I'm satisfied it is correct and has doesnt leak, coalesses free blocks and can do a 'stop the world' defragmentation.
That's a great first step. Once you have a working custom memory allocator you can of course do better!
The problem is, as expected there is quite a bit of internal(power of 2 blocks) and external fragmentation. I'm not an expert in this field and although I find it facinating (I'm still a student), I wonder if there is any other implementations that have done the same or similar thing? Surely I cant be the only one?
The power of two is a generic approach. However, note that this may not be the best simply because your allocation pattern may not follow the same geometric progression. In such a case it is best to test as much as you can and see what block sizes are getting allocated the most and optimize accordingly.
I would also like to suggest this a wonderful article by Andrei Alexandrescu and Emery Berger on the topic of memory allocation: Policy-Based Memory Allocation and the latter's work in particular: The Hoard Memory Allocator.
If possible go through the references mentioned at the end of that article. They may just as well provide additional insights.
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
