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

Memory Allocation

samwho.dev

Post reply on HN
Print view View original

21–30 of 182 posts

Re: Memory Allocation

#21

Post by davidgrenier »

samwho wrote: post #17
davidgrenier wrote: post #16

The only thing that confused me is how it said we can know the location of the block after and before by calculating: address + address - Shouldn't this be? address + + 3 address - - 3

Well shit. I think you're right.

Oh another thing, I'm not a fan of the premise:

"As a general-purpose memory allocator, though, we can't get away with having no free implementation."

I have a belief that the future of software are short-lived programs that never free memory. Programs allocate and terminate. Short-lived program communicate with each other via blocking CSP-style channels (see Reppy's Concurrent Programming in ML).

If you could also educate me on why this is a bad idea I would appreciate.

Re: Memory Allocation

#22

Post by ModernMech »

samwho wrote: post #14
ModernMech wrote: post #13

This is wonderful! I'm definitely going to be sharing this with my students (college sophomores studying CS). If I were to make some suggestions, based on how I know they would receive this: - I would make explicit reference to heap and stack. Students who are learning this material are learning about the heap/stack dichotomy, and I think it would really improve the exposition to make clear that not all memory is all…

Really appreciate you taking the time to write this, thank you. I tried a couple of different ways to introduce the stack and the heap but it always felt like it made the post too long and complicated. In the end I decided to take a pure, idealistic view of memory in order to focus on the algorithms used to pack allocations effectively. You can see some of my abandoned efforts as HTML comments in the post :D Introduc…

Maybe make this a series? I think another post just like this on the stack is in order. You could show allocating stack frames with the slider! Then you can put them both together in a third post and show the entire memory layout of a C program.

Would definitely like to see more thoughts from those cute corgis.

Re: Memory Allocation

#23

Post by samwho »

davidgrenier wrote: post #21
samwho wrote: post #17

Earlier quoted context omitted.

Well shit. I think you're right.

Oh another thing, I'm not a fan of the premise: "As a general-purpose memory allocator, though, we can't get away with having no free implementation." I have a belief that the future of software are short-lived programs that never free memory. Programs allocate and terminate. Short-lived program communicate with each other via blocking CSP-style channels (see Reppy's Concurrent Programming in ML). If you could also e…

It's funny, I saw and retweeted this while writing this post: https://twitter.com/samwhoo/status/1650572915770036225?s=20

Not sure the future you describe is where we'll end up, haven't given it a huge amount of thought. Would be interesting to see, though.

Things like web servers could probably get away with doing some sort of arena allocation per request (I'd be surprised if some don't already do this).

Re: Memory Allocation

#24

Post by samwho »

samsquire wrote: post #7

Thank you for this, this is helpful. I wrote a JIT compiler and I didn't bother calling free much, I just let the operating system free up all allocated memory. I got into this situation often: return_struct = do_something(mystruct); return_struct->inner_struct = malloc(sizeof(struct my_inner_struct)); Now, who owns inner_struct? Who is responsible for freeing it? Do I free it when I assign to it? I feel this ownersh…

Yeah, I hear you. I've not done a lot of FFI stuff directly, it scares me.

Arena allocators are cool, the idea is you allocate a large-ish region of memory and sub-allocate into it (often with a fast, simple allocator like a bump allocator) and then free the large-ish block when you're done. It's a way to take knowing how much memory you need as a whole and optimise that to a single call to malloc/free.

You may enjoy looking through https://www.cs.usfca.edu/~galles/visualization/Algorithms.ht....

Re: Memory Allocation

#25

Post by samwho »

ModernMech wrote: post #22
samwho wrote: post #14

Earlier quoted context omitted.

Really appreciate you taking the time to write this, thank you. I tried a couple of different ways to introduce the stack and the heap but it always felt like it made the post too long and complicated. In the end I decided to take a pure, idealistic view of memory in order to focus on the algorithms used to pack allocations effectively. You can see some of my abandoned efforts as HTML comments in the post :D Introduc…

Maybe make this a series? I think another post just like this on the stack is in order. You could show allocating stack frames with the slider! Then you can put them both together in a third post and show the entire memory layout of a C program. Would definitely like to see more thoughts from those cute corgis.

A few people suggested a series, but there's a human problem: my attention jumps between topics quite a lot! At the end of this post, and my load balancing post, my main feeling was relief in that I could start looking into a new topic.

Maybe after more time has gone by I can revisit earlier posts and do follow-ups :)

