Writing a Memory Allocator (2019)
dmitrysoshnikov.com
Writing a Memory Allocator (2019)
1–10 of 44 posts
Re: Writing a Memory Allocator (2019)
#2Every time I hear someone talking about writing a memory allocator, it always reminds me of the brilliant CppCon 2015 talk by Andrei Alexandrescu about how he wrote an modular allocator library that can be built up in pieces to make whatever you like.
Re: Writing a Memory Allocator (2019)
#3Nice! At CMU, we have 15-213, an introductory course on computer systems and one of the hardest/fun assignments is implementing malloc. We end up using seglists, mini-blocks and other optimizations, ending up with a faster implementation than the standard malloc itself on several benchmark tests.
Re: Writing a Memory Allocator (2019)
#4I've been listening to Dmitry's lessons and lectures lately, I find they are really straightforward and well delivered. You can find some of his other lectures here:
Re: Writing a Memory Allocator (2019)
#5Every time I hear someone talking about writing a memory allocator, it always reminds me of the brilliant CppCon 2015 talk by Andrei Alexandrescu about how he wrote an modular allocator library that can be built up in pieces to make whatever you like. https://www.youtube.com/watch?v=LIb3L4vKZ7U
His implementation of it can be found in the D programming languages standard library.
You can build a jemalloc in about 10 lines roughly.
Re: Writing a Memory Allocator (2019)
#6I built a memory allocator for testing not too long ago that only allocated but no-op'd deallocate(using the C++ Allocator interface). It was quite amazing that it resulted in a 25-50% performance boost in many cases I was testing. It's not for real code as you only get destruction but not deallocation. It let me pull that part out of the tests to get a better view of the performance
Re: Writing a Memory Allocator (2019)
#7Implementing a memory allocator seems to require system calls. What happens when there's no OS? For example on an MCU like Arduino, is the memory allocator packaged along with the program data? If so and in the case of an Arduino, is the code for it available anywhere? I would be curious to see how this is implemented on an embedded system.
Re: Writing a Memory Allocator (2019)
#8Implementing a memory allocator seems to require system calls. What happens when there's no OS? For example on an MCU like Arduino, is the memory allocator packaged along with the program data? If so and in the case of an Arduino, is the code for it available anywhere? I would be curious to see how this is implemented on an embedded system.
You generally don’t have dynamic memory allocation on such a system. All memory will either be statically allocated globals, or on the stack. Some systems even require stack allocation to be statically determined, which means no recursion.
Re: Writing a Memory Allocator (2019)
#9Implementing a memory allocator seems to require system calls. What happens when there's no OS? For example on an MCU like Arduino, is the memory allocator packaged along with the program data? If so and in the case of an Arduino, is the code for it available anywhere? I would be curious to see how this is implemented on an embedded system.
You generally don’t have dynamic memory allocation on such a system. All memory will either be statically allocated globals, or on the stack. Some systems even require stack allocation to be statically determined, which means no recursion.
For Arduino specifically, it certainly does have an allocator and heap by default, even on MCUs with less than 1KB RAM. However, there's no separation, so the stack and heap grow towards each other. If the heap is never used, it always stays at a size of 0. For code side, just not using malloc or anything that uses it will cause it not to be linked.
Re: Writing a Memory Allocator (2019)
#10I built a memory allocator for testing not too long ago that only allocated but no-op'd deallocate(using the C++ Allocator interface). It was quite amazing that it resulted in a 25-50% performance boost in many cases I was testing. It's not for real code as you only get destruction but not deallocation. It let me pull that part out of the tests to get a better view of the performance
Yes as it turns out malloc is much faster if free doesn’t exist.