12 ms·
Proposed New Go GC: Transaction-Oriented Collector
- vvanders 10y agoLooks a lot like an Arena allocator tied to a specific execution context.
- Doradus 10y agoI'm not sure you've grasped the write barrier part. That's the really new part.
- Kapura 10y agoI have a generational art program that I wrote under Go 1.4 which was absolutely crushed by 1.5's GC. The program heavily abuses goroutines, so I'm cautiously optimistic that this optimisation would allow me to keep my version of Go current once again.
- _ak 10y agoHave you tested it with the GC improvements in 1.6 and the 1.7 beta? If so, did they have any impact on your program's performance?
- Kapura 10y agoI did test in 1.6, and the performance and output were still significantly worse than in 1.4. The part I'm saddest about is that because some of the goroutines abuse involved literally building in a race condition, the aggressive garbage collection made the resulting output less artistically interesting (on top of taking an hour to complete instead of a few minutes).
- iainmerrick 10y agoThat doesn't sound like something that's likely to get fixed. More like a loophole that's now gone.
- Kapura 10y agoI think you're probably right, but this whitepaper gave me a sliver of hope that my goroutines might be free to work some nondeterministic magic once again
- h8liu 10y agointeresting work. if I am understanding correctly, you are essentially using the randomness generated by the scheduler to produce art pieces. do you have a public link to your work?
- deleted 10y ago[deleted]
- Kapura 10y agoAlas, I've been hording almost all of the most interesting images I've created using the process, but I wrote up a short piece when I got the initial program running [1], and I do have a few examples of pictures generated using the derivations of the code that still make use of the core of the algorithm (these are all huge images!) [2][3][4][5][6]. [1] https://medium.com/@kapuramax/procedural-image-generation-in-go-7a57ff2e2e90#.7dxx5hzci https://medium.com/@kapuramax/procedural-image-generation-in... [2] http://www.nobledust.com/full_size/bullet.r0g0b0.x1000y1000.blur5.ch100.cpu2.png http://www.nobledust.com/full_size/bullet.r0g0b0.x1000y1000.... [3] http://www.nobledust.com/full_size/b.brg.rr0.90.blur1.ch8.cpu8.png http://www.nobledust.com/full_size/b.brg.rr0.90.blur1.ch8.cp... [4] http://www.nobledust.com/full_size/a.jpg http://www.nobledust.com/full_size/a.jpg [5] http://www.nobledust.com/reds.png http://www.nobledust.com/reds.png [6] http://www.nobledust.com/full_size/mosey.png http://www.nobledust.com/full_size/mosey.png
- jerf 10y agoLooking over your code, did you ever run it single-threaded to compare the performance? I see you spawning what appears to be a crapton of goroutines, each of which performs a very small number of operations, then terminates. As cheap as goroutines are, they still have some cost to startup and shutdown, and it's not a good idea to spawn a goroutine if it's going to do roughly the same order of work inside the goroutine as the spawn & shutdown costs. This is a pessimal situation. I'm not sure if you're seeing the GC fail or if you're seeing the scheduler choke under the harsh load. If you just want nondeterminacy, I'd suggest using math/rand directly, not accidents of scheduling... which, as was just proved, can disappear as quickly as they appear. In fact it doesn't even take something as serious as a language upgrade for that to happen, that kind of indeterminancy can disappear if you so much as add a member to a struct or have another process on your system eating 100% of one CPU or something. It's not reliable, not even a little.
- gtirloni 10y agoWhat is a generational art program? If you don't mind me asking.
- overcast 10y agoSenior finger painting classes.
- 0xdeadbeefbabe 10y agoIn Florida.
- Kapura 10y agoWell, in my case specifically, it was a program that generated coloured images based on a set of simple rules (namely, don't reuse the same RGB colour for any pixel & try to be as close to the colour of neighbouring pixels as possible). I wrote a brief overview around the time I finished the first version[1]. More recently, I wrote a new routine which generates several of those and then averages the RGB channel values on a per-pixel basis, and then repeatedly re-averages the original images with those average images to create more "generations." I haven't written anything up about that because the code required to sum and average pixels in a PNG is significantly less interesting. [1] https://medium.com/@kapuramax/procedural-image-generation-in-go-7a57ff2e2e90#.7dxx5hzci https://medium.com/@kapuramax/procedural-image-generation-in...
- spriggan3 10y agos/generational/generative ?
- vessenes 10y agoThat's interesting -- my use case had up to 2 minute GC pauses in 1.4, and now runs without a hiccup. For a variety of reasons, some code-side and some on Go's side. I didn't know there were use cases that were negatively affected by GC work done in the last year or two.
- giovannibajo1 10y agoDid you open a bug report with some datasets (profile dumps, etc.)? Go developers treat these kinds of regressions very very seriously. They absolutely want to avoid situations were users are pinned to an old version because of a performance regression.
- dboreham 10y agoFinally a reason for me to consider using Go vs Java.
- andrewfromx 10y agooh there were plenty other reasons before this!
- pjmlp 10y agoI used to think like that until they decided to freeze the language.
- federicoponzi 10y agoWhat do you mean?
- TheDong 10y agoThe Go1 promise (https://golang.org/doc/go1compat https://golang.org/doc/go1compat) means that they cannot refine the language any further. It's frozen. For example, there's a mess of different error handling techniques (e.g. err == io.EOF vs os.IsNotExist(err) vs perr, ok := err.(*os.PathError); ok). This also prevents the language from evolving, as can be seen in the case of the context package (see 'Frozen' in this post https://github.com/golang/go/issues/14660#issue-138695431 https://github.com/golang/go/issues/14660#issue-138695431 ) While the above poster didn't explain his problem clearly, it is a valid complaint.
- andrewfromx 10y agowow, i've been golanging for a year now checking tons of if err != nil and I never once thought there was a problem.
- deleted 10y ago[deleted]
- DblPlusUngood 10y agoInteresting. The transactional hypothesis sounds like a refinement of the generational hypothesis. Seems like the main advantage of this transaction oriented collector over a typical generational collector is that it precisely identifies the old-to-young pointers and thus may scan less total objects.
- stormbrew 10y agoI'm having trouble seeing how this is actually different from a normal generational collector to begin with in practice (as opposed to implementation details). The differences I read into it are: - There is one heap rather than a young and tenure heap, but tenured objects are marked as such. - Rather than moving an object from one heap to another, the write barrier tags the object being written to a tenured object (and presumably all its children). Not all collectors move actively (as opposed to lazily at collection time) to the tenured heap, but I'm pretty sure it has been done. - 'Young generation' collections happen at a specific time: when a goroutine terminates, and happens more or less like a quick version of a semiheap copying collector, in that it just drops all objects not marked reachable. So there is interesting stuff in there, and it seems like a very appropriate approach for an event-driven environment, but it still seems like a generational collector to me. Also, I'm confused how the separation of the goroutines is maintained in this heap. When a goroutine advances its current pointer, what happens if it bumps into another goroutine's initial pointer?
- pcwalton 10y ago> - There is one heap rather than a young and tenure heap, but tenured objects are marked as such. That's a big difference. One of the largest, if not the largest, advantages of a standard generational GC in practice is bump allocation in the nursery. If I understand correctly, because of the fact that GCs don't unconditionally tenure surviving objects (instead only tenuring objects that cross thread boundaries), this algorithm loses the fast bump allocation because objects in the nursery can become noncontiguous.
- stormbrew 10y ago
- justin_vanw 10y agoIf you replace 'transaction' with 'stack'...
- vvanders 10y agoAnd if you had move semantics for values 'published' from a goroutine...
- uluyol 10y agoPlenty of things in C++ are heap allocated. When you create a vector or dynamic string, it isn't allocated on the stack. Yes RAII would still take care of it but that's a separate thing.
- vvanders 10y agoAt the risk of sounding a bit pedantic a vector or string isn't required to be on the heap. You can use either a fixed size arena allocator, or one using alloca(you better know what you're doing) and still allocate those things on the stack. In cases where you know the bounds of your input and runtime constraints you can get some really incredible performance boosts(multi-orders of mag) with those approaches.
- Jweb_Guru 10y agoAdditionally, in C++ strings of less than 23 (IIRC) bytes are not heap allocated (they reuse fields in the existing structure). Whether this is a good thing is a matter of opinion, of course.
- masklinn 10y ago> Additionally, in C++ strings of less than 23 (IIRC) bytes are not heap allocated (they reuse fields in the existing structure). Not quite. SSO is a lib-specific optimisation. LLVM's libc++ has a 22 characters SSO[0], recent MSVC and recent GNU libstdc++ have 15 characters SSO, Apache and older libstdc++ didn't have SSO at all (and used COW). The SSO-23 POC/proposal does provide a 23-characters SSO for a 24 bytes string structure (such as LLVM's, MSVC 2013 and modern G++ strings are 32 bytes and SSO-23's scheme provides space for 31 characters in the same stack space). [0] all capacities exclude the final NUL as it's required and unusable outside of C compatibility
- cmurphycode 10y agoI'm having trouble understanding what the practical difference between the transaction concept and something like RAII. It may just be the example they chose (goroutine processes an incoming request, does not "share" the contents with anyone else, and terminates when complete) but nonetheless I'm having a mental block. Can anyone clarify? Note that I'm not saying that they should've used RAII along with existing GC, I'm just trying to distinguish the transaction concept and the RAII concept.
- stormbrew 10y agoIf you take the corollary to RAII (resource disposal is destruction) as a given, then this (and any other automatic GC) system does not fit it. In C++ RAII, deallocation and deinitialization happens deterministically. In this it does not.
- pcwalton 10y agoRAII is completely static; the lifetimes of all (uniquely-owned) objects are determined at compile time with a set of rules based on the language syntax. But the "published"/"local" distinction as in this GC is dynamic: the compiler does not (and cannot) statically work out which objects are published and instead determines that at runtime. This basic distinction leads to completely different implementations.
- eternalban 10y agoWe really need to stop thinking of memory as a 'store'. Treat it as a cache and (a) GC naturally becomes a background process, and (b) you get persistent memory for free.
- weberc2 10y agoCan you elaborate? What's the distinction between 'store' and 'cache'? By 'memory', do you mean the heap or heap and stack?
- eternalban 10y agoWhen considered as 'store', the value image is at a specific memory location, i.e. a specific offset in process heap. GC's difficult role here is to manage these allocations and compact the heap, etc. When considered as a 'cache', the entire heap is a fixed sized cache. (LRU or better 2Q to deal with ephemeral objects). The actual memory object is at an offset in a mapped segment. (If mapped to a file, then voila, persistent memory). As object are created, they are immediately placed in the 'process cache'. So to take the example of the OP's 'transactional' memobjs, these are cache entries that get promoted to the LRU section of a 2Q, get utilized, and then are naturally 'garbage collected' by eviction. This scheme is not universal. Very long lived processes that sporadically access 'ancient' objects will stress the VM/FS. One can extend the temporal range of this scheme by employing a set of rotating FS-backed memory segments, but of course there will be a limit (e.g. your FS). Does that clarify the scheme? [p.s. of course one can used a leveled cache hierarchy, with optimal realization mapping to L1, L2, wired-memory. But a basic version can just use a single level 2Q cache.]
- weberc2 10y ago> Does that clarify the scheme? Sadly no. I'm sure your explanation was good, but my familiarity with GC and low-level memory management is nominal at best. Thanks for trying. :)
- SixSigma 10y agoI doubt it : @rob_pike Caches are bugs waiting to happen. 22 Mar 2014 https://twitter.com/rob_pike/status/447202124753952768 https://twitter.com/rob_pike/status/447202124753952768
- pizlonator 10y agoInteresting that they are publishing the algorithm before implementing it. I wish more people did this. This way, if the algorithm doesn't work out, we'll have some way of knowing. If they hadn't published the algorithm, tried it, and then abandoned it, then nobody would have any way of knowing that there had been a negative result. I don't have high hopes for this algorithm, because my intuition is that transactions aren't common enough to make a big difference. Looking forward to seeing the implementation and empirical data.
- deleted 10y ago[deleted]
- sctb 10y agoAnother excellent write-up ahead of implementation: http://wiki.luajit.org/New-Garbage-Collector http://wiki.luajit.org/New-Garbage-Collector.
- fsfod 10y agoWhile trying to implement the new LuaJIT GC one of the things I tested adding early on was support for explicitly creating arenas from Lua and setting the 2 active arenas allocations happen from to support this kind of allocation patten. The minor GC mode also work well with this patten only having to touch modified objects and only sweeping away fresh white objects.
- twotwotwo 10y ago"Transactions" here doesn't mean roll-back-able units like in a database, just small bits of code that terminate (and, the authors hope, leave some garbage behind that you can clean up without scanning a bunch of RAM). Request-oriented collector would have been about as good a name. This is kind of a spin on generational collection, built around the observation that a lot of Go programs are HTTP/RPC/whatever servers.
- Jweb_Guru 10y agoIt's also not exactly original to Go... the Ur language, for instance, employs a request-oriented collector (arguably, though the documentation claims it does not use garbage collection).
- kevan 10y agoI'm not at all an expert in this area but to me this sounds like a similar concept as Rust-esque ownership, at least internally in the runtime. If the runtime knows that an object wasn't shared by its goroutine owner and the owner goes out of scope then cleanup becomes (theoretically) much faster, if only because scope is greatly limited vs GC that has to scan the entire heap.
- pcwalton 10y agoIt's no more similar to Rust than any generational collector is (which is to say: not much at all). Rust's memory management story is primarily static, while this is dynamic.
- cwzwarich 10y agoRust's memory management story is not primarily static. Anything that is allocated on the stack or anchored by a stack allocation is dynamic; it can fail, and Rust checks for failure at runtime.
- dikaiosune 10y agoBut rust determines at compile time when almost all allocations need to be freed (the exceptions being Rc/Arc reference counting boxes), whereas it seems like a transaction/request GC would discover that at runtime. In other words, the allocations and deallocations are determined statically, they aren't static allocations in and of themselves.
- exabrial 10y agoNice... why hasnt the JVM ever done this?
- icholy 10y agoI'm guessing because the transactions are essentially goroutines which the JVM doesn't have.
- Doradus 10y agoNope. Transactions, in the sense of the article, bear no relation to goroutines. The right answer is that Java's generational collector supports this transaction lifetime reasonably well in many cases.
- pjmlp 10y agoWhich JVM, there are plenty to choose from. Some of them have quite good escape analysis algorithms, which are somehow similar to this.
- twic 10y agoGood question. A while ago, i had an idea for a "tidal" collector. If you look at what a thread in a typical server application is doing, it's in a loop where it picks up some task (a network request, a job from a queue, etc), then goes and does a load of work on it. If you plot at the stack depth over successive loops, you should see a sort of rising and falling tide - low tide when the task is picked up, and high tide during processing. Along with that rising and falling tide, you should get a rising and falling volume of live objects. Because garbage collection has a cost proportional to the number of live objects, for best efficiency, you want to collect when there are the fewest live objects. Which should be low tide. To make use of this idea (which might be false, but at least sounds plausible), you'd need two things: a layout where each thread has its own memory (at least, enough of its own memory to hold all the objects that escape eden but become garbage during a request cycle; you might want a shared old generation), and some magic device which watches the stack depth and identifies the moment of low tide. G1 might provide the right layout. I think every thread gets its own eden region; if you could tweak it so that each one promotes into its own survivor regions, and then be able to find the survivor regions for a given thread, you just need to be able to decide when is the right time to collect. You might be able to do that on the back of the dynamic profiling infrastructure already in the JVM; you would want to sample each thread every now and then to identify the method, even the particular line of code, where low tide happens, and then compile in a GC trigger there. I am a humble application programmer, so the only work i ever did on this idea was maybe telling people about it on newsgroups or forums (hi everybody!). I'd be amazed if nobody else has thought of it. But i've never heard of anyone trying it. Perhaps it's just a terrible idea. The proposed Go design sounds really quite like this. With a huge advantage: because Go tends to use these fire-and-forget goroutines, the problem of identifying low tide goes away, and you can just collect when the goroutine dies.
- tekacs 10y agoFor folks looking for a collector with a similar ideal (though with a potentially more useful constraint model), you might see the Pony language [1] collector [2]. The essence being to take advantage of some form of isolation in a concurrent system to dynamically infer something that looks like scoping/lifetimes. [1]: http://www.ponylang.org/ http://www.ponylang.org/ [2]: http://blog.acolyer.org/2016/02/18/ownership-and-reference-counting-based-garbage-collection-in-the-actor-world http://blog.acolyer.org/2016/02/18/ownership-and-reference-c...
- kevindeasis 10y agoSomewhat off topic, but since there are growing opportunities for golang developers, I'm gonna ask a golang development question. Is anyone using golang with a different language like C, rust, etc? Are you using it through linkage or through microservices? What libraries are you using with golang that's written in a different language. What does your company /app / system / software do? Do you recommend using libraries in a different language or using related golang libraries?
- stcredzero 10y agoI'd like to see this tried, along with a couple of wrinkles. Could information from the escape analysis done by the Golang compiler be used to provide "hints" to the garbage collector to make it more efficient? Could such hints be combined with further hints from the programmer, such as "finalize" calls or tags? Could runtime tracing information be used to derive even more hints for more efficient GC?
- thwd 10y agoNote: "finalize"-hints in Go are just curly braces, which begin and end blocks. Variables local to the scope are "finalized" (i.e. collectable, assuming they live on the heap) when the block ends.
- stcredzero 10y agoNote: "finalize"-hints in Go are just curly braces, which begin and end blocks. But sometimes objects will survive the close braces.
- thwd 10y agoI'm not sure I understand: do you mean that they are collected after the program counter hits the last instruction of a given scope or are you implying that scope-local variables outlive their scope somehow?
- joosters 10y agoEach release of Go seems to have yet another garbage collection algorithm, targetting a different use case each time. Presumably the previous use cases are left behind, ready for a future update going back to target them too. This leads to an infinite loop of GC alterations. Does anyone feel confident that a 'good enough for everyone' GC will ever be produced? If not, surely the language designers should settle on picking a type of program that they will optimise for, and sticking to it.
- oleganza 10y agoGC highlight time-memory tradeoff at its worst because GC-based languages typically do not allow programmer to explicitly express his memory model forcing a lot of unnecessary "garbage" to be created. In Ruby all objects that do not fit in a tagged pointer are objects. In Go and Java some types are specifically optimized for being stack-based "value" types that reduces amount of work for GC. I personally like the "ARC" approach with ObjC and Swift where compiler statically adds and optimizes reference counting routines, promotes objects to stack when possible and requires programmer to manually resolve cyclic references (and Xcode supports nice methods to debug and visualize memory in order to detect unintentional cycles). Accidental memory cycles are rare enough and quite debuggable at a very little mental cost to mark some references as "weak" or "unowned". But the long-term performance and memory exhaustion issues caused by GCs are completely bypassed.
- pjmlp 10y agoThe problem with RC as algorithm is that it increases locking on shared data structures, thus cache contention, and you still have "stop the world" when destroying a complex data structure causes a cascade of deletions. There was a Swift talk exactly about struct vs reference types and making use of COW data structures to reduce ARC impact.
- ngrilly 10y ago> Presumably the previous use cases are left behind No, they are not. The optimization discussed here adds something to the existing GC, and removes nothing. > Does anyone feel confident that a 'good enough for everyone' GC will ever be produced? The Go GC is constantly improving, and its performance in Go 1.6 and 1.7 is considered very good my most users.
- oleganza 10y agoThis is similar to "stack promotion" in Swift (http://fossies.org/linux/swift-swift/lib/LLVMPasses/LLVMStackPromotion.cpp http://fossies.org/linux/swift-swift/lib/LLVMPasses/LLVMStac...). Objects that can be determined to stay within a local scope get allocated on the stack instead of a heap, so cleanup is very efficient. The difference with Go is that decision is done at compile time in Swift and in runtime in Go.
- leaveyou 10y agoActually no. Go compiler already has "stack promotion" (using "escape analysis"). TOC is in addition to that and I think it's intended to cover the cases not covered by "stack promotion" for example Function A calls Function B which allocates some memory and returns it to Function A which "consumes it" before returning. In this case the allocation can't be promoted to stack because B returns and its stack gets destroyed.. but the allocated memory can still be safely released when Function A returns.
- strictfp 10y agoI've been thinking about this before as RAII with optional deferring of recollection when batching would be advantageous , for instance when you have a high allocation pressure and small blocks.
- Doradus 10y agoRAII is using one C++ misfeature (destructors) to work around another misfeature (inability to do cleanup when leaving a lexical scope). Go has a far more elegant solution to the latter; if you're not familiar with the defer statement, check it out.
- stormbrew 10y agoExcept that deterministic destruction is actually a feature that enables cleanup when leaving a scope. Manually peppering your code with defer statements is often doing work a computer can do better than you can.
- strictfp 10y agoEh, defer is more similar to javas try-with-resources or C#:s using, who both put the burden on the user of the object and cannot handle recursive cleanup (cleanup of trees). So I consider it much worse than destructors.
- twotwotwo 10y agoA nice thing about this is that it keeps the collections happening while no users are waiting. Before seeing this I figured what they'd do for throughput might be more of a Java/C#-like compacting young gen collection, which still introduces (short!) pauses. Also, fun wrinkle: seems like occasionally, wrapping a slowish, mostly-self-contained, garbage-heavy function call in a goroutine could be a useful hint to this collector. It seems like it's only useful when 1) a transactional GC on the calling thread or full GC would really be slower (e.g. calling thread keeps lots of live data so GC on it takes more work), and 2) the launch/communication costs (expect at least µsecs) are small enough relative to gains. But interesting it's even possible for it to work out that way.
- japasc 10y agowhy dont let programers choose transactions boundaries within a goroutine, so they can have fine grained control over allocations and deletions
- enneff 10y agoBecause that would be a different language altogether, and that language exists: Rust. It's pretty cool.