Re: Memory Allocation

#26

Post by secondcoming »

samsquire wrote: post #7

Thank you for this, this is helpful. I wrote a JIT compiler and I didn't bother calling free much, I just let the operating system free up all allocated memory. I got into this situation often: return_struct = do_something(mystruct); return_struct->inner_struct = malloc(sizeof(struct my_inner_struct)); Now, who owns inner_struct? Who is responsible for freeing it? Do I free it when I assign to it? I feel this ownersh…

> Now, who owns inner_struct?

return_struct does since it is the only thing that knows the address.

> Who is responsible for freeing it?

return_struct is, unless you hand that responsibility over to something else.

> Do I free it when I assign to it?

Yes, unless you want leaks.

> I think if we could visualise memory as cars on a road, we would see obvious traffic jams.

That visualisation is helpful for threads, where the program is the road/map and the cars are the threads. I don't see how it's useful for memory.

Re: Memory Allocation

#27

Post by junon »

Seems to be a bug on the first interactive graph, at least for me. Unless I'm misunderstanding the point of the graph, `malloc(7)` only allocates 2 bytes.

Re: Memory Allocation

#28

Post by samsquire »

samwho wrote: post #24
samsquire wrote: post #7

Thank you for this, this is helpful. I wrote a JIT compiler and I didn't bother calling free much, I just let the operating system free up all allocated memory. I got into this situation often: return_struct = do_something(mystruct); return_struct->inner_struct = malloc(sizeof(struct my_inner_struct)); Now, who owns inner_struct? Who is responsible for freeing it? Do I free it when I assign to it? I feel this ownersh…

Yeah, I hear you. I've not done a lot of FFI stuff directly, it scares me. Arena allocators are cool, the idea is you allocate a large-ish region of memory and sub-allocate into it (often with a fast, simple allocator like a bump allocator) and then free the large-ish block when you're done. It's a way to take knowing how much memory you need as a whole and optimise that to a single call to malloc/free. You may enjoy…

Thanks for the link to the animations.

I want an extremely performant deep copy solution, I've been thinking of using an allocator to implement it.

If we have a tree data structure or a nested hashmap, then we want to copy it cheaply, there is copy on write. But most copies of hashmaps are slow because they instantiate every child object in a recursive loop.

So I want to be able to memcpy a complicated data structure for cheap copies.

Re: Memory Allocation

#29

Post by junon »

davidgrenier wrote: post #21
samwho wrote: post #17

Earlier quoted context omitted.

Well shit. I think you're right.

Oh another thing, I'm not a fan of the premise: "As a general-purpose memory allocator, though, we can't get away with having no free implementation." I have a belief that the future of software are short-lived programs that never free memory. Programs allocate and terminate. Short-lived program communicate with each other via blocking CSP-style channels (see Reppy's Concurrent Programming in ML). If you could also e…

I agree with your point but disagree with your reasoning. I think programs should always free memory at some point because then it's easier to reason about debugging memory leaks.

Practically speaking though, there are arena allocators that do exactly this - you allocate a bunch of memory at once, assign like-typed instances to "slots" in that memory region, and then deallocate everything all at once. Thus, the individual instance `free()` is a no-op.

Re: Memory Allocation

#30

Post by ozfive »

junon wrote: post #27

Seems to be a bug on the first interactive graph, at least for me. Unless I'm misunderstanding the point of the graph, `malloc(7)` only allocates 2 bytes.

I came here to see if anyone else noticed this and am confirming that there is a bug in the first slider on malloc(7). Indeed it only allocates two bytes instead of seven.
Post reply on HN