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

121–130 of 182 posts

Re: Memory Allocation

#121

Post by samwho »

bambax wrote: post #112

Excellent, excellent article! I have a question though. > Couldn't we rearrange the memory to get a block of 6 contiguous bytes? Some sort of defragmentation process? > Sadly not. Remember earlier we talked about how the return value of malloc is the address of a byte in memory? Moving allocations won't change the pointers we have already returned from malloc. We would change the value those pointers are pointed at,…

You’d need cooperation between your malloc implementation and the application code. It’s possible, but tricky. If your malloc returned a pointer to a pointer, and promised to keep the first level pointer up to date, and was able to lock your application whenever it moved things around, it could work.

Someone else already mentioned, but garbage collected languages do actually do this. Because they’re fully in control of memory (the language exposes no raw pointers), they’re able to create the layer of indirection you’ve suggested and move things around as they please. I know at minimum the JVM does this. The term to search for is “heap compaction.”

There’s also the weird and wonderful work of Emery Berger et al with their “Mesh” malloc implementation, which blows my mind: https://youtu.be/XRAP3lBivYM.

Re: Memory Allocation

#122

Post by samwho »

ftxbro wrote: post #97

> "There's no shortage of information about memory allocators on the Internet, and if you've read this far you should be well-placed to dive in to it. Join the discussion on Hacker News! https://news.ycombinator.com/item?id=36029087 " Interesting to use hacker news as the blog's own comment section in this way.

I’ve seen a few people doing it, seems to work well.

Re: Memory Allocation

#123

Post by samwho »

markus_zhang wrote: post #110

Interesting. Is there a book that focuses on evolution of allocators so we can follow along and code allocators of different difficulties?

Good question! I’m not aware of one, but I also haven’t looked.

Most of the research for this post was done by reading papers for various malloc implementations (phkmalloc, dlmalloc, tcmalloc, mimalloc) and reading their source code.

Re: Memory Allocation

#124

Post by EvanAnderson »

zeusk wrote: post #119
alex7734 wrote: post #104

Earlier quoted context omitted.

Yes and no, it took me from 8am to 3am once we decided it needed to get fixed but really it sat on the app for years, it only happened on a background process that sent print jobs on a timer, since it used Windows GDI to compose the image we sent to the printer it was affected (our "frontend" should've been affected too but never was, I guess because it had a different memory usage pattern). We just had it restart it…

How do you attach kd to VM? While I was at MS, it was such a big PITA - we just had a bunch of IT managed machines with KVM console access and KDNET for debugging.

In Hyper-V it's fairly easy. You make a virtual serial port ("COMPort"), set the bootloader to enable kernel debugging over serial, then connect to the virtual serial port from the host via a named pipe.

https://learn.microsoft.com/en-us/windows-hardware/drivers/d...

I haven't tried it with vSphere but I suspect it'd be similar.

Re: Memory Allocation

#125

Post by aidenn0 »

bambax wrote: post #112

Excellent, excellent article! I have a question though. > Couldn't we rearrange the memory to get a block of 6 contiguous bytes? Some sort of defragmentation process? > Sadly not. Remember earlier we talked about how the return value of malloc is the address of a byte in memory? Moving allocations won't change the pointers we have already returned from malloc. We would change the value those pointers are pointed at,…

> But why not? Couldn't we store information about old pointers somewhere and match them with new addresses when defragmenting? Some kind of virtual memory driver that would map old pointers to new adresses transparently for the programs? Or would it be too much overhead for too little benefit?

In languages where memory is managed for you, you can absolutely do this, since the runtime can find every single pointer to an object and rewrite it.

Virtual memory can let you do this, but would require a separate page for each allocation (since virtual memory operates on a page-level). Given that the smallest page on modern architectures is 4k, this would mean using 4k of ram for each allocation (and rounding up each allocation to a 4k page boundary).

On top of that, it's an OS system call to map and unmap pages, which means you incur a system-call on every allocation and deallocation, which is much slower than using a user-space allocator.

Re: Memory Allocation

#126

Post by AshamedCaptain »

bambax wrote: post #112

Excellent, excellent article! I have a question though. > Couldn't we rearrange the memory to get a block of 6 contiguous bytes? Some sort of defragmentation process? > Sadly not. Remember earlier we talked about how the return value of malloc is the address of a byte in memory? Moving allocations won't change the pointers we have already returned from malloc. We would change the value those pointers are pointed at,…

Most OSes today do that "transparently" with virtual memory, but usually with a coarse granularity (e.g. 4k). A page table is just a translation of "pointers" to "memory addresses"; the OS can rearrange physical memory as it sees fit without the program having to update its pointers.

In OSes without virtual memory, one option is to do the same non-transparently: instead of returning pointers, malloc and friends work with "pointers to pointers" (called handles), so there is one extra level of indirection, and now the OS is free to rearrange this 2nd level as it sees fit. Whenever a program wants to read/write the data behind a handle, it must dereference the handle to get to the real pointer, but it also must let the OS know that it is currently using the real pointer -- this is to avoid the OS moving it around. This is usually called "locking/unlocking" the handle.

Some classic examples are Windows 3.x, Mac OS (toolbox), PalmOS, etc.

https://en.wikipedia.org/wiki/Classic_Mac_OS_memory_manageme...

Re: Memory Allocation

#127

Post by e_y_ »

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…

This would probably be something closer to actors (https://en.wikipedia.org/wiki/Actor_model) rather than programs since programs are traditionally implemented as OS processes which are relatively expensive to spin up and terminate. At some level, though, somebody has to deal with freeing the memory, and they may do it less efficiently than you can.

Re: Memory Allocation

#128

Post by cinntaile »

samwho wrote: post #45
cinntaile wrote: post #43

Can you highlight the specific malloc() calls in the interactive part? It confused me when it said malloc(5) because it looks almost exactly like malloc(4). Specifically highlighting the malloc(5) allocation would make that a bit clearer I think.

I completely agree with you on this, though I couldn't find a great way to do it. It was suggested to me to put an outline around the allocation or free that just happened, but I struggled to get the box to look good when the allocation was split across 2 lines. I've started writing my next post and have learnt a bit more about PixiJS/GSAP3, and think I know a way to do it that would work nicely but would require cha…

I understand. It's surprisingly difficult to do anything non-trivial on the web.

Re: Memory Allocation

#130

Post by winrid »

I was having some fun recently just seeing how fast we can allocate large chunks of memory.

There's something refreshing about firing up a C (or maybe now Zig, in my case) compiler and allocating a gigabyte of memory, and seeing that your process is using exactly 1GB.

Post reply on HN