Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a Memory Allocator (2019)

dmitrysoshnikov.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: Writing a Memory Allocator (2019)

#11

Post by troutwine »

beached_whale wrote: post #6

I 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

In case you weren't aware, this is a common enough technique for it to actually have a name: bump allocation. It's very useful in short lived programs with bounded allocations, for the exact reason you outlined.

Re: Writing a Memory Allocator (2019)

#12

Post by saagarjha »

ajfjrbfbf wrote: post #7

Implementing 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.

In every allocator there has to be a way to get “the memory” that is available for you to hand out. When a normal OS is present, system calls are used to get this in the form of pages. On embedded environments you don’t need to do this because “the memory” is just something like “addresses from 0x2000000 to 0x8000000” and you don’t have to ask for it, it’s just there for you to use.

Re: Writing a Memory Allocator (2019)

#13

Post by saagarjha »

fermentation wrote: post #10
beached_whale wrote: post #6

I 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.

Not just that: malloc is faster if you don’t have to care about thread safety, or support interposing, or hooks, or if security is not a concern. It is easy to “beat malloc” in a specific usecase if you know what it will be beforehand. Doing this in general is what is hard.

Re: Writing a Memory Allocator (2019)

#14

Post by saagarjha »

jiggawatts wrote: post #2

Every 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

It’s a great talk, but something I would watch after learning how to implement a malloc as it talks about other kinds of allocators and how to make them composable rather than say “how would I encode a freelist”.

Re: Writing a Memory Allocator (2019)

#15

Post by [deleted] »

saagarjha wrote: post #12
ajfjrbfbf wrote: post #7

Implementing 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.

In every allocator there has to be a way to get “the memory” that is available for you to hand out. When a normal OS is present, system calls are used to get this in the form of pages. On embedded environments you don’t need to do this because “the memory” is just something like “addresses from 0x2000000 to 0x8000000” and you don’t have to ask for it, it’s just there for you to use.

[deleted]

Re: Writing a Memory Allocator (2019)

#16

Post by porknubbins »

bholagabbar wrote: post #3

Nice! 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.

I did that lab and I recall the professor saying “this will be the hardest code some of you have ever written.” I supposed thats true if its an intro course at CMU? Debugging was certainly mind numbing reading pages of hex to figure out where the bug is. I don’t think I ever did get realloc to pass all tests.

Re: Writing a Memory Allocator (2019)

#19

Post by akandiah »

bholagabbar wrote: post #3

Nice! 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.

I believe Bryant and O'Hallaron wrote a text book just for this course. You can always "optimize" it by reverse engineering the benchmark app and providing the correctly aligned blocks to the bench-marking application. It'll beat the standard malloc calls by several magnitudes if you were to do that.

This is one of the reasons why people write custom allocators - to suit a specific purpose where the allocation pattern is known well in advance.

Re: Writing a Memory Allocator (2019)

#20

Post by vinay_ys »

A modern lecture on memory allocators should have covered aspects to developer ergonomics w.r.t memory safety features like leak detection, use after free etc and allocation statistics in general. These are must-have features of any memory allocator library.
Post reply on HN