On Thu, Jul 9, 2020 at 6:40 PM Markus Heukelom <markus.heuke...@gain.pro> wrote:
> Many data structures are implemented using pointers. How does this perform > wrt garbage collecting? For example take any data structure that uses some > tree of nodes, or even simpler just a singly linked list: there is one > pointer from the left node to the next. Wouldn't this incur huge GC > (unavoidable) cycles for large linked lists that will look at all pointers? > I can imagine that a large AVL tree would then cause potentially large > hick-ups in the GC cycle? > > Is your worry latency in the form of pause times while doing GC, or bandwidth in the form of CPU cycles when doing GC? It isn't entirely clear. In any case, you are right that these things require attention in a garbage collector, both of them. But Go has addressed this for many years now. As an example, imagine you have a binary AVL or Red/Black tree taking up 128 Gigabyte of memory space. You now delete the root node of said tree. Example 1: in C++ we have reference counted the tree. Deleting the root node sets its childrens refcounts to 0, so they get deleted, and so on recursively down the tree. It might take some time to delete 128 Gigabyte of data this way. So C++ isn't exempt from memory reclamation pauses either. Example 2: Imagine a language using Cheney's copying collection as the main garbage collection scheme. It will use 256 gigabyte of memory for its two copying spaces, but collection time will be 0, since the tree's data isn't live. You are paying with memory for faster collection in this case. Example 3: Concurrent collectors, like the one Go uses nowadays, will collect the tree while the program is running and doing productive work. While doing so incurs a bandwidth loss, latency pause times do not suffer. If you have spare CPU cores, they'll be used to handle the collection while the remaining cores run the program (more or less, this is a gross simplification). As for generics: When you use a generic, you substitute in a type to generate a special-case of a function for that type. If the implementation uses monomorphization, it will generate a new piece of code specifically for that type invocation. This might mean other optimizations trigger for the code path, notably stripping pointers away. As for general worry: In some cases it is beneficial to construct data structures such that they pack data well and don't use excessive amounts of pointers. One reason is that collecting pointers takes time in any language. Another reason is that pointer indirections cost memory loads, which can be expensive. A third reason is that packed data has cache locality, so access to data close together is several orders of magnitude faster than following yet another pointer indirection. And finally, it might avoid memory pressure in copying data around. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAGrdgiWh%2By%2BN92M0%2Bas650hQ4ZLJXAnDq5vz1RqJXPZooNDi%3DA%40mail.gmail.com.
