5 ms·
This is great. Garbage collection is one of those things that tends to scare people, even though a basic garbage collector can be very simple (though a naive ap
by vidarh 7y ago
This is great. Garbage collection is one of those things that tends to scare people, even though a basic garbage collector can be very simple (though a naive approach is usually also horribly slow..). Great to see the amount of illustrations to make it easier to grasp.
- z92 7y agoGarbage collection isn't that slow. I find allocating off the fragmented memory after collection slower.
- vidarh 7y agoA good gc isn't slow. But a naive one that tends to be awful. E.g common problems involve thrashing cache by touching the entire heap regularly.
- amelius 7y agoDesigning and implementing a low latency concurrent garbage collector is actually at least as difficult as writing an optimizing compiler. Many languages today still struggle with concurrency+GC (see e.g. python, ocaml). Good to see this chapter on GC, but I think the subject deserves an entire book!
- munificent 7y ago> Garbage collection is one of those things that tends to scare people That's exactly why I was excited to write this chapter. They have a reputation for being hard, but the core algorithm is really just a simple graph traversal.
- cracauer 7y agoA GCed piece of nontrivial code can also be faster than a malloc/free solution. The reason being that allocation can be much faster. The GCed code can allocate memory with as much as an increment of a pointer (and that is atomic, so no thread locking needed). malloc/free always do full function calls, and they might/will descent into dealing with fragmentation (aka finding free space). Likewise, free() isn't free and cross-thread allocation/deallocation can further complicate things.
- jashmatthews 7y agoIs this universally true? Redis for example vendors jemalloc so it’s entirely possible for malloc to mostly inline? IIUC malloc isn’t a syscall like the underlying sbrk and mmap calls that malloc implementations use to get memory from the kernel?
- cracauer 7y agoSure, you can change any of the individual properties. But if you cannot move memory (adjust pointers like most GCs do) then you will have to deal with fragmentation, which slows down allocation (or causes other drawbacks). Moving GC can also make the program faster due to memory compactation and hence being more efficient wrt CPU cache and TLB.
- vidarh 7y agoFragmentation issues depends greatly on language. E.g I'm (perpetually, it seems) working on a Ruby compiler, and I slotted in a naive gc as a starting point and instrumented it. Turned out the vast majority of allocations are tiny object instances of a handful of different sizes. As a result minimizing fragmentation is as easy as allocating pools of a fixed size for small objects, and round up larger objects to a multiple of block size. There are still truly pathological patterns possible, and a compacting / generational gc may still be worth it later both to deal with that and to reduce the cost of a collection, but for a lot of uses you can get away with simple options like that.
- umanwizard 7y agoMalloc is not a syscall, you're right. But it's a quite complicated funtion, so it wouldn't make sense for the compiler (or linker) to inline it wherever it's called.
- jashmatthews 7y agojemalloc is deliberately structured so that the fast path is all inlined and all unlikely paths which would cause it to blow the inlining complexity budget get pushed out.
- stevekemp 7y agoI recently read this piece, which I think has been posted here before, which walks through the process in an isolated fashion: https://journal.stuffwithstuff.com/2013/12/08/babys-first-garbage-collector/ https://journal.stuffwithstuff.com/2013/12/08/babys-first-ga... I've implemented a couple of scripting languages, but thus far I've ignored GC. It is something I'd like to experiment with in the future though